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