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