Blender  V3.3
BLI_ghash_utils.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
11 #include <string.h>
12 
13 #include "MEM_guardedalloc.h"
14 
15 #include "BLI_ghash.h" /* own include */
16 #include "BLI_hash_mm2a.h"
17 #include "BLI_utildefines.h"
18 
19 /* keep last */
20 #include "BLI_strict_flags.h"
21 
22 /* -------------------------------------------------------------------- */
26 #if 0
27 /* works but slower */
28 uint BLI_ghashutil_ptrhash(const void *key)
29 {
30  return (uint)(intptr_t)key;
31 }
32 #else
33 uint BLI_ghashutil_ptrhash(const void *key)
34 {
35  /* Based Python3.7's pointer hashing function. */
36 
37  size_t y = (size_t)key;
38  /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
39  * excessive hash collisions for dicts and sets */
40 
41  /* NOTE: Unlike Python 'sizeof(uint)' is used instead of 'sizeof(void *)',
42  * Otherwise casting to 'uint' ignores the upper bits on 64bit platforms. */
43  return (uint)(y >> 4) | ((uint)y << (sizeof(uint[8]) - 4));
44 }
45 #endif
46 bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
47 {
48  return (a != b);
49 }
50 
52 {
53  uint hash;
54  hash = key[0];
55  hash *= 37;
56  hash += key[1];
57  hash *= 37;
58  hash += key[2];
59  hash *= 37;
60  hash += key[3];
61  return hash;
62 }
63 
65 {
66  return BLI_hash_mm2((const unsigned char *)key, sizeof(int[4]) /* sizeof(key) */, 0);
67 }
68 
69 bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
70 {
71  return (memcmp(a, b, sizeof(uint[4])) != 0);
72 }
73 
75 {
76  key += ~(key << 16);
77  key ^= (key >> 5);
78  key += (key << 3);
79  key ^= (key >> 13);
80  key += ~(key << 9);
81  key ^= (key >> 17);
82 
83  return key;
84 }
85 
87 {
88  uintptr_t key = (uintptr_t)ptr;
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 (uint)(key & 0xffffffff);
98 }
99 
101 {
102  uintptr_t key = (uintptr_t)ptr;
103 
104  return BLI_hash_mm2((const unsigned char *)&key, sizeof(key), 0);
105 }
106 
108 {
109  return POINTER_AS_UINT(ptr);
110 }
111 
112 bool BLI_ghashutil_intcmp(const void *a, const void *b)
113 {
114  return (a != b);
115 }
116 
117 size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
118 {
119  return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2));
120 }
121 
122 uint BLI_ghashutil_strhash_n(const char *key, size_t n)
123 {
124  const signed char *p;
125  uint h = 5381;
126 
127  for (p = (const signed char *)key; n-- && *p != '\0'; p++) {
128  h = (uint)((h << 5) + h) + (uint)*p;
129  }
130 
131  return h;
132 }
134 {
135  const signed char *p;
136  uint h = 5381;
137 
138  for (p = ptr; *p != '\0'; p++) {
139  h = (uint)((h << 5) + h) + (uint)*p;
140  }
141 
142  return h;
143 }
145 {
146  const unsigned char *key = ptr;
147 
148  return BLI_hash_mm2(key, strlen((const char *)key) + 1, 0);
149 }
150 bool BLI_ghashutil_strcmp(const void *a, const void *b)
151 {
152  return (a == b) ? false : !STREQ(a, b);
153 }
154 
155 GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
156 {
157  GHashPair *pair = MEM_mallocN(sizeof(GHashPair), "GHashPair");
158  pair->first = first;
159  pair->second = second;
160  return pair;
161 }
162 
164 {
165  const GHashPair *pair = ptr;
167  return hash ^ BLI_ghashutil_ptrhash(pair->second);
168 }
169 
170 bool BLI_ghashutil_paircmp(const void *a, const void *b)
171 {
172  const GHashPair *A = a;
173  const GHashPair *B = b;
174 
175  return ((A->first != B->first) || (A->second != B->second));
176 }
177 
179 {
180  MEM_freeN(ptr);
181 }
182 
185 /* -------------------------------------------------------------------- */
189 GHash *BLI_ghash_ptr_new_ex(const char *info, const uint nentries_reserve)
190 {
191  return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
192 }
193 GHash *BLI_ghash_ptr_new(const char *info)
194 {
195  return BLI_ghash_ptr_new_ex(info, 0);
196 }
197 
198 GHash *BLI_ghash_str_new_ex(const char *info, const uint nentries_reserve)
199 {
200  return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
201 }
202 GHash *BLI_ghash_str_new(const char *info)
203 {
204  return BLI_ghash_str_new_ex(info, 0);
205 }
206 
207 GHash *BLI_ghash_int_new_ex(const char *info, const uint nentries_reserve)
208 {
209  return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
210 }
211 GHash *BLI_ghash_int_new(const char *info)
212 {
213  return BLI_ghash_int_new_ex(info, 0);
214 }
215 
216 GHash *BLI_ghash_pair_new_ex(const char *info, const uint nentries_reserve)
217 {
218  return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
219 }
220 GHash *BLI_ghash_pair_new(const char *info)
221 {
222  return BLI_ghash_pair_new_ex(info, 0);
223 }
224 
227 /* -------------------------------------------------------------------- */
231 GSet *BLI_gset_ptr_new_ex(const char *info, const uint nentries_reserve)
232 {
233  return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
234 }
235 GSet *BLI_gset_ptr_new(const char *info)
236 {
237  return BLI_gset_ptr_new_ex(info, 0);
238 }
239 
240 GSet *BLI_gset_str_new_ex(const char *info, const uint nentries_reserve)
241 {
242  return BLI_gset_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
243 }
244 GSet *BLI_gset_str_new(const char *info)
245 {
246  return BLI_gset_str_new_ex(info, 0);
247 }
248 
249 GSet *BLI_gset_pair_new_ex(const char *info, const uint nentries_reserve)
250 {
251  return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
252 }
253 GSet *BLI_gset_pair_new(const char *info)
254 {
255  return BLI_gset_pair_new_ex(info, 0);
256 }
257 
258 GSet *BLI_gset_int_new_ex(const char *info, const uint nentries_reserve)
259 {
260  return BLI_gset_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
261 }
262 GSet *BLI_gset_int_new(const char *info)
263 {
264  return BLI_gset_int_new_ex(info, 0);
265 }
266 
struct GSet GSet
Definition: BLI_ghash.h:340
GSet * BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:939
GHash * BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:681
GSet * BLI_gset_str_new(const char *info)
GSet * BLI_gset_int_new_ex(const char *info, const uint nentries_reserve)
bool BLI_ghashutil_strcmp(const void *a, const void *b)
uint BLI_ghashutil_strhash_p(const void *ptr)
uint BLI_ghashutil_inthash_p(const void *ptr)
size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
uint BLI_ghashutil_uinthash_v4(const uint key[4])
GSet * BLI_gset_ptr_new_ex(const char *info, const uint nentries_reserve)
GHash * BLI_ghash_pair_new_ex(const char *info, const uint nentries_reserve)
GHashPair * BLI_ghashutil_pairalloc(const void *first, const void *second)
GSet * BLI_gset_ptr_new(const char *info)
uint BLI_ghashutil_inthash_p_simple(const void *ptr)
GHash * BLI_ghash_str_new_ex(const char *info, const uint nentries_reserve)
GHash * BLI_ghash_ptr_new_ex(const char *info, const uint nentries_reserve)
GHash * BLI_ghash_ptr_new(const char *info)
uint BLI_ghashutil_strhash_p_murmur(const void *ptr)
void BLI_ghashutil_pairfree(void *ptr)
uint BLI_ghashutil_pairhash(const void *ptr)
GSet * BLI_gset_str_new_ex(const char *info, const uint nentries_reserve)
GSet * BLI_gset_pair_new_ex(const char *info, const uint nentries_reserve)
uint BLI_ghashutil_ptrhash(const void *key)
bool BLI_ghashutil_intcmp(const void *a, const void *b)
bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
uint BLI_ghashutil_inthash_p_murmur(const void *ptr)
GSet * BLI_gset_pair_new(const char *info)
GSet * BLI_gset_int_new(const char *info)
GHash * BLI_ghash_int_new_ex(const char *info, const uint nentries_reserve)
uint BLI_ghashutil_uinthash(uint key)
bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
bool BLI_ghashutil_paircmp(const void *a, const void *b)
GHash * BLI_ghash_int_new(const char *info)
uint BLI_ghashutil_uinthash_v4_murmur(const uint key[4])
uint BLI_ghashutil_strhash_n(const char *key, size_t n)
GHash * BLI_ghash_str_new(const char *info)
GHash * BLI_ghash_pair_new(const char *info)
uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed)
Definition: hash_mm2a.c:99
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define POINTER_AS_UINT(i)
#define STREQ(a, b)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
Read Guarded memory(de)allocation.
#define A
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
#define B
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define hash
Definition: noise.c:153
_W64 unsigned int uintptr_t
Definition: stdint.h:119
_W64 int intptr_t
Definition: stdint.h:118
const void * second
Definition: BLI_ghash.h:605
const void * first
Definition: BLI_ghash.h:604
PointerRNA * ptr
Definition: wm_files.c:3480