2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief hashset: datastructure containing objects accessible by their key
23 * @author Markus Armbruster
26 #ifndef FIRM_ADT_SET_H
27 #define FIRM_ADT_SET_H
34 * The abstract type of a set.
36 * This sets stores copies of its elements, so there is no need
37 * to store the elements after they were added to a set.
41 typedef struct set set;
43 /** The entry of a set, representing an element in the set and it's meta-information */
44 typedef struct set_entry {
45 unsigned hash; /**< the hash value of the element */
46 size_t size; /**< the size of the element */
47 int dptr[1]; /**< the element itself, data copied in must not need more
48 alignment than this */
52 * The type of a set compare function.
54 * @param elt pointer to an element
55 * @param key pointer to another element
56 * @param size size of the elements
59 * 0 if the elements are identically, non-zero else
62 * Although it is possible to define different meanings of equality
63 * of two elements of a set, they can be only equal if their sizes are
64 * are equal. This is checked before the compare function is called.
66 typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);
71 * @param func The compare function of this set.
72 * @param slots Initial number of collision chains. I.e., \#slots
73 * different keys can be hashed without collisions.
78 FIRM_API set *new_set(set_cmp_fun func, int slots);
81 * Deletes a set and all elements of it.
83 * @param set the set to delete
85 FIRM_API void del_set(set *set);
88 * Returns the number of elements in a set.
92 FIRM_API int set_count(set *set);
95 * Searches an element in a set.
97 * @param set the set to search in
98 * @param key the element to is searched
99 * @param size the size of key
100 * @param hash the hash value of key
103 * The address of the found element in the set or NULL if it was not found.
105 FIRM_API void *set_find(set *set, const void *key, size_t size, unsigned hash);
108 * Inserts an element into a set.
110 * @param set the set to insert in
111 * @param key a pointer to the element to be inserted. Element is copied!
112 * @param size the size of the element that should be inserted
113 * @param hash the hash-value of the element
115 * @return a pointer to the inserted element
118 * It is not possible to insert one element more than once. If an element
119 * that should be inserted is already in the set, this functions does
120 * nothing but returning its pointer.
122 FIRM_API void *set_insert(set *set, const void *key, size_t size, unsigned hash);
125 * Inserts an element into a set and returns its set_entry.
127 * @param set the set to insert in
128 * @param key a pointer to the element to be inserted. Element is copied!
129 * @param size the size of the element that should be inserted
130 * @param hash the hash-value of the element
132 * @return a pointer to the set_entry of the inserted element
135 * It is not possible to insert an element more than once. If an element
136 * that should be inserted is already in the set, this functions does
137 * nothing but returning its set_entry.
139 FIRM_API set_entry *set_hinsert(set *set, const void *key, size_t size, unsigned hash);
142 * Inserts an element into a set, zero-terminate it and returns its set_entry.
144 * @param set the set to insert in
145 * @param key a pointer to the element to be inserted. Element is copied!
146 * @param size the size of the element that should be inserted
147 * @param hash the hash-value of the element
149 * @return a pointer to the set_entry of the inserted element
152 * It is not possible to insert on element more than once. If an element
153 * that should be inserted is already in the set, this functions does
154 * nothing but returning its set_entry.
156 FIRM_API set_entry *set_hinsert0(set *set, const void *key, size_t size, unsigned hash);
159 * Returns the first element of a set.
161 * @param set the set to iterate
163 * @return a pointer to the element or NULL if the set is empty
165 FIRM_API void *set_first(set *set);
168 * Returns the next element of a set.
170 * @param set the set to iterate
172 * @return a pointer to the next element or NULL if the
173 * iteration is finished
175 FIRM_API void *set_next(set *set);
178 * Breaks the iteration of a set. Must be called before
179 * the next set_first() call if the iteration was NOT
184 FIRM_API void set_break(set *set);
187 * Iterates over an set.
190 * @param entry the iterator
192 #define foreach_set(set, entry) for (entry = set_first(set); entry; entry = set_next(set))
194 /* implementation specific */
195 #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
196 #define set_find(set, key, size, hash) \
197 _set_search ((set), (key), (size), (hash), _set_find)
198 #define set_insert(set, key, size, hash) \
199 _set_search ((set), (key), (size), (hash), _set_insert)
200 #define set_hinsert(set, key, size, hash) \
201 ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
202 #define set_hinsert0(set, key, size, hash) \
203 ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
205 #define SET_VRFY(set) (void)0
209 * Prints statistics on a set to stdout.
213 void set_stats (set *set);
215 # define set_stats(s) ((void)0)
222 * Writes a description of a set to stdout. The description includes:
223 * - a header telling how many elements (nkey) and segments (nseg) are in use
224 * - for every collision chain the number of element with its hash values
228 FIRM_API void set_describe (set *set);
234 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
236 FIRM_API void *_set_search(set *, const void *, size_t, unsigned, _set_action);
238 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
239 extern const char *set_tag;
241 # define SET_TRACE set_tag = SET_ID,
243 # define SET_TRACE set_tag = __FILE__,
245 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
247 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */