Blender V5.3
BLI_ghash_utils.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <cstring>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_ghash.hh" /* own include */
17#include "BLI_hash_mm2a.hh"
18#include "BLI_utildefines.hh"
19
20#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
21
22namespace blender {
23
24/* -------------------------------------------------------------------- */
27
28#if 0
29/* works but slower */
30uint BLI_ghashutil_ptrhash(const void *key)
31{
32 return uint(intptr_t(key));
33}
34#else
36{
37 /* Based Python3.7's pointer hashing function. */
38
39 size_t y = size_t(key);
40 /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
41 * excessive hash collisions for dictionaries and sets */
42
43 /* NOTE: Unlike Python `sizeof(uint)` is used instead of `sizeof(void *)`,
44 * Otherwise casting to 'uint' ignores the upper bits on 64bit platforms. */
45 return uint(y >> 4) | (uint(y) << (sizeof(uint[8]) - 4));
46}
47#endif
48bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
49{
50 return (a != b);
51}
52
54{
55 uint hash;
56 hash = key[0];
57 hash *= 37;
58 hash += key[1];
59 hash *= 37;
60 hash += key[2];
61 hash *= 37;
62 hash += key[3];
63 return hash;
64}
65
67{
68 return BLI_hash_mm2(reinterpret_cast<const uchar *>(key), sizeof(int[4]) /* sizeof(key) */, 0);
69}
70
71bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
72{
73 return (memcmp(a, b, sizeof(uint[4])) != 0);
74}
75
77{
78 key += ~(key << 16);
79 key ^= (key >> 5);
80 key += (key << 3);
81 key ^= (key >> 13);
82 key += ~(key << 9);
83 key ^= (key >> 17);
84
85 return key;
86}
87
89{
90 uintptr_t key = uintptr_t(ptr);
91
92 key += ~(key << 16);
93 key ^= (key >> 5);
94 key += (key << 3);
95 key ^= (key >> 13);
96 key += ~(key << 9);
97 key ^= (key >> 17);
98
99 return uint(key & 0xffffffff);
100}
101
103{
104 uintptr_t key = uintptr_t(ptr);
105
106 return BLI_hash_mm2(reinterpret_cast<const uchar *>(&key), sizeof(key), 0);
107}
108
110{
111 return POINTER_AS_UINT(ptr);
112}
113
114bool BLI_ghashutil_intcmp(const void *a, const void *b)
115{
116 return (a != b);
117}
118
119size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
120{
121 return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2));
122}
123
124uint BLI_ghashutil_strhash_n(const char *key, size_t n)
125{
126 const signed char *p;
127 uint h = 5381;
128
129 for (p = reinterpret_cast<const signed char *>(key); n-- && *p != '\0'; p++) {
130 h = ((h << 5) + h) + uint(*p);
131 }
132
133 return h;
134}
136{
137 const signed char *p;
138 uint h = 5381;
139
140 for (p = static_cast<const signed char *>(ptr); *p != '\0'; p++) {
141 h = ((h << 5) + h) + uint(*p);
142 }
143
144 return h;
145}
147{
148 const uchar *key = static_cast<const uchar *>(ptr);
149
150 return BLI_hash_mm2(key, strlen(reinterpret_cast<const char *>(key)) + 1, 0);
151}
152bool BLI_ghashutil_strcmp(const void *a, const void *b)
153{
154 return (a == b) ? false : !STREQ(static_cast<const char *>(a), static_cast<const char *>(b));
155}
156
157GHashPair *BLI_ghashutil_pairalloc(const void *first, const void *second)
158{
159 GHashPair *pair = MEM_new_uninitialized<GHashPair>("GHashPair");
160 pair->first = first;
161 pair->second = second;
162 return pair;
163}
164
166{
167 const GHashPair *pair = static_cast<const GHashPair *>(ptr);
169 return hash ^ BLI_ghashutil_ptrhash(pair->second);
170}
171
172bool BLI_ghashutil_paircmp(const void *a, const void *b)
173{
174 const GHashPair *A = static_cast<const GHashPair *>(a);
175 const GHashPair *B = static_cast<const GHashPair *>(b);
176
177 return ((A->first != B->first) || (A->second != B->second));
178}
179
181{
182 MEM_delete(static_cast<const GHashPair *>(ptr));
183}
184
186
187/* -------------------------------------------------------------------- */
190
191GHash *BLI_ghash_ptr_new_ex(const char *info, const uint nentries_reserve)
192{
193 return BLI_ghash_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
194}
195GHash *BLI_ghash_ptr_new(const char *info)
196{
197 return BLI_ghash_ptr_new_ex(info, 0);
198}
199
200GHash *BLI_ghash_str_new_ex(const char *info, const uint nentries_reserve)
201{
202 return BLI_ghash_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
203}
204GHash *BLI_ghash_str_new(const char *info)
205{
206 return BLI_ghash_str_new_ex(info, 0);
207}
208
209GHash *BLI_ghash_int_new_ex(const char *info, const uint nentries_reserve)
210{
211 return BLI_ghash_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
212}
213GHash *BLI_ghash_int_new(const char *info)
214{
215 return BLI_ghash_int_new_ex(info, 0);
216}
217
218GHash *BLI_ghash_pair_new_ex(const char *info, const uint nentries_reserve)
219{
220 return BLI_ghash_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
221}
222GHash *BLI_ghash_pair_new(const char *info)
223{
224 return BLI_ghash_pair_new_ex(info, 0);
225}
226
228
229/* -------------------------------------------------------------------- */
232
233GSet *BLI_gset_ptr_new_ex(const char *info, const uint nentries_reserve)
234{
235 return BLI_gset_new_ex(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, info, nentries_reserve);
236}
237GSet *BLI_gset_ptr_new(const char *info)
238{
239 return BLI_gset_ptr_new_ex(info, 0);
240}
241
242GSet *BLI_gset_str_new_ex(const char *info, const uint nentries_reserve)
243{
244 return BLI_gset_new_ex(BLI_ghashutil_strhash_p, BLI_ghashutil_strcmp, info, nentries_reserve);
245}
246GSet *BLI_gset_str_new(const char *info)
247{
248 return BLI_gset_str_new_ex(info, 0);
249}
250
251GSet *BLI_gset_pair_new_ex(const char *info, const uint nentries_reserve)
252{
253 return BLI_gset_new_ex(BLI_ghashutil_pairhash, BLI_ghashutil_paircmp, info, nentries_reserve);
254}
255GSet *BLI_gset_pair_new(const char *info)
256{
257 return BLI_gset_pair_new_ex(info, 0);
258}
259
260GSet *BLI_gset_int_new_ex(const char *info, const uint nentries_reserve)
261{
262 return BLI_gset_new_ex(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, info, nentries_reserve);
263}
264GSet *BLI_gset_int_new(const char *info)
265{
266 return BLI_gset_int_new_ex(info, 0);
267}
268
270
271} // namespace blender
Read Blender memory allocation and freeing.
#define POINTER_AS_UINT(i)
#define STREQ(a, b)
#define A
#define B
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
unsigned int BLI_ghashutil_uinthash(unsigned int key)
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
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.cc:682
GHash * BLI_ghash_str_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int uint
Definition BKE_text.h:55
unsigned int BLI_ghashutil_strhash_n(const char *key, size_t n)
GHash * BLI_ghash_ptr_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GSet * BLI_gset_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int BLI_ghashutil_ptrhash(const void *key)
void BLI_ghashutil_pairfree(void *ptr)
unsigned int BLI_ghashutil_strhash_p_murmur(const void *ptr)
GSet * BLI_gset_pair_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
bool BLI_ghashutil_paircmp(const void *a, const void *b)
GSet * BLI_gset_str_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
GSet * BLI_gset_ptr_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned char uchar
Definition BKE_text.h:58
GHashPair * BLI_ghashutil_pairalloc(const void *first, const void *second)
uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed)
Definition hash_mm2a.cc:102
bool BLI_ghashutil_intcmp(const void *a, const void *b)
GHash * BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int BLI_ghashutil_inthash_p_murmur(const void *ptr)
GHash * BLI_ghash_str_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4])
GSet * BLI_gset_int_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
GSet * BLI_gset_ptr_new(const char *info)
GHash * BLI_ghash_pair_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int BLI_ghashutil_inthash_p_simple(const void *ptr)
unsigned int BLI_ghashutil_pairhash(const void *ptr)
size_t BLI_ghashutil_combine_hash(size_t hash_a, size_t hash_b)
unsigned int BLI_ghashutil_strhash_p(const void *ptr)
GSet * BLI_gset_str_new(const char *info)
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.cc:942
unsigned int BLI_ghashutil_inthash_p(const void *ptr)
GHash * BLI_ghash_int_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_ghashutil_ptrcmp(const void *a, const void *b)
GSet * BLI_gset_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
unsigned int BLI_ghashutil_uinthash_v4(const unsigned int key[4])
GHash * BLI_ghash_pair_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_ghashutil_strcmp(const void *a, const void *b)
_W64 int intptr_t
Definition BKE_text.h:119
#define hash
Definition noise_c.cc:156
const void * first
Definition BLI_ghash.hh:604
const void * second
Definition BLI_ghash.hh:605