Cleanup: Remove more #if 0 blocks
[blender.git] / source / blender / blenlib / intern / BLI_ghash_utils.c
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 /** \file blender/blenlib/intern/BLI_ghash_utils.c
29  *  \ingroup bli
30  *
31  * Helper functions and implementations of standard data types for #GHash
32  * (not it's implementation).
33  */
34
35 #include <string.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_hash_mm2a.h"
41 #include "BLI_ghash.h"  /* own include */
42
43 /* keep last */
44 #include "BLI_strict_flags.h"
45
46 /* -------------------------------------------------------------------- */
47 /** \name Generic Key Hash & Comparison Functions
48  * \{ */
49
50
51 /* based python3.3's pointer hashing function */
52 uint BLI_ghashutil_ptrhash(const void *key)
53 {
54         size_t y = (size_t)key;
55         /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
56          * excessive hash collisions for dicts and sets */
57         y = (y >> 4) | (y << (8 * sizeof(void *) - 4));
58         return (uint)y;
59 }
60
61 bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
62 {
63         return (a != b);
64 }
65
66 uint BLI_ghashutil_uinthash_v4(const uint key[4])
67 {
68         uint hash;
69         hash  = key[0];
70         hash *= 37;
71         hash += key[1];
72         hash *= 37;
73         hash += key[2];
74         hash *= 37;
75         hash += key[3];
76         return hash;
77 }
78 uint BLI_ghashutil_uinthash_v4_murmur(const uint key[4])
79 {
80         return BLI_hash_mm2((const unsigned char *)key, sizeof(int) * 4  /* sizeof(key) */, 0);
81 }
82
83 bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
84 {
85         return (memcmp(a, b, sizeof(uint[4])) != 0);
86 }
87
88 uint BLI_ghashutil_uinthash(uint key)
89 {
90         key += ~(key << 16);
91         key ^=  (key >>  5);
92         key +=  (key <<  3);
93         key ^=  (key >> 13);
94         key += ~(key <<  9);
95         key ^=  (key >> 17);
96
97         return key;
98 }
99
100 uint BLI_ghashutil_inthash_p(const void *ptr)
101 {
102         uintptr_t key = (uintptr_t)ptr;
103
104         key += ~(key << 16);
105         key ^=  (key >>  5);
106         key +=  (key <<  3);
107         key ^=  (key >> 13);
108         key += ~(key <<  9);
109         key ^=  (key >> 17);
110
111         return (uint)(key & 0xffffffff);
112 }
113
114 uint BLI_ghashutil_inthash_p_murmur(const void *ptr)
115 {
116         uintptr_t key = (uintptr_t)ptr;
117
118         return BLI_hash_mm2((const unsigned char *)&key, sizeof(key), 0);
119 }
120
121 uint BLI_ghashutil_inthash_p_simple(const void *ptr)
122 {
123         return POINTER_AS_UINT(ptr);
124 }
125
126 bool BLI_ghashutil_intcmp(const void *a, const void *b)
127 {
128         return (a != b);
129 }
130
131 size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
132 {
133         return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2));
134 }
135
136 /**
137  * This function implements the widely used "djb" hash apparently posted
138  * by Daniel Bernstein to comp.lang.c some time ago.  The 32 bit
139  * unsigned hash value starts at 5381 and for each byte 'c' in the
140  * string, is updated: ``hash = hash * 33 + c``.  This
141  * function uses the signed value of each byte.
142  *
143  * note: this is the same hash method that glib 2.34.0 uses.
144  */
145 uint BLI_ghashutil_strhash_n(const char *key, size_t n)
146 {
147         const signed char *p;
148         uint h = 5381;
149
150         for (p = (const signed char *)key; n-- && *p != '\0'; p++) {
151                 h = (uint)((h << 5) + h) + (uint)*p;
152         }
153
154         return h;
155 }
156 uint BLI_ghashutil_strhash_p(const void *ptr)
157 {
158         const signed char *p;
159         uint h = 5381;
160
161         for (p = ptr; *p != '\0'; p++) {
162                 h = (uint)((h << 5) + h) + (uint)*p;
163         }
164
165         return h;
166 }
167 uint BLI_ghashutil_strhash_p_murmur(const void *ptr)
168 {
169         const unsigned char *key = ptr;
170
171         return BLI_hash_mm2(key, strlen((const char *)key) + 1, 0);
172 }
173 bool BLI_ghashutil_strcmp(const void *a, const void *b)
174 {
175         return (a == b) ? false : !STREQ(a, b);
176 }
177
178 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
179 {
180         GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
181         pair->first = first;
182         pair->second = second;
183         return pair;
184 }
185
186 uint BLI_ghashutil_pairhash(const void *ptr)
187 {
188         const GHashPair *pair = ptr;
189         uint hash = BLI_ghashutil_ptrhash(pair->first);
190         return hash ^ BLI_ghashutil_ptrhash(pair->second);
191 }
192
193 bool BLI_ghashutil_paircmp(const void *a, const void *b)
194 {
195         const GHashPair *A = a;
196         const GHashPair *B = b;
197
198         return (BLI_ghashutil_ptrcmp(A->first, B->first) ||
199                 BLI_ghashutil_ptrcmp(A->second, B->second));
200 }
201
202 void BLI_ghashutil_pairfree(void *ptr)
203 {
204         MEM_freeN(ptr);
205 }
206
207 /** \} */
208
209 /* -------------------------------------------------------------------- */
210 /** \name Convenience GHash Creation Functions
211  * \{ */
212
213 GHash *BLI_ghash_ptr_new_ex(const char *info, const uint nentries_reserve)
214 {
215         return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
216 }
217 GHash *BLI_ghash_ptr_new(const char *info)
218 {
219         return BLI_ghash_ptr_new_ex(info, 0);
220 }
221
222 GHash *BLI_ghash_str_new_ex(const char *info, const uint nentries_reserve)
223 {
224         return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
225 }
226 GHash *BLI_ghash_str_new(const char *info)
227 {
228         return BLI_ghash_str_new_ex(info, 0);
229 }
230
231 GHash *BLI_ghash_int_new_ex(const char *info, const uint nentries_reserve)
232 {
233         return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
234 }
235 GHash *BLI_ghash_int_new(const char *info)
236 {
237         return BLI_ghash_int_new_ex(info, 0);
238 }
239
240 GHash *BLI_ghash_pair_new_ex(const char *info, const uint nentries_reserve)
241 {
242         return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
243 }
244 GHash *BLI_ghash_pair_new(const char *info)
245 {
246         return BLI_ghash_pair_new_ex(info, 0);
247 }
248
249 /** \} */
250
251 /* -------------------------------------------------------------------- */
252 /** \name Convenience GSet Creation Functions
253  * \{ */
254
255 GSet *BLI_gset_ptr_new_ex(const char *info, const uint nentries_reserve)
256 {
257         return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
258 }
259 GSet *BLI_gset_ptr_new(const char *info)
260 {
261         return BLI_gset_ptr_new_ex(info, 0);
262 }
263
264 GSet *BLI_gset_str_new_ex(const char *info, const uint nentries_reserve)
265 {
266         return BLI_gset_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
267 }
268 GSet *BLI_gset_str_new(const char *info)
269 {
270         return BLI_gset_str_new_ex(info, 0);
271 }
272
273 GSet *BLI_gset_pair_new_ex(const char *info, const uint nentries_reserve)
274 {
275         return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
276 }
277 GSet *BLI_gset_pair_new(const char *info)
278 {
279         return BLI_gset_pair_new_ex(info, 0);
280 }
281
282 /** \} */