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