1 files changed, 34 insertions, 132 deletions

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index b3fdbf1..320befb 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -582,6 +582,36 @@ PyDict_GetItem(PyObject *op, PyObject *key)
 	return ep->me_value;
 }
 
+/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
+   This returns NULL *with* an exception set if an exception occurred.
+   It returns NULL *without* an exception set if the key wasn't present.
+*/
+PyObject *
+PyDict_GetItemWithError(PyObject *op, PyObject *key)
+{
+	long hash;
+	dictobject *mp = (dictobject *)op;
+	dictentry *ep;
+
+	if (!PyDict_Check(op)) {
+		PyErr_BadInternalCall();
+		return NULL;
+	}
+	if (!PyString_CheckExact(key) ||
+	    (hash = ((PyStringObject *) key)->ob_shash) == -1)
+	{
+		hash = PyObject_Hash(key);
+		if (hash == -1) {
+			return NULL;
+		}
+	}
+
+	ep = (mp->ma_lookup)(mp, key, hash);
+	if (ep == NULL)
+		return NULL;
+	return ep->me_value;
+}
+
 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
  * dictionary if it's merely replacing the value for an existing key.
  * This means that it's safe to loop over a dictionary with PyDict_Next()
@@ -1432,136 +1462,6 @@ PyDict_Items(PyObject *mp)
 	return dict_items((dictobject *)mp);
 }
 
-/* Subroutine which returns the smallest key in a for which b's value
-   is different or absent.  The value is returned too, through the
-   pval argument.  Both are NULL if no key in a is found for which b's status
-   differs.  The refcounts on (and only on) non-NULL *pval and function return
-   values must be decremented by the caller (characterize() increments them
-   to ensure that mutating comparison and PyDict_GetItem calls can't delete
-   them before the caller is done looking at them). */
-
-static PyObject *
-characterize(dictobject *a, dictobject *b, PyObject **pval)
-{
-	PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
-	PyObject *aval = NULL; /* a[akey] */
-	Py_ssize_t i;
-	int cmp;
-
-	for (i = 0; i <= a->ma_mask; i++) {
-		PyObject *thiskey, *thisaval, *thisbval;
-		if (a->ma_table[i].me_value == NULL)
-			continue;
-		thiskey = a->ma_table[i].me_key;
-		Py_INCREF(thiskey);  /* keep alive across compares */
-		if (akey != NULL) {
-			cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
-			if (cmp < 0) {
-				Py_DECREF(thiskey);
-				goto Fail;
-			}
-			if (cmp > 0 ||
-			    i > a->ma_mask ||
-			    a->ma_table[i].me_value == NULL)
-			{
-				/* Not the *smallest* a key; or maybe it is
-				 * but the compare shrunk the dict so we can't
-				 * find its associated value anymore; or
-				 * maybe it is but the compare deleted the
-				 * a[thiskey] entry.
-				 */
-				Py_DECREF(thiskey);
-				continue;
-			}
-		}
-
-		/* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
-		thisaval = a->ma_table[i].me_value;
-		assert(thisaval);
-		Py_INCREF(thisaval);   /* keep alive */
-		thisbval = PyDict_GetItem((PyObject *)b, thiskey);
-		if (thisbval == NULL)
-			cmp = 0;
-		else {
-			/* both dicts have thiskey:  same values? */
-			cmp = PyObject_RichCompareBool(
-						thisaval, thisbval, Py_EQ);
-			if (cmp < 0) {
-		    		Py_DECREF(thiskey);
-		    		Py_DECREF(thisaval);
-		    		goto Fail;
-			}
-		}
-		if (cmp == 0) {
-			/* New winner. */
-			Py_XDECREF(akey);
-			Py_XDECREF(aval);
-			akey = thiskey;
-			aval = thisaval;
-		}
-		else {
-			Py_DECREF(thiskey);
-			Py_DECREF(thisaval);
-		}
-	}
-	*pval = aval;
-	return akey;
-
-Fail:
-	Py_XDECREF(akey);
-	Py_XDECREF(aval);
-	*pval = NULL;
-	return NULL;
-}
-
-static int
-dict_compare(dictobject *a, dictobject *b)
-{
-	PyObject *adiff, *bdiff, *aval, *bval;
-	int res;
-
-	/* Compare lengths first */
-	if (a->ma_used < b->ma_used)
-		return -1;	/* a is shorter */
-	else if (a->ma_used > b->ma_used)
-		return 1;	/* b is shorter */
-
-	/* Same length -- check all keys */
-	bdiff = bval = NULL;
-	adiff = characterize(a, b, &aval);
-	if (adiff == NULL) {
-		assert(!aval);
-		/* Either an error, or a is a subset with the same length so
-		 * must be equal.
-		 */
-		res = PyErr_Occurred() ? -1 : 0;
-		goto Finished;
-	}
-	bdiff = characterize(b, a, &bval);
-	if (bdiff == NULL && PyErr_Occurred()) {
-		assert(!bval);
-		res = -1;
-		goto Finished;
-	}
-	res = 0;
-	if (bdiff) {
-		/* bdiff == NULL "should be" impossible now, but perhaps
-		 * the last comparison done by the characterize() on a had
-		 * the side effect of making the dicts equal!
-		 */
-		res = PyObject_Compare(adiff, bdiff);
-	}
-	if (res == 0 && bval != NULL)
-		res = PyObject_Compare(aval, bval);
-
-Finished:
-	Py_XDECREF(adiff);
-	Py_XDECREF(bdiff);
-	Py_XDECREF(aval);
-	Py_XDECREF(bval);
-	return res;
-}
-
 /* Return 1 if dicts equal, 0 if not, -1 if error.
  * Gets out as soon as any difference is detected.
  * Uses only Py_EQ comparison.
@@ -1585,9 +1485,11 @@ dict_equal(dictobject *a, dictobject *b)
 			/* temporarily bump aval's refcount to ensure it stays
 			   alive until we're done with it */
 			Py_INCREF(aval);
-			bval = PyDict_GetItem((PyObject *)b, key);
+			bval = PyDict_GetItemWithError((PyObject *)b, key);
 			if (bval == NULL) {
 				Py_DECREF(aval);
+				if (PyErr_Occurred())
+					return -1;
 				return 0;
 			}
 			cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
@@ -2028,7 +1930,7 @@ PyTypeObject PyDict_Type = {
 	(printfunc)dict_print,			/* tp_print */
 	0,					/* tp_getattr */
 	0,					/* tp_setattr */
-	(cmpfunc)dict_compare,			/* tp_compare */
+	0,					/* tp_compare */
 	(reprfunc)dict_repr,			/* tp_repr */
 	0,					/* tp_as_number */
 	&dict_as_sequence,			/* tp_as_sequence */