From 6f8c51b8f9c626f1e4c6a541812ca4d131a13aa0 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sat, 22 Oct 2016 09:58:14 -0700
Subject: Reference the original compact-and-ordered proposal

---
 Objects/dictobject.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 03c973be63..2cca2c678e 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:
 
-- 
cgit v1.2.1


From af0cb9c1e35bb720a3ad0b01e8d9607bb92d0455 Mon Sep 17 00:00:00 2001
From: INADA Naoki <songofacandy@gmail.com>
Date: Fri, 4 Nov 2016 16:59:10 +0900
Subject: Issue #28580: Optimize iterating split table values.

Patch by Xiang Zhang.
---
 Objects/dictobject.c | 62 +++++++++++++++++++++-------------------------------
 1 file changed, 25 insertions(+), 37 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 30062cb775..85ada6cc5f 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1700,7 +1700,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;
@@ -1709,21 +1709,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++;
@@ -3380,7 +3377,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;
 
@@ -3397,18 +3394,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++;
@@ -3466,7 +3460,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)
@@ -3481,18 +3475,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++;
@@ -3550,7 +3541,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)
@@ -3565,19 +3556,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++;
-- 
cgit v1.2.1


From d4870f38df7c4e96b5c4eb684e904465e39080f3 Mon Sep 17 00:00:00 2001
From: Serhiy Storchaka <storchaka@gmail.com>
Date: Sat, 29 Oct 2016 10:50:00 +0300
Subject: Issue #28199: Microoptimized dict resizing.  Based on patch by Naoki
 Inada.

---
 Objects/dictobject.c | 123 ++++++++++++++++++++++++++-------------------------
 1 file changed, 63 insertions(+), 60 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 9bf4eeef41..cb67dda33f 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1198,41 +1198,21 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
 }
 
 /*
-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;
 }
 
 /*
@@ -1248,10 +1228,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;
@@ -1262,8 +1242,14 @@ dictresize(PyDictObject *mp, Py_ssize_t minused)
         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) {
@@ -1272,42 +1258,59 @@ dictresize(PyDictObject *mp, Py_ssize_t minused)
     }
     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;
 }
 
-- 
cgit v1.2.1


From bc2f49454c330a83373e1f00c3de717dad4070ef Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Fri, 11 Nov 2016 01:43:56 +0100
Subject: Use PyThreadState_GET() in performance critical code

It seems like _PyThreadState_UncheckedGet() is not inlined as expected, even
when using gcc -O3.
---
 Objects/dictobject.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index cb67dda33f..290686b88f 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1409,7 +1409,7 @@ 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;
-- 
cgit v1.2.1


From 980554ec4d992135f53e5a919047c835b7a68925 Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Tue, 15 Nov 2016 15:13:40 +0100
Subject: Issue #28618: Mark dict lookup functions as hot

It's common to see these functions in the top 3 of "perf report".
---
 Objects/dictobject.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 290686b88f..320dff6dfc 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -683,7 +683,7 @@ 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)
 {
@@ -798,7 +798,7 @@ 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)
 {
@@ -873,7 +873,7 @@ 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_ssize_t *hashpos)
@@ -941,7 +941,7 @@ 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)
 {
-- 
cgit v1.2.1


From a7eaa88fb34028a2928eca85701651703e3047f7 Mon Sep 17 00:00:00 2001
From: INADA Naoki <songofacandy@gmail.com>
Date: Tue, 22 Nov 2016 00:57:02 +0900
Subject: Issue #28731: Optimize _PyDict_NewPresized() to create correct size
 dict

Improve speed of dict literal with constant keys up to 30%.
---
 Objects/dictobject.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 320dff6dfc..2a01f70b71 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -389,7 +389,7 @@ dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
  * This can be used to reserve enough size to insert n entries without
  * resizing.
  */
