1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
/*
* This functionality is designed specifically for the ufunc machinery to
* dispatch based on multiple DTypes. Since this is designed to be used
* as purely a cache, it currently does no reference counting.
* Even though this is a cache, there is currently no maximum size. It may
* make sense to limit the size, or count collisions: If too many collisions
* occur, we could grow the cache, otherwise, just replace an old item that
* was presumably not used for a long time.
*
* If a different part of NumPy requires a custom hashtable, the code should
* be reused with care since specializing it more for the ufunc dispatching
* case is likely desired.
*/
#include "templ_common.h"
#include "npy_hashtable.h"
#if SIZEOF_PY_UHASH_T > 4
#define _NpyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
#define _NpyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
#define _NpyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
#define _NpyHASH_XXROTATE(x) ((x << 31) | (x >> 33)) /* Rotate left 31 bits */
#else
#define _NpyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
#define _NpyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
#define _NpyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
#define _NpyHASH_XXROTATE(x) ((x << 13) | (x >> 19)) /* Rotate left 13 bits */
#endif
/*
* This hashing function is basically the Python tuple hash with the type
* identity hash inlined. The tuple hash itself is a reduced version of xxHash.
*
* Users cannot control pointers, so we do not have to worry about DoS attacks?
*/
static inline Py_hash_t
identity_list_hash(PyObject *const *v, int len)
{
Py_uhash_t acc = _NpyHASH_XXPRIME_5;
for (int i = 0; i < len; i++) {
/*
* Lane is the single item hash, which for us is the rotated pointer.
* Identical to the python type hash (pointers end with 0s normally).
*/
size_t y = (size_t)v[i];
Py_uhash_t lane = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));
acc += lane * _NpyHASH_XXPRIME_2;
acc = _NpyHASH_XXROTATE(acc);
acc *= _NpyHASH_XXPRIME_1;
}
return acc;
}
#undef _NpyHASH_XXPRIME_1
#undef _NpyHASH_XXPRIME_2
#undef _NpyHASH_XXPRIME_5
#undef _NpyHASH_XXROTATE
static inline PyObject **
find_item(PyArrayIdentityHash const *tb, PyObject *const *key)
{
Py_hash_t hash = identity_list_hash(key, tb->key_len);
npy_uintp perturb = (npy_uintp)hash;
npy_intp bucket;
npy_intp mask = tb->size - 1 ;
PyObject **item;
bucket = (npy_intp)hash & mask;
while (1) {
item = &(tb->buckets[bucket * (tb->key_len + 1)]);
if (item[0] == NULL) {
/* The item is not in the cache; return the empty bucket */
return item;
}
if (memcmp(item+1, key, tb->key_len * sizeof(PyObject *)) == 0) {
/* This is a match, so return the item/bucket */
return item;
}
/* Hash collision, perturb like Python (must happen rarely!) */
perturb >>= 5; /* Python uses the macro PERTURB_SHIFT == 5 */
bucket = mask & (bucket * 5 + perturb + 1);
}
}
NPY_NO_EXPORT PyArrayIdentityHash *
PyArrayIdentityHash_New(int key_len)
{
PyArrayIdentityHash *res = PyMem_Malloc(sizeof(PyArrayIdentityHash));
if (res == NULL) {
PyErr_NoMemory();
return NULL;
}
assert(key_len > 0);
res->key_len = key_len;
res->size = 4; /* Start with a size of 4 */
res->nelem = 0;
res->buckets = PyMem_Calloc(4 * (key_len + 1), sizeof(PyObject *));
if (res->buckets == NULL) {
PyErr_NoMemory();
PyMem_Free(res);
return NULL;
}
return res;
}
NPY_NO_EXPORT void
PyArrayIdentityHash_Dealloc(PyArrayIdentityHash *tb)
{
PyMem_Free(tb->buckets);
PyMem_Free(tb);
}
static int
_resize_if_necessary(PyArrayIdentityHash *tb)
{
npy_intp new_size, prev_size = tb->size;
PyObject **old_table = tb->buckets;
assert(prev_size > 0);
if ((tb->nelem + 1) * 2 > prev_size) {
/* Double in size */
new_size = prev_size * 2;
}
else {
new_size = prev_size;
while ((tb->nelem + 8) * 2 < new_size / 2) {
/*
* Should possibly be improved. However, we assume that we
* almost never shrink. Still if we do, do not shrink as much
* as possible to avoid growing right away.
*/
new_size /= 2;
}
assert(new_size >= 4);
}
if (new_size == prev_size) {
return 0;
}
npy_intp alloc_size;
if (npy_mul_sizes_with_overflow(&alloc_size, new_size, tb->key_len + 1)) {
return -1;
}
tb->buckets = PyMem_Calloc(alloc_size, sizeof(PyObject *));
if (tb->buckets == NULL) {
tb->buckets = old_table;
PyErr_NoMemory();
return -1;
}
tb->size = new_size;
for (npy_intp i = 0; i < prev_size; i++) {
PyObject **item = &old_table[i * (tb->key_len + 1)];
if (item[0] != NULL) {
tb->nelem -= 1; /* Decrement, setitem will increment again */
PyArrayIdentityHash_SetItem(tb, item+1, item[0], 1);
}
}
PyMem_Free(old_table);
return 0;
}
/**
* Add an item to the identity cache. The storage location must not change
* unless the cache is cleared.
*
* @param tb The mapping.
* @param key The key, must be a C-array of pointers of the length
* corresponding to the mapping.
* @param value Normally a Python object, no reference counting is done.
* use NULL to clear an item. If the item does not exist, no
* action is performed for NULL.
* @param replace If 1, allow replacements.
* @returns 0 on success, -1 with a MemoryError or RuntimeError (if an item
* is added which is already in the cache). The caller should avoid
* the RuntimeError.
*/
NPY_NO_EXPORT int
PyArrayIdentityHash_SetItem(PyArrayIdentityHash *tb,
PyObject *const *key, PyObject *value, int replace)
{
if (value != NULL && _resize_if_necessary(tb) < 0) {
/* Shrink, only if a new value is added. */
return -1;
}
PyObject **tb_item = find_item(tb, key);
if (value != NULL) {
if (tb_item[0] != NULL && !replace) {
PyErr_SetString(PyExc_RuntimeError,
"Identity cache already includes the item.");
return -1;
}
tb_item[0] = value;
memcpy(tb_item+1, key, tb->key_len * sizeof(PyObject *));
tb->nelem += 1;
}
else {
/* Clear the bucket -- just the value should be enough though. */
memset(tb_item, 0, (tb->key_len + 1) * sizeof(PyObject *));
}
return 0;
}
NPY_NO_EXPORT PyObject *
PyArrayIdentityHash_GetItem(PyArrayIdentityHash const *tb, PyObject *const *key)
{
return find_item(tb, key)[0];
}
|
