add missing doxygen docu
[libfirm] / include / libfirm / adt / pset.h
1 /*
2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3  *
4  * This file is part of libFirm.
5  *
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.
10  *
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.
14  *
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
17  * PURPOSE.
18  */
19
20 /**
21  * @file
22  * @brief      optimized version of set for sets containing only pointers
23  *             (deprecated)
24  * @author     Markus Armbruster
25  */
26 #ifndef FIRM_ADT_PSET_H
27 #define FIRM_ADT_PSET_H
28
29 #include <stddef.h>
30
31 #include "hashptr.h"
32
33 #include "../begin.h"
34
35 /**
36  * @ingroup adt
37  * @defgroup pset Pointer Set
38  * (Hash)sets containing pointers.
39  * @note This code has been deprecated. Use pset_new or cpset for new code.
40  * @{
41  */
42
43 /**
44  * The default comparison function for pointers.
45  * @param x A pointer.
46  * @param y A pointer.
47  * @return 0 if @p x and @p y are equal. Some value != 0 otherwise.
48  */
49 FIRM_API int pset_default_ptr_cmp(const void *x, const void *y);
50
51 /**
52  * The abstract type of a pset (Set of pointers).
53  *
54  * This kind of sets stores only pointer to elements, the elements itself
55  * must be stored somewhere else.
56  *
57  * @see set
58  */
59 typedef struct pset pset;
60
61 /** Inserts into pointer set with default hash function. */
62 #define pset_insert_ptr(set,key)  pset_insert(set, key, hash_ptr(key))
63 /** Inserts into pointer set with default hash function and return entry */
64 #define pset_hinsert_ptr(set,key) pset_hinsert(set, key, hash_ptr(key))
65 /** Removes pointer from pointer set with default hash function */
66 #define pset_remove_ptr(set,key)  pset_remove(set, key, hash_ptr(key))
67 /** Finds pointer in pointer set with default hash function */
68 #define pset_find_ptr(set,key)    pset_find(set, key, hash_ptr(key))
69 /** Creates new pointer set with default compare function */
70 #define pset_new_ptr(slots)       new_pset(pset_default_ptr_cmp, slots)
71 /** Creates new pointer set with default compare function and default size */
72 #define pset_new_ptr_default()    pset_new_ptr(64)
73
74 /** The entry of a pset, representing an element pointer in the set and its meta-information */
75 typedef struct {
76   unsigned hash; /**< hash value of element */
77   void *dptr;    /**< pointer to element data */
78 } pset_entry;
79
80 /**
81  * The type of a set compare function.
82  *
83  * @param elt   pointer to an element
84  * @param key   pointer to another element
85  *
86  * @return
87  *    0 if the elements are identically, non-zero else
88  */
89 typedef int (*pset_cmp_fun) (const void *elt, const void *key);
90
91 /**
92  * Creates a new pset.
93  *
94  * @param func    The compare function of this pset.
95  * @param slots   Initial number of collision chains.  I.e., \#slots
96  *                different keys can be hashed without collisions.
97  *
98  * @returns
99  *    created pset
100  */
101 FIRM_API pset *new_pset(pset_cmp_fun func, size_t slots);
102
103 /**
104  * Deletes a pset.
105  *
106  * @param pset   the pset
107  *
108  * @note
109  *    This does NOT delete the elements of this pset, just its pointers!
110  */
111 FIRM_API void del_pset(pset *pset);
112
113 /**
114  * Returns the number of elements in a pset.
115  *
116  * @param pset   the pset
117  */
118 FIRM_API size_t pset_count(pset *pset);
119
120 /**
121  * Searches an element pointer in a pset.
122  *
123  * @param pset  the pset to search in
124  * @param key   the element to search
125  * @param hash  the hash value of key
126  *
127  * @return
128  *    the pointer of the found element in the pset or NULL if it was not found
129  */
130 FIRM_API void *pset_find(pset *pset, const void *key, unsigned hash);
131
132 /**
133  * Inserts an element pointer into a pset.
134  *
135  * @param pset  the pset to insert in
136  * @param key   a pointer to the element to be inserted
137  * @param hash  the hash-value of the element
138  *
139  * @return a pointer to the inserted element
140  *
141  * @note
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 already existing set_entry.
145
146  */
147 FIRM_API void *pset_insert(pset *pset, const void *key, unsigned hash);
148
149 /**
150  * Inserts an element pointer into a pset and returns its pset_entry.
151  *
152  * @param pset  the pset to insert in
153  * @param key   a pointer to the element to be inserted
154  * @param hash  the hash-value of the element
155  *
156  * @return a pointer to the pset_entry of the inserted element
157  *
158  * @note
159  *    It is not possible to insert an element more than once. If an element
160  *    that should be inserted is already in the pset, this functions does
161  *    nothing but returning its pset_entry.
162  */
163 FIRM_API pset_entry *pset_hinsert(pset *pset, const void *key, unsigned hash);
164
165 /**
166  * Removes an element from a pset.
167  *
168  * @param pset  the pset to delete in
169  * @param key   a pointer to the element to be deleted
170  * @param hash  the hash-value of the element
171  *
172  * @return
173  *    the pointer to the removed element
174  *
175  * @remark
176  *    The current implementation did not allow to remove non-existing elements.
177  *    @@@ so, does it do now?
178  *    Further, it is allowed to remove elements during an iteration
179  *    including the current one.
180  */
181 FIRM_API void *pset_remove(pset *pset, const void *key, unsigned hash);
182
183 /**
184  * Returns the first element of a pset.
185  *
186  * @param pset  the pset to iterate
187  *
188  * @return a pointer to the element or NULL if the set is empty
189  */
190 FIRM_API void *pset_first(pset *pset);
191
192 /**
193  * Returns the first element of a pset.
194  * This is a wrapper for pset_first(pmap *map); It allows to express the
195  * intended type of the set elements (instead of weakly typed void*).
196  *
197  * @param type  destination type of the pointers in the set
198  * @param pset  the pset to iterate
199  *
200  * @return a pointer to the element or NULL if the set is empty
201  */
202 #define pset_first(type, pset) ((type*)pset_first((pset)))
203
204 /**
205  * Returns the next element of a pset.
206  *
207  * @param pset  the pset to iterate
208  *
209  * @return a pointer to the next element or NULL if the
210  *         iteration is finished
211  */
212 FIRM_API void *pset_next(pset *pset);
213
214 /**
215  * Returns the next element of a pset.
216  * This is a wrapper for pset_next(pmap *map); It allows to express the
217  * intended type of the set elements (instead of weakly typed void*).
218  *
219  * @param type  destination type of the pointers in the set
220  * @param pset  the pset to iterate
221  *
222  * @return a pointer to the next element or NULL if the
223  *         iteration is finished
224  */
225 #define pset_next(type, pset) ((type*)pset_next((pset)))
226
227 /**
228  * Breaks the iteration of a set. Must be called before
229  * the next pset_first() call if the iteration was NOT
230  * finished.
231  *
232  * @param pset  the pset
233  */
234 FIRM_API void pset_break(pset *pset);
235
236 /**
237  * Iterates oven an pset.
238  *
239  * @param pset   the pset
240  * @param type   type of iterator variable
241  * @param entry  the iterator
242  */
243 #define foreach_pset(pset, type, entry) for (type *entry = pset_first(type, pset); entry; entry = pset_next(type, pset))
244
245 /**
246  * Inserts all elements of the pointer set src into
247  * the set target (union).
248  *
249  * @param target  the target set, will contain the union
250  * @param src     a set, will not be changed
251  */
252 FIRM_API void pset_insert_pset_ptr(pset *target, pset *src);
253
254 /** @cond PRIVATE */
255
256 #define new_pset(cmp, slots) ((new_pset) ((cmp), (slots)))
257 #define pset_find(pset, key, hash) \
258   _pset_search ((pset), (key), (hash), _pset_find)
259 #define pset_insert(pset, key, hash) \
260   _pset_search ((pset), (key), (hash), _pset_insert)
261 #define pset_hinsert(pset, key, hash) \
262   ((pset_entry *)_pset_search ((pset), (key), (hash), _pset_hinsert))
263
264 typedef enum { _pset_find, _pset_insert, _pset_hinsert } _pset_action;
265
266 FIRM_API void *_pset_search(pset *, const void *, unsigned, _pset_action);
267
268 /** @endcond */
269
270 /** @} */
271
272 #include "../end.h"
273
274 #endif