Merge of descr-branch back into trunk.

1 files changed, 76 insertions, 1 deletions

diff --git a/Include/dictobject.h b/Include/dictobject.h
index 4f5f94a..abc8ed5 100644
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -7,9 +7,83 @@ extern "C" {
 
 /* Dictionary object type -- mapping from hashable object to object */
 
+/*
+There are three kinds of slots in the table:
+
+1. Unused.  me_key == me_value == NULL
+   Does not hold an active (key, value) pair now and never did.  Unused can
+   transition to Active upon key insertion.  This is the only case in which
+   me_key is NULL, and is each slot's initial state.
+
+2. Active.  me_key != NULL and me_key != dummy and me_value != NULL
+   Holds an active (key, value) pair.  Active can transition to Dummy upon
+   key deletion.  This is the only case in which me_value != NULL.
+
+3. Dummy.  me_key == dummy and me_value == NULL
+   Previously held an active (key, value) pair, but that was deleted and an
+   active pair has not yet overwritten the slot.  Dummy can transition to
+   Active upon key insertion.  Dummy slots cannot be made Unused again
+   (cannot have me_key set to NULL), else the probe sequence in case of
+   collision would have no way to know they were once active.
+
+Note: .popitem() abuses the me_hash field of an Unused or Dummy slot to
+hold a search finger.  The me_hash field of Unused or Dummy slots has no
+meaning otherwise.
+*/
+
+/* PyDict_MINSIZE is the minimum size of a dictionary.  This many slots are
+ * allocated directly in the dict object (in the ma_smalltable member).
+ * It must be a power of 2, and at least 4.  8 allows dicts with no more
+ * than 5 active entries to live in ma_smalltable (and so avoid an
+ * additional malloc); instrumentation suggested this suffices for the
+ * majority of dicts (consisting mostly of usually-small instance dicts and
+ * usually-small dicts created to pass keyword arguments).
+ */
+#define PyDict_MINSIZE 8
+
+typedef struct {
+	long me_hash;      /* cached hash code of me_key */
+	PyObject *me_key;
+	PyObject *me_value;
+#ifdef USE_CACHE_ALIGNED
+	long	aligner;
+#endif
+} PyDictEntry;
+
+/*
+To ensure the lookup algorithm terminates, there must be at least one Unused
+slot (NULL key) in the table.
+The value ma_fill is the number of non-NULL keys (sum of Active and Dummy);
+ma_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
+values == the number of Active items).
+To avoid slowing down lookups on a near-full table, we resize the table when
+it's two-thirds full.
+*/
+typedef struct _dictobject PyDictObject;
+struct _dictobject {
+	PyObject_HEAD
+	int ma_fill;  /* # Active + # Dummy */
+	int ma_used;  /* # Active */
+
+	/* The table contains ma_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.
+	 */
+	int ma_mask;
+
+	/* ma_table points to ma_smalltable for small tables, else to
+	 * additional malloc'ed memory.  ma_table is never NULL!  This rule
+	 * saves repeated runtime null-tests in the workhorse getitem and
+	 * setitem calls.
+	 */
+	PyDictEntry *ma_table;
+	PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
+	PyDictEntry ma_smalltable[PyDict_MINSIZE];
+};
+
 extern DL_IMPORT(PyTypeObject) PyDict_Type;
 
-#define PyDict_Check(op) ((op)->ob_type == &PyDict_Type)
+#define PyDict_Check(op) PyObject_TypeCheck(op, &PyDict_Type)
 
 extern DL_IMPORT(PyObject *) PyDict_New(void);
 extern DL_IMPORT(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
@@ -23,6 +97,7 @@ extern DL_IMPORT(PyObject *) PyDict_Values(PyObject *mp);
 extern DL_IMPORT(PyObject *) PyDict_Items(PyObject *mp);
 extern DL_IMPORT(int) PyDict_Size(PyObject *mp);
 extern DL_IMPORT(PyObject *) PyDict_Copy(PyObject *mp);
+extern DL_IMPORT(int) PyDict_Update(PyObject *mp, PyObject *other);
 
 
 extern DL_IMPORT(PyObject *) PyDict_GetItemString(PyObject *dp, char *key);