cpython: f0fbc6071d7e (original) (raw)

--- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -1196,41 +1196,21 @@ insertdict(PyDictObject *mp, PyObject k } / -Internal routine used by dictresize() to insert an item which is -known to be absent from the dict. This routine also assumes that -the dict contains no deleted entries. Besides the performance benefit, -using insertdict() in dictresize() is dangerous (SF bug #1456209). -Note that no refcounts are changed by this routine; if needed, the caller -is responsible for incref'ing key and value. -Neither mp->ma_used nor k->dk_usable are modified by this routine; the caller -must set them correctly +Internal routine used by dictresize() to buid a hashtable of entries. */ static void -insertdict_clean(PyDictObject *mp, PyObject *key, Py_hash_t hash,

```
            PyObject *value)[](#l1.19)
```

+build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n) {

size_t i;
PyDictKeysObject *k = mp->ma_keys;
size_t mask = (size_t)DK_SIZE(k)-1;
PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
PyDictKeyEntry *ep;

assert(k->dk_lookup != NULL);
assert(value != NULL);
assert(key != NULL);
assert(PyUnicode_CheckExact(key) || k->dk_lookup == lookdict);
i = hash & mask;
for (size_t perturb = hash; dk_get_index(k, i) != DKIX_EMPTY;) {
```
   perturb >>= PERTURB_SHIFT;[](#l1.34)
```

   i = mask & ((i << 2) + i + perturb + 1);[](#l1.35)

size_t mask = (size_t)DK_SIZE(keys) - 1;
for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {

   Py_hash_t hash = ep->me_hash;[](#l1.38)

```
   size_t i = hash & mask;[](#l1.39)
```

   for (size_t perturb = hash; dk_get_index(keys, i) != DKIX_EMPTY;) {[](#l1.40)

       perturb >>= PERTURB_SHIFT;[](#l1.41)

       i = mask & ((i << 2) + i + perturb + 1);[](#l1.42)

```
   }[](#l1.43)
```
```
   dk_set_index(keys, i, ix);[](#l1.44)
```
}

ep = &ep0[k->dk_nentries];
assert(ep->me_value == NULL);
dk_set_index(k, i, k->dk_nentries);
k->dk_nentries++;
ep->me_key = key;
ep->me_hash = hash;
ep->me_value = value;

} /* @@ -1246,10 +1226,10 @@ but can be resplit by make_keys_shared() static int dictresize(PyDictObject *mp, Py_ssize_t minused) {

Py_ssize_t i, newsize;

Py_ssize_t newsize, numentries; PyDictKeysObject *oldkeys; PyObject **oldvalues;

PyDictKeyEntry *ep0;

PyDictKeyEntry *oldentries, *newentries;

/* Find the smallest table size > minused. */ for (newsize = PyDict_MINSIZE; @@ -1260,8 +1240,14 @@ dictresize(PyDictObject *mp, Py_ssize_t PyErr_NoMemory(); return -1; } + oldkeys = mp->ma_keys;

oldvalues = mp->ma_values;

/* NOTE: Current odict checks mp->ma_keys to detect resize happen.

* So we can't reuse oldkeys even if oldkeys->dk_size == newsize.[](#l1.78)

* TODO: Try reusing oldkeys when reimplement odict.[](#l1.79)

```
*/[](#l1.80)
```

+ /* Allocate a new table. */ mp->ma_keys = new_keys_object(newsize); if (mp->ma_keys == NULL) { @@ -1270,42 +1256,59 @@ dictresize(PyDictObject *mp, Py_ssize_t } if (oldkeys->dk_lookup == lookdict) mp->ma_keys->dk_lookup = lookdict;

mp->ma_values = NULL;
ep0 = DK_ENTRIES(oldkeys);
/* Main loop below assumes we can transfer refcount to new keys

* and that value is stored in me_value.[](#l1.92)

* Increment ref-counts and copy values here to compensate[](#l1.93)

* This (resizing a split table) should be relatively rare */[](#l1.94)

numentries = mp->ma_used;
oldentries = DK_ENTRIES(oldkeys);
newentries = DK_ENTRIES(mp->ma_keys);
oldvalues = mp->ma_values; if (oldvalues != NULL) {

   for (i = 0; i < oldkeys->dk_nentries; i++) {[](#l1.101)

       if (oldvalues[i] != NULL) {[](#l1.102)

           Py_INCREF(ep0[i].me_key);[](#l1.103)

           ep0[i].me_value = oldvalues[i];[](#l1.104)

```
       }[](#l1.105)
```

   /* Convert split table into new combined table.[](#l1.106)

    * We must incref keys; we can transfer values.[](#l1.107)

    * Note that values of split table is always dense.[](#l1.108)

```
    */[](#l1.109)
```

   for (Py_ssize_t i = 0; i < numentries; i++) {[](#l1.110)

       assert(oldvalues[i] != NULL);[](#l1.111)

       PyDictKeyEntry *ep = &oldentries[i];[](#l1.112)

       PyObject *key = ep->me_key;[](#l1.113)

```
       Py_INCREF(key);[](#l1.114)
```

       newentries[i].me_key = key;[](#l1.115)

       newentries[i].me_hash = ep->me_hash;[](#l1.116)

       newentries[i].me_value = oldvalues[i];[](#l1.117)
   }[](#l1.118)

}
/* Main loop */
for (i = 0; i < oldkeys->dk_nentries; i++) {

   PyDictKeyEntry *ep = &ep0[i];[](#l1.122)

   if (ep->me_value != NULL) {[](#l1.123)

       insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);[](#l1.124)

```
   }[](#l1.125)
```
}
mp->ma_keys->dk_usable -= mp->ma_used;
if (oldvalues != NULL) {

   /* NULL out me_value slot in oldkeys, in case it was shared */[](#l1.129)

   for (i = 0; i < oldkeys->dk_nentries; i++)[](#l1.130)

       ep0[i].me_value = NULL;[](#l1.131)

+ DK_DECREF(oldkeys);

   mp->ma_values = NULL;[](#l1.134)
   if (oldvalues != empty_values) {[](#l1.135)
       free_values(oldvalues);[](#l1.136)
   }[](#l1.137)

}

else {

else { // combined table.

   if (oldkeys->dk_nentries == numentries) {[](#l1.141)

       memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));[](#l1.142)

```
   }[](#l1.143)
```
```
   else {[](#l1.144)
```

       PyDictKeyEntry *ep = oldentries;[](#l1.145)

       for (Py_ssize_t i = 0; i < numentries; i++) {[](#l1.146)

           while (ep->me_value == NULL)[](#l1.147)

```
               ep++;[](#l1.148)
```

           newentries[i] = *ep++;[](#l1.149)

```
       }[](#l1.150)
```
```
   }[](#l1.151)
```

+ assert(oldkeys->dk_lookup != lookdict_split); assert(oldkeys->dk_refcnt == 1);

   DK_DEBUG_DECREF PyObject_FREE(oldkeys);[](#l1.155)

   if (oldkeys->dk_size == PyDict_MINSIZE &&[](#l1.156)

       numfreekeys < PyDict_MAXFREELIST) {[](#l1.157)

       DK_DEBUG_DECREF keys_free_list[numfreekeys++] = oldkeys;[](#l1.158)

```
   }[](#l1.159)
```
```
   else {[](#l1.160)
```

       DK_DEBUG_DECREF PyObject_FREE(oldkeys);[](#l1.161)

```
   }[](#l1.162)
```
} +
build_indices(mp->ma_keys, newentries, numentries);
mp->ma_keys->dk_usable -= numentries;
mp->ma_keys->dk_nentries = numentries; return 0; }