summaryrefslogtreecommitdiffstats
path: root/Include
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2005-07-31 01:16:36 (GMT)
committerRaymond Hettinger <python@rcn.com>2005-07-31 01:16:36 (GMT)
commit9f1a6796eb83a2884df5fd93487634e46d8830a7 (patch)
tree53e9ef211666eb6f534d0d5040969146fdaeee0e /Include
parentfe256431922c44375fa1e6c21bca69f5cb65481d (diff)
downloadcpython-9f1a6796eb83a2884df5fd93487634e46d8830a7.zip
cpython-9f1a6796eb83a2884df5fd93487634e46d8830a7.tar.gz
cpython-9f1a6796eb83a2884df5fd93487634e46d8830a7.tar.bz2
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.
Diffstat (limited to 'Include')
-rw-r--r--Include/setobject.h58
1 files changed, 45 insertions, 13 deletions
diff --git a/Include/setobject.h b/Include/setobject.h
index cc2d683..8569ed1 100644
--- a/Include/setobject.h
+++ b/Include/setobject.h
@@ -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 || \