doxygen: add newline after \file
[blender.git] / source / blender / blenlib / intern / BLI_ghash_utils.c
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 /** \file
21  * \ingroup bli
22  *
23  * Helper functions and implementations of standard data types for #GHash
24  * (not it's implementation).
25  */
26
27 #include <string.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_utildefines.h"
32 #include "BLI_hash_mm2a.h"
33 #include "BLI_ghash.h"  /* own include */
34
35 /* keep last */
36 #include "BLI_strict_flags.h"
37
38 /* -------------------------------------------------------------------- */
39 /** \name Generic Key Hash & Comparison Functions
40  * \{ */
41
42 #if 0
43 /* works but slower */
44 uint BLI_ghashutil_ptrhash(const void *key)
45 {
46         return (uint)(intptr_t)key;
47 }
48 #else
49 /* Based Python3.7's pointer hashing function. */
50 uint BLI_ghashutil_ptrhash(const void *key)
51 {
52         size_t y = (size_t)key;
53         /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
54          * excessive hash collisions for dicts and sets */
55
56         /* Note: Unlike Python 'sizeof(uint)' is used instead of 'sizeof(void *)',
57          * Otherwise casting to 'uint' ignores the upper bits on 64bit platforms. */
58         return (uint)(y >> 4) | ((uint)y << (8 * sizeof(uint) - 4));
59 }
60 #endif
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 ((A->first != B->first) ||
199                 (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 /** \} */