2 * Copyright (C) 1995-2011 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
25 #ifndef FIRM_ADT_SET_H
26 #define FIRM_ADT_SET_H
34 * @defgroup set Generic Hashset
36 * @note This code has been deprecated. Use hashset for new code.
41 * The abstract type of a set.
43 * This sets stores copies of its elements, so there is no need
44 * to store the elements after they were added to a set.
48 typedef struct set set;
50 /** The entry of a set, representing an element in the set and its meta-information */
51 typedef struct set_entry {
52 unsigned hash; /**< the hash value of the element */
53 size_t size; /**< the size of the element */
54 int dptr[1]; /**< the element itself, data copied in must not need more
55 alignment than this */
59 * The type of a set compare function.
61 * @param elt pointer to an element
62 * @param key pointer to another element
63 * @param size size of the elements
66 * 0 if the elements are identically, non-zero else
69 * Although it is possible to define different meanings of equality
70 * of two elements of a set, they can be only equal if their sizes are
71 * are equal. This is checked before the compare function is called.
73 typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);
78 * @param func The compare function of this set.
79 * @param slots Initial number of collision chains. I.e., \#slots
80 * different keys can be hashed without collisions.
85 FIRM_API set *new_set(set_cmp_fun func, size_t slots);
88 * Deletes a set and all elements of it.
90 * @param set the set to delete
92 FIRM_API void del_set(set *set);
95 * Returns the number of elements in a set.
99 FIRM_API size_t set_count(set *set);
102 * Searches an element in a set.
104 * @param set the set to search in
105 * @param key the element to is searched
106 * @param size the size of key
107 * @param hash the hash value of key
110 * The address of the found element in the set or NULL if it was not found.
112 FIRM_API void *set_find(set *set, const void *key, size_t size, unsigned hash);
115 * Inserts an element into a set.
117 * @param set the set to insert in
118 * @param key a pointer to the element to be inserted. Element is copied!
119 * @param size the size of the element that should be inserted
120 * @param hash the hash-value of the element
122 * @return a pointer to the inserted element
125 * It is not possible to insert one element more than once. If an element
126 * that should be inserted is already in the set, this functions does
127 * nothing but returning its pointer.
129 FIRM_API void *set_insert(set *set, const void *key, size_t size, unsigned hash);
132 * Inserts an element into a set and returns its set_entry.
134 * @param set the set to insert in
135 * @param key a pointer to the element to be inserted. Element is copied!
136 * @param size the size of the element that should be inserted
137 * @param hash the hash-value of the element
139 * @return a pointer to the set_entry of the inserted element
142 * It is not possible to insert an element more than once. If an element
143 * that should be inserted is already in the set, this functions does
144 * nothing but returning its set_entry.
146 FIRM_API set_entry *set_hinsert(set *set, const void *key, size_t size, unsigned hash);
149 * Inserts an element into a set, zero-terminate it and returns its set_entry.
151 * @param set the set to insert in
152 * @param key a pointer to the element to be inserted. Element is copied!
153 * @param size the size of the element that should be inserted
154 * @param hash the hash-value of the element
156 * @return a pointer to the set_entry of the inserted element
159 * It is not possible to insert on element more than once. If an element
160 * that should be inserted is already in the set, this functions does
161 * nothing but returning its set_entry.
163 FIRM_API set_entry *set_hinsert0(set *set, const void *key, size_t size, unsigned hash);
166 * Returns the first element of a set.
168 * @param set the set to iterate
170 * @return a pointer to the element or NULL if the set is empty
172 FIRM_API void *set_first(set *set);
174 #define set_first(type, set) ((type*)set_first((set)))
177 * Returns the next element of a set.
179 * @param set the set to iterate
181 * @return a pointer to the next element or NULL if the
182 * iteration is finished
184 FIRM_API void *set_next(set *set);
186 #define set_next(type, set) ((type*)set_next((set)))
189 * Breaks the iteration of a set. Must be called before
190 * the next set_first() call if the iteration was NOT
195 FIRM_API void set_break(set *set);
198 * Iterates over an set.
201 * @param type type of iterator variable
202 * @param entry the iterator
204 #define foreach_set(set, type, entry) for (type *entry = set_first(type, set); entry; entry = set_next(type, set))
208 /* implementation specific */
209 #define new_set(cmp, slots) ((new_set) ((cmp), (slots)))
210 #define set_find(type, set, key, size, hash) \
211 ((type*)_set_search((set), 1 ? (key) : (type*)0 /* type check */, (size), (hash), _set_find))
212 #define set_insert(type, set, key, size, hash) \
213 ((type*)_set_search((set), 1 ? (key) : (type*)0 /* type check */, (size), (hash), _set_insert))
214 #define set_hinsert(set, key, size, hash) \
215 ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
216 #define set_hinsert0(set, key, size, hash) \
217 ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
219 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
221 FIRM_API void *_set_search(set *, const void *, size_t, unsigned, _set_action);