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 || \