-#define ESTIMATE_SIZE(n)  (((n)*3) >> 1)
+#define ESTIMATE_SIZE(n)  (((n)*3+1) >> 1)
 
 /* Alternative fraction that is otherwise close enough to 2n/3 to make
  * little difference. 8 * 2/3 == 8 * 5/8 == 5. 16 * 2/3 == 16 * 5/8 == 10.
@@ -1361,12 +1361,26 @@ make_keys_shared(PyObject *op)
 PyObject *
 _PyDict_NewPresized(Py_ssize_t minused)
 {
+    const Py_ssize_t max_presize = 128 * 1024;
     Py_ssize_t newsize;
     PyDictKeysObject *new_keys;
-    for (newsize = PyDict_MINSIZE;
-         newsize <= minused && newsize > 0;
-         newsize <<= 1)
-        ;
+
+    /* There are no strict guarantee that returned dict can contain minused
+     * items without resize.  So we create medium size dict instead of very
+     * large dict or MemoryError.
+     */
+    if (minused > USABLE_FRACTION(max_presize)) {
+        newsize = max_presize;
+    }
+    else {
+        Py_ssize_t minsize = ESTIMATE_SIZE(minused);
+        newsize = PyDict_MINSIZE;
+        while (newsize < minsize) {
+            newsize <<= 1;
+        }
+    }
+    assert(IS_POWER_OF_2(newsize));
+
     new_keys = new_keys_object(newsize);
     if (new_keys == NULL)
         return NULL;
-- 
cgit v1.2.1


From 366f4ee4da4420842eac26b3fa00c2b01d4515a6 Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Thu, 1 Dec 2016 14:43:22 +0100
Subject: Replace PyObject_CallFunctionObjArgs() with fastcall

* PyObject_CallFunctionObjArgs(func, NULL) => _PyObject_CallNoArg(func)
* PyObject_CallFunctionObjArgs(func, arg, NULL) => _PyObject_CallArg1(func, arg)

PyObject_CallFunctionObjArgs() allocates 40 bytes on the C stack and requires
extra work to "parse" C arguments to build a C array of PyObject*.

_PyObject_CallNoArg() and _PyObject_CallArg1() are simpler and don't allocate
memory on the C stack.

This change is part of the fastcall project. The change on listsort() is
related to the issue #23507.
---
 Objects/dictobject.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 2a01f70b71..b74941ac29 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2066,8 +2066,7 @@ dict_subscript(PyDictObject *mp, PyObject *key)
             _Py_IDENTIFIER(__missing__);
             missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
             if (missing != NULL) {
-                res = PyObject_CallFunctionObjArgs(missing,
-                                                   key, NULL);
+                res = _PyObject_CallArg1(missing, key);
                 Py_DECREF(missing);
                 return res;
             }
-- 
cgit v1.2.1


From 39ae5bedd90f9caf9a78efa82f4d11e838933b3a Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Sun, 4 Dec 2016 22:59:09 +0100
Subject: Backed out changeset b9c9691c72c5

Issue #28858: The change b9c9691c72c5 introduced a regression. It seems like
_PyObject_CallArg1() uses more stack memory than
PyObject_CallFunctionObjArgs().
---
 Objects/dictobject.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index b74941ac29..2a01f70b71 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2066,7 +2066,8 @@ dict_subscript(PyDictObject *mp, PyObject *key)
             _Py_IDENTIFIER(__missing__);
             missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
             if (missing != NULL) {
-                res = _PyObject_CallArg1(missing, key);
+                res = PyObject_CallFunctionObjArgs(missing,
+                                                   key, NULL);
                 Py_DECREF(missing);
                 return res;
             }
-- 
cgit v1.2.1


From b729181a504b6aff2461dcbc07c33e902ee90cb0 Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Tue, 6 Dec 2016 18:45:50 +0100
Subject: Use _PyObject_CallNoArg()

Replace:
    PyObject_CallObject(callable, NULL)
with:
    _PyObject_CallNoArg(callable)
---
 Objects/dictobject.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 2a01f70b71..6ec4e0a4a1 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1843,7 +1843,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;
 
-- 
cgit v1.2.1


