Generalized version of dictionaries, with compatibility hacks.

1 files changed, 705 insertions, 0 deletions

diff --git a/Objects/mappingobject.c b/Objects/mappingobject.c
new file mode 100644
index 0000000..1cfa308
--- /dev/null
+++ b/Objects/mappingobject.c
@@ -0,0 +1,705 @@
+/***********************************************************
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
+
+                        All Rights Reserved
+
+Permission to use, copy, modify, and distribute this software and its 
+documentation for any purpose and without fee is hereby granted, 
+provided that the above copyright notice appear in all copies and that
+both that copyright notice and this permission notice appear in 
+supporting documentation, and that the names of Stichting Mathematisch
+Centrum or CWI not be used in advertising or publicity pertaining to
+distribution of the software without specific, written prior permission.
+
+STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
+THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
+FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
+OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+******************************************************************/
+
+/* Mapping object implementation; using a hash table */
+
+#include "allobjects.h"
+#include "mappingobject.h"
+#include "modsupport.h"
+
+
+/*
+Table of primes suitable as keys, in ascending order.
+The first line are the largest primes less than some powers of two,
+the second line is the largest prime less than 6000,
+and the third line is a selection from Knuth, Vol. 3, Sec. 6.1, Table 1.
+The final value is a sentinel and should cause the memory allocation
+of that many entries to fail (if none of the earlier values cause such
+failure already).
+*/
+static unsigned int primes[] = {
+	3, 7, 13, 31, 61, 127, 251, 509, 1021, 2017, 4093,
+	5987,
+	9551, 15683, 19609, 31397,
+	0xffffffff /* All bits set -- truncation OK */
+};
+
+/* Object used as dummy key to fill deleted entries */
+static object *dummy; /* Initialized by first call to newmappingobject() */
+
+/*
+Invariant for entries: when in use, de_value is not NULL and de_key is
+not NULL and not dummy; when not in use, de_value is NULL and de_key
+is either NULL or dummy.  A dummy key value cannot be replaced by
+NULL, since otherwise other keys may be lost.
+*/
+typedef struct {
+	long me_hash;
+	object *me_key;
+	object *me_value;
+} mappingentry;
+
+/*
+To ensure the lookup algorithm terminates, the table size must be a
+prime number and there must be at least one NULL key in the table.
+The value ma_fill is the number of non-NULL keys; ma_used is the number
+of non-NULL, non-dummy keys.
+To avoid slowing down lookups on a near-full table, we resize the table
+when it is more than half filled.
+*/
+typedef struct {
+	OB_HEAD
+	int ma_fill;
+	int ma_used;
+	int ma_size;
+	mappingentry *ma_table;
+} mappingobject;
+
+object *
+newmappingobject()
+{
+	register mappingobject *mp;
+	if (dummy == NULL) { /* Auto-initialize dummy */
+		dummy = newstringobject("<dummy key>");
+		if (dummy == NULL)
+			return NULL;
+	}
+	mp = NEWOBJ(mappingobject, &Mappingtype);
+	if (mp == NULL)
+		return NULL;
+	mp->ma_size = primes[0];
+	mp->ma_table = (mappingentry *) calloc(sizeof(mappingentry), mp->ma_size);
+	if (mp->ma_table == NULL) {
+		DEL(mp);
+		return err_nomem();
+	}
+	mp->ma_fill = 0;
+	mp->ma_used = 0;
+	return (object *)mp;
+}
+
+/*
+The basic lookup function used by all operations.
+This is essentially Algorithm D from Knuth Vol. 3, Sec. 6.4.
+Open addressing is preferred over chaining since the link overhead for
+chaining would be substantial (100% with typical malloc overhead).
+
+First a 32-bit hash value, 'sum', is computed from the key string.
+The first character is added an extra time shifted by 8 to avoid hashing
+single-character keys (often heavily used variables) too close together.
+All arithmetic on sum should ignore overflow.
+
+The initial probe index is then computed as sum mod the table size.
+Subsequent probe indices are incr apart (mod table size), where incr
+is also derived from sum, with the additional requirement that it is
+relative prime to the table size (i.e., 1 <= incr < size, since the size
+is a prime number).  My choice for incr is somewhat arbitrary.
+*/
+static mappingentry *lookmapping PROTO((mappingobject *, object *, long));
+static mappingentry *
+lookmapping(mp, key, hash)
+	register mappingobject *mp;
+	object *key;
+	long hash;
+{
+	register int i, incr;
+	register unsigned long sum = (unsigned long) hash;
+	register mappingentry *freeslot = NULL;
+	/* We must come up with (i, incr) such that 0 <= i < ma_size
+	   and 0 < incr < ma_size and both are a function of hash */
+	i = sum % mp->ma_size;
+	do {
+		sum = sum + sum + sum + 1;
+		incr = sum % mp->ma_size;
+	} while (incr == 0);
+	for (;;) {
+		register mappingentry *ep = &mp->ma_table[i];
+		if (ep->me_key == NULL) {
+			if (freeslot != NULL)
+				return freeslot;
+			else
+				return ep;
+		}
+		if (ep->me_key == dummy) {
+			if (freeslot != NULL)
+				freeslot = ep;
+		}
+		else if (ep->me_hash == hash &&
+			 cmpobject(ep->me_key, key) == 0) {
+			return ep;
+		}
+		i = (i + incr) % mp->ma_size;
+	}
+}
+
+/*
+Internal routine to insert a new item into the table.
+Used both by the internal resize routine and by the public insert routine.
+Eats a reference to key and one to value.
+*/
+static void insertmapping PROTO((mappingobject *, object *, long, object *));
+static void
+insertmapping(mp, key, hash, value)
+	register mappingobject *mp;
+	object *key;
+	long hash;
+	object *value;
+{
+	register mappingentry *ep;
+	ep = lookmapping(mp, key, hash);
+	if (ep->me_value != NULL) {
+		DECREF(ep->me_value);
+		DECREF(key);
+	}
+	else {
+		if (ep->me_key == NULL)
+			mp->ma_fill++;
+		else
+			DECREF(ep->me_key);
+		ep->me_key = key;
+		ep->me_hash = hash;
+		mp->ma_used++;
+	}
+	ep->me_value = value;
+}
+
+/*
+Restructure the table by allocating a new table and reinserting all
+items again.  When entries have been deleted, the new table may
+actually be smaller than the old one.
+*/
+static int mappingresize PROTO((mappingobject *));
+static int
+mappingresize(mp)
+	mappingobject *mp;
+{
+	register int oldsize = mp->ma_size;
+	register int newsize;
+	register mappingentry *oldtable = mp->ma_table;
+	register mappingentry *newtable;
+	register mappingentry *ep;
+	register int i;
+	newsize = mp->ma_size;
+	for (i = 0; ; i++) {
+		if (primes[i] > mp->ma_used*2) {
+			newsize = primes[i];
+			break;
+		}
+	}
+	newtable = (mappingentry *) calloc(sizeof(mappingentry), newsize);
+	if (newtable == NULL) {
+		err_nomem();
+		return -1;
+	}
+	mp->ma_size = newsize;
+	mp->ma_table = newtable;
+	mp->ma_fill = 0;
+	mp->ma_used = 0;
+	for (i = 0, ep = oldtable; i < oldsize; i++, ep++) {
+		if (ep->me_value != NULL)
+			insertmapping(mp,ep->me_key,ep->me_hash,ep->me_value);
+		else {
+			XDECREF(ep->me_key);
+		}
+	}
+	DEL(oldtable);
+	return 0;
+}
+
+object *
+mappinglookup(op, key)
+	object *op;
+	object *key;
+{
+	long hash;
+	if (!is_mappingobject(op)) {
+		err_badcall();
+		return NULL;
+	}
+	hash = hashobject(key);
+	if (hash == -1)
+		return NULL;
+	return lookmapping((mappingobject *)op, key, hash) -> me_value;
+}
+
+int
+mappinginsert(op, key, value)
+	register object *op;
+	object *key;
+	object *value;
+{
+	register mappingobject *mp;
+	register long hash;
+	if (!is_mappingobject(op)) {
+		err_badcall();
+		return -1;
+	}
+	hash = hashobject(key);
+	if (hash == -1)
+		return -1;
+	mp = (mappingobject *)op;
+	/* if fill >= 2/3 size, resize */
+	if (mp->ma_fill*3 >= mp->ma_size*2) {
+		if (mappingresize(mp) != 0) {
+			if (mp->ma_fill+1 > mp->ma_size)
+				return -1;
+		}
+	}
+	INCREF(value);
+	INCREF(key);
+	insertmapping(mp, key, hash, value);
+	return 0;
+}
+
+int
+mappingremove(op, key)
+	object *op;
+	object *key;
+{
+	register mappingobject *mp;
+	register long hash;
+	register mappingentry *ep;
+	if (!is_mappingobject(op)) {
+		err_badcall();
+		return -1;
+	}
+	hash = hashobject(key);
+	if (hash == -1)
+		return -1;
+	mp = (mappingobject *)op;
+	ep = lookmapping(mp, key, hash);
+	if (ep->me_value == NULL) {
+		err_setval(KeyError, key);
+		return -1;
+	}
+	DECREF(ep->me_key);
+	INCREF(dummy);
+	ep->me_key = dummy;
+	DECREF(ep->me_value);
+	ep->me_value = NULL;
+	mp->ma_used--;
+	return 0;
+}
+
+int
+getmappingsize(op)
+	register object *op;
+{
+	if (!is_mappingobject(op)) {
+		err_badcall();
+		return -1;
+	}
+	return ((mappingobject *)op) -> ma_size;
+}
+
+object *
+getmappingkey(op, i)
+	object *op;
+	register int i;
+{
+	/* XXX This can't return errors since its callers assume
+	   that NULL means there was no key at that point */
+	register mappingobject *mp;
+	if (!is_mappingobject(op)) {
+		/* err_badcall(); */
+		return NULL;
+	}
+	mp = (mappingobject *)op;
+	if (i < 0 || i >= mp->ma_size) {
+		/* err_badarg(); */
+		return NULL;
+	}
+	if (mp->ma_table[i].me_value == NULL) {
+		/* Not an error! */
+		return NULL;
+	}
+	return (object *) mp->ma_table[i].me_key;
+}
+
+/* Methods */
+
+static void
+mapping_dealloc(mp)
+	register mappingobject *mp;
+{
+	register int i;
+	register mappingentry *ep;
+	for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
+		if (ep->me_key != NULL)
+			DECREF(ep->me_key);
+		if (ep->me_value != NULL)
+			DECREF(ep->me_value);
+	}
+	if (mp->ma_table != NULL)
+		DEL(mp->ma_table);
+	DEL(mp);
+}
+
+static int
+mapping_print(mp, fp, flags)
+	register mappingobject *mp;
+	register FILE *fp;
+	register int flags;
+{
+	register int i;
+	register int any;
+	register mappingentry *ep;
+	fprintf(fp, "{");
+	any = 0;
+	for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
+		if (ep->me_value != NULL) {
+			if (any++ > 0)
+				fprintf(fp, ", ");
+			if (printobject((object *)ep->me_key, fp, flags) != 0)
+				return -1;
+			fprintf(fp, ": ");
+			if (printobject(ep->me_value, fp, flags) != 0)
+				return -1;
+		}
+	}
+	fprintf(fp, "}");
+	return 0;
+}
+
+static void
+js(pv, w)
+	object **pv;
+	object *w;
+{
+	joinstring(pv, w);
+	XDECREF(w);
+}
+
+static object *
+mapping_repr(mp)
+	mappingobject *mp;
+{
+	auto object *v;
+	object *sepa, *colon;
+	register int i;
+	register int any;
+	register mappingentry *ep;
+	v = newstringobject("{");
+	sepa = newstringobject(", ");
+	colon = newstringobject(": ");
+	any = 0;
+	for (i = 0, ep = mp->ma_table; i < mp->ma_size; i++, ep++) {
+		if (ep->me_value != NULL) {
+			if (any++)
+				joinstring(&v, sepa);
+			js(&v, reprobject(ep->me_key));
+			joinstring(&v, colon);
+			js(&v, reprobject(ep->me_value));
+		}
+	}
+	js(&v, newstringobject("}"));
+	XDECREF(sepa);
+	XDECREF(colon);
+	return v;
+}
+
+static int
+mapping_length(mp)
+	mappingobject *mp;
+{
+	return mp->ma_used;
+}
+
+static object *
+mapping_subscript(mp, key)
+	mappingobject *mp;
+	register object *key;
+{
+	object *v;
+	long hash = hashobject(key);
+	if (hash == -1)
+		return NULL;
+	v = lookmapping(mp, key, hash) -> me_value;
+	if (v == NULL)
+		err_setval(KeyError, key);
+	else
+		INCREF(v);
+	return v;
+}
+
+static int
+mapping_ass_sub(mp, v, w)
+	mappingobject *mp;
+	object *v, *w;
+{
+	if (w == NULL)
+		return mappingremove((object *)mp, v);
+	else
+		return mappinginsert((object *)mp, v, w);
+}
+
+static mapping_methods mapping_as_mapping = {
+	mapping_length,	/*mp_length*/
+	mapping_subscript,	/*mp_subscript*/
+	mapping_ass_sub,	/*mp_ass_subscript*/
+};
+
+static object *
+mapping_keys(mp, args)
+	register mappingobject *mp;
+	object *args;
+{
+	register object *v;
+	register int i, j;
+	if (!getnoarg(args))
+		return NULL;
+	v = newlistobject(mp->ma_used);
+	if (v == NULL)
+		return NULL;
+	for (i = 0, j = 0; i < mp->ma_size; i++) {
+		if (mp->ma_table[i].me_value != NULL) {
+			object *key = mp->ma_table[i].me_key;
+			INCREF(key);
+			setlistitem(v, j, key);
+			j++;
+		}
+	}
+	return v;
+}
+
+object *
+getmappingkeys(mp)
+	object *mp;
+{
+	if (mp == NULL || !is_mappingobject(mp)) {
+		err_badcall();
+		return NULL;
+	}
+	return mapping_keys((mappingobject *)mp, (object *)NULL);
+}
+
+static int
+mapping_compare(a, b)
+	mappingobject *a, *b;
+{
+	object *akeys, *bkeys;
+	int i, n, res;
+	if (a == b)
+		return 0;
+	if (a->ma_used == 0) {
+		if (b->ma_used != 0)
+			return -1;
+		else
+			return 0;
+	}
+	else {
+		if (b->ma_used == 0)
+			return 1;
+	}
+	akeys = mapping_keys(a, (object *)NULL);
+	bkeys = mapping_keys(b, (object *)NULL);
+	if (akeys == NULL || bkeys == NULL) {
+		/* Oops, out of memory -- what to do? */
+		/* For now, sort on address! */
+		XDECREF(akeys);
+		XDECREF(bkeys);
+		if (a < b)
+			return -1;
+		else
+			return 1;
+	}
+	sortlist(akeys);
+	sortlist(bkeys);
+	n = a->ma_used < b->ma_used ? a->ma_used : b->ma_used; /* smallest */
+	res = 0;
+	for (i = 0; i < n; i++) {
+		object *akey, *bkey, *aval, *bval;
+		long ahash, bhash;
+		akey = getlistitem(akeys, i);
+		bkey = getlistitem(bkeys, i);
+		res = cmpobject(akey, bkey);
+		if (res != 0)
+			break;
+		ahash = hashobject(akey);
+		if (ahash == -1)
+			err_clear(); /* Don't want errors here */
+		bhash = hashobject(bkey);
+		if (bhash == -1)
+			err_clear(); /* Don't want errors here */
+		aval = lookmapping(a, akey, ahash) -> me_value;
+		bval = lookmapping(b, bkey, bhash) -> me_value;
+		res = cmpobject(aval, bval);
+		if (res != 0)
+			break;
+	}
+	if (res == 0) {
+		if (a->ma_used < b->ma_used)
+			res = -1;
+		else if (a->ma_used > b->ma_used)
+			res = 1;
+	}
+	DECREF(akeys);
+	DECREF(bkeys);
+	return res;
+}
+
+static object *
+mapping_has_key(mp, args)
+	register mappingobject *mp;
+	object *args;
+{
+	object *key;
+	long hash;
+	register long ok;
+	if (!getargs(args, "O", &key))
+		return NULL;
+	hash = hashobject(key);
+	if (hash == -1)
+		return NULL;
+	ok = lookmapping(mp, key, hash)->me_value != NULL;
+	return newintobject(ok);
+}
+
+static struct methodlist mapp_methods[] = {
+	{"keys",	mapping_keys},
+	{"has_key",	mapping_has_key},
+	{NULL,		NULL}		/* sentinel */
+};
+
+static object *
+mapping_getattr(mp, name)
+	mappingobject *mp;
+	char *name;
+{
+	return findmethod(mapp_methods, (object *)mp, name);
+}
+
+typeobject Mappingtype = {
+	OB_HEAD_INIT(&Typetype)
+	0,
+	"mapping",
+	sizeof(mappingobject),
+	0,
+	mapping_dealloc,	/*tp_dealloc*/
+	mapping_print,		/*tp_print*/
+	mapping_getattr,	/*tp_getattr*/
+	0,			/*tp_setattr*/
+	mapping_compare,	/*tp_compare*/
+	mapping_repr,		/*tp_repr*/
+	0,			/*tp_as_number*/
+	0,			/*tp_as_sequence*/
+	&mapping_as_mapping,	/*tp_as_mapping*/
+};
+
+/* For backward compatibility with old dictionary interface */
+
+static object *last_name_object;
+static char *last_name_char;
+
+object *
+getattro(v, name)
+	object *v;
+	object *name;
+{
+	if (name != last_name_object) {
+		XDECREF(last_name_object);
+		INCREF(name);
+		last_name_object = name;
+		last_name_char = getstringvalue(name);
+	}
+	return getattr(v, last_name_char);
+}
+
+int
+setattro(v, name, value)
+	object *v;
+	object *name;
+	object *value;
+{
+	if (name != last_name_object) {
+		XDECREF(last_name_object);
+		INCREF(name);
+		last_name_object = name;
+		last_name_char = getstringvalue(name);
+	}
+	return setattr(v, last_name_char, value);
+}
+
+object *
+dictlookup(v, key)
+	object *v;
+	char *key;
+{
+	if (key != last_name_char) {
+		XDECREF(last_name_object);
+		last_name_object = newstringobject(key);
+		if (last_name_object == NULL) {
+			last_name_char = NULL;
+			return NULL;
+		}
+		last_name_char = key;
+	}
+	return mappinglookup(v, last_name_object);
+}
+
+int
+dictinsert(v, key, item)
+	object *v;
+	char *key;
+	object *item;
+{
+	if (key != last_name_char) {
+		XDECREF(last_name_object);
+		last_name_object = newstringobject(key);
+		if (last_name_object == NULL) {
+			last_name_char = NULL;
+			return NULL;
+		}
+		last_name_char = key;
+	}
+	return mappinginsert(v, last_name_object, item);
+}
+
+int
+dictremove(v, key)
+	object *v;
+	char *key;
+{
+	if (key != last_name_char) {
+		XDECREF(last_name_object);
+		last_name_object = newstringobject(key);
+		if (last_name_object == NULL) {
+			last_name_char = NULL;
+			return NULL;
+		}
+		last_name_char = key;
+	}
+	return mappingremove(v, last_name_object);
+}
+
+char *
+getdictkey(v, i)
+	object *v;
+	int i;
+{
+	object *key = getmappingkey(v, i);
+	if (key == NULL)
+		return NULL;
+	return getstringvalue(key);
+}