ClangFormat: apply to source, most of intern
[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
24  * \ingroup bli
25  *
26  * GHash is a hash-map implementation (unordered key, value pairs).
27  *
28  * This is also used to implement a 'set' (see #GSet below).
29  */
30
31 #include "BLI_sys_types.h" /* for bool */
32 #include "BLI_compiler_attrs.h"
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 };
144 BLI_INLINE void *BLI_ghashIterator_getKey(GHashIterator *ghi)
145 {
146   return ((struct _gh_Entry *)ghi->curEntry)->key;
147 }
148 BLI_INLINE void *BLI_ghashIterator_getValue(GHashIterator *ghi)
149 {
150   return ((struct _gh_Entry *)ghi->curEntry)->val;
151 }
152 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi)
153 {
154   return &((struct _gh_Entry *)ghi->curEntry)->val;
155 }
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 *gh, 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 *gh, 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
239 BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs)
240 {
241   return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs);
242 }
243 BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs)
244 {
245   BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs);
246 }
247 BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi)
248 {
249   BLI_ghashIterator_free((GHashIterator *)gsi);
250 }
251 BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi)
252 {
253   return BLI_ghashIterator_getKey((GHashIterator *)gsi);
254 }
255 BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi)
256 {
257   BLI_ghashIterator_step((GHashIterator *)gsi);
258 }
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 *key);
346 unsigned int BLI_ghashutil_strhash_p_murmur(const void *key);
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
410 /** \} */
411
412 #ifdef __cplusplus
413 }
414 #endif
415
416 #endif /* __BLI_GHASH_H__ */