Message276915
Here is a rough (very rough and not compileable) sketch of the direction that resizing should take:
static void
insert_indices_clean(PyDictObject *mp, Py_hash_t hash)
{
size_t i, perturb;
PyDictKeysObject *k = mp->ma_keys;
size_t mask = (size_t)DK_SIZE(k)-1;
i = hash & mask;
for (perturb = hash; dk_get_index(k, i) != DKIX_EMPTY;
perturb >>= PERTURB_SHIFT) {
i = mask & ((i << 2) + i + perturb + 1);
}
dk_set_index(k, i, k->dk_nentries);
}
static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
Py_ssize_t i, newsize;
PyDictKeyEntry *ep0;
/* Find the smallest table size > minused. */
for (newsize = PyDict_MINSIZE;
newsize <= minused && newsize > 0;
newsize <<= 1)
;
if (newsize <= 0) {
PyErr_NoMemory();
return -1;
}
realloc(dk->dk_indicies, es * newsize);
memset(&dk->dk_indices.as_1[0], 0xff, es * size);
dk->dk_size = size;
for (i = 0; i < mp->dk_nentries; i++) {
PyDictKeyEntry *ep = &ep0[i];
if (ep->me_value != NULL) {
insert_indices_clean(mp, ep->me_hash);
}
}
return 0;
} |
|
Date |
User |
Action |
Args |
2016-09-18 21:14:27 | rhettinger | set | recipients:
+ rhettinger, vstinner, ned.deily, methane, serhiy.storchaka, xiang.zhang |
2016-09-18 21:14:27 | rhettinger | set | messageid: <1474233267.13.0.0813817493389.issue28183@psf.upfronthosting.co.za> |
2016-09-18 21:14:27 | rhettinger | link | issue28183 messages |
2016-09-18 21:14:27 | rhettinger | create | |
|