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