From e5f0c097b310b8aea17164d8851aba4b7571ce49 Mon Sep 17 00:00:00 2001
From: INADA Naoki <songofacandy@gmail.com>
Date: Wed, 7 Dec 2016 20:41:42 +0900
Subject: Issue #28818: Simplify lookdict functions

---
 Objects/dictobject.c | 216 ++++++++++++++++++++++-----------------------------
 1 file changed, 94 insertions(+), 122 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 6ec4e0a4a1..e7c0db1882 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -223,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);
@@ -685,7 +685,7 @@ where the key index should be inserted.
 */
 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;
@@ -714,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;
@@ -730,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;
@@ -766,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) {
@@ -783,7 +783,7 @@ top:
                     if (hashpos != NULL) {
                         *hashpos = i;
                     }
-                    *value_addr = &ep->me_value;
+                    *value_addr = ep->me_value;
                     return ix;
                 }
             }
@@ -800,7 +800,7 @@ top:
 /* 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, 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);
@@ -834,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;
@@ -860,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;
             }
@@ -875,7 +875,7 @@ lookdict_unicode(PyDictObject *mp, PyObject *key,
  * will be present. */
 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;
@@ -908,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;;) {
@@ -928,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;
         }
     }
@@ -943,7 +943,7 @@ lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
  */
 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);
@@ -955,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;
     }
@@ -975,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;;) {
@@ -995,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;
         }
     }
@@ -1068,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
@@ -1111,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)) {
@@ -1120,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;
     }
@@ -1133,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;
@@ -1175,24 +1166,21 @@ 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;
 }
@@ -1404,7 +1392,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;
@@ -1428,20 +1416,20 @@ PyDict_GetItem(PyObject *op, PyObject *key)
         /* 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.
@@ -1453,18 +1441,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.
@@ -1477,7 +1465,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();
@@ -1492,10 +1480,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 *
@@ -1520,7 +1508,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)
@@ -1531,17 +1519,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
@@ -1616,7 +1604,6 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
     PyDictObject *mp;
     PyDictKeyEntry *ep;
     PyObject *old_key, *old_value;
-    PyObject **value_addr;
 
     if (!PyDict_Check(op)) {
         PyErr_BadInternalCall();
@@ -1625,10 +1612,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;
     }
@@ -1639,13 +1626,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);
     }
 
-    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];
@@ -1653,6 +1638,7 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
     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);
 
@@ -1777,7 +1763,6 @@ _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
     Py_ssize_t ix, hashpos;
     PyObject *old_value, *old_key;
     PyDictKeyEntry *ep;
-    PyObject **value_addr;
     PyDictObject *mp;
 
     assert(PyDict_Check(dict));
@@ -1797,10 +1782,10 @@ _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
         if (hash == -1)
             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;
@@ -1814,13 +1799,11 @@ _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
         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);
@@ -1828,6 +1811,7 @@ _PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
     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));
@@ -2045,10 +2029,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) {
@@ -2056,10 +2039,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;
@@ -2077,9 +2060,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
@@ -2651,7 +2633,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 */
@@ -2659,10 +2640,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);
@@ -2718,7 +2696,7 @@ dict___contains__(PyDictObject *self, PyObject *key)
     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) {
@@ -2726,10 +2704,10 @@ 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;
 }
@@ -2742,7 +2720,6 @@ dict_get(PyDictObject *mp, PyObject *args)
     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;
@@ -2753,13 +2730,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 = (mp->ma_keys->dk_lookup)(mp, key, hash, &val, NULL);
     if (ix == DKIX_ERROR)
         return NULL;
-    if (ix == DKIX_EMPTY || *value_addr == NULL)
+    if (ix == DKIX_EMPTY || val == NULL) {
         val = failobj;
-    else
-        val = *value_addr;
+    }
     Py_INCREF(val);
     return val;
 }
@@ -2771,7 +2747,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();
@@ -2790,17 +2765,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;
     }
 
@@ -2811,7 +2786,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];
@@ -2821,7 +2796,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;
         }
