Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / BLI_ghash.h
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 #ifndef __BLI_GHASH_H__
21 #define __BLI_GHASH_H__
22
23 /** \file \ingroup bli
24  *
25  * GHash is a hash-map implementation (unordered key, value pairs).
26  *
27  * This is also used to implement a 'set' (see #GSet below).
28  */
29
30 #include "BLI_sys_types.h" /* for bool */
31 #include "BLI_compiler_attrs.h"
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 #define _GHASH_INTERNAL_ATTR
38 #ifndef GHASH_INTERNAL_API
39 #  ifdef __GNUC__
40 #    undef  _GHASH_INTERNAL_ATTR
41 #    define _GHASH_INTERNAL_ATTR __attribute__ ((deprecated))  /* not deprecated, just private. */
42 #  endif
43 #endif
44
45 typedef unsigned int  (*GHashHashFP)     (const void *key);
46 /** returns false when equal */
47 typedef bool          (*GHashCmpFP)      (const void *a, const void *b);
48 typedef void          (*GHashKeyFreeFP)  (void *key);
49 typedef void          (*GHashValFreeFP)  (void *val);
50 typedef void         *(*GHashKeyCopyFP)  (const void *key);
51 typedef void         *(*GHashValCopyFP)  (const void *val);
52
53 typedef struct GHash GHash;
54
55 typedef struct GHashIterator {
56         GHash *gh;
57         struct Entry *curEntry;
58         unsigned int curBucket;
59 } GHashIterator;
60
61 typedef struct GHashIterState {
62         unsigned int curr_bucket _GHASH_INTERNAL_ATTR;
63 } GHashIterState;
64
65
66
67 enum {
68         GHASH_FLAG_ALLOW_DUPES  = (1 << 0),  /* Only checked for in debug mode */
69         GHASH_FLAG_ALLOW_SHRINK = (1 << 1),  /* Allow to shrink buckets' size. */
70
71 #ifdef GHASH_INTERNAL_API
72         /* Internal usage only */
73         /* Whether the GHash is actually used as GSet (no value storage). */
74         GHASH_FLAG_IS_GSET      = (1 << 16),
75 #endif
76 };
77
78 /** \name GHash API
79  *
80  * Defined in ``BLI_ghash.c``
81  * \{ */
82
83 GHash *BLI_ghash_new_ex(
84         GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
85         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
86 GHash *BLI_ghash_new(
87         GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
88 GHash *BLI_ghash_copy(
89         GHash *gh, GHashKeyCopyFP keycopyfp,
90         GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
91 void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
92 void   BLI_ghash_reserve(GHash *gh, const unsigned int nentries_reserve);
93 void   BLI_ghash_insert(GHash *gh, void *key, void *val);
94 bool   BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
95 void  *BLI_ghash_replace_key(GHash *gh, void *key);
96 void  *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
97 void  *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT;
98 void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
99 bool   BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT;
100 bool   BLI_ghash_ensure_p_ex(GHash *gh, const void *key, void ***r_key, void ***r_val) ATTR_WARN_UNUSED_RESULT;
101 bool   BLI_ghash_remove(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
102 void   BLI_ghash_clear(
103         GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
104 void   BLI_ghash_clear_ex(
105         GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
106         const unsigned int nentries_reserve);
107 void  *BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT;
108 bool   BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
109 bool   BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
110 unsigned int BLI_ghash_len(GHash *gh) ATTR_WARN_UNUSED_RESULT;
111 void   BLI_ghash_flag_set(GHash *gh, unsigned int flag);
112 void   BLI_ghash_flag_clear(GHash *gh, unsigned int flag);
113
114 /** \} */
115
116 /** \name GHash Iterator
117  * \{ */
118
119 GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
120
121 void           BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
122 void           BLI_ghashIterator_free(GHashIterator *ghi);
123 void           BLI_ghashIterator_step(GHashIterator *ghi);
124
125 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
126 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
127 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
128 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
129
130 struct _gh_Entry { void *next, *key, *val; };
131 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi)     { return  ((struct _gh_Entry *)ghi->curEntry)->key; }
132 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi)   { return  ((struct _gh_Entry *)ghi->curEntry)->val; }
133 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) { return &((struct _gh_Entry *)ghi->curEntry)->val; }
134 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi)       { return !ghi->curEntry; }
135 /* disallow further access */
136 #ifdef __GNUC__
137 #  pragma GCC poison _gh_Entry
138 #else
139 #  define _gh_Entry void
140 #endif
141
142 #define GHASH_ITER(gh_iter_, ghash_) \
143         for (BLI_ghashIterator_init(&gh_iter_, ghash_); \
144              BLI_ghashIterator_done(&gh_iter_) == false; \
145              BLI_ghashIterator_step(&gh_iter_))
146
147 #define GHASH_ITER_INDEX(gh_iter_, ghash_, i_) \
148         for (BLI_ghashIterator_init(&gh_iter_, ghash_), i_ = 0; \
149              BLI_ghashIterator_done(&gh_iter_) == false; \
150              BLI_ghashIterator_step(&gh_iter_), i_++)
151
152 /** \} */
153
154 /** \name GSet API
155  * A 'set' implementation (unordered collection of unique elements).
156  *
157  * Internally this is a 'GHash' without any keys,
158  * which is why this API's are in the same header & source file.
159  *
160  * \{ */
161
162 typedef struct GSet GSet;
163
164 typedef GHashHashFP GSetHashFP;
165 typedef GHashCmpFP GSetCmpFP;
166 typedef GHashKeyFreeFP GSetKeyFreeFP;
167 typedef GHashKeyCopyFP GSetKeyCopyFP;
168
169 typedef GHashIterState GSetIterState;
170
171 GSet  *BLI_gset_new_ex(
172         GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
173         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
174 GSet  *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
175 GSet  *BLI_gset_copy(GSet *gs, GSetKeyCopyFP keycopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
176 unsigned int BLI_gset_len(GSet *gs) ATTR_WARN_UNUSED_RESULT;
177 void   BLI_gset_flag_set(GSet *gs, unsigned int flag);
178 void   BLI_gset_flag_clear(GSet *gs, unsigned int flag);
179 void   BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp);
180 void   BLI_gset_insert(GSet *gh, void *key);
181 bool   BLI_gset_add(GSet *gs, void *key);
182 bool   BLI_gset_ensure_p_ex(GSet *gs, const void *key, void ***r_key);
183 bool   BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp);
184 void  *BLI_gset_replace_key(GSet *gs, void *key);
185 bool   BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
186 bool   BLI_gset_pop(GSet *gs, GSetIterState *state, void **r_key) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
187 bool   BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp);
188 void   BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
189                          const unsigned int nentries_reserve);
190 void   BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
191
192 /* When set's are used for key & value. */
193 void  *BLI_gset_lookup(GSet *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
194 void  *BLI_gset_pop_key(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
195
196 /** \} */
197
198 /** \name GSet Iterator
199  * \{ */
200
201 /* rely on inline api for now */
202
203 /* so we can cast but compiler sees as different */
204 typedef struct GSetIterator {
205         GHashIterator _ghi
206 #ifdef __GNUC__
207         __attribute__ ((deprecated))
208 #endif
209         ;
210 } GSetIterator;
211
212 BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs) { return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs); }
213 BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs) { BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs); }
214 BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi) { BLI_ghashIterator_free((GHashIterator *)gsi); }
215 BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi) { return BLI_ghashIterator_getKey((GHashIterator *)gsi); }
216 BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi) { BLI_ghashIterator_step((GHashIterator *)gsi); }
217 BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashIterator_done((GHashIterator *)gsi); }
218
219 #define GSET_ITER(gs_iter_, gset_) \
220         for (BLI_gsetIterator_init(&gs_iter_, gset_); \
221              BLI_gsetIterator_done(&gs_iter_) == false; \
222              BLI_gsetIterator_step(&gs_iter_))
223
224 #define GSET_ITER_INDEX(gs_iter_, gset_, i_) \
225         for (BLI_gsetIterator_init(&gs_iter_, gset_), i_ = 0; \
226              BLI_gsetIterator_done(&gs_iter_) == false; \
227              BLI_gsetIterator_step(&gs_iter_), i_++)
228
229 /** \} */
230
231 /** \name GHash/GSet Debugging API's
232  * \{ */
233
234 /* For testing, debugging only */
235 #ifdef GHASH_INTERNAL_API
236 int BLI_ghash_buckets_len(GHash *gh);
237 int BLI_gset_buckets_len(GSet *gs);
238
239 double BLI_ghash_calc_quality_ex(
240         GHash *gh, double *r_load, double *r_variance,
241         double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
242 double BLI_gset_calc_quality_ex(
243         GSet *gs, double *r_load, double *r_variance,
244         double *r_prop_empty_buckets, double *r_prop_overloaded_buckets, int *r_biggest_bucket);
245 double BLI_ghash_calc_quality(GHash *gh);
246 double BLI_gset_calc_quality(GSet *gs);
247 #endif  /* GHASH_INTERNAL_API */
248 /** \} */
249
250 /** \name GHash/GSet Macros
251  * \{ */
252
253 #define GHASH_FOREACH_BEGIN(type, var, what) \
254         do { \
255                 GHashIterator gh_iter##var; \
256                 GHASH_ITER(gh_iter##var, what) { \
257                         type var = (type)(BLI_ghashIterator_getValue(&gh_iter##var)); \
258
259 #define GHASH_FOREACH_END() \
260                 } \
261         } while(0)
262
263 #define GSET_FOREACH_BEGIN(type, var, what) \
264         do { \
265                 GSetIterator gh_iter##var; \
266                 GSET_ITER(gh_iter##var, what) { \
267                         type var = (type)(BLI_gsetIterator_getKey(&gh_iter##var));
268
269 #define GSET_FOREACH_END() \
270                 } \
271         } while(0)
272
273 /** \} */
274
275 /** \name GHash/GSet Utils
276  *
277  * Defined in ``BLI_ghash_utils.c``
278  * \{ */
279
280 /**
281  * Callbacks for GHash (``BLI_ghashutil_``)
282  *
283  * \note '_p' suffix denotes void pointer arg,
284  * so we can have functions that take correctly typed args too.
285  */
286
287 unsigned int    BLI_ghashutil_ptrhash(const void *key);
288 bool            BLI_ghashutil_ptrcmp(const void *a, const void *b);
289
290 unsigned int    BLI_ghashutil_strhash_n(const char *key, size_t n);
291 #define         BLI_ghashutil_strhash(key) ( \
292                 CHECK_TYPE_ANY(key, char *, const char *, const char * const), \
293                 BLI_ghashutil_strhash_p(key))
294 unsigned int    BLI_ghashutil_strhash_p(const void *key);
295 unsigned int    BLI_ghashutil_strhash_p_murmur(const void *key);
296 bool            BLI_ghashutil_strcmp(const void *a, const void *b);
297
298 #define         BLI_ghashutil_inthash(key) ( \
299                 CHECK_TYPE_ANY(&(key), int *, const int *), \
300                 BLI_ghashutil_uinthash((unsigned int)key))
301 unsigned int    BLI_ghashutil_uinthash(unsigned int key);
302 unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
303 unsigned int    BLI_ghashutil_inthash_p_murmur(const void *ptr);
304 unsigned int    BLI_ghashutil_inthash_p_simple(const void *ptr);
305 bool            BLI_ghashutil_intcmp(const void *a, const void *b);
306
307 size_t          BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b);
308
309
310 unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
311 #define         BLI_ghashutil_inthash_v4(key) ( \
312                 CHECK_TYPE_ANY(key, int *, const int *), \
313                 BLI_ghashutil_uinthash_v4((const unsigned int *)key))
314 #define         BLI_ghashutil_inthash_v4_p \
315    ((GSetHashFP)BLI_ghashutil_uinthash_v4)
316 #define         BLI_ghashutil_uinthash_v4_p \
317    ((GSetHashFP)BLI_ghashutil_uinthash_v4)
318 unsigned int    BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]);
319 #define         BLI_ghashutil_inthash_v4_murmur(key) ( \
320                 CHECK_TYPE_ANY(key, int *, const int *), \
321                 BLI_ghashutil_uinthash_v4_murmur((const unsigned int *)key))
322 #define         BLI_ghashutil_inthash_v4_p_murmur \
323    ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
324 #define         BLI_ghashutil_uinthash_v4_p_murmur \
325    ((GSetHashFP)BLI_ghashutil_uinthash_v4_murmur)
326 bool            BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
327 #define         BLI_ghashutil_inthash_v4_cmp \
328                 BLI_ghashutil_uinthash_v4_cmp
329
330 typedef struct GHashPair {
331         const void *first;
332         const void *second;
333 } GHashPair;
334
335 GHashPair      *BLI_ghashutil_pairalloc(const void *first, const void *second);
336 unsigned int    BLI_ghashutil_pairhash(const void *ptr);
337 bool            BLI_ghashutil_paircmp(const void *a, const void *b);
338 void            BLI_ghashutil_pairfree(void *ptr);
339
340 /**
341  * Wrapper GHash Creation Functions
342  */
343
344 GHash *BLI_ghash_ptr_new_ex(
345         const char *info,
346         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
347 GHash *BLI_ghash_ptr_new(
348         const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
349 GHash *BLI_ghash_str_new_ex(
350         const char *info,
351         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
352 GHash *BLI_ghash_str_new(
353         const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
354 GHash *BLI_ghash_int_new_ex(
355         const char *info,
356         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
357 GHash *BLI_ghash_int_new(
358         const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
359 GHash *BLI_ghash_pair_new_ex(
360         const char *info,
361         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
362 GHash *BLI_ghash_pair_new(
363         const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
364
365 GSet *BLI_gset_ptr_new_ex(
366         const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
367 GSet *BLI_gset_ptr_new(
368         const char *info);
369 GSet *BLI_gset_str_new_ex(
370         const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
371 GSet *BLI_gset_str_new(
372         const char *info);
373 GSet *BLI_gset_pair_new_ex(
374         const char *info, const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
375 GSet *BLI_gset_pair_new(
376         const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
377
378 /** \} */
379
380 #ifdef __cplusplus
381 }
382 #endif
383
384 #endif /* __BLI_GHASH_H__ */