Add documentation to the dict implementation

vstinner · vstinner · commit a4348cc1bef6 · 2016-09-08T12:01:25.000-07:00
Issue #27350.
diff --git a/Include/dictobject.h b/Include/dictobject.h
@@ -22,8 +22,17 @@ typedef struct _dictkeysobject PyDictKeysObject;
  */
 typedef struct {
     PyObject_HEAD
+
+    /* Number of items in the dictionary */
     Py_ssize_t ma_used;
+
     PyDictKeysObject *ma_keys;
+
+    /* If ma_values is NULL, the table is "combined": keys and values
+       are stored in ma_keys (and ma_keys->dk_refcnt == 1).
+
+       If ma_values is not NULL, the table is splitted:
+       keys are stored in ma_keys and values are stored in ma_values */
     PyObject **ma_values;
 } PyDictObject;
 
diff --git a/Objects/dict-common.h b/Objects/dict-common.h
@@ -22,11 +22,50 @@ typedef Py_ssize_t (*dict_lookup_func)
 /* See dictobject.c for actual layout of DictKeysObject */
 struct _dictkeysobject {
     Py_ssize_t dk_refcnt;
+
+    /* Size of the hash table (dk_indices). It must be a power of 2. */
     Py_ssize_t dk_size;
+
+    /* Function to lookup in the hash table (dk_indices):
+
+       - lookdict(): general-purpose, and may return DKIX_ERROR if (and
+         only if) a comparison raises an exception.
+
+       - lookdict_unicode(): specialized to Unicode string keys, comparison of
+         which can never raise an exception; that function can never return
+         DKIX_ERROR.
+
+       - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
+         specialized for Unicode string keys that cannot be the <dummy> value.
+
+       - lookdict_split(): Version of lookdict() for split tables. */
     dict_lookup_func dk_lookup;
+
+    /* Number of usable entries in dk_entries.
+       0 <= dk_usable <= USABLE_FRACTION(dk_size) */
     Py_ssize_t dk_usable;
-    Py_ssize_t dk_nentries;  /* How many entries are used. */
-    char dk_indices[8];      /* dynamically sized. 8 is minimum. */
+
+    /* Number of used entries in dk_entries.
+       0 <= dk_nentries < dk_size */
+    Py_ssize_t dk_nentries;
+
+    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
+       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
+
+       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
+
+       The size in bytes of an indice depends on dk_size:
+
+       - 1 byte if dk_size <= 0xff (char*)
+       - 2 bytes if dk_size <= 0xffff (int16_t*)
+       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
+       - 8 bytes otherwise (Py_ssize_t*)
+
+       Dynamically sized, 8 is minimum. */
+    char dk_indices[8];
+
+    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
+       see the DK_ENTRIES() macro */
 };
 
 #endif
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
@@ -593,7 +593,7 @@ contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
 Christian Tismer.
 
 lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
-comparison raises an exception (this was new in Python 2.5).
+comparison raises an exception.
 lookdict_unicode() below is specialized to string keys, comparison of which can
 never raise an exception; that function can never return DKIX_ERROR.
 lookdict_unicode_nodummy is further specialized for string keys that cannot be