@@ -2834,19 +2809,16 @@ 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;
@@ -3100,7 +3072,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) {
@@ -3108,10 +3080,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 */
@@ -3119,13 +3091,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" */
-- 
cgit v1.2.1


From 2b51b5bb59545d275d04fe958f4d347cb2508027 Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Thu, 19 Jan 2017 12:37:13 +0100
Subject: dict.get() and dict.setdefault() now use AC

Issue #29311: dict.get() and dict.setdefault() methods now use Argument Clinic
to parse arguments. Their calling convention changes from METH_VARARGS to
METH_FASTCALL which avoids the creation of a temporary tuple.

The signature of docstrings is also enhanced. For example,
    get(...)
becomes:
    get(self, key, default=None, /)
---
 Objects/dictobject.c | 53 ++++++++++++++++++++++++++++------------------------
 1 file changed, 29 insertions(+), 24 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 9950f50896..1a6eedd738 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2787,25 +2787,31 @@ dict___contains__(PyDictObject *self, PyObject *key)
     Py_RETURN_TRUE;
 }
 
+/*[clinic input]
+dict.get
+
+    key: object
+    default as failobj: object = None
+    /
+
+D.get(key[, default]) -> D[key] if key in D, else default.
+[clinic start generated code]*/
+
 static PyObject *
-dict_get(PyDictObject *mp, PyObject *args)
+dict_get_impl(PyDictObject *self, PyObject *key, PyObject *failobj)
+/*[clinic end generated code: output=c4a84a7ddbca9b7b input=7c976a78f258e915]*/
 {
-    PyObject *key;
-    PyObject *failobj = Py_None;
     PyObject *val = NULL;
     Py_hash_t hash;
     Py_ssize_t ix;
 
-    if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
-        return NULL;
-
     if (!PyUnicode_CheckExact(key) ||
         (hash = ((PyASCIIObject *) key)->hash) == -1) {
         hash = PyObject_Hash(key);
         if (hash == -1)
             return NULL;
     }
-    ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &val, NULL);
+    ix = (self->ma_keys->dk_lookup) (self, key, hash, &val, NULL);
     if (ix == DKIX_ERROR)
         return NULL;
     if (ix == DKIX_EMPTY || val == NULL) {
@@ -2899,16 +2905,23 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
     return value;
 }
 
+/*[clinic input]
+dict.setdefault
+
+    key: object
+    default as defaultobj: object = None
+    /
+
+D.get(key,default), also set D[key]=default if key not in D.
+[clinic start generated code]*/
+
 static PyObject *
-dict_setdefault(PyDictObject *mp, PyObject *args)
+dict_setdefault_impl(PyDictObject *self, PyObject *key, PyObject *defaultobj)
+/*[clinic end generated code: output=692f85384b0b292e input=178f0c81d496d5cd]*/
 {
-    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, defaultobj);
     Py_XINCREF(val);
     return val;
 }
@@ -3072,12 +3085,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");
@@ -3116,10 +3123,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,
-- 
cgit v1.2.1


From 1c9596159bb39c2767bddedaa0dea93a945e7d2e Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Thu, 19 Jan 2017 12:45:06 +0100
Subject: Add a note explaining why dict_update() doesn't use METH_FASTCALL

