Experimental new implementation of dictionary comparison. This

defines that a shorter dictionary is always smaller than a longer one.
For dictionaries of the same size, the smallest differing element
determines the outcome (which yields the same results as before,
without explicit sorting).

2 files changed, 126 insertions, 0 deletions

diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 274abda..023de8f 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -642,6 +642,67 @@ getmappingitems(mp)
 	return mapping_items((mappingobject *)mp, (object *)NULL);
 }
 
+#define NEWCMP
+
+#ifdef NEWCMP
+
+/* 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.  No reference counts are incremented. */
+
+static object *
+characterize(a, b, pval)
+	mappingobject *a;
+	mappingobject *b;
+	object **pval;
+{
+	object *diff = NULL;
+	int i;
+
+	*pval = NULL;
+	for (i = 0; i < a->ma_size; i++) {
+		if (a->ma_table[i].me_value != NULL) {
+			object *key = a->ma_table[i].me_key;
+			object *aval, *bval;
+			if (diff != NULL && cmpobject(key, diff) > 0)
+				continue;
+			aval = a->ma_table[i].me_value;
+			bval = mappinglookup((object *)b, key);
+			if (bval == NULL || cmpobject(aval, bval) != 0) {
+				diff = key;
+				*pval = aval;
+			}
+		}
+	}
+	return diff;
+}
+
+static int
+mapping_compare(a, b)
+	mappingobject *a, *b;
+{
+	object *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 */
+	adiff = characterize(a, b, &aval);
+	if (adiff == NULL)
+		return 0;	/* a is a subset with the same length */
+	bdiff = characterize(b, a, &bval);
+	/* bdiff == NULL would be impossible now */
+	res = cmpobject(adiff, bdiff);
+	if (res == 0)
+		res = cmpobject(aval, bval);
+	return res;
+}
+
+#else /* !NEWCMP */
+
 static int
 mapping_compare(a, b)
 	mappingobject *a, *b;
@@ -713,6 +774,8 @@ mapping_compare(a, b)
 	return res;
 }
 
+#endif /* !NEWCMP */
+
 static object *
 mapping_has_key(mp, args)
 	register mappingobject *mp;
diff --git a/Objects/mappingobject.c b/Objects/mappingobject.c
index 274abda..023de8f 100644
--- a/Objects/mappingobject.c
+++ b/Objects/mappingobject.c
@@ -642,6 +642,67 @@ getmappingitems(mp)
 	return mapping_items((mappingobject *)mp, (object *)NULL);
 }
 
+#define NEWCMP
+
+#ifdef NEWCMP
+
+/* 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.  No reference counts are incremented. */
+
+static object *
+characterize(a, b, pval)
+	mappingobject *a;
+	mappingobject *b;
+	object **pval;
+{
+	object *diff = NULL;
+	int i;
+
+	*pval = NULL;
+	for (i = 0; i < a->ma_size; i++) {
+		if (a->ma_table[i].me_value != NULL) {
+			object *key = a->ma_table[i].me_key;
+			object *aval, *bval;
+			if (diff != NULL && cmpobject(key, diff) > 0)
+				continue;
+			aval = a->ma_table[i].me_value;
+			bval = mappinglookup((object *)b, key);
+			if (bval == NULL || cmpobject(aval, bval) != 0) {
+				diff = key;
+				*pval = aval;
+			}
+		}
+	}
+	return diff;
+}
+
+static int
+mapping_compare(a, b)
+	mappingobject *a, *b;
+{
+	object *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 */
+	adiff = characterize(a, b, &aval);
+	if (adiff == NULL)
+		return 0;	/* a is a subset with the same length */
+	bdiff = characterize(b, a, &bval);
+	/* bdiff == NULL would be impossible now */
+	res = cmpobject(adiff, bdiff);
+	if (res == 0)
+		res = cmpobject(aval, bval);
+	return res;
+}
+
+#else /* !NEWCMP */
+
 static int
 mapping_compare(a, b)
 	mappingobject *a, *b;
@@ -713,6 +774,8 @@ mapping_compare(a, b)
 	return res;
 }
 
+#endif /* !NEWCMP */
+
 static object *
 mapping_has_key(mp, args)
 	register mappingobject *mp;