diff options
Diffstat (limited to 'Objects/dictobject.c')
| -rw-r--r-- | Objects/dictobject.c | 506 |
1 files changed, 241 insertions, 265 deletions
diff --git a/Objects/dictobject.c b/Objects/dictobject.c index a7b403bcec..43584b7bb2 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -10,8 +10,9 @@ This implements the dictionary's hashtable. -As of Python 3.6, this is compact and ordered. Basic idea is described here. -https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html +As of Python 3.6, this is compact and ordered. Basic idea is described here: +* https://mail.python.org/pipermail/python-dev/2012-December/123028.html +* https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html layout: @@ -222,17 +223,17 @@ equally good collision statistics, needed less code & used less memory. /* forward declarations */ static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos); static Py_ssize_t lookdict_unicode(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos); static Py_ssize_t lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos); static Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos); static int dictresize(PyDictObject *mp, Py_ssize_t minused); @@ -682,9 +683,9 @@ the <dummy> value. For both, when the key isn't found a DKIX_EMPTY is returned. hashpos returns where the key index should be inserted. */ -static Py_ssize_t +static Py_ssize_t _Py_HOT_FUNCTION lookdict(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, Py_ssize_t *hashpos) + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos) { size_t i, mask; Py_ssize_t ix, freeslot; @@ -713,7 +714,7 @@ top: ep = &ep0[ix]; assert(ep->me_key != NULL); if (ep->me_key == key) { - *value_addr = &ep->me_value; + *value_addr = ep->me_value; if (hashpos != NULL) *hashpos = i; return ix; @@ -729,7 +730,7 @@ top: } if (dk == mp->ma_keys && ep->me_key == startkey) { if (cmp > 0) { - *value_addr = &ep->me_value; + *value_addr = ep->me_value; if (hashpos != NULL) *hashpos = i; return ix; @@ -765,7 +766,7 @@ top: if (hashpos != NULL) { *hashpos = i; } - *value_addr = &ep->me_value; + *value_addr = ep->me_value; return ix; } if (ep->me_hash == hash) { @@ -782,7 +783,7 @@ top: if (hashpos != NULL) { *hashpos = i; } - *value_addr = &ep->me_value; + *value_addr = ep->me_value; return ix; } } @@ -797,9 +798,9 @@ top: } /* Specialized version for string-only keys */ -static Py_ssize_t +static Py_ssize_t _Py_HOT_FUNCTION lookdict_unicode(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, Py_ssize_t *hashpos) + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos) { size_t i; size_t mask = DK_MASK(mp->ma_keys); @@ -833,7 +834,7 @@ lookdict_unicode(PyDictObject *mp, PyObject *key, || (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { if (hashpos != NULL) *hashpos = i; - *value_addr = &ep->me_value; + *value_addr = ep->me_value; return ix; } freeslot = -1; @@ -859,7 +860,7 @@ lookdict_unicode(PyDictObject *mp, PyObject *key, assert(ep->me_key != NULL); if (ep->me_key == key || (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { - *value_addr = &ep->me_value; + *value_addr = ep->me_value; if (hashpos != NULL) { *hashpos = i; } @@ -872,9 +873,9 @@ lookdict_unicode(PyDictObject *mp, PyObject *key, /* Faster version of lookdict_unicode when it is known that no <dummy> keys * will be present. */ -static Py_ssize_t +static Py_ssize_t _Py_HOT_FUNCTION lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos) { size_t i; @@ -907,7 +908,7 @@ lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { if (hashpos != NULL) *hashpos = i; - *value_addr = &ep->me_value; + *value_addr = ep->me_value; return ix; } for (size_t perturb = hash;;) { @@ -927,7 +928,7 @@ lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { if (hashpos != NULL) *hashpos = i; - *value_addr = &ep->me_value; + *value_addr = ep->me_value; return ix; } } @@ -940,9 +941,9 @@ lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, * Split tables only contain unicode keys and no dummy keys, * so algorithm is the same as lookdict_unicode_nodummy. */ -static Py_ssize_t +static Py_ssize_t _Py_HOT_FUNCTION lookdict_split(PyDictObject *mp, PyObject *key, - Py_hash_t hash, PyObject ***value_addr, Py_ssize_t *hashpos) + Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos) { size_t i; size_t mask = DK_MASK(mp->ma_keys); @@ -954,7 +955,7 @@ lookdict_split(PyDictObject *mp, PyObject *key, if (!PyUnicode_CheckExact(key)) { ix = lookdict(mp, key, hash, value_addr, hashpos); if (ix >= 0) { - *value_addr = &mp->ma_values[ix]; + *value_addr = mp->ma_values[ix]; } return ix; } @@ -974,7 +975,7 @@ lookdict_split(PyDictObject *mp, PyObject *key, (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { if (hashpos != NULL) *hashpos = i; - *value_addr = &mp->ma_values[ix]; + *value_addr = mp->ma_values[ix]; return ix; } for (size_t perturb = hash;;) { @@ -994,7 +995,7 @@ lookdict_split(PyDictObject *mp, PyObject *key, (ep->me_hash == hash && unicode_eq(ep->me_key, key))) { if (hashpos != NULL) *hashpos = i; - *value_addr = &mp->ma_values[ix]; + *value_addr = mp->ma_values[ix]; return ix; } } @@ -1067,32 +1068,24 @@ _PyDict_MaybeUntrack(PyObject *op) when it is known that the key is not present in the dict. The dict must be combined. */ -static void -find_empty_slot(PyDictObject *mp, PyObject *key, Py_hash_t hash, - PyObject ***value_addr, Py_ssize_t *hashpos) +static Py_ssize_t +find_empty_slot(PyDictKeysObject *keys, PyObject *key, Py_hash_t hash) { size_t i; - size_t mask = DK_MASK(mp->ma_keys); + size_t mask = DK_MASK(keys); Py_ssize_t ix; - PyDictKeyEntry *ep, *ep0 = DK_ENTRIES(mp->ma_keys); - assert(!_PyDict_HasSplitTable(mp)); - assert(hashpos != NULL); assert(key != NULL); - if (!PyUnicode_CheckExact(key)) - mp->ma_keys->dk_lookup = lookdict; i = hash & mask; - ix = dk_get_index(mp->ma_keys, i); + ix = dk_get_index(keys, i); for (size_t perturb = hash; ix != DKIX_EMPTY;) { perturb >>= PERTURB_SHIFT; i = (i << 2) + i + perturb + 1; - ix = dk_get_index(mp->ma_keys, i & mask); + ix = dk_get_index(keys, i & mask); } - ep = &ep0[mp->ma_keys->dk_nentries]; - *hashpos = i & mask; - assert(ep->me_value == NULL); - *value_addr = &ep->me_value; + assert(DK_ENTRIES(keys)[keys->dk_nentries].me_value == NULL); + return i & mask; } static int @@ -1110,8 +1103,7 @@ static int insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) { PyObject *old_value; - PyObject **value_addr; - PyDictKeyEntry *ep, *ep0; + PyDictKeyEntry *ep; Py_ssize_t hashpos, ix; if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) { @@ -1119,7 +1111,7 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) return -1; } - ix = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr, &hashpos); + ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value, &hashpos); if (ix == DKIX_ERROR) { return -1; } @@ -1132,28 +1124,28 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) * the key anymore. Convert this instance to combine table. */ if (_PyDict_HasSplitTable(mp) && - ((ix >= 0 && *value_addr == NULL && mp->ma_used != ix) || + ((ix >= 0 && old_value == NULL && mp->ma_used != ix) || (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) { if (insertion_resize(mp) < 0) { Py_DECREF(value); return -1; } - find_empty_slot(mp, key, hash, &value_addr, &hashpos); + hashpos = find_empty_slot(mp->ma_keys, key, hash); ix = DKIX_EMPTY; } if (ix == DKIX_EMPTY) { /* Insert into new slot. */ + assert(old_value == NULL); if (mp->ma_keys->dk_usable <= 0) { /* Need to resize. */ if (insertion_resize(mp) < 0) { Py_DECREF(value); return -1; } - find_empty_slot(mp, key, hash, &value_addr, &hashpos); + hashpos = find_empty_slot(mp->ma_keys, key, hash); } - ep0 = DK_ENTRIES(mp->ma_keys); - ep = &ep0[mp->ma_keys->dk_nentries]; + ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries); Py_INCREF(key); ep->me_key = key; @@ -1174,64 +1166,41 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) return 0; } - assert(value_addr != NULL); - - old_value = *value_addr; - if (old_value != NULL) { - *value_addr = value; - mp->ma_version_tag = DICT_NEXT_VERSION(); - assert(_PyDict_CheckConsistency(mp)); - - Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */ - return 0; + if (_PyDict_HasSplitTable(mp)) { + mp->ma_values[ix] = value; + if (old_value == NULL) { + /* pending state */ + assert(ix == mp->ma_used); + mp->ma_used++; + } + } + else { + assert(old_value != NULL); + DK_ENTRIES(mp->ma_keys)[ix].me_value = value; } - /* pending state */ - assert(_PyDict_HasSplitTable(mp)); - assert(ix == mp->ma_used); - *value_addr = value; - mp->ma_used++; mp->ma_version_tag = DICT_NEXT_VERSION(); + Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */ assert(_PyDict_CheckConsistency(mp)); return 0; } /* -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) +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; - i = mask & ((i << 2) + i + perturb + 1); + 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; + size_t i = hash & mask; + for (size_t perturb = hash; dk_get_index(keys, i) != DKIX_EMPTY;) { + perturb >>= PERTURB_SHIFT; + i = mask & ((i << 2) + i + perturb + 1); + } + dk_set_index(keys, i, ix); } - 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; } /* @@ -1247,10 +1216,10 @@ but can be resplit by make_keys_shared(). static int dictresize(PyDictObject *mp, Py_ssize_t minsize) { - 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; @@ -1261,8 +1230,14 @@ dictresize(PyDictObject *mp, Py_ssize_t minsize) 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. + * TODO: Try reusing oldkeys when reimplement odict. + */ + /* Allocate a new table. */ mp->ma_keys = new_keys_object(newsize); if (mp->ma_keys == NULL) { @@ -1273,42 +1248,59 @@ dictresize(PyDictObject *mp, Py_ssize_t minsize) assert(mp->ma_keys->dk_usable >= mp->ma_used); 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. - * Increment ref-counts and copy values here to compensate - * This (resizing a split table) should be relatively rare */ + + 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++) { - if (oldvalues[i] != NULL) { - Py_INCREF(ep0[i].me_key); - ep0[i].me_value = oldvalues[i]; - } - } - } - /* Main loop */ - for (i = 0; i < oldkeys->dk_nentries; i++) { - PyDictKeyEntry *ep = &ep0[i]; - if (ep->me_value != NULL) { - insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value); + /* Convert split table into new combined table. + * We must incref keys; we can transfer values. + * Note that values of split table is always dense. + */ + for (Py_ssize_t i = 0; i < numentries; i++) { + assert(oldvalues[i] != NULL); + PyDictKeyEntry *ep = &oldentries[i]; + PyObject *key = ep->me_key; + Py_INCREF(key); + newentries[i].me_key = key; + newentries[i].me_hash = ep->me_hash; + newentries[i].me_value = oldvalues[i]; } - } - mp->ma_keys->dk_usable -= mp->ma_used; - if (oldvalues != NULL) { - /* NULL out me_value slot in oldkeys, in case it was shared */ - for (i = 0; i < oldkeys->dk_nentries; i++) - ep0[i].me_value = NULL; + DK_DECREF(oldkeys); + mp->ma_values = NULL; if (oldvalues != empty_values) { free_values(oldvalues); } } - else { + else { // combined table. + if (oldkeys->dk_nentries == numentries) { + memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry)); + } + else { + PyDictKeyEntry *ep = oldentries; + for (Py_ssize_t i = 0; i < numentries; i++) { + while (ep->me_value == NULL) + ep++; + newentries[i] = *ep++; + } + } + assert(oldkeys->dk_lookup != lookdict_split); assert(oldkeys->dk_refcnt == 1); - DK_DEBUG_DECREF PyObject_FREE(oldkeys); + if (oldkeys->dk_size == PyDict_MINSIZE && + numfreekeys < PyDict_MAXFREELIST) { + DK_DEBUG_DECREF keys_free_list[numfreekeys++] = oldkeys; + } + else { + DK_DEBUG_DECREF PyObject_FREE(oldkeys); + } } + + build_indices(mp->ma_keys, newentries, numentries); + mp->ma_keys->dk_usable -= numentries; + mp->ma_keys->dk_nentries = numentries; return 0; } @@ -1402,7 +1394,7 @@ PyDict_GetItem(PyObject *op, PyObject *key) Py_ssize_t ix; PyDictObject *mp = (PyDictObject *)op; PyThreadState *tstate; - PyObject **value_addr; + PyObject *value; if (!PyDict_Check(op)) return NULL; @@ -1421,25 +1413,25 @@ PyDict_GetItem(PyObject *op, PyObject *key) Let's just hope that no exception occurs then... This must be _PyThreadState_Current and not PyThreadState_GET() because in debug mode, the latter complains if tstate is NULL. */ - tstate = _PyThreadState_UncheckedGet(); + tstate = PyThreadState_GET(); if (tstate != NULL && tstate->curexc_type != NULL) { /* preserve the existing exception */ PyObject *err_type, *err_value, *err_tb; PyErr_Fetch(&err_type, &err_value, &err_tb); - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); /* ignore errors */ PyErr_Restore(err_type, err_value, err_tb); if (ix < 0) return NULL; } else { - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix < 0) { PyErr_Clear(); return NULL; } } - return *value_addr; + return value; } /* Same as PyDict_GetItemWithError() but with hash supplied by caller. @@ -1451,18 +1443,18 @@ _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) { Py_ssize_t ix; PyDictObject *mp = (PyDictObject *)op; - PyObject **value_addr; + PyObject *value; if (!PyDict_Check(op)) { PyErr_BadInternalCall(); return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix < 0) { return NULL; } - return *value_addr; + return value; } /* Variant of PyDict_GetItem() that doesn't suppress exceptions. @@ -1475,7 +1467,7 @@ PyDict_GetItemWithError(PyObject *op, PyObject *key) Py_ssize_t ix; Py_hash_t hash; PyDictObject*mp = (PyDictObject *)op; - PyObject **value_addr; + PyObject *value; if (!PyDict_Check(op)) { PyErr_BadInternalCall(); @@ -1490,10 +1482,10 @@ PyDict_GetItemWithError(PyObject *op, PyObject *key) } } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix < 0) return NULL; - return *value_addr; + return value; } PyObject * @@ -1518,7 +1510,7 @@ _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key) { Py_ssize_t ix; Py_hash_t hash; - PyObject **value_addr; + PyObject *value; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) @@ -1529,17 +1521,17 @@ _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key) } /* namespace 1: globals */ - ix = globals->ma_keys->dk_lookup(globals, key, hash, &value_addr, NULL); + ix = globals->ma_keys->dk_lookup(globals, key, hash, &value, NULL); if (ix == DKIX_ERROR) return NULL; - if (ix != DKIX_EMPTY && *value_addr != NULL) - return *value_addr; + if (ix != DKIX_EMPTY && value != NULL) + return value; /* namespace 2: builtins */ - ix = builtins->ma_keys->dk_lookup(builtins, key, hash, &value_addr, NULL); + ix = builtins->ma_keys->dk_lookup(builtins, key, hash, &value, NULL); if (ix < 0) return NULL; - return *value_addr; + return value; } /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the @@ -1593,14 +1585,11 @@ _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value, static int delitem_common(PyDictObject *mp, Py_ssize_t hashpos, Py_ssize_t ix, - PyObject **value_addr) + PyObject *old_value) { - PyObject *old_key, *old_value; + PyObject *old_key; PyDictKeyEntry *ep; - old_value = *value_addr; - assert(old_value != NULL); - *value_addr = NULL; mp->ma_used--; mp->ma_version_tag = DICT_NEXT_VERSION(); ep = &DK_ENTRIES(mp->ma_keys)[ix]; @@ -1608,6 +1597,7 @@ delitem_common(PyDictObject *mp, Py_ssize_t hashpos, Py_ssize_t ix, ENSURE_ALLOWS_DELETIONS(mp); old_key = ep->me_key; ep->me_key = NULL; + ep->me_value = NULL; Py_DECREF(old_key); Py_DECREF(old_value); @@ -1635,7 +1625,7 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) { Py_ssize_t hashpos, ix; PyDictObject *mp; - PyObject **value_addr; + PyObject *old_value; if (!PyDict_Check(op)) { PyErr_BadInternalCall(); @@ -1644,10 +1634,10 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) assert(key); assert(hash != -1); mp = (PyDictObject *)op; - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); if (ix == DKIX_ERROR) return -1; - if (ix == DKIX_EMPTY || *value_addr == NULL) { + if (ix == DKIX_EMPTY || old_value == NULL) { _PyErr_SetKeyError(key); return -1; } @@ -1658,10 +1648,11 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) if (dictresize(mp, DK_SIZE(mp->ma_keys))) { return -1; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); assert(ix >= 0); } - return delitem_common(mp, hashpos, ix, value_addr); + + return delitem_common(mp, hashpos, ix, old_value); } /* This function promises that the predicate -> deletion sequence is atomic @@ -1675,7 +1666,7 @@ _PyDict_DelItemIf(PyObject *op, PyObject *key, Py_ssize_t hashpos, ix; PyDictObject *mp; Py_hash_t hash; - PyObject **value_addr; + PyObject *old_value; int res; if (!PyDict_Check(op)) { @@ -1687,10 +1678,10 @@ _PyDict_DelItemIf(PyObject *op, PyObject *key, if (hash == -1) return -1; mp = (PyDictObject *)op; - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); if (ix == DKIX_ERROR) return -1; - if (ix == DKIX_EMPTY || *value_addr == NULL) { + if (ix == DKIX_EMPTY || old_value == NULL) { _PyErr_SetKeyError(key); return -1; } @@ -1701,15 +1692,15 @@ _PyDict_DelItemIf(PyObject *op, PyObject *key, if (dictresize(mp, DK_SIZE(mp->ma_keys))) { return -1; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); assert(ix >= 0); } - res = predicate(*value_addr); + res = predicate(old_value); if (res == -1) return -1; if (res > 0) - return delitem_common(mp, hashpos, ix, value_addr); + return delitem_common(mp, hashpos, ix, old_value); else return 0; } @@ -1760,7 +1751,7 @@ int _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, Py_hash_t *phash) { - Py_ssize_t i, n; + Py_ssize_t i; PyDictObject *mp; PyDictKeyEntry *entry_ptr; PyObject *value; @@ -1769,21 +1760,18 @@ _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, return 0; mp = (PyDictObject *)op; i = *ppos; - n = mp->ma_keys->dk_nentries; - if ((size_t)i >= (size_t)n) - return 0; if (mp->ma_values) { - PyObject **value_ptr = &mp->ma_values[i]; - while (i < n && *value_ptr == NULL) { - value_ptr++; - i++; - } - if (i >= n) + if (i < 0 || i >= mp->ma_used) return 0; + /* values of split table is always dense */ entry_ptr = &DK_ENTRIES(mp->ma_keys)[i]; - value = *value_ptr; + value = mp->ma_values[i]; + assert(value != NULL); } else { + Py_ssize_t n = mp->ma_keys->dk_nentries; + if (i < 0 || i >= n) + return 0; entry_ptr = &DK_ENTRIES(mp->ma_keys)[i]; while (i < n && entry_ptr->me_value == NULL) { entry_ptr++; @@ -1834,7 +1822,6 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d Py_ssize_t ix, hashpos; PyObject *old_value, *old_key; PyDictKeyEntry *ep; - PyObject **value_addr; PyDictObject *mp; assert(PyDict_Check(dict)); @@ -1848,10 +1835,10 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d _PyErr_SetKeyError(key); return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); if (ix == DKIX_ERROR) return NULL; - if (ix == DKIX_EMPTY || *value_addr == NULL) { + if (ix == DKIX_EMPTY || old_value == NULL) { if (deflt) { Py_INCREF(deflt); return deflt; @@ -1865,13 +1852,11 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d if (dictresize(mp, DK_SIZE(mp->ma_keys))) { return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos); assert(ix >= 0); } - old_value = *value_addr; assert(old_value != NULL); - *value_addr = NULL; mp->ma_used--; mp->ma_version_tag = DICT_NEXT_VERSION(); dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY); @@ -1879,6 +1864,7 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d ENSURE_ALLOWS_DELETIONS(mp); old_key = ep->me_key; ep->me_key = NULL; + ep->me_value = NULL; Py_DECREF(old_key); assert(_PyDict_CheckConsistency(mp)); @@ -1916,7 +1902,7 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) PyObject *d; int status; - d = PyObject_CallObject(cls, NULL); + d = _PyObject_CallNoArg(cls); if (d == NULL) return NULL; @@ -2118,10 +2104,9 @@ dict_length(PyDictObject *mp) static PyObject * dict_subscript(PyDictObject *mp, PyObject *key) { - PyObject *v; Py_ssize_t ix; Py_hash_t hash; - PyObject **value_addr; + PyObject *value; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -2129,10 +2114,10 @@ dict_subscript(PyDictObject *mp, PyObject *key) if (hash == -1) return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix == DKIX_ERROR) return NULL; - if (ix == DKIX_EMPTY || *value_addr == NULL) { + if (ix == DKIX_EMPTY || value == NULL) { if (!PyDict_CheckExact(mp)) { /* Look up __missing__ method if we're a subclass. */ PyObject *missing, *res; @@ -2150,9 +2135,8 @@ dict_subscript(PyDictObject *mp, PyObject *key) _PyErr_SetKeyError(key); return NULL; } - v = *value_addr; - Py_INCREF(v); - return v; + Py_INCREF(value); + return value; } static int @@ -2327,12 +2311,12 @@ dict.fromkeys value: object=None / -Returns a new dict with keys from iterable and values equal to value. +Create a new dictionary with keys from iterable and values set to value. [clinic start generated code]*/ static PyObject * dict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value) -/*[clinic end generated code: output=8fb98e4b10384999 input=b85a667f9bf4669d]*/ +/*[clinic end generated code: output=8fb98e4b10384999 input=382ba4855d0f74c3]*/ { return _PyDict_FromKeys((PyObject *)type, iterable, value); } @@ -2363,6 +2347,9 @@ dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, return result; } +/* Note: dict.update() uses the METH_VARARGS|METH_KEYWORDS calling convention. + Using METH_FASTCALL would make dict.update(**dict2) calls slower, see the + issue #29312. */ static PyObject * dict_update(PyObject *self, PyObject *args, PyObject *kwds) { @@ -2724,7 +2711,6 @@ dict_equal(PyDictObject *a, PyDictObject *b) if (aval != NULL) { int cmp; PyObject *bval; - PyObject **vaddr; PyObject *key = ep->me_key; /* temporarily bump aval's refcount to ensure it stays alive until we're done with it */ @@ -2732,10 +2718,7 @@ dict_equal(PyDictObject *a, PyDictObject *b) /* ditto for key */ Py_INCREF(key); /* reuse the known hash value */ - if ((b->ma_keys->dk_lookup)(b, key, ep->me_hash, &vaddr, NULL) < 0) - bval = NULL; - else - bval = *vaddr; + b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval, NULL); Py_DECREF(key); if (bval == NULL) { Py_DECREF(aval); @@ -2781,17 +2764,17 @@ dict.__contains__ key: object / -True if D has a key k, else False. +True if the dictionary has the specified key, else False. [clinic start generated code]*/ static PyObject * dict___contains__(PyDictObject *self, PyObject *key) -/*[clinic end generated code: output=a3d03db709ed6e6b input=b852b2a19b51ab24]*/ +/*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/ { register PyDictObject *mp = self; Py_hash_t hash; Py_ssize_t ix; - PyObject **value_addr; + PyObject *value; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -2799,26 +2782,31 @@ dict___contains__(PyDictObject *self, PyObject *key) if (hash == -1) return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix == DKIX_ERROR) return NULL; - if (ix == DKIX_EMPTY || *value_addr == NULL) + if (ix == DKIX_EMPTY || value == NULL) Py_RETURN_FALSE; Py_RETURN_TRUE; } +/*[clinic input] +dict.get + + key: object + default: object = None + / + +Return the value for key if key is in the dictionary, else default. +[clinic start generated code]*/ + static PyObject * -dict_get(PyDictObject *mp, PyObject *args) +dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value) +/*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/ { - PyObject *key; - PyObject *failobj = Py_None; PyObject *val = NULL; Py_hash_t hash; Py_ssize_t ix; - PyObject **value_addr; - - if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj)) - return NULL; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -2826,13 +2814,12 @@ dict_get(PyDictObject *mp, PyObject *args) if (hash == -1) return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (self->ma_keys->dk_lookup) (self, key, hash, &val, NULL); if (ix == DKIX_ERROR) return NULL; - if (ix == DKIX_EMPTY || *value_addr == NULL) - val = failobj; - else - val = *value_addr; + if (ix == DKIX_EMPTY || val == NULL) { + val = default_value; + } Py_INCREF(val); return val; } @@ -2844,7 +2831,6 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) PyObject *value; Py_hash_t hash; Py_ssize_t hashpos, ix; - PyObject **value_addr; if (!PyDict_Check(d)) { PyErr_BadInternalCall(); @@ -2863,17 +2849,17 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) return NULL; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, &hashpos); if (ix == DKIX_ERROR) return NULL; if (_PyDict_HasSplitTable(mp) && - ((ix >= 0 && *value_addr == NULL && mp->ma_used != ix) || + ((ix >= 0 && value == NULL && mp->ma_used != ix) || (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) { if (insertion_resize(mp) < 0) { return NULL; } - find_empty_slot(mp, key, hash, &value_addr, &hashpos); + hashpos = find_empty_slot(mp->ma_keys, key, hash); ix = DKIX_EMPTY; } @@ -2884,7 +2870,7 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) if (insertion_resize(mp) < 0) { return NULL; } - find_empty_slot(mp, key, hash, &value_addr, &hashpos); + hashpos = find_empty_slot(mp->ma_keys, key, hash); } ep0 = DK_ENTRIES(mp->ma_keys); ep = &ep0[mp->ma_keys->dk_nentries]; @@ -2894,7 +2880,7 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) MAINTAIN_TRACKING(mp, key, value); ep->me_key = key; ep->me_hash = hash; - if (mp->ma_values) { + if (_PyDict_HasSplitTable(mp)) { assert(mp->ma_values[mp->ma_keys->dk_nentries] == NULL); mp->ma_values[mp->ma_keys->dk_nentries] = value; } @@ -2907,34 +2893,41 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) mp->ma_keys->dk_nentries++; assert(mp->ma_keys->dk_usable >= 0); } - else if (*value_addr == NULL) { + else if (value == NULL) { value = defaultobj; assert(_PyDict_HasSplitTable(mp)); assert(ix == mp->ma_used); Py_INCREF(value); MAINTAIN_TRACKING(mp, key, value); - *value_addr = value; + mp->ma_values[ix] = value; mp->ma_used++; mp->ma_version_tag = DICT_NEXT_VERSION(); } - else { - value = *value_addr; - } assert(_PyDict_CheckConsistency(mp)); return value; } +/*[clinic input] +dict.setdefault + + key: object + default: object = None + / + +Insert key with a value of default if key is not in the dictionary. + +Return the value for key if key is in the dictionary, else default. +[clinic start generated code]*/ + static PyObject * -dict_setdefault(PyDictObject *mp, PyObject *args) +dict_setdefault_impl(PyDictObject *self, PyObject *key, + PyObject *default_value) +/*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/ { - PyObject *key, *val; - PyObject *defaultobj = Py_None; + PyObject *val; - if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &defaultobj)) - return NULL; - - val = PyDict_SetDefault((PyObject *)mp, key, defaultobj); + val = PyDict_SetDefault((PyObject *)self, key, default_value); Py_XINCREF(val); return val; } @@ -3098,12 +3091,6 @@ PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]"); PyDoc_STRVAR(sizeof__doc__, "D.__sizeof__() -> size of D in memory, in bytes"); -PyDoc_STRVAR(get__doc__, -"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None."); - -PyDoc_STRVAR(setdefault_doc__, -"D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D"); - PyDoc_STRVAR(pop__doc__, "D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\ If key is not found, d is returned if given, otherwise KeyError is raised"); @@ -3142,10 +3129,8 @@ static PyMethodDef mapp_methods[] = { getitem__doc__}, {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS, sizeof__doc__}, - {"get", (PyCFunction)dict_get, METH_VARARGS, - get__doc__}, - {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS, - setdefault_doc__}, + DICT_GET_METHODDEF + DICT_SETDEFAULT_METHODDEF {"pop", (PyCFunction)dict_pop, METH_VARARGS, pop__doc__}, {"popitem", (PyCFunction)dict_popitem, METH_NOARGS, @@ -3173,7 +3158,7 @@ PyDict_Contains(PyObject *op, PyObject *key) Py_hash_t hash; Py_ssize_t ix; PyDictObject *mp = (PyDictObject *)op; - PyObject **value_addr; + PyObject *value; if (!PyUnicode_CheckExact(key) || (hash = ((PyASCIIObject *) key)->hash) == -1) { @@ -3181,10 +3166,10 @@ PyDict_Contains(PyObject *op, PyObject *key) if (hash == -1) return -1; } - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix == DKIX_ERROR) return -1; - return (ix != DKIX_EMPTY && *value_addr != NULL); + return (ix != DKIX_EMPTY && value != NULL); } /* Internal version of PyDict_Contains used when the hash value is already known */ @@ -3192,13 +3177,13 @@ int _PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash) { PyDictObject *mp = (PyDictObject *)op; - PyObject **value_addr; + PyObject *value; Py_ssize_t ix; - ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); + ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL); if (ix == DKIX_ERROR) return -1; - return (ix != DKIX_EMPTY && *value_addr != NULL); + return (ix != DKIX_EMPTY && value != NULL); } /* Hack to implement "key in dict" */ @@ -3463,7 +3448,7 @@ static PyObject* dictiter_iternextkey(dictiterobject *di) { PyObject *key; - Py_ssize_t i, n; + Py_ssize_t i; PyDictKeysObject *k; PyDictObject *d = di->di_dict; @@ -3480,18 +3465,15 @@ dictiter_iternextkey(dictiterobject *di) i = di->di_pos; k = d->ma_keys; - n = k->dk_nentries; + assert(i >= 0); if (d->ma_values) { - PyObject **value_ptr = &d->ma_values[i]; - while (i < n && *value_ptr == NULL) { - value_ptr++; - i++; - } - if (i >= n) + if (i >= d->ma_used) goto fail; key = DK_ENTRIES(k)[i].me_key; + assert(d->ma_values[i] != NULL); } else { + Py_ssize_t n = k->dk_nentries; PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i]; while (i < n && entry_ptr->me_value == NULL) { entry_ptr++; @@ -3549,7 +3531,7 @@ static PyObject * dictiter_iternextvalue(dictiterobject *di) { PyObject *value; - Py_ssize_t i, n; + Py_ssize_t i; PyDictObject *d = di->di_dict; if (d == NULL) @@ -3564,18 +3546,15 @@ dictiter_iternextvalue(dictiterobject *di) } i = di->di_pos; - n = d->ma_keys->dk_nentries; + assert(i >= 0); if (d->ma_values) { - PyObject **value_ptr = &d->ma_values[i]; - while (i < n && *value_ptr == NULL) { - value_ptr++; - i++; - } - if (i >= n) + if (i >= d->ma_used) goto fail; - value = *value_ptr; + value = d->ma_values[i]; + assert(value != NULL); } else { + Py_ssize_t n = d->ma_keys->dk_nentries; PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i]; while (i < n && entry_ptr->me_value == NULL) { entry_ptr++; @@ -3633,7 +3612,7 @@ static PyObject * dictiter_iternextitem(dictiterobject *di) { PyObject *key, *value, *result = di->di_result; - Py_ssize_t i, n; + Py_ssize_t i; PyDictObject *d = di->di_dict; if (d == NULL) @@ -3648,19 +3627,16 @@ dictiter_iternextitem(dictiterobject *di) } i = di->di_pos; - n = d->ma_keys->dk_nentries; + assert(i >= 0); if (d->ma_values) { - PyObject **value_ptr = &d->ma_values[i]; - while (i < n && *value_ptr == NULL) { - value_ptr++; - i++; - } - if (i >= n) + if (i >= d->ma_used) goto fail; key = DK_ENTRIES(d->ma_keys)[i].me_key; - value = *value_ptr; + value = d->ma_values[i]; + assert(value != NULL); } else { + Py_ssize_t n = d->ma_keys->dk_nentries; PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i]; while (i < n && entry_ptr->me_value == NULL) { entry_ptr++; |