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