cpython: 828c9b920532 (original) (raw)

--- a/Misc/NEWS +++ b/Misc/NEWS @@ -10,6 +10,9 @@ Release date: XXXX-XX-XX Core and Builtins ----------------- +- Issue #25462: The hash of the key now is calculated only once in most

• operations in C implementation of OrderedDict. +

• Issue #22995: Default implementation of reduce and reduce_ex now rejects builtin types with not defined new.

--- a/Objects/odictobject.c +++ b/Objects/odictobject.c @@ -88,15 +88,16 @@ For adding nodes:

• _odict_add_head(od, node)
• _odict_add_tail(od, node) -* _odict_add_new_node(od, key) +* _odict_add_new_node(od, key, hash) For removing nodes: -* _odict_clear_node(od, node) +* _odict_clear_node(od, node, key, hash)
• _odict_clear_nodes(od, clear_each) Others: +* _odict_find_node_hash(od, key, hash)
• _odict_find_node(od, key)
• _odict_keys_equal(od1, od2) @@ -532,7 +533,7 @@ static void /* Return the index into the hash table, regardless of a valid node. */ static Py_ssize_t -_odict_get_index_hash(PyODictObject *od, PyObject *key, Py_hash_t hash) +_odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash) { PyObject **value_addr = NULL; PyDictKeyEntry ep; @@ -563,7 +564,7 @@ static int / Copy the current nodes into the table. */ _odict_FOREACH(od, node) {

•    i = _odict_get_index_hash(od, _odictnode_KEY(node),[](#l2.35)

•    i = _odict_get_index_raw(od, _odictnode_KEY(node),[](#l2.36)
                               _odictnode_HASH(node));[](#l2.37)
     if (i < 0) {[](#l2.38)
         PyMem_FREE(fast_nodes);[](#l2.39)

@@ -582,15 +583,11 @@ static int /* Return the index into the hash table, regardless of a valid node. */ static Py_ssize_t -_odict_get_index(PyODictObject *od, PyObject *key) +_odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash) {

• Py_hash_t hash; PyDictKeysObject *keys; assert(key != NULL);
• hash = PyObject_Hash(key);
• if (hash == -1)

•    return -1;[](#l2.53)

  keys = ((PyDictObject )od)->ma_keys; / Ensure od_fast_nodes and dk_entries are in sync. */ @@ -601,18 +598,35 @@ static Py_ssize_t return -1; }
• return _odict_get_index_hash(od, key, hash);

• return _odict_get_index_raw(od, key, hash);

} /* Returns NULL if there was some error or the key was not found. */ static _ODictNode * -_odict_find_node(PyODictObject *od, PyObject *key) +_odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash) { Py_ssize_t index; if (_odict_EMPTY(od)) return NULL;

• index = _odict_get_index(od, key);

• index = _odict_get_index(od, key, hash);
• if (index < 0)

•    return NULL;[](#l2.77)

• return od->od_fast_nodes[index];

+} + +static _ODictNode * +_odict_find_node(PyODictObject *od, PyObject *key) +{

• Py_ssize_t index;
• Py_hash_t hash;

+

• if (_odict_EMPTY(od))

•    return NULL;[](#l2.88)

• hash = PyObject_Hash(key);
• if (hash == -1)

•    return NULL;[](#l2.91)

• index = _odict_get_index(od, key, hash); if (index < 0) return NULL; return od->od_fast_nodes[index]; @@ -646,18 +660,13 @@ static void /* adds the node to the end of the list */ static int -_odict_add_new_node(PyODictObject *od, PyObject *key) +_odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash) {

• Py_hash_t hash; Py_ssize_t i; _ODictNode *node;
• hash = PyObject_Hash(key);
• if (hash == -1)

•    return -1;[](#l2.109)

- Py_INCREF(key);

• i = _odict_get_index(od, key);

• i = _odict_get_index(od, key, hash); if (i < 0) { if (!PyErr_Occurred()) PyErr_SetObject(PyExc_KeyError, key);

@@ -728,7 +737,8 @@ static void we modify od_fast_nodes. */ static int -_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key) +_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,

•              Py_hash_t hash)[](#l2.123)

{ Py_ssize_t i; @@ -738,7 +748,7 @@ static int return 0; }

• i = _odict_get_index(od, key);

• i = _odict_get_index(od, key, hash); if (i < 0) return PyErr_Occurred() ? -1 : 0;

@@ -1091,7 +1101,8 @@ odict_pop(PyObject *od, PyObject *args, } static PyObject * -_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj) +_odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,

•               Py_hash_t hash)[](#l2.142)

{ _ODictNode *node; PyObject *value = NULL; @@ -1099,13 +1110,13 @@ static PyObject / Pop the node first to avoid a possible dict resize (due to eval loop reentrancy) and complications due to hash collision resolution. */

• node = _odict_find_node((PyODictObject *)od, key);

• node = _odict_find_node_hash((PyODictObject *)od, key, hash); if (node == NULL) { if (PyErr_Occurred()) return NULL; } else {

•    int res = _odict_clear_node((PyODictObject *)od, node, key);[](#l2.157)

•    int res = _odict_clear_node((PyODictObject *)od, node, key, hash);[](#l2.158)
     if (res < 0) {[](#l2.159)
         return NULL;[](#l2.160)
     }[](#l2.161)

@@ -1114,8 +1125,14 @@ static PyObject / Now delete the value from the dict. */ if (PyODict_CheckExact(od)) { if (node != NULL) {

•        /* We could do PyDict_GetItem() and PyDict_DelItem() directly... */[](#l2.166)

•        value = _PyDict_Pop((PyDictObject *)od, key, failobj);[](#l2.167)

•        value = _PyDict_GetItem_KnownHash(od, key, hash);  /* borrowed */[](#l2.168)

•        if (value != NULL) {[](#l2.169)

•            Py_INCREF(value);[](#l2.170)

•            if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {[](#l2.171)

•                Py_DECREF(value);[](#l2.172)

•                return NULL;[](#l2.173)

•            }[](#l2.174)

•        }[](#l2.175)
     }[](#l2.176)

  } else { @@ -1146,6 +1163,16 @@ static PyObject * return value; } +static PyObject * +_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj) +{
• Py_hash_t hash = PyObject_Hash(key);
• if (hash == -1)

•    return NULL;[](#l2.188)

+

• return _odict_popkey_hash(od, key, failobj, hash);

+} + /* popitem() */ PyDoc_STRVAR(odict_popitem__doc__, @@ -1178,7 +1205,7 @@ odict_popitem(PyObject *od, PyObject *ar node = last ? _odict_LAST(od) : _odict_FIRST(od); key = _odictnode_KEY(node); Py_INCREF(key);

• value = _odict_popkey(od, key, NULL);

• value = _odict_popkey_hash(od, key, NULL, _odictnode_HASH(node)); if (value == NULL) return NULL; item = PyTuple_Pack(2, key, value); @@ -1237,6 +1264,10 @@ odict_clear(register PyODictObject od) / copy() / +/ forward */ +static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *,

•                                  Py_hash_t);[](#l2.211)

+ PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od"); static PyObject * @@ -1261,7 +1292,8 @@ odict_copy(register PyODictObject *od) PyErr_SetObject(PyExc_KeyError, key); goto fail; }

•        if (PyODict_SetItem((PyObject *)od_copy, key, value) != 0)[](#l2.220)

•        if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value,[](#l2.221)

•                                       _odictnode_HASH(node)) != 0)[](#l2.222)
             goto fail;[](#l2.223)
     }[](#l2.224)

  } @@ -1720,16 +1752,18 @@ PyODict_New(void) { return odict_new(&PyODict_Type, NULL, NULL); }; -int -PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) {

• int res = PyDict_SetItem(od, key, value);

+static int +_PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,

•                       Py_hash_t hash)[](#l2.235)

+{

• int res = _PyDict_SetItem_KnownHash(od, key, value, hash); if (res == 0) {

•    res = _odict_add_new_node((PyODictObject *)od, key);[](#l2.239)

•    res = _odict_add_new_node((PyODictObject *)od, key, hash);[](#l2.240)
     if (res < 0) {[](#l2.241)
         /* Revert setting the value on the dict */[](#l2.242)
         PyObject *exc, *val, *tb;[](#l2.243)
         PyErr_Fetch(&exc, &val, &tb);[](#l2.244)

•        (void) PyDict_DelItem(od, key);[](#l2.245)

•        (void) _PyDict_DelItem_KnownHash(od, key, hash);[](#l2.246)
         _PyErr_ChainExceptions(exc, val, tb);[](#l2.247)
     }[](#l2.248)

  } @@ -1737,11 +1771,25 @@ PyODict_SetItem(PyObject *od, PyObject * }; int -PyODict_DelItem(PyObject *od, PyObject *key) {

• int res = _odict_clear_node((PyODictObject *)od, NULL, key);

+PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) +{

• Py_hash_t hash = PyObject_Hash(key);
• if (hash == -1)

•    return -1;[](#l2.260)

• return _PyODict_SetItem_KnownHash(od, key, value, hash);

+}; + +int +PyODict_DelItem(PyObject *od, PyObject *key) +{

• int res;
• Py_hash_t hash = PyObject_Hash(key);
• if (hash == -1)

•    return -1;[](#l2.270)

• res = _odict_clear_node((PyODictObject *)od, NULL, key, hash); if (res < 0) return -1;

• return PyDict_DelItem(od, key);

• return _PyDict_DelItem_KnownHash(od, key, hash);

};