Issue #29312.
---
 Objects/dictobject.c | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 1a6eedd738..f9414865ad 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2347,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)
 {
-- 
cgit v1.2.1


From ca1f7e8b325371854b2c8396cf3e9aae9f31b5e4 Mon Sep 17 00:00:00 2001
From: Serhiy Storchaka <storchaka@gmail.com>
Date: Thu, 19 Jan 2017 19:00:30 +0200
Subject: Issue #29311: Argument Clinic generates reasonable name for the
 parameter "default".

---
 Objects/dictobject.c | 17 +++++++++--------
 1 file changed, 9 insertions(+), 8 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index f9414865ad..9ff52c32aa 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2794,15 +2794,15 @@ dict___contains__(PyDictObject *self, PyObject *key)
 dict.get
 
     key: object
-    default as failobj: object = None
+    default: object = None
     /
 
 D.get(key[, default]) -> D[key] if key in D, else default.
 [clinic start generated code]*/
 
 static PyObject *
-dict_get_impl(PyDictObject *self, PyObject *key, PyObject *failobj)
-/*[clinic end generated code: output=c4a84a7ddbca9b7b input=7c976a78f258e915]*/
+dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
+/*[clinic end generated code: output=bba707729dee05bf input=e73ab0f028f4b2be]*/
 {
     PyObject *val = NULL;
     Py_hash_t hash;
@@ -2818,7 +2818,7 @@ dict_get_impl(PyDictObject *self, PyObject *key, PyObject *failobj)
     if (ix == DKIX_ERROR)
         return NULL;
     if (ix == DKIX_EMPTY || val == NULL) {
-        val = failobj;
+        val = default_value;
     }
     Py_INCREF(val);
     return val;
@@ -2912,19 +2912,20 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
 dict.setdefault
 
     key: object
-    default as defaultobj: object = None
+    default: object = None
     /
 
 D.get(key,default), also set D[key]=default if key not in D.
 [clinic start generated code]*/
 
 static PyObject *
-dict_setdefault_impl(PyDictObject *self, PyObject *key, PyObject *defaultobj)
-/*[clinic end generated code: output=692f85384b0b292e input=178f0c81d496d5cd]*/
+dict_setdefault_impl(PyDictObject *self, PyObject *key,
+                     PyObject *default_value)
+/*[clinic end generated code: output=f8c1101ebf69e220 input=b2826255bacd845a]*/
 {
     PyObject *val;
 
-    val = PyDict_SetDefault((PyObject *)self, key, defaultobj);
+    val = PyDict_SetDefault((PyObject *)self, key, default_value);
     Py_XINCREF(val);
     return val;
 }
-- 
cgit v1.2.1


From 35d2352df15a03d98bb7296a49fd16032b949bb3 Mon Sep 17 00:00:00 2001
From: Serhiy Storchaka <storchaka@gmail.com>
Date: Wed, 25 Jan 2017 00:30:04 +0200
Subject: Issues #29311, #29289: Fixed and improved docstrings for dict and
 OrderedDict methods.

---
 Objects/dictobject.c | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 9ff52c32aa..00fd58c81d 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2311,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);
 }
@@ -2764,12 +2764,12 @@ 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=f39613886bf975b7]*/
 {
     register PyDictObject *mp = self;
     Py_hash_t hash;
@@ -2797,12 +2797,12 @@ dict.get
     default: object = None
     /
 
-D.get(key[, default]) -> D[key] if key in D, else default.
+Return the value for key if key is in the dictionary, else default.
 [clinic start generated code]*/
 
 static PyObject *
 dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
-/*[clinic end generated code: output=bba707729dee05bf input=e73ab0f028f4b2be]*/
+/*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
 {
     PyObject *val = NULL;
     Py_hash_t hash;
@@ -2915,13 +2915,15 @@ dict.setdefault
     default: object = None
     /
 
-D.get(key,default), also set D[key]=default if key not in D.
+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_impl(PyDictObject *self, PyObject *key,
                      PyObject *default_value)
-/*[clinic end generated code: output=f8c1101ebf69e220 input=b2826255bacd845a]*/
+/*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/
 {
     PyObject *val;
 
-- 
cgit v1.2.1


From 9bfb9694a65124a8191cdb8ce7992445d1d0f4d2 Mon Sep 17 00:00:00 2001
From: Serhiy Storchaka <storchaka@gmail.com>
Date: Sat, 4 Feb 2017 08:05:07 +0200
Subject: Issue #29311: Regenerate Argument Clinic.

---
 Objects/dictobject.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'Objects/dictobject.c')

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 00fd58c81d..43584b7bb2 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -2769,7 +2769,7 @@ True if the dictionary has the specified key, else False.
 
 static PyObject *
 dict___contains__(PyDictObject *self, PyObject *key)
-/*[clinic end generated code: output=a3d03db709ed6e6b input=f39613886bf975b7]*/
+/*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
 {
     register PyDictObject *mp = self;
     Py_hash_t hash;
-- 
cgit v1.2.1