GHash: use bool for comparison (simplify compare)
[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  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27  
28 #ifndef __BLI_GHASH_H__
29 #define __BLI_GHASH_H__
30
31 /** \file BLI_ghash.h
32  *  \ingroup bli
33  *  \brief A general (pointer -> pointer) hash table ADT
34  */
35
36 #include "BLI_sys_types.h" /* for bool */
37 #include "BLI_compiler_attrs.h"
38
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42
43 typedef unsigned int  (*GHashHashFP)     (const void *key);
44 typedef bool          (*GHashCmpFP)      (const void *a, const void *b);
45 typedef void          (*GHashKeyFreeFP)  (void *key);
46 typedef void          (*GHashValFreeFP)  (void *val);
47
48 typedef struct GHash GHash;
49
50 typedef struct GHashIterator {
51         GHash *gh;
52         struct Entry *curEntry;
53         unsigned int curBucket;
54 } GHashIterator;
55
56 enum {
57         GHASH_FLAG_ALLOW_DUPES = (1 << 0),  /* only checked for in debug mode */
58 };
59
60 /* *** */
61
62 GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
63                         const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
64 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
65 void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
66 void   BLI_ghash_insert(GHash *gh, void *key, void *val);
67 bool   BLI_ghash_reinsert(GHash *gh, void *key, void *val, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
68 void  *BLI_ghash_lookup(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
69 void  *BLI_ghash_lookup_default(GHash *gh, const void *key, void *val_default) ATTR_WARN_UNUSED_RESULT;
70 void **BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
71 bool   BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
72 void   BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
73 void   BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
74                           const unsigned int nentries_reserve);
75 void  *BLI_ghash_popkey(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT;
76 bool   BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
77 int    BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT;
78 void   BLI_ghash_flag_set(GHash *gh, unsigned int flag);
79 void   BLI_ghash_flag_clear(GHash *gh, unsigned int flag);
80
81 /* *** */
82
83 GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
84
85 void           BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
86 void           BLI_ghashIterator_free(GHashIterator *ghi);
87 void           BLI_ghashIterator_step(GHashIterator *ghi);
88
89 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
90 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
91 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
92 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
93
94 struct _gh_Entry { void *next, *key, *val; };
95 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi)     { return  ((struct _gh_Entry *)ghi->curEntry)->key; }
96 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi)   { return  ((struct _gh_Entry *)ghi->curEntry)->val; }
97 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) { return &((struct _gh_Entry *)ghi->curEntry)->val; }
98 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi)       { return !ghi->curEntry; }
99 /* disallow further access */
100 #ifdef __GNUC__
101 #  pragma GCC poison _gh_Entry
102 #else
103 #  define _gh_Entry void
104 #endif
105
106 #define GHASH_ITER(gh_iter_, ghash_)                                          \
107         for (BLI_ghashIterator_init(&gh_iter_, ghash_);                           \
108              BLI_ghashIterator_done(&gh_iter_) == false;                          \
109              BLI_ghashIterator_step(&gh_iter_))
110
111 #define GHASH_ITER_INDEX(gh_iter_, ghash_, i_)                                \
112         for (BLI_ghashIterator_init(&gh_iter_, ghash_), i_ = 0;                   \
113              BLI_ghashIterator_done(&gh_iter_) == false;                          \
114              BLI_ghashIterator_step(&gh_iter_), i_++)
115
116 /** \name Callbacks for GHash
117  *
118  * \note '_p' suffix denotes void pointer arg,
119  * so we can have functions that take correctly typed args too.
120  * \{ */
121
122 unsigned int    BLI_ghashutil_ptrhash(const void *key);
123 bool            BLI_ghashutil_ptrcmp(const void *a, const void *b);
124
125 unsigned int    BLI_ghashutil_strhash_n(const char *key, size_t n);
126 #define         BLI_ghashutil_strhash(key) ( \
127                 CHECK_TYPE_INLINE(key, char *), \
128                 BLI_ghashutil_strhash_p(key))
129 unsigned int    BLI_ghashutil_strhash_p(const void *key);
130 bool            BLI_ghashutil_strcmp(const void *a, const void *b);
131
132 #define         BLI_ghashutil_inthash(key) ( \
133                 CHECK_TYPE_INLINE(&(key), int *), \
134                 BLI_ghashutil_uinthash((unsigned int)key))
135 unsigned int    BLI_ghashutil_uinthash(unsigned int key);
136 #define         BLI_ghashutil_inthash_v4(key) ( \
137                 CHECK_TYPE_INLINE(key, int *), \
138                 BLI_ghashutil_uinthash_v4((const unsigned int *)key))
139 unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
140 #define         BLI_ghashutil_inthash_v4_p \
141    ((GSetHashFP)BLI_ghashutil_uinthash_v4)
142 bool            BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
143 #define         BLI_ghashutil_inthash_v4_cmp \
144                 BLI_ghashutil_uinthash_v4_cmp
145 unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
146 bool            BLI_ghashutil_intcmp(const void *a, const void *b);
147
148 /** \} */
149
150 GHash          *BLI_ghash_ptr_new_ex(const char *info,
151                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
152 GHash          *BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
153 GHash          *BLI_ghash_str_new_ex(const char *info,
154                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
155 GHash          *BLI_ghash_str_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
156 GHash          *BLI_ghash_int_new_ex(const char *info,
157                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
158 GHash          *BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
159 GHash          *BLI_ghash_pair_new_ex(const char *info,
160                                       const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
161 GHash          *BLI_ghash_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
162
163 typedef struct GHashPair {
164         const void *first;
165         const void *second;
166 } GHashPair;
167
168 GHashPair      *BLI_ghashutil_pairalloc(const void *first, const void *second);
169 unsigned int    BLI_ghashutil_pairhash(const void *ptr);
170 bool            BLI_ghashutil_paircmp(const void *a, const void *b);
171 void            BLI_ghashutil_pairfree(void *ptr);
172
173
174 /* *** */
175
176 typedef struct GSet GSet;
177
178 typedef GHashHashFP GSetHashFP;
179 typedef GHashCmpFP GSetCmpFP;
180 typedef GHashKeyFreeFP GSetKeyFreeFP;
181
182 /* so we can cast but compiler sees as different */
183 typedef struct GSetIterator {
184         GHashIterator _ghi
185 #ifdef __GNUC__
186         __attribute__ ((deprecated))
187 #endif
188         ;
189 } GSetIterator;
190
191 GSet  *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
192                        const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
193 GSet  *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
194 int    BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT;
195 void   BLI_gset_flag_set(GSet *gs, unsigned int flag);
196 void   BLI_gset_flag_clear(GSet *gs, unsigned int flag);
197 void   BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp);
198 void   BLI_gset_insert(GSet *gh, void *key);
199 bool   BLI_gset_add(GSet *gs, void *key);
200 bool   BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp);
201 bool   BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
202 bool   BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp);
203 void   BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
204                          const unsigned int nentries_reserve);
205 void  BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
206
207 GSet *BLI_gset_ptr_new_ex(const char *info,
208                           const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
209 GSet *BLI_gset_ptr_new(const char *info);
210 GSet *BLI_gset_pair_new_ex(const char *info,
211                             const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
212 GSet *BLI_gset_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
213
214 /* rely on inline api for now */
215 BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs) { return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs); }
216 BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs) { BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs); }
217 BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi) { BLI_ghashIterator_free((GHashIterator *)gsi); }
218 BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi) { return BLI_ghashIterator_getKey((GHashIterator *)gsi); }
219 BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi) { BLI_ghashIterator_step((GHashIterator *)gsi); }
220 BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashIterator_done((GHashIterator *)gsi); }
221
222 #define GSET_ITER(gs_iter_, gset_)                                            \
223         for (BLI_gsetIterator_init(&gs_iter_, gset_);                             \
224              BLI_gsetIterator_done(&gs_iter_) == false;                           \
225              BLI_gsetIterator_step(&gs_iter_))
226
227 #define GSET_ITER_INDEX(gs_iter_, gset_, i_)                                  \
228         for (BLI_gsetIterator_init(&gs_iter_, gset_), i_ = 0;                     \
229              BLI_gsetIterator_done(&gs_iter_) == false;                           \
230              BLI_gsetIterator_step(&gs_iter_), i_++)
231
232 #ifdef DEBUG
233 double BLI_ghash_calc_quality(GHash *gh);
234 double BLI_gset_calc_quality(GSet *gs);
235 #endif
236
237 #ifdef __cplusplus
238 }
239 #endif
240
241 #endif /* __BLI_GHASH_H__ */