Lines Matching defs:hash
10 The initial probe index is computed as hash mod the table size.
16 reduces the cost of hash collisions because consecutive memory accesses
18 we then use more of the upper bits from the hash value and apply a simple
22 All arithmetic on hash should ignore overflow.
45 /* ======= Begin logic for probing the hash table ========================= */
56 set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
60 size_t perturb = hash;
62 size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */
70 if (entry->hash == 0 && entry->key == NULL)
72 if (entry->hash == hash) {
88 return set_lookkey(so, key, hash);
103 set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
121 i = (size_t)hash & mask;
123 perturb = hash;
129 if (entry->hash == 0 && entry->key == NULL)
131 if (entry->hash == hash) {
152 else if (entry->hash == -1) {
167 freeslot->hash = hash;
174 entry->hash = hash;
197 set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash)
200 size_t perturb = hash;
201 size_t i = (size_t)hash & mask;
220 entry->hash = hash;
223 /* ======== End logic for probing the hash table ========================== */
293 set_insert_clean(newtable, newmask, entry->key, entry->hash);
300 set_insert_clean(newtable, newmask, entry->key, entry->hash);
311 set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
315 entry = set_lookkey(so, key, hash);
325 set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
330 entry = set_lookkey(so, key, hash);
337 entry->hash = -1;
346 Py_hash_t hash;
349 (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
350 hash = PyObject_Hash(key);
351 if (hash == -1)
354 return set_add_entry(so, key, hash);
360 Py_hash_t hash;
363 (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
364 hash = PyObject_Hash(key);
365 if (hash == -1)
368 return set_contains_entry(so, key, hash);
374 Py_hash_t hash;
377 (hash = _PyASCIIObject_CAST(key)->hash) == -1) {
378 hash = PyObject_Hash(key);
379 if (hash == -1)
382 return set_discard_entry(so, key, hash);
393 so->hash = -1;
593 so_entry->hash = other_entry->hash;
611 set_insert_clean(newtable, newmask, key, other_entry->hash);
622 if (set_add_entry(so, key, other_entry->hash))
648 entry->hash = -1;
668 /* Work to increase the bit dispersion for closely spaced hash values.
671 combinations collapse to only a handful of distinct hash values. */
679 /* Most of the constants in this hash algorithm are randomly chosen
689 Py_uhash_t hash = 0;
692 if (so->hash != -1)
693 return so->hash;
695 /* Xor-in shuffled bits from every entry's hash field because xor is
696 commutative and a frozenset hash should be independent of order.
699 subtract out their effect afterwards so that the final hash
706 hash ^= _shuffle_bits(entry->hash);
710 hash ^= _shuffle_bits(0);
714 hash ^= _shuffle_bits(-1);
717 hash ^= ((Py_uhash_t)PySet_GET_SIZE(self) + 1) * 1927868237UL;
720 hash ^= (hash >> 11) ^ (hash >> 25);
721 hash = hash * 69069U + 907133923UL;
724 if (hash == (Py_uhash_t)-1)
725 hash = 590923713UL;
727 so->hash = hash;
728 return hash;
891 Py_hash_t hash;
904 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
905 if (set_add_entry(so, key, hash))
965 so->hash = -1;
1086 h = a->hash; a->hash = b->hash; b->hash = h;
1088 a->hash = -1;
1089 b->hash = -1;
1185 Py_hash_t hash;
1207 hash = entry->hash;
1209 rv = set_contains_entry(so, key, hash);
1216 if (set_add_entry(result, key, hash)) {
1234 hash = PyObject_Hash(key);
1235 if (hash == -1)
1237 rv = set_contains_entry(so, key, hash);
1241 if (set_add_entry(result, key, hash))
1368 rv = set_contains_entry(so, key, entry->hash);
1430 if (set_discard_entry(so, key, entry->hash) < 0) {
1498 Py_hash_t hash;
1526 hash = entry->hash;
1528 rv = _PyDict_Contains_KnownHash(other, key, hash);
1535 if (set_add_entry((PySetObject *)result, key, hash)) {
1549 hash = entry->hash;
1551 rv = set_contains_entry((PySetObject *)other, key, hash);
1558 if (set_add_entry((PySetObject *)result, key, hash)) {
1622 Py_hash_t hash;
1631 while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
1633 rv = set_discard_entry(so, key, hash);
1639 if (set_add_entry(so, key, hash)) {
1660 hash = entry->hash;
1662 rv = set_discard_entry(so, key, hash);
1669 if (set_add_entry(so, key, hash)) {
1752 rv = set_contains_entry((PySetObject *)other, key, entry->hash);
1811 if (v->hash != -1 &&
1812 ((PySetObject *)w)->hash != -1 &&
1813 v->hash != ((PySetObject *)w)->hash)
1992 self->hash = -1;
2341 _PySet_NextEntry(PyObject *set, Py_ssize_t *pos, PyObject **key, Py_hash_t *hash)
2352 *hash = entry->hash;
2399 Py_hash_t hash;
2462 while (_PySet_NextEntry((PyObject *)dup, &i, &x, &hash)) {