[Python-checkins] bpo-44206: Add a version number to dictionary keys (GH-26333)
markshannon
webhook-mailer at python.org
Fri May 28 04:54:26 EDT 2021
https://github.com/python/cpython/commit/f8a95df84bcedebc0aa7132b3d1a4e8f000914bc
commit: f8a95df84bcedebc0aa7132b3d1a4e8f000914bc
branch: main
author: Mark Shannon <mark at hotpy.org>
committer: markshannon <mark at hotpy.org>
date: 2021-05-28T09:54:10+01:00
summary:
bpo-44206: Add a version number to dictionary keys (GH-26333)
* Store log2(size) instead of size in dict-keys.
* Use enum instead of function pointer to record kind of keys.
* Add version number to dict keys.
files:
M Include/cpython/dictobject.h
M Lib/test/test_ordered_dict.py
M Lib/test/test_sys.py
M Objects/dict-common.h
M Objects/dictobject.c
M Objects/odictobject.c
M Tools/gdb/libpython.py
diff --git a/Include/cpython/dictobject.h b/Include/cpython/dictobject.h
index 6822a65cad95e8..de3c1160b489ce 100644
--- a/Include/cpython/dictobject.h
+++ b/Include/cpython/dictobject.h
@@ -82,3 +82,7 @@ typedef struct {
PyAPI_FUNC(PyObject *) _PyDictView_New(PyObject *, PyTypeObject *);
PyAPI_FUNC(PyObject *) _PyDictView_Intersect(PyObject* self, PyObject *other);
+
+/* Gets a version number unique to the current state of the keys of dict, if possible.
+ * Returns the version number, or zero if it was not possible to get a version number. */
+uint32_t _PyDictKeys_GetVersionForCurrentState(PyDictObject *dict);
diff --git a/Lib/test/test_ordered_dict.py b/Lib/test/test_ordered_dict.py
index eb404463e92550..d48edb5881a14d 100644
--- a/Lib/test/test_ordered_dict.py
+++ b/Lib/test/test_ordered_dict.py
@@ -752,7 +752,7 @@ def test_sizeof_exact(self):
check = self.check_sizeof
basicsize = size('nQ2P' + '3PnPn2P')
- keysize = calcsize('2nP2n')
+ keysize = calcsize('n2BI2n')
entrysize = calcsize('n2P')
p = calcsize('P')
diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py
index 6574c4f9b70273..40fb721f3fa595 100644
--- a/Lib/test/test_sys.py
+++ b/Lib/test/test_sys.py
@@ -22,6 +22,7 @@
# strings to intern in test_intern()
INTERN_NUMRUNS = 0
+DICT_KEY_STRUCT_FORMAT = 'n2BI2n'
class DisplayHookTest(unittest.TestCase):
@@ -1229,9 +1230,9 @@ def inner():
# empty dict
check({}, size('nQ2P'))
# dict
- check({"a": 1}, size('nQ2P') + calcsize('2nP2n') + 8 + (8*2//3)*calcsize('n2P'))
+ check({"a": 1}, size('nQ2P') + calcsize(DICT_KEY_STRUCT_FORMAT) + 8 + (8*2//3)*calcsize('n2P'))
longdict = {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7, 8:8}
- check(longdict, size('nQ2P') + calcsize('2nP2n') + 16 + (16*2//3)*calcsize('n2P'))
+ check(longdict, size('nQ2P') + calcsize(DICT_KEY_STRUCT_FORMAT) + 16 + (16*2//3)*calcsize('n2P'))
# dictionary-keyview
check({}.keys(), size('P'))
# dictionary-valueview
@@ -1385,13 +1386,13 @@ def delx(self): del self.__x
'5P')
class newstyleclass(object): pass
# Separate block for PyDictKeysObject with 8 keys and 5 entries
- check(newstyleclass, s + calcsize("2nP2n0P") + 8 + 5*calcsize("n2P"))
+ check(newstyleclass, s + calcsize(DICT_KEY_STRUCT_FORMAT) + 8 + 5*calcsize("n2P"))
# dict with shared keys
check(newstyleclass().__dict__, size('nQ2P') + 5*self.P)
o = newstyleclass()
o.a = o.b = o.c = o.d = o.e = o.f = o.g = o.h = 1
# Separate block for PyDictKeysObject with 16 keys and 10 entries
- check(newstyleclass, s + calcsize("2nP2n0P") + 16 + 10*calcsize("n2P"))
+ check(newstyleclass, s + calcsize(DICT_KEY_STRUCT_FORMAT) + 16 + 10*calcsize("n2P"))
# dict with shared keys
check(newstyleclass().__dict__, size('nQ2P') + 10*self.P)
# unicode
diff --git a/Objects/dict-common.h b/Objects/dict-common.h
index 71d6b0274420b8..a6f518f301885a 100644
--- a/Objects/dict-common.h
+++ b/Objects/dict-common.h
@@ -8,37 +8,34 @@ typedef struct {
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
-/* dict_lookup_func() returns index of entry which can be used like DK_ENTRIES(dk)[index].
+/* _Py_dict_lookup() returns index of entry which can be used like DK_ENTRIES(dk)[index].
* -1 when no entry found, -3 when compare raises error.
*/
-typedef Py_ssize_t (*dict_lookup_func)
- (PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
+Py_ssize_t _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
+
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) /* Used internally */
#define DKIX_ERROR (-3)
+typedef enum {
+ DICT_KEYS_GENERAL = 0,
+ DICT_KEYS_UNICODE = 1,
+ DICT_KEYS_SPLIT = 2
+} DictKeysKind;
+
/* See dictobject.c for actual layout of DictKeysObject */
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
/* Size of the hash table (dk_indices). It must be a power of 2. */
- Py_ssize_t dk_size;
-
- /* Function to lookup in the hash table (dk_indices):
-
- - lookdict(): general-purpose, and may return DKIX_ERROR if (and
- only if) a comparison raises an exception.
-
- - lookdict_unicode(): specialized to Unicode string keys, comparison of
- which can never raise an exception; that function can never return
- DKIX_ERROR.
+ uint8_t dk_log2_size;
- - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
- specialized for Unicode string keys that cannot be the <dummy> value.
+ /* Kind of keys */
+ uint8_t dk_kind;
- - lookdict_split(): Version of lookdict() for split tables. */
- dict_lookup_func dk_lookup;
+ /* Version number -- Reset to 0 by any modification to keys */
+ uint32_t dk_version;
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable;
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 24973c07b1d488..47b69c8f286c54 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -18,8 +18,8 @@ As of Python 3.6, this is compact and ordered. Basic idea is described here:
+---------------+
| dk_refcnt |
-| dk_size |
-| dk_lookup |
+| dk_log2_size |
+| dk_kind |
| dk_usable |
| dk_nentries |
+---------------+
@@ -108,6 +108,7 @@ converting the dict to the combined table.
* Making this 8, rather than 4 reduces the number of resizes for most
* dictionaries, without any significant extra memory use.
*/
+#define PyDict_LOG_MINSIZE 3
#define PyDict_MINSIZE 8
#include "Python.h"
@@ -226,18 +227,7 @@ 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);
-static Py_ssize_t lookdict_unicode(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr);
-static Py_ssize_t
-lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr);
-static Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr);
-
-static int dictresize(PyDictObject *mp, Py_ssize_t newsize);
+static int dictresize(PyDictObject *mp, uint8_t log_newsize);
static PyObject* dict_iter(PyDictObject *dict);
@@ -295,24 +285,25 @@ _PyDict_DebugMallocStats(FILE *out)
state->numfree, sizeof(PyDictObject));
}
-
-#define DK_SIZE(dk) ((dk)->dk_size)
+#define DK_LOG_SIZE(dk) ((dk)->dk_log2_size)
#if SIZEOF_VOID_P > 4
-#define DK_IXSIZE(dk) \
- (DK_SIZE(dk) <= 0xff ? \
- 1 : DK_SIZE(dk) <= 0xffff ? \
- 2 : DK_SIZE(dk) <= 0xffffffff ? \
+#define DK_SIZE(dk) (((int64_t)1)<<DK_LOG_SIZE(dk))
+#define DK_IXSIZE(dk) \
+ (DK_LOG_SIZE(dk) <= 7 ? \
+ 1 : DK_LOG_SIZE(dk) <= 15 ? \
+ 2 : DK_LOG_SIZE(dk) <= 31 ? \
4 : sizeof(int64_t))
#else
-#define DK_IXSIZE(dk) \
- (DK_SIZE(dk) <= 0xff ? \
- 1 : DK_SIZE(dk) <= 0xffff ? \
+#define DK_SIZE(dk) (1<<DK_LOG_SIZE(dk))
+#define DK_IXSIZE(dk) \
+ (DK_LOG_SIZE(dk) <= 7 ? \
+ 1 : DK_LOG_SIZE(dk) <= 15 ? \
2 : sizeof(int32_t))
#endif
#define DK_ENTRIES(dk) \
((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))
-#define DK_MASK(dk) (((dk)->dk_size)-1)
+#define DK_MASK(dk) (DK_SIZE(dk)-1)
#define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
static void free_keys_object(PyDictKeysObject *keys);
@@ -374,6 +365,7 @@ dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
Py_ssize_t s = DK_SIZE(keys);
assert(ix >= DKIX_DUMMY);
+ assert(keys->dk_version == 0);
if (s <= 0xff) {
int8_t *indices = (int8_t*)(keys->dk_indices);
@@ -413,25 +405,25 @@ dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
#define USABLE_FRACTION(n) (((n) << 1)/3)
/* Find the smallest dk_size >= minsize. */
-static inline Py_ssize_t
-calculate_keysize(Py_ssize_t minsize)
+static inline uint8_t
+calculate_log2_keysize(Py_ssize_t minsize)
{
#if SIZEOF_LONG == SIZEOF_SIZE_T
minsize = (minsize | PyDict_MINSIZE) - 1;
- return 1LL << _Py_bit_length(minsize | (PyDict_MINSIZE-1));
+ return _Py_bit_length(minsize | (PyDict_MINSIZE-1));
#elif defined(_MSC_VER)
// On 64bit Windows, sizeof(long) == 4.
minsize = (minsize | PyDict_MINSIZE) - 1;
unsigned long msb;
_BitScanReverse64(&msb, (uint64_t)minsize);
- return 1LL << (msb + 1);
+ return msb + 1;
#else
- Py_ssize_t size;
- for (size = PyDict_MINSIZE;
- size < minsize && size > 0;
- size <<= 1)
+ uint8_t log2_size;
+ for (log2_size = PyDict_LOG_MINSIZE;
+ (((Py_ssize_t)1) << log2_size) < minsize;
+ log2_size++)
;
- return size;
+ return log2_size;
#endif
}
@@ -440,10 +432,10 @@ calculate_keysize(Py_ssize_t minsize)
* This can be used to reserve enough size to insert n entries without
* resizing.
*/
-static inline Py_ssize_t
-estimate_keysize(Py_ssize_t n)
+static inline uint8_t
+estimate_log2_keysize(Py_ssize_t n)
{
- return calculate_keysize((n*3 + 1) / 2);
+ return calculate_log2_keysize((n*3 + 1) / 2);
}
@@ -459,18 +451,14 @@ estimate_keysize(Py_ssize_t n)
*/
#define GROWTH_RATE(d) ((d)->ma_used*3)
-#define ENSURE_ALLOWS_DELETIONS(d) \
- if ((d)->ma_keys->dk_lookup == lookdict_unicode_nodummy) { \
- (d)->ma_keys->dk_lookup = lookdict_unicode; \
- }
-
/* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
* (which cannot fail and thus can do no allocation).
*/
static PyDictKeysObject empty_keys_struct = {
1, /* dk_refcnt */
- 1, /* dk_size */
- lookdict_split, /* dk_lookup */
+ 0, /* dk_log2_size */
+ DICT_KEYS_SPLIT, /* dk_kind */
+ 1, /* dk_version */
0, /* dk_usable (immutable) */
0, /* dk_nentries */
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
@@ -503,10 +491,9 @@ _PyDict_CheckConsistency(PyObject *op, int check_content)
PyDictKeysObject *keys = mp->ma_keys;
int splitted = _PyDict_HasSplitTable(mp);
- Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
+ Py_ssize_t usable = USABLE_FRACTION(DK_SIZE(keys));
CHECK(0 <= mp->ma_used && mp->ma_used <= usable);
- CHECK(IS_POWER_OF_2(keys->dk_size));
CHECK(0 <= keys->dk_usable && keys->dk_usable <= usable);
CHECK(0 <= keys->dk_nentries && keys->dk_nentries <= usable);
CHECK(keys->dk_usable + keys->dk_nentries <= usable);
@@ -520,7 +507,7 @@ _PyDict_CheckConsistency(PyObject *op, int check_content)
PyDictKeyEntry *entries = DK_ENTRIES(keys);
Py_ssize_t i;
- for (i=0; i < keys->dk_size; i++) {
+ for (i=0; i < DK_SIZE(keys); i++) {
Py_ssize_t ix = dictkeys_get_index(keys, i);
CHECK(DKIX_DUMMY <= ix && ix <= usable);
}
@@ -563,23 +550,22 @@ _PyDict_CheckConsistency(PyObject *op, int check_content)
static PyDictKeysObject*
-new_keys_object(Py_ssize_t size)
+new_keys_object(uint8_t log2_size)
{
PyDictKeysObject *dk;
Py_ssize_t es, usable;
- assert(size >= PyDict_MINSIZE);
- assert(IS_POWER_OF_2(size));
+ assert(log2_size >= PyDict_LOG_MINSIZE);
- usable = USABLE_FRACTION(size);
- if (size <= 0xff) {
+ usable = USABLE_FRACTION(1<<log2_size);
+ if (log2_size <= 7) {
es = 1;
}
- else if (size <= 0xffff) {
+ else if (log2_size <= 15) {
es = 2;
}
#if SIZEOF_VOID_P > 4
- else if (size <= 0xffffffff) {
+ else if (log2_size <= 31) {
es = 4;
}
#endif
@@ -592,13 +578,13 @@ new_keys_object(Py_ssize_t size)
// new_keys_object() must not be called after _PyDict_Fini()
assert(state->keys_numfree != -1);
#endif
- if (size == PyDict_MINSIZE && state->keys_numfree > 0) {
+ if (log2_size == PyDict_LOG_MINSIZE && state->keys_numfree > 0) {
dk = state->keys_free_list[--state->keys_numfree];
}
else
{
dk = PyObject_Malloc(sizeof(PyDictKeysObject)
- + es * size
+ + (es<<log2_size)
+ sizeof(PyDictKeyEntry) * usable);
if (dk == NULL) {
PyErr_NoMemory();
@@ -609,11 +595,12 @@ new_keys_object(Py_ssize_t size)
_Py_RefTotal++;
#endif
dk->dk_refcnt = 1;
- dk->dk_size = size;
+ dk->dk_log2_size = log2_size;
dk->dk_usable = usable;
- dk->dk_lookup = lookdict_unicode_nodummy;
+ dk->dk_kind = DICT_KEYS_UNICODE;
dk->dk_nentries = 0;
- memset(&dk->dk_indices[0], 0xff, es * size);
+ dk->dk_version = 0;
+ memset(&dk->dk_indices[0], 0xff, es * (1<<log2_size));
memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
return dk;
}
@@ -632,7 +619,7 @@ free_keys_object(PyDictKeysObject *keys)
// free_keys_object() must not be called after _PyDict_Fini()
assert(state->keys_numfree != -1);
#endif
- if (keys->dk_size == PyDict_MINSIZE && state->keys_numfree < PyDict_MAXFREELIST) {
+ if (DK_SIZE(keys) == PyDict_MINSIZE && state->keys_numfree < PyDict_MAXFREELIST) {
state->keys_free_list[state->keys_numfree++] = keys;
return;
}
@@ -778,36 +765,62 @@ probe indices are computed as explained earlier.
All arithmetic on hash should ignore overflow.
-The details in this version are due to Tim Peters, building on many past
-contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
-Christian Tismer.
-
-lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
+_Py_dict_lookup() is general-purpose, and may return DKIX_ERROR if (and only if) a
comparison raises an exception.
-lookdict_unicode() below is specialized to string keys, comparison of which can
-never raise an exception; that function can never return DKIX_ERROR when key
-is string. Otherwise, it falls back to lookdict().
-lookdict_unicode_nodummy is further specialized for string keys that cannot be
-the <dummy> value.
-For both, when the key isn't found a DKIX_EMPTY is returned.
+When the key isn't found a DKIX_EMPTY is returned.
*/
-static Py_ssize_t _Py_HOT_FUNCTION
-lookdict(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr)
+Py_ssize_t _Py_HOT_FUNCTION
+_Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
{
- size_t i, mask, perturb;
PyDictKeysObject *dk;
- PyDictKeyEntry *ep0;
-
-top:
+start:
dk = mp->ma_keys;
- ep0 = DK_ENTRIES(dk);
- mask = DK_MASK(dk);
- perturb = hash;
- i = (size_t)hash & mask;
-
+ DictKeysKind kind = dk->dk_kind;
+ PyDictKeyEntry *ep0 = DK_ENTRIES(dk);
+ size_t mask = DK_MASK(dk);
+ size_t perturb = hash;
+ size_t i = (size_t)hash & mask;
+ Py_ssize_t ix;
+ if (PyUnicode_CheckExact(key) && kind != DICT_KEYS_GENERAL) {
+ /* Strings only */
+ for (;;) {
+ ix = dictkeys_get_index(mp->ma_keys, i);
+ if (ix >= 0) {
+ PyDictKeyEntry *ep = &ep0[ix];
+ assert(ep->me_key != NULL);
+ assert(PyUnicode_CheckExact(ep->me_key));
+ if (ep->me_key == key ||
+ (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
+ goto found;
+ }
+ }
+ else if (ix == DKIX_EMPTY) {
+ *value_addr = NULL;
+ return DKIX_EMPTY;
+ }
+ perturb >>= PERTURB_SHIFT;
+ i = mask & (i*5 + perturb + 1);
+ ix = dictkeys_get_index(mp->ma_keys, i);
+ if (ix >= 0) {
+ PyDictKeyEntry *ep = &ep0[ix];
+ assert(ep->me_key != NULL);
+ assert(PyUnicode_CheckExact(ep->me_key));
+ if (ep->me_key == key ||
+ (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
+ goto found;
+ }
+ }
+ else if (ix == DKIX_EMPTY) {
+ *value_addr = NULL;
+ return DKIX_EMPTY;
+ }
+ perturb >>= PERTURB_SHIFT;
+ i = mask & (i*5 + perturb + 1);
+ }
+ Py_UNREACHABLE();
+ }
for (;;) {
- Py_ssize_t ix = dictkeys_get_index(dk, i);
+ ix = dictkeys_get_index(dk, i);
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return ix;
@@ -816,8 +829,7 @@ lookdict(PyDictObject *mp, PyObject *key,
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
if (ep->me_key == key) {
- *value_addr = ep->me_value;
- return ix;
+ goto found;
}
if (ep->me_hash == hash) {
PyObject *startkey = ep->me_key;
@@ -830,13 +842,12 @@ lookdict(PyDictObject *mp, PyObject *key,
}
if (dk == mp->ma_keys && ep->me_key == startkey) {
if (cmp > 0) {
- *value_addr = ep->me_value;
- return ix;
+ goto found;
}
}
else {
/* The dict was mutated, restart */
- goto top;
+ goto start;
}
}
}
@@ -844,133 +855,14 @@ lookdict(PyDictObject *mp, PyObject *key,
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
-}
-
-/* Specialized version for string-only keys */
-static Py_ssize_t _Py_HOT_FUNCTION
-lookdict_unicode(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr)
-{
- assert(mp->ma_values == NULL);
- /* Make sure this function doesn't have to handle non-unicode keys,
- including subclasses of str; e.g., one reason to subclass
- unicodes is to override __eq__, and for speed we don't cater to
- that here. */
- if (!PyUnicode_CheckExact(key)) {
- return lookdict(mp, key, hash, value_addr);
- }
-
- PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
- size_t mask = DK_MASK(mp->ma_keys);
- size_t perturb = (size_t)hash;
- size_t i = (size_t)hash & mask;
-
- for (;;) {
- Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
- if (ix == DKIX_EMPTY) {
- *value_addr = NULL;
- return DKIX_EMPTY;
- }
- if (ix >= 0) {
- PyDictKeyEntry *ep = &ep0[ix];
- assert(ep->me_key != NULL);
- assert(PyUnicode_CheckExact(ep->me_key));
- if (ep->me_key == key ||
- (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
- *value_addr = ep->me_value;
- return ix;
- }
- }
- perturb >>= PERTURB_SHIFT;
- i = mask & (i*5 + perturb + 1);
- }
- Py_UNREACHABLE();
-}
-
-/* Faster version of lookdict_unicode when it is known that no <dummy> keys
- * will be present. */
-static Py_ssize_t _Py_HOT_FUNCTION
-lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr)
-{
- assert(mp->ma_values == NULL);
- /* Make sure this function doesn't have to handle non-unicode keys,
- including subclasses of str; e.g., one reason to subclass
- unicodes is to override __eq__, and for speed we don't cater to
- that here. */
- if (!PyUnicode_CheckExact(key)) {
- return lookdict(mp, key, hash, value_addr);
+found:
+ if (dk->dk_kind == DICT_KEYS_SPLIT) {
+ *value_addr = mp->ma_values[ix];
}
-
- PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
- size_t mask = DK_MASK(mp->ma_keys);
- size_t perturb = (size_t)hash;
- size_t i = (size_t)hash & mask;
-
- for (;;) {
- Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
- assert (ix != DKIX_DUMMY);
- if (ix == DKIX_EMPTY) {
- *value_addr = NULL;
- return DKIX_EMPTY;
- }
- PyDictKeyEntry *ep = &ep0[ix];
- assert(ep->me_key != NULL);
- assert(PyUnicode_CheckExact(ep->me_key));
- if (ep->me_key == key ||
- (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
- *value_addr = ep->me_value;
- return ix;
- }
- perturb >>= PERTURB_SHIFT;
- i = mask & (i*5 + perturb + 1);
- }
- Py_UNREACHABLE();
-}
-
-/* Version of lookdict for split tables.
- * All split tables and only split tables use this lookup function.
- * Split tables only contain unicode keys and no dummy keys,
- * so algorithm is the same as lookdict_unicode_nodummy.
- */
-static Py_ssize_t _Py_HOT_FUNCTION
-lookdict_split(PyDictObject *mp, PyObject *key,
- Py_hash_t hash, PyObject **value_addr)
-{
- /* mp must split table */
- assert(mp->ma_values != NULL);
- if (!PyUnicode_CheckExact(key)) {
- Py_ssize_t ix = lookdict(mp, key, hash, value_addr);
- if (ix >= 0) {
- *value_addr = mp->ma_values[ix];
- }
- return ix;
- }
-
- PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
- size_t mask = DK_MASK(mp->ma_keys);
- size_t perturb = (size_t)hash;
- size_t i = (size_t)hash & mask;
-
- for (;;) {
- Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
- assert (ix != DKIX_DUMMY);
- if (ix == DKIX_EMPTY) {
- *value_addr = NULL;
- return DKIX_EMPTY;
- }
- PyDictKeyEntry *ep = &ep0[ix];
- assert(ep->me_key != NULL);
- assert(PyUnicode_CheckExact(ep->me_key));
- if (ep->me_key == key ||
- (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
- *value_addr = mp->ma_values[ix];
- return ix;
- }
- perturb >>= PERTURB_SHIFT;
- i = mask & (i*5 + perturb + 1);
+ else {
+ *value_addr = ep0[ix].me_value;
}
- Py_UNREACHABLE();
+ return ix;
}
int
@@ -980,7 +872,7 @@ _PyDict_HasOnlyStringKeys(PyObject *dict)
PyObject *key, *value;
assert(PyDict_Check(dict));
/* Shortcut */
- if (((PyDictObject *)dict)->ma_keys->dk_lookup != lookdict)
+ if (((PyDictObject *)dict)->ma_keys->dk_kind != DICT_KEYS_GENERAL)
return 1;
while (PyDict_Next(dict, &pos, &key, &value))
if (!PyUnicode_Check(key))
@@ -1057,7 +949,7 @@ find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
static int
insertion_resize(PyDictObject *mp)
{
- return dictresize(mp, calculate_keysize(GROWTH_RATE(mp)));
+ return dictresize(mp, calculate_log2_keysize(GROWTH_RATE(mp)));
}
/*
@@ -1078,7 +970,7 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
goto Fail;
}
- Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
+ Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
goto Fail;
@@ -1097,14 +989,15 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
if (ix == DKIX_EMPTY) {
/* Insert into new slot. */
+ mp->ma_keys->dk_version = 0;
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
/* Need to resize. */
if (insertion_resize(mp) < 0)
goto Fail;
}
- if (!PyUnicode_CheckExact(key) && mp->ma_keys->dk_lookup != lookdict) {
- mp->ma_keys->dk_lookup = lookdict;
+ if (!PyUnicode_CheckExact(key) && mp->ma_keys->dk_kind != DICT_KEYS_GENERAL) {
+ mp->ma_keys->dk_kind = DICT_KEYS_GENERAL;
}
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
@@ -1160,12 +1053,12 @@ insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
{
assert(mp->ma_keys == Py_EMPTY_KEYS);
- PyDictKeysObject *newkeys = new_keys_object(PyDict_MINSIZE);
+ PyDictKeysObject *newkeys = new_keys_object(PyDict_LOG_MINSIZE);
if (newkeys == NULL) {
return -1;
}
if (!PyUnicode_CheckExact(key)) {
- newkeys->dk_lookup = lookdict;
+ newkeys->dk_kind = DICT_KEYS_GENERAL;
}
dictkeys_decref(Py_EMPTY_KEYS);
mp->ma_keys = newkeys;
@@ -1217,19 +1110,18 @@ After resizing a table is always combined,
but can be resplit by make_keys_shared().
*/
static int
-dictresize(PyDictObject *mp, Py_ssize_t newsize)
+dictresize(PyDictObject *mp, uint8_t log2_newsize)
{
Py_ssize_t numentries;
PyDictKeysObject *oldkeys;
PyObject **oldvalues;
PyDictKeyEntry *oldentries, *newentries;
- if (newsize <= 0) {
+ if (log2_newsize >= SIZEOF_SIZE_T*8) {
PyErr_NoMemory();
return -1;
}
- assert(IS_POWER_OF_2(newsize));
- assert(newsize >= PyDict_MINSIZE);
+ assert(log2_newsize >= PyDict_LOG_MINSIZE);
oldkeys = mp->ma_keys;
@@ -1239,15 +1131,15 @@ dictresize(PyDictObject *mp, Py_ssize_t newsize)
*/
/* Allocate a new table. */
- mp->ma_keys = new_keys_object(newsize);
+ mp->ma_keys = new_keys_object(log2_newsize);
if (mp->ma_keys == NULL) {
mp->ma_keys = oldkeys;
return -1;
}
// New table must be large enough.
assert(mp->ma_keys->dk_usable >= mp->ma_used);
- if (oldkeys->dk_lookup == lookdict)
- mp->ma_keys->dk_lookup = lookdict;
+ if (oldkeys->dk_kind == DICT_KEYS_GENERAL)
+ mp->ma_keys->dk_kind = DICT_KEYS_GENERAL;
numentries = mp->ma_used;
oldentries = DK_ENTRIES(oldkeys);
@@ -1287,7 +1179,7 @@ dictresize(PyDictObject *mp, Py_ssize_t newsize)
}
}
- assert(oldkeys->dk_lookup != lookdict_split);
+ assert(oldkeys->dk_kind != DICT_KEYS_SPLIT);
assert(oldkeys->dk_refcnt == 1);
#ifdef Py_REF_DEBUG
_Py_RefTotal--;
@@ -1297,7 +1189,7 @@ dictresize(PyDictObject *mp, Py_ssize_t newsize)
// dictresize() must not be called after _PyDict_Fini()
assert(state->keys_numfree != -1);
#endif
- if (oldkeys->dk_size == PyDict_MINSIZE &&
+ if (DK_SIZE(oldkeys) == PyDict_MINSIZE &&
state->keys_numfree < PyDict_MAXFREELIST)
{
state->keys_free_list[state->keys_numfree++] = oldkeys;
@@ -1328,15 +1220,15 @@ make_keys_shared(PyObject *op)
PyDictKeyEntry *ep0;
PyObject **values;
assert(mp->ma_keys->dk_refcnt == 1);
- if (mp->ma_keys->dk_lookup == lookdict) {
+ if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) {
return NULL;
}
- else if (mp->ma_keys->dk_lookup == lookdict_unicode) {
+ else if (mp->ma_used > mp->ma_keys->dk_nentries) {
/* Remove dummy keys */
- if (dictresize(mp, DK_SIZE(mp->ma_keys)))
+ if (dictresize(mp, DK_LOG_SIZE(mp->ma_keys)))
return NULL;
}
- assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);
+ assert(mp->ma_used == mp->ma_keys->dk_nentries);
/* Copy values into a new array */
ep0 = DK_ENTRIES(mp->ma_keys);
size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
@@ -1350,7 +1242,7 @@ make_keys_shared(PyObject *op)
values[i] = ep0[i].me_value;
ep0[i].me_value = NULL;
}
- mp->ma_keys->dk_lookup = lookdict_split;
+ mp->ma_keys->dk_kind = DICT_KEYS_SPLIT;
mp->ma_values = values;
}
dictkeys_incref(mp->ma_keys);
@@ -1360,8 +1252,9 @@ make_keys_shared(PyObject *op)
PyObject *
_PyDict_NewPresized(Py_ssize_t minused)
{
- const Py_ssize_t max_presize = 128 * 1024;
- Py_ssize_t newsize;
+ const uint8_t log2_max_presize = 17;
+ const Py_ssize_t max_presize = ((Py_ssize_t)1) << log2_max_presize;
+ uint8_t log2_newsize;
PyDictKeysObject *new_keys;
if (minused <= USABLE_FRACTION(PyDict_MINSIZE)) {
@@ -1372,13 +1265,13 @@ _PyDict_NewPresized(Py_ssize_t minused)
* large dict or MemoryError.
*/
if (minused > USABLE_FRACTION(max_presize)) {
- newsize = max_presize;
+ log2_newsize = log2_max_presize;
}
else {
- newsize = estimate_keysize(minused);
+ log2_newsize = estimate_log2_keysize(minused);
}
- new_keys = new_keys_object(newsize);
+ new_keys = new_keys_object(log2_newsize);
if (new_keys == NULL)
return NULL;
return new_dict(new_keys, NULL);
@@ -1426,14 +1319,13 @@ PyDict_GetItem(PyObject *op, PyObject *key)
Py_ssize_t ix;
_PyErr_Fetch(tstate, &exc_type, &exc_value, &exc_tb);
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ ix = _Py_dict_lookup(mp, key, hash, &value);
/* Ignore any exception raised by the lookup */
_PyErr_Restore(tstate, exc_type, exc_value, exc_tb);
- if (ix < 0) {
- return NULL;
- }
+
+ assert(ix >= 0 || value == NULL);
return value;
}
@@ -1450,7 +1342,7 @@ _PyDict_GetItemHint(PyDictObject *mp, PyObject *key,
PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys) + (size_t)hint;
if (ep->me_key == key) {
- if (mp->ma_keys->dk_lookup == lookdict_split) {
+ if (mp->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
assert(mp->ma_values != NULL);
res = mp->ma_values[(size_t)hint];
}
@@ -1472,7 +1364,7 @@ _PyDict_GetItemHint(PyDictObject *mp, PyObject *key,
}
}
- return (mp->ma_keys->dk_lookup)(mp, key, hash, value);
+ return _Py_dict_lookup(mp, key, hash, value);
}
/* Same as PyDict_GetItemWithError() but with hash supplied by caller.
@@ -1491,10 +1383,8 @@ _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
return NULL;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
- if (ix < 0) {
- return NULL;
- }
+ ix = _Py_dict_lookup(mp, key, hash, &value);
+ assert(ix >= 0 || value == NULL);
return value;
}
@@ -1523,9 +1413,8 @@ PyDict_GetItemWithError(PyObject *op, PyObject *key)
}
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
- if (ix < 0)
- return NULL;
+ ix = _Py_dict_lookup(mp, key, hash, &value);
+ assert(ix >= 0 || value == NULL);
return value;
}
@@ -1577,16 +1466,15 @@ _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key)
}
/* namespace 1: globals */
- ix = globals->ma_keys->dk_lookup(globals, key, hash, &value);
+ ix = _Py_dict_lookup(globals, key, hash, &value);
if (ix == DKIX_ERROR)
return NULL;
if (ix != DKIX_EMPTY && value != NULL)
return value;
/* namespace 2: builtins */
- ix = builtins->ma_keys->dk_lookup(builtins, key, hash, &value);
- if (ix < 0)
- return NULL;
+ ix = _Py_dict_lookup(builtins, key, hash, &value);
+ assert(ix >= 0 || value == NULL);
return value;
}
@@ -1659,7 +1547,7 @@ delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
mp->ma_version_tag = DICT_NEXT_VERSION();
ep = &DK_ENTRIES(mp->ma_keys)[ix];
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
- ENSURE_ALLOWS_DELETIONS(mp);
+ mp->ma_keys->dk_version = 0;
old_key = ep->me_key;
ep->me_key = NULL;
ep->me_value = NULL;
@@ -1699,7 +1587,7 @@ _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, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return -1;
if (ix == DKIX_EMPTY || old_value == NULL) {
@@ -1709,10 +1597,10 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
- if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
+ if (dictresize(mp, DK_LOG_SIZE(mp->ma_keys))) {
return -1;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
assert(ix >= 0);
}
@@ -1742,7 +1630,7 @@ _PyDict_DelItemIf(PyObject *op, PyObject *key,
if (hash == -1)
return -1;
mp = (PyDictObject *)op;
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return -1;
if (ix == DKIX_EMPTY || old_value == NULL) {
@@ -1752,10 +1640,10 @@ _PyDict_DelItemIf(PyObject *op, PyObject *key,
// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
- if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
+ if (dictresize(mp, DK_LOG_SIZE(mp->ma_keys))) {
return -1;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
assert(ix >= 0);
}
@@ -1902,7 +1790,7 @@ _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, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return NULL;
if (ix == DKIX_EMPTY || old_value == NULL) {
@@ -1916,10 +1804,10 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d
// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
- if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
+ if (dictresize(mp, DK_LOG_SIZE(mp->ma_keys))) {
return NULL;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
+ ix = _Py_dict_lookup(mp, key, hash, &old_value);
assert(ix >= 0);
}
@@ -1930,7 +1818,7 @@ _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *d
mp->ma_version_tag = DICT_NEXT_VERSION();
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
ep = &DK_ENTRIES(mp->ma_keys)[ix];
- ENSURE_ALLOWS_DELETIONS(mp);
+ mp->ma_keys->dk_version = 0;
old_key = ep->me_key;
ep->me_key = NULL;
ep->me_value = NULL;
@@ -1983,7 +1871,7 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
PyObject *key;
Py_hash_t hash;
- if (dictresize(mp, estimate_keysize(PyDict_GET_SIZE(iterable)))) {
+ if (dictresize(mp, estimate_log2_keysize(PyDict_GET_SIZE(iterable)))) {
Py_DECREF(d);
return NULL;
}
@@ -2002,7 +1890,7 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
PyObject *key;
Py_hash_t hash;
- if (dictresize(mp, estimate_keysize(PySet_GET_SIZE(iterable)))) {
+ if (dictresize(mp, estimate_log2_keysize(PySet_GET_SIZE(iterable)))) {
Py_DECREF(d);
return NULL;
}
@@ -2192,7 +2080,7 @@ dict_subscript(PyDictObject *mp, PyObject *key)
if (hash == -1)
return NULL;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return NULL;
if (ix == DKIX_EMPTY || value == NULL) {
@@ -2578,8 +2466,8 @@ dict_merge(PyObject *a, PyObject *b, int override)
// If other is clean, combined, and just allocated, just clone it.
if (other->ma_values == NULL &&
other->ma_used == okeys->dk_nentries &&
- (okeys->dk_size == PyDict_MINSIZE ||
- USABLE_FRACTION(okeys->dk_size/2) < other->ma_used)) {
+ (DK_SIZE(okeys) == PyDict_MINSIZE ||
+ USABLE_FRACTION(DK_SIZE(okeys)/2) < other->ma_used)) {
PyDictKeysObject *keys = clone_combined_dict_keys(other);
if (keys == NULL) {
return -1;
@@ -2610,8 +2498,8 @@ dict_merge(PyObject *a, PyObject *b, int override)
* incrementally resizing as we insert new items. Expect
* that there will be no (or few) overlapping keys.
*/
- if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
- if (dictresize(mp, estimate_keysize(mp->ma_used + other->ma_used))) {
+ if (USABLE_FRACTION(DK_SIZE(mp->ma_keys)) < other->ma_used) {
+ if (dictresize(mp, estimate_log2_keysize(mp->ma_used + other->ma_used))) {
return -1;
}
}
@@ -2908,7 +2796,7 @@ dict_equal(PyDictObject *a, PyDictObject *b)
/* ditto for key */
Py_INCREF(key);
/* reuse the known hash value */
- b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval);
+ _Py_dict_lookup(b, key, ep->me_hash, &bval);
if (bval == NULL) {
Py_DECREF(key);
Py_DECREF(aval);
@@ -2975,7 +2863,7 @@ dict___contains__(PyDictObject *self, PyObject *key)
if (hash == -1)
return NULL;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return NULL;
if (ix == DKIX_EMPTY || value == NULL)
@@ -3007,7 +2895,7 @@ dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
if (hash == -1)
return NULL;
}
- ix = (self->ma_keys->dk_lookup) (self, key, hash, &val);
+ ix = _Py_dict_lookup(self, key, hash, &val);
if (ix == DKIX_ERROR)
return NULL;
if (ix == DKIX_EMPTY || val == NULL) {
@@ -3047,7 +2935,7 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
return NULL;
}
- Py_ssize_t ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return NULL;
@@ -3061,6 +2949,7 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
}
if (ix == DKIX_EMPTY) {
+ mp->ma_keys->dk_version = 0;
PyDictKeyEntry *ep, *ep0;
value = defaultobj;
if (mp->ma_keys->dk_usable <= 0) {
@@ -3068,8 +2957,8 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
return NULL;
}
}
- if (!PyUnicode_CheckExact(key) && mp->ma_keys->dk_lookup != lookdict) {
- mp->ma_keys->dk_lookup = lookdict;
+ if (!PyUnicode_CheckExact(key) && mp->ma_keys->dk_kind != DICT_KEYS_GENERAL) {
+ mp->ma_keys->dk_kind = DICT_KEYS_GENERAL;
}
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
ep0 = DK_ENTRIES(mp->ma_keys);
@@ -3194,13 +3083,13 @@ dict_popitem_impl(PyDictObject *self)
return NULL;
}
/* Convert split table to combined table */
- if (self->ma_keys->dk_lookup == lookdict_split) {
- if (dictresize(self, DK_SIZE(self->ma_keys))) {
+ if (self->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
+ if (dictresize(self, DK_LOG_SIZE(self->ma_keys))) {
Py_DECREF(res);
return NULL;
}
}
- ENSURE_ALLOWS_DELETIONS(self);
+ self->ma_keys->dk_version = 0;
/* Pop last item */
ep0 = DK_ENTRIES(self->ma_keys);
@@ -3236,7 +3125,7 @@ dict_traverse(PyObject *op, visitproc visit, void *arg)
PyDictKeyEntry *entries = DK_ENTRIES(keys);
Py_ssize_t i, n = keys->dk_nentries;
- if (keys->dk_lookup == lookdict) {
+ if (keys->dk_kind == DICT_KEYS_GENERAL) {
for (i = 0; i < n; i++) {
if (entries[i].me_value != NULL) {
Py_VISIT(entries[i].me_value);
@@ -3401,7 +3290,7 @@ PyDict_Contains(PyObject *op, PyObject *key)
if (hash == -1)
return -1;
}
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return -1;
return (ix != DKIX_EMPTY && value != NULL);
@@ -3415,7 +3304,7 @@ _PyDict_Contains_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
PyObject *value;
Py_ssize_t ix;
- ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
+ ix = _Py_dict_lookup(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return -1;
return (ix != DKIX_EMPTY && value != NULL);
@@ -4974,12 +4863,12 @@ dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
PyDictKeysObject *
_PyDict_NewKeysForClass(void)
{
- PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
+ PyDictKeysObject *keys = new_keys_object(PyDict_LOG_MINSIZE);
if (keys == NULL) {
PyErr_Clear();
}
else {
- keys->dk_lookup = lookdict_split;
+ keys->dk_kind = DICT_KEYS_SPLIT;
}
return keys;
}
@@ -5091,3 +4980,18 @@ _PyDictKeys_DecRef(PyDictKeysObject *keys)
{
dictkeys_decref(keys);
}
+
+static uint32_t next_dict_keys_version = 2;
+
+uint32_t _PyDictKeys_GetVersionForCurrentState(PyDictObject *dict)
+{
+ if (dict->ma_keys->dk_version != 0) {
+ return dict->ma_keys->dk_version;
+ }
+ if (next_dict_keys_version == 0) {
+ return 0;
+ }
+ uint32_t v = next_dict_keys_version++;
+ dict->ma_keys->dk_version = v;
+ return v;
+}
diff --git a/Objects/odictobject.c b/Objects/odictobject.c
index 6c7f1175cd652c..470322f866eea2 100644
--- a/Objects/odictobject.c
+++ b/Objects/odictobject.c
@@ -40,9 +40,9 @@ we've considered:
The approach with the least performance impact (time and space) is #2,
mirroring the key order of dict's dk_entries with an array of node pointers.
-While lookdict() and friends (dk_lookup) don't give us the index into the
-array, we make use of pointer arithmetic to get that index. An alternative
-would be to refactor lookdict() to provide the index, explicitly exposing
+While _Py_dict_lookup() does not give us the index into the array,
+we make use of pointer arithmetic to get that index. An alternative would
+be to refactor _Py_dict_lookup() to provide the index, explicitly exposing
the implementation detail. We could even just use a custom lookup function
for OrderedDict that facilitates our need. However, both approaches are
significantly more complicated than just using pointer arithmetic.
@@ -535,7 +535,7 @@ _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
Py_ssize_t ix;
- ix = (keys->dk_lookup)((PyDictObject *)od, key, hash, &value);
+ ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);
if (ix == DKIX_EMPTY) {
return keys->dk_nentries; /* index of new entry */
}
@@ -553,7 +553,7 @@ _odict_resize(PyODictObject *od)
_ODictNode **fast_nodes, *node;
/* Initialize a new "fast nodes" table. */
- size = ((PyDictObject *)od)->ma_keys->dk_size;
+ size = 1 << (((PyDictObject *)od)->ma_keys->dk_log2_size);
fast_nodes = PyMem_NEW(_ODictNode *, size);
if (fast_nodes == NULL) {
PyErr_NoMemory();
@@ -592,7 +592,7 @@ _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)
/* Ensure od_fast_nodes and dk_entries are in sync. */
if (od->od_resize_sentinel != keys ||
- od->od_fast_nodes_size != keys->dk_size) {
+ od->od_fast_nodes_size != (1 << (keys->dk_log2_size))) {
int resize_res = _odict_resize(od);
if (resize_res < 0)
return -1;
diff --git a/Tools/gdb/libpython.py b/Tools/gdb/libpython.py
index b726b353b77ab8..c1d2cd8ced68c4 100755
--- a/Tools/gdb/libpython.py
+++ b/Tools/gdb/libpython.py
@@ -730,7 +730,7 @@ def write_repr(self, out, visited):
def _get_entries(self, keys):
dk_nentries = int(keys['dk_nentries'])
- dk_size = int(keys['dk_size'])
+ dk_size = 1<<int(keys['dk_log2_size'])
try:
# <= Python 3.5
return keys['dk_entries'], dk_size
More information about the Python-checkins
mailing list