| 59 | |
| 60 | |
| 61 | static inline PyObject ** |
| 62 | find_item(PyArrayIdentityHash const *tb, PyObject *const *key) |
| 63 | { |
| 64 | Py_hash_t hash = identity_list_hash(key, tb->key_len); |
| 65 | npy_uintp perturb = (npy_uintp)hash; |
| 66 | npy_intp bucket; |
| 67 | npy_intp mask = tb->size - 1 ; |
| 68 | PyObject **item; |
| 69 | |
| 70 | bucket = (npy_intp)hash & mask; |
| 71 | while (1) { |
| 72 | item = &(tb->buckets[bucket * (tb->key_len + 1)]); |
| 73 | |
| 74 | if (item[0] == NULL) { |
| 75 | /* The item is not in the cache; return the empty bucket */ |
| 76 | return item; |
| 77 | } |
| 78 | if (memcmp(item+1, key, tb->key_len * sizeof(PyObject *)) == 0) { |
| 79 | /* This is a match, so return the item/bucket */ |
| 80 | return item; |
| 81 | } |
| 82 | /* Hash collision, perturb like Python (must happen rarely!) */ |
| 83 | perturb >>= 5; /* Python uses the macro PERTURB_SHIFT == 5 */ |
| 84 | bucket = mask & (bucket * 5 + perturb + 1); |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | |
| 89 | NPY_NO_EXPORT PyArrayIdentityHash * |
no test coverage detected