GHash: add BLI_ghashutil_uinthash_v4 for hashing 4 ints at once
[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 int           (*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_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
70 bool   BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
71 void   BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
72 void   BLI_ghash_clear_ex(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp,
73                           const unsigned int nentries_reserve);
74 void  *BLI_ghash_popkey(GHash *gh, void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT;
75 bool   BLI_ghash_haskey(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT;
76 int    BLI_ghash_size(GHash *gh) ATTR_WARN_UNUSED_RESULT;
77 void   BLI_ghash_flag_set(GHash *gh, unsigned int flag);
78 void   BLI_ghash_flag_clear(GHash *gh, unsigned int flag);
79
80 /* *** */
81
82 GHashIterator *BLI_ghashIterator_new(GHash *gh) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
83
84 void           BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
85 void           BLI_ghashIterator_free(GHashIterator *ghi);
86 void           BLI_ghashIterator_step(GHashIterator *ghi);
87
88 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
89 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
90 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
91 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT;
92
93 struct _gh_Entry { void *next, *key, *val; };
94 BLI_INLINE void  *BLI_ghashIterator_getKey(GHashIterator *ghi)     { return  ((struct _gh_Entry *)ghi->curEntry)->key; }
95 BLI_INLINE void  *BLI_ghashIterator_getValue(GHashIterator *ghi)   { return  ((struct _gh_Entry *)ghi->curEntry)->val; }
96 BLI_INLINE void **BLI_ghashIterator_getValue_p(GHashIterator *ghi) { return &((struct _gh_Entry *)ghi->curEntry)->val; }
97 BLI_INLINE bool   BLI_ghashIterator_done(GHashIterator *ghi)       { return !ghi->curEntry; }
98 /* disallow further access */
99 #ifdef __GNUC__
100 #  pragma GCC poison _gh_Entry
101 #else
102 #  define _gh_Entry void
103 #endif
104
105 #define GHASH_ITER(gh_iter_, ghash_)                                          \
106         for (BLI_ghashIterator_init(&gh_iter_, ghash_);                           \
107              BLI_ghashIterator_done(&gh_iter_) == false;                          \
108              BLI_ghashIterator_step(&gh_iter_))
109
110 #define GHASH_ITER_INDEX(gh_iter_, ghash_, i_)                                \
111         for (BLI_ghashIterator_init(&gh_iter_, ghash_), i_ = 0;                   \
112              BLI_ghashIterator_done(&gh_iter_) == false;                          \
113              BLI_ghashIterator_step(&gh_iter_), i_++)
114
115 /** \name Callbacks for GHash
116  *
117  * \note '_p' suffix denotes void pointer arg,
118  * so we can have functions that take correctly typed args too.
119  * \{ */
120
121 unsigned int    BLI_ghashutil_ptrhash(const void *key);
122 int             BLI_ghashutil_ptrcmp(const void *a, const void *b);
123
124 unsigned int    BLI_ghashutil_strhash_n(const char *key, size_t n);
125 #define         BLI_ghashutil_strhash(key) ( \
126                 CHECK_TYPE_INLINE(key, char *), \
127                 BLI_ghashutil_strhash_p(key))
128 unsigned int    BLI_ghashutil_strhash_p(const void *key);
129 int             BLI_ghashutil_strcmp(const void *a, const void *b);
130
131 #define         BLI_ghashutil_inthash(key) ( \
132                 CHECK_TYPE_INLINE(key, int), \
133                 BLI_ghashutil_uinthash((unsigned int)key))
134 unsigned int    BLI_ghashutil_uinthash(unsigned int key);
135 #define         BLI_ghashutil_inthash_v4(key) ( \
136                 CHECK_TYPE_INLINE(key, int *), \
137                 BLI_ghashutil_uinthash_v4((const unsigned int *)key))
138 unsigned int    BLI_ghashutil_uinthash_v4(const unsigned int key[4]);
139 #define         BLI_ghashutil_inthash_v4_p \
140    ((GSetHashFP)BLI_ghashutil_uinthash_v4)
141 unsigned int    BLI_ghashutil_inthash_p(const void *ptr);
142 int             BLI_ghashutil_intcmp(const void *a, const void *b);
143
144 /** \} */
145
146 GHash          *BLI_ghash_ptr_new_ex(const char *info,
147                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
148 GHash          *BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
149 GHash          *BLI_ghash_str_new_ex(const char *info,
150                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
151 GHash          *BLI_ghash_str_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
152 GHash          *BLI_ghash_int_new_ex(const char *info,
153                                      const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
154 GHash          *BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
155 GHash          *BLI_ghash_pair_new_ex(const char *info,
156                                       const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
157 GHash          *BLI_ghash_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
158
159 typedef struct GHashPair {
160         const void *first;
161         const void *second;
162 } GHashPair;
163
164 GHashPair      *BLI_ghashutil_pairalloc(const void *first, const void *second);
165 unsigned int    BLI_ghashutil_pairhash(const void *ptr);
166 int             BLI_ghashutil_paircmp(const void *a, const void *b);
167 void            BLI_ghashutil_pairfree(void *ptr);
168
169
170 /* *** */
171
172 typedef struct GSet GSet;
173
174 typedef GHashHashFP GSetHashFP;
175 typedef GHashCmpFP GSetCmpFP;
176 typedef GHashKeyFreeFP GSetKeyFreeFP;
177
178 /* so we can cast but compiler sees as different */
179 typedef struct GSetIterator {
180         GHashIterator _ghi
181 #ifdef __GNUC__
182         __attribute__ ((deprecated))
183 #endif
184         ;
185 } GSetIterator;
186
187 GSet  *BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info,
188                        const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
189 GSet  *BLI_gset_new(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
190 int    BLI_gset_size(GSet *gs) ATTR_WARN_UNUSED_RESULT;
191 void   BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp);
192 void   BLI_gset_insert(GSet *gh, void *key);
193 bool   BLI_gset_reinsert(GSet *gh, void *key, GSetKeyFreeFP keyfreefp);
194 bool   BLI_gset_haskey(GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT;
195 bool   BLI_gset_remove(GSet *gs, void *key, GSetKeyFreeFP keyfreefp);
196 void   BLI_gset_clear_ex(GSet *gs, GSetKeyFreeFP keyfreefp,
197                          const unsigned int nentries_reserve);
198 void  BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp);
199
200 GSet *BLI_gset_ptr_new_ex(const char *info,
201                           const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
202 GSet *BLI_gset_ptr_new(const char *info);
203 GSet *BLI_gset_pair_new_ex(const char *info,
204                             const unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
205 GSet *BLI_gset_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT;
206
207 /* rely on inline api for now */
208 BLI_INLINE GSetIterator *BLI_gsetIterator_new(GSet *gs) { return (GSetIterator *)BLI_ghashIterator_new((GHash *)gs); }
209 BLI_INLINE void BLI_gsetIterator_init(GSetIterator *gsi, GSet *gs) { BLI_ghashIterator_init((GHashIterator *)gsi, (GHash *)gs); }
210 BLI_INLINE void BLI_gsetIterator_free(GSetIterator *gsi) { BLI_ghashIterator_free((GHashIterator *)gsi); }
211 BLI_INLINE void *BLI_gsetIterator_getKey(GSetIterator *gsi) { return BLI_ghashIterator_getKey((GHashIterator *)gsi); }
212 BLI_INLINE void BLI_gsetIterator_step(GSetIterator *gsi) { BLI_ghashIterator_step((GHashIterator *)gsi); }
213 BLI_INLINE bool BLI_gsetIterator_done(GSetIterator *gsi) { return BLI_ghashIterator_done((GHashIterator *)gsi); }
214
215 #define GSET_ITER(gs_iter_, gset_)                                            \
216         for (BLI_gsetIterator_init(&gs_iter_, gset_);                             \
217              BLI_gsetIterator_done(&gs_iter_) == false;                           \
218              BLI_gsetIterator_step(&gs_iter_))
219
220 #define GSET_ITER_INDEX(gs_iter_, gset_, i_)                                  \
221         for (BLI_gsetIterator_init(&gs_iter_, gset_), i_ = 0;                     \
222              BLI_gsetIterator_done(&gs_iter_) == false;                           \
223              BLI_gsetIterator_step(&gs_iter_), i_++)
224
225 #ifdef __cplusplus
226 }
227 #endif
228
229 #endif /* __BLI_GHASH_H__ */