X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fset.h;h=8236152fcab907f77cec4330c7b4c87501afaecd;hb=ef5f65eb6b79824a5523a18d6a114c5466d95d53;hp=af119f7913d3083113cf377a64b772b53db2a529;hpb=abfc0f7ffbd2f3248897c0732f3355b8284808a1;p=libfirm diff --git a/ir/adt/set.h b/ir/adt/set.h index af119f791..8236152fc 100644 --- a/ir/adt/set.h +++ b/ir/adt/set.h @@ -1,16 +1,30 @@ -/* Declarations for set. - Copyright (C) 1995, 1996 Markus Armbruster */ - -/* $Id$ */ - -/** - * @file set.h +/* + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. * - * Declarations for set. + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ -#ifndef _SET_H -#define _SET_H +/** + * @file + * @brief hashset: datastructure containing objects accessible by their key + * @author Markus Armbruster + * @verison $Id$ + */ +#ifndef FIRM_ADT_SET_H +#define FIRM_ADT_SET_H #include @@ -18,7 +32,7 @@ * The abstract type of a set. * * This sets stores copies of its elements, so there is no need - * to store the elements after there were added to a set. + * to store the elements after they were added to a set. * * @see pset */ @@ -28,8 +42,8 @@ typedef struct set set; typedef struct set_entry { unsigned hash; /**< the hash value of the element */ size_t size; /**< the size of the element */ - int dptr[1]; /**< the element itself, data copied in must not need more - alignment than this */ + int dptr[1]; /**< the element itself, data copied in must not need more + alignment than this */ } set_entry; /** @@ -43,26 +57,36 @@ typedef struct set_entry { * 0 if the elements are identically, non-zero else * * @note - * Although it is possible to define different meanings for equality of two - * elements of a sets, they can be only equal if there sizes are - * equal. This is checked before the compare function is called. + * Although it is possible to define different meanings of equality + * of two elements of a set, they can be only equal if their sizes are + * are equal. This is checked before the compare function is called. */ typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size); /** * Creates a new set. * - * @param func the compare function of this set - * @param slots number of slots + * @param func The compare function of this set. + * @param slots Initial number of collision chains. I.e., #slots + * different keys can be hashed without collisions. * * @returns * created set */ set *new_set (set_cmp_fun func, int slots); -/** Deletes a set and all elements of it. */ +/** + * Deletes a set and all elements of it. + */ void del_set (set *set); +/** + * Returns the number of elements in a set. + * + * @param set the set + */ +int set_count (set *set); + /** * Searches an element in a set. * @@ -72,7 +96,7 @@ void del_set (set *set); * @param hash the hash value of key * * @return - * the address of the found element in the set of NULL if it was not found + * The address of the found element in the set or NULL if it was not found. */ void *set_find (set *set, const void *key, size_t size, unsigned hash); @@ -80,14 +104,14 @@ void *set_find (set *set, const void *key, size_t size, unsigned hash); * Inserts an element into a set. * * @param set the set to insert in - * @param key a pointer to the element to be inserted + * @param key a pointer to the element to be inserted. Element is copied! * @param size the size of the element that should be inserted * @param hash the hash-value of the element * * @return a pointer to the inserted element * * @note - * It is not possible to insert on element more than once. If a element + * It is not possible to insert one element more than once. If an element * that should be inserted is already in the set, this functions does * nothing but returning its pointer. */ @@ -97,14 +121,14 @@ void *set_insert (set *set, const void *key, size_t size, unsigned hash); * Inserts an element into a set and returns its set_entry. * * @param set the set to insert in - * @param key a pointer to the element to be inserted + * @param key a pointer to the element to be inserted. Element is copied! * @param size the size of the element that should be inserted * @param hash the hash-value of the element * * @return a pointer to the set_entry of the inserted element * * @note - * It is not possible to insert on element more than once. If a element + * It is not possible to insert an element more than once. If an element * that should be inserted is already in the set, this functions does * nothing but returning its set_entry. */ @@ -114,28 +138,55 @@ set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash); * Inserts an element into a set, zero-terminate it and returns its set_entry. * * @param set the set to insert in - * @param key a pointer to the element to be inserted + * @param key a pointer to the element to be inserted. Element is copied! * @param size the size of the element that should be inserted * @param hash the hash-value of the element * * @return a pointer to the set_entry of the inserted element * * @note - * It is not possible to insert on element more than once. If a element + * It is not possible to insert on element more than once. If an element * that should be inserted is already in the set, this functions does * nothing but returning its set_entry. */ set_entry *set_hinsert0 (set *set, const void *key, size_t size, unsigned hash); -/** Returns the first element of a set. */ +/** + * Returns the first element of a set. + * + * @param set the set to iterate + * + * @return a pointer to the element or NULL if the set is empty + */ void *set_first (set *set); -/** Returns the next element of a set. */ +/** + * Returns the next element of a set. + * + * @param set the set to iterate + * + * @return a pointer to the next element or NULL if the + * iteration is finished + */ void *set_next (set *set); -/** Breaks the iteration of a set. Must be called before the next set_first() call */ +/** + * Breaks the iteration of a set. Must be called before + * the next set_first() call if the iteration was NOT + * finished. + * + * @param set the set + */ void set_break (set *set); +/** + * Iterates over an set. + * + * @param set the set + * @param entry the iterator + */ +#define foreach_set(set, entry) for (entry = set_first(set); entry; entry = set_next(set)) + /* implementation specific */ #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots))) #define set_find(set, key, size, hash) \ @@ -150,13 +201,27 @@ void set_break (set *set); #define SET_VRFY(set) (void)0 #ifdef STATS -void set_stats (set *); +/** + * Prints statistics on a set to stdout. + * + * @param set the set + */ +void set_stats (set *set); #else # define set_stats(s) ((void)0) #endif #ifdef DEBUG -void set_describe (set *); +/** + * Describe a set. + * + * Writes a description of a set to stdout. The description includes: + * - a header telling how many elements (nkey) and segments (nseg) are in use + * - for every collision chain the number of element with its hash values + * + * @param set the set + */ +void set_describe (set *set); #endif