[Python-checkins] python/dist/src/Include setobject.h,2.5,2.6

[rhettinger@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Include
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv27783/Include

Modified Files:
	setobject.h 
Log Message:
Revised the set() and frozenset() implementaion to use its own internal
data structure instead of using dictionaries.  Reduces memory consumption
by 1/3 and provides modest speed-ups for most set operations.



Index: setobject.h
===================================================================
RCS file: /cvsroot/python/python/dist/src/Include/setobject.h,v
retrieving revision 2.5
retrieving revision 2.6
diff -u -d -r2.5 -r2.6
--- setobject.h	28 Oct 2004 16:31:59 -0000	2.5
+++ setobject.h	31 Jul 2005 01:16:36 -0000	2.6
@@ -1,4 +1,3 @@
-
 /* Set object interface */
 
 #ifndef Py_SETOBJECT_H
@@ -7,28 +6,61 @@
 extern "C" {
 #endif
 
+
 /*
-This data structure is shared by set and frozenset objects.
+There are three kinds of slots in the table:
+
+1. Unused:  key == NULL
+2. Active:  key != NULL and key != dummy
+3. Dummy:   key == dummy
 */
 
+#define PySet_MINSIZE 8
+
 typedef struct {
+	long hash;      /* cached hash code for the entry key */
+	PyObject *key;
+} setentry;
+
+
+/*
+This data structure is shared by set and frozenset objects.
+*/
+
+typedef struct _setobject PySetObject;
+struct _setobject {
 	PyObject_HEAD
-	PyObject *data;
-	long hash;	/* only used by frozenset objects */
-	PyObject *weakreflist; /* List of weak references */
 
-	/* Invariants:
-	 *     data is a dictionary whose values are all True.
-	 *     data points to the same dict for the whole life of the set.
-	 * For frozensets only:
-	 *     data is immutable.
-	 *     hash is the hash of the frozenset or -1 if not computed yet.
+	int fill;  /* # Active + # Dummy */
+	int used;  /* # Active */
+
+	/* The table contains mask + 1 slots, and that's a power of 2.
+	 * We store the mask instead of the size because the mask is more
+	 * frequently needed.
 	 */
-} PySetObject;
+	int mask;
+
+	/* table points to smalltable for small tables, else to
+	 * additional malloc'ed memory.  table is never NULL!  This rule
+	 * saves repeated runtime null-tests in the workhorse getitem and
+	 * setitem calls.
+	 */
+	setentry *table;
+	setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
+	setentry smalltable[PySet_MINSIZE];
+
+	long hash;		/* only used by frozenset objects */
+	PyObject *weakreflist;	/* List of weak references */
+};
 
 PyAPI_DATA(PyTypeObject) PySet_Type;
 PyAPI_DATA(PyTypeObject) PyFrozenSet_Type;
 
+/* Invariants for frozensets only:
+ *     data is immutable.
+ *     hash is the hash of the frozenset or -1 if not computed yet.
+ */
+
 #define PyFrozenSet_CheckExact(ob) ((ob)->ob_type == &PyFrozenSet_Type)
 #define PyAnySet_Check(ob) \
 	((ob)->ob_type == &PySet_Type || (ob)->ob_type == &PyFrozenSet_Type || \