[Python-checkins] cpython: Add documentation to the dict implementation

[victor.stinner]

https://hg.python.org/cpython/rev/378e000a6878
changeset:   103346:378e000a6878
user:        Victor Stinner <victor.stinner at gmail.com>
date:        Thu Sep 08 12:01:25 2016 -0700
summary:
  Add documentation to the dict implementation

Issue #27350.

files:
  Include/dictobject.h  |   9 ++++++
  Objects/dict-common.h |  43 +++++++++++++++++++++++++++++-
  Objects/dictobject.c  |   2 +-
  3 files changed, 51 insertions(+), 3 deletions(-)


diff --git a/Include/dictobject.h b/Include/dictobject.h
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -22,8 +22,17 @@
  */
 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
--- a/Objects/dict-common.h
+++ b/Objects/dict-common.h
@@ -22,11 +22,50 @@
 /* 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
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -593,7 +593,7 @@
 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

-- 
Repository URL: https://hg.python.org/cpython