--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/symbian-qemu-0.9.1-12/python-2.6.1/Objects/dictobject.c Fri Jul 31 15:01:17 2009 +0100
@@ -0,0 +1,2606 @@
+
+/* Dictionary object implementation using a hash table */
+
+/* The distribution includes a separate file, Objects/dictnotes.txt,
+ describing explorations into dictionary design and optimization.
+ It covers typical dictionary use patterns, the parameters for
+ tuning dictionaries, and several ideas for possible optimizations.
+*/
+
+#include "Python.h"
+
+
+/* Set a key error with the specified argument, wrapping it in a
+ * tuple automatically so that tuple keys are not unpacked as the
+ * exception arguments. */
+static void
+set_key_error(PyObject *arg)
+{
+ PyObject *tup;
+ tup = PyTuple_Pack(1, arg);
+ if (!tup)
+ return; /* caller will expect error to be set anyway */
+ PyErr_SetObject(PyExc_KeyError, tup);
+ Py_DECREF(tup);
+}
+
+/* Define this out if you don't want conversion statistics on exit. */
+#undef SHOW_CONVERSION_COUNTS
+
+/* See large comment block below. This must be >= 1. */
+#define PERTURB_SHIFT 5
+
+/*
+Major subtleties ahead: Most hash schemes depend on having a "good" hash
+function, in the sense of simulating randomness. Python doesn't: its most
+important hash functions (for strings and ints) are very regular in common
+cases:
+
+>>> map(hash, (0, 1, 2, 3))
+[0, 1, 2, 3]
+>>> map(hash, ("namea", "nameb", "namec", "named"))
+[-1658398457, -1658398460, -1658398459, -1658398462]
+>>>
+
+This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
+the low-order i bits as the initial table index is extremely fast, and there
+are no collisions at all for dicts indexed by a contiguous range of ints.
+The same is approximately true when keys are "consecutive" strings. So this
+gives better-than-random behavior in common cases, and that's very desirable.
+
+OTOH, when collisions occur, the tendency to fill contiguous slices of the
+hash table makes a good collision resolution strategy crucial. Taking only
+the last i bits of the hash code is also vulnerable: for example, consider
+[i << 16 for i in range(20000)] as a set of keys. Since ints are their own
+hash codes, and this fits in a dict of size 2**15, the last 15 bits of every
+hash code are all 0: they *all* map to the same table index.
+
+But catering to unusual cases should not slow the usual ones, so we just take
+the last i bits anyway. It's up to collision resolution to do the rest. If
+we *usually* find the key we're looking for on the first try (and, it turns
+out, we usually do -- the table load factor is kept under 2/3, so the odds
+are solidly in our favor), then it makes best sense to keep the initial index
+computation dirt cheap.
+
+The first half of collision resolution is to visit table indices via this
+recurrence:
+
+ j = ((5*j) + 1) mod 2**i
+
+For any initial j in range(2**i), repeating that 2**i times generates each
+int in range(2**i) exactly once (see any text on random-number generation for
+proof). By itself, this doesn't help much: like linear probing (setting
+j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
+order. This would be bad, except that's not the only thing we do, and it's
+actually *good* in the common cases where hash keys are consecutive. In an
+example that's really too small to make this entirely clear, for a table of
+size 2**3 the order of indices is:
+
+ 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
+
+If two things come in at index 5, the first place we look after is index 2,
+not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
+Linear probing is deadly in this case because there the fixed probe order
+is the *same* as the order consecutive keys are likely to arrive. But it's
+extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
+and certain that consecutive hash codes do not.
+
+The other half of the strategy is to get the other bits of the hash code
+into play. This is done by initializing a (unsigned) vrbl "perturb" to the
+full hash code, and changing the recurrence to:
+
+ j = (5*j) + 1 + perturb;
+ perturb >>= PERTURB_SHIFT;
+ use j % 2**i as the next table index;
+
+Now the probe sequence depends (eventually) on every bit in the hash code,
+and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
+because it quickly magnifies small differences in the bits that didn't affect
+the initial index. Note that because perturb is unsigned, if the recurrence
+is executed often enough perturb eventually becomes and remains 0. At that
+point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
+that's certain to find an empty slot eventually (since it generates every int
+in range(2**i), and we make sure there's always at least one empty slot).
+
+Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
+small so that the high bits of the hash code continue to affect the probe
+sequence across iterations; but you want it large so that in really bad cases
+the high-order hash bits have an effect on early iterations. 5 was "the
+best" in minimizing total collisions across experiments Tim Peters ran (on
+both normal and pathological cases), but 4 and 6 weren't significantly worse.
+
+Historical: Reimer Behrends contributed the idea of using a polynomial-based
+approach, using repeated multiplication by x in GF(2**n) where an irreducible
+polynomial for each table size was chosen such that x was a primitive root.
+Christian Tismer later extended that to use division by x instead, as an
+efficient way to get the high bits of the hash code into play. This scheme
+also gave excellent collision statistics, but was more expensive: two
+if-tests were required inside the loop; computing "the next" index took about
+the same number of operations but without as much potential parallelism
+(e.g., computing 5*j can go on at the same time as computing 1+perturb in the
+above, and then shifting perturb can be done while the table index is being
+masked); and the PyDictObject struct required a member to hold the table's
+polynomial. In Tim's experiments the current scheme ran faster, produced
+equally good collision statistics, needed less code & used less memory.
+
+Theoretical Python 2.5 headache: hash codes are only C "long", but
+sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a
+dict is genuinely huge, then only the slots directly reachable via indexing
+by a C long can be the first slot in a probe sequence. The probe sequence
+will still eventually reach every slot in the table, but the collision rate
+on initial probes may be much higher than this scheme was designed for.
+Getting a hash code as fat as Py_ssize_t is the only real cure. But in
+practice, this probably won't make a lick of difference for many years (at
+which point everyone will have terabytes of RAM on 64-bit boxes).
+*/
+
+/* Object used as dummy key to fill deleted entries */
+static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */
+
+#ifdef Py_REF_DEBUG
+PyObject *
+_PyDict_Dummy(void)
+{
+ return dummy;
+}
+#endif
+
+/* forward declarations */
+static PyDictEntry *
+lookdict_string(PyDictObject *mp, PyObject *key, long hash);
+
+#ifdef SHOW_CONVERSION_COUNTS
+static long created = 0L;
+static long converted = 0L;
+
+static void
+show_counts(void)
+{
+ fprintf(stderr, "created %ld string dicts\n", created);
+ fprintf(stderr, "converted %ld to normal dicts\n", converted);
+ fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);
+}
+#endif
+
+/* Debug statistic to compare allocations with reuse through the free list */
+#undef SHOW_ALLOC_COUNT
+#ifdef SHOW_ALLOC_COUNT
+static size_t count_alloc = 0;
+static size_t count_reuse = 0;
+
+static void
+show_alloc(void)
+{
+ fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",
+ count_alloc);
+ fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
+ "d\n", count_reuse);
+ fprintf(stderr, "%.2f%% reuse rate\n\n",
+ (100.0*count_reuse/(count_alloc+count_reuse)));
+}
+#endif
+
+/* Initialization macros.
+ There are two ways to create a dict: PyDict_New() is the main C API
+ function, and the tp_new slot maps to dict_new(). In the latter case we
+ can save a little time over what PyDict_New does because it's guaranteed
+ that the PyDictObject struct is already zeroed out.
+ Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
+ an excellent reason not to).
+*/
+
+#define INIT_NONZERO_DICT_SLOTS(mp) do { \
+ (mp)->ma_table = (mp)->ma_smalltable; \
+ (mp)->ma_mask = PyDict_MINSIZE - 1; \
+ } while(0)
+
+#define EMPTY_TO_MINSIZE(mp) do { \
+ memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
+ (mp)->ma_used = (mp)->ma_fill = 0; \
+ INIT_NONZERO_DICT_SLOTS(mp); \
+ } while(0)
+
+/* Dictionary reuse scheme to save calls to malloc, free, and memset */
+#ifndef PyDict_MAXFREELIST
+#define PyDict_MAXFREELIST 80
+#endif
+static PyDictObject *free_list[PyDict_MAXFREELIST];
+static int numfree = 0;
+
+void
+PyDict_Fini(void)
+{
+ PyDictObject *op;
+
+ while (numfree) {
+ op = free_list[--numfree];
+ assert(PyDict_CheckExact(op));
+ PyObject_GC_Del(op);
+ }
+}
+
+PyObject *
+PyDict_New(void)
+{
+ register PyDictObject *mp;
+ if (dummy == NULL) { /* Auto-initialize dummy */
+ dummy = PyString_FromString("<dummy key>");
+ if (dummy == NULL)
+ return NULL;
+#ifdef SHOW_CONVERSION_COUNTS
+ Py_AtExit(show_counts);
+#endif
+#ifdef SHOW_ALLOC_COUNT
+ Py_AtExit(show_alloc);
+#endif
+ }
+ if (numfree) {
+ mp = free_list[--numfree];
+ assert (mp != NULL);
+ assert (Py_TYPE(mp) == &PyDict_Type);
+ _Py_NewReference((PyObject *)mp);
+ if (mp->ma_fill) {
+ EMPTY_TO_MINSIZE(mp);
+ } else {
+ /* At least set ma_table and ma_mask; these are wrong
+ if an empty but presized dict is added to freelist */
+ INIT_NONZERO_DICT_SLOTS(mp);
+ }
+ assert (mp->ma_used == 0);
+ assert (mp->ma_table == mp->ma_smalltable);
+ assert (mp->ma_mask == PyDict_MINSIZE - 1);
+#ifdef SHOW_ALLOC_COUNT
+ count_reuse++;
+#endif
+ } else {
+ mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
+ if (mp == NULL)
+ return NULL;
+ EMPTY_TO_MINSIZE(mp);
+#ifdef SHOW_ALLOC_COUNT
+ count_alloc++;
+#endif
+ }
+ mp->ma_lookup = lookdict_string;
+#ifdef SHOW_CONVERSION_COUNTS
+ ++created;
+#endif
+ _PyObject_GC_TRACK(mp);
+ return (PyObject *)mp;
+}
+
+/*
+The basic lookup function used by all operations.
+This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
+Open addressing is preferred over chaining since the link overhead for
+chaining would be substantial (100% with typical malloc overhead).
+
+The initial probe index is computed as hash mod the table size. Subsequent
+probe indices are computed as explained earlier.
+
+All arithmetic on hash should ignore overflow.
+
+(The details in this version are due to Tim Peters, building on many past
+contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
+Christian Tismer).
+
+lookdict() is general-purpose, and may return NULL if (and only if) a
+comparison raises an exception (this was new in Python 2.5).
+lookdict_string() below is specialized to string keys, comparison of which can
+never raise an exception; that function can never return NULL. For both, when
+the key isn't found a PyDictEntry* is returned for which the me_value field is
+NULL; this is the slot in the dict at which the key would have been found, and
+the caller can (if it wishes) add the <key, value> pair to the returned
+PyDictEntry*.
+*/
+static PyDictEntry *
+lookdict(PyDictObject *mp, PyObject *key, register long hash)
+{
+ register size_t i;
+ register size_t perturb;
+ register PyDictEntry *freeslot;
+ register size_t mask = (size_t)mp->ma_mask;
+ PyDictEntry *ep0 = mp->ma_table;
+ register PyDictEntry *ep;
+ register int cmp;
+ PyObject *startkey;
+
+ i = (size_t)hash & mask;
+ ep = &ep0[i];
+ if (ep->me_key == NULL || ep->me_key == key)
+ return ep;
+
+ if (ep->me_key == dummy)
+ freeslot = ep;
+ else {
+ if (ep->me_hash == hash) {
+ startkey = ep->me_key;
+ Py_INCREF(startkey);
+ cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+ Py_DECREF(startkey);
+ if (cmp < 0)
+ return NULL;
+ if (ep0 == mp->ma_table && ep->me_key == startkey) {
+ if (cmp > 0)
+ return ep;
+ }
+ else {
+ /* The compare did major nasty stuff to the
+ * dict: start over.
+ * XXX A clever adversary could prevent this
+ * XXX from terminating.
+ */
+ return lookdict(mp, key, hash);
+ }
+ }
+ freeslot = NULL;
+ }
+
+ /* In the loop, me_key == dummy is by far (factor of 100s) the
+ least likely outcome, so test for that last. */
+ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
+ i = (i << 2) + i + perturb + 1;
+ ep = &ep0[i & mask];
+ if (ep->me_key == NULL)
+ return freeslot == NULL ? ep : freeslot;
+ if (ep->me_key == key)
+ return ep;
+ if (ep->me_hash == hash && ep->me_key != dummy) {
+ startkey = ep->me_key;
+ Py_INCREF(startkey);
+ cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+ Py_DECREF(startkey);
+ if (cmp < 0)
+ return NULL;
+ if (ep0 == mp->ma_table && ep->me_key == startkey) {
+ if (cmp > 0)
+ return ep;
+ }
+ else {
+ /* The compare did major nasty stuff to the
+ * dict: start over.
+ * XXX A clever adversary could prevent this
+ * XXX from terminating.
+ */
+ return lookdict(mp, key, hash);
+ }
+ }
+ else if (ep->me_key == dummy && freeslot == NULL)
+ freeslot = ep;
+ }
+ assert(0); /* NOT REACHED */
+ return 0;
+}
+
+/*
+ * Hacked up version of lookdict which can assume keys are always strings;
+ * this assumption allows testing for errors during PyObject_RichCompareBool()
+ * to be dropped; string-string comparisons never raise exceptions. This also
+ * means we don't need to go through PyObject_RichCompareBool(); we can always
+ * use _PyString_Eq() directly.
+ *
+ * This is valuable because dicts with only string keys are very common.
+ */
+static PyDictEntry *
+lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
+{
+ register size_t i;
+ register size_t perturb;
+ register PyDictEntry *freeslot;
+ register size_t mask = (size_t)mp->ma_mask;
+ PyDictEntry *ep0 = mp->ma_table;
+ register PyDictEntry *ep;
+
+ /* Make sure this function doesn't have to handle non-string keys,
+ including subclasses of str; e.g., one reason to subclass
+ strings is to override __eq__, and for speed we don't cater to
+ that here. */
+ if (!PyString_CheckExact(key)) {
+#ifdef SHOW_CONVERSION_COUNTS
+ ++converted;
+#endif
+ mp->ma_lookup = lookdict;
+ return lookdict(mp, key, hash);
+ }
+ i = hash & mask;
+ ep = &ep0[i];
+ if (ep->me_key == NULL || ep->me_key == key)
+ return ep;
+ if (ep->me_key == dummy)
+ freeslot = ep;
+ else {
+ if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
+ return ep;
+ freeslot = NULL;
+ }
+
+ /* In the loop, me_key == dummy is by far (factor of 100s) the
+ least likely outcome, so test for that last. */
+ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
+ i = (i << 2) + i + perturb + 1;
+ ep = &ep0[i & mask];
+ if (ep->me_key == NULL)
+ return freeslot == NULL ? ep : freeslot;
+ if (ep->me_key == key
+ || (ep->me_hash == hash
+ && ep->me_key != dummy
+ && _PyString_Eq(ep->me_key, key)))
+ return ep;
+ if (ep->me_key == dummy && freeslot == NULL)
+ freeslot = ep;
+ }
+ assert(0); /* NOT REACHED */
+ return 0;
+}
+
+/*
+Internal routine to insert a new item into the table.
+Used both by the internal resize routine and by the public insert routine.
+Eats a reference to key and one to value.
+Returns -1 if an error occurred, or 0 on success.
+*/
+static int
+insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
+{
+ PyObject *old_value;
+ register PyDictEntry *ep;
+ typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);
+
+ assert(mp->ma_lookup != NULL);
+ ep = mp->ma_lookup(mp, key, hash);
+ if (ep == NULL) {
+ Py_DECREF(key);
+ Py_DECREF(value);
+ return -1;
+ }
+ if (ep->me_value != NULL) {
+ old_value = ep->me_value;
+ ep->me_value = value;
+ Py_DECREF(old_value); /* which **CAN** re-enter */
+ Py_DECREF(key);
+ }
+ else {
+ if (ep->me_key == NULL)
+ mp->ma_fill++;
+ else {
+ assert(ep->me_key == dummy);
+ Py_DECREF(dummy);
+ }
+ ep->me_key = key;
+ ep->me_hash = (Py_ssize_t)hash;
+ ep->me_value = value;
+ mp->ma_used++;
+ }
+ return 0;
+}
+
+/*
+Internal routine used by dictresize() to insert an item which is
+known to be absent from the dict. This routine also assumes that
+the dict contains no deleted entries. Besides the performance benefit,
+using insertdict() in dictresize() is dangerous (SF bug #1456209).
+Note that no refcounts are changed by this routine; if needed, the caller
+is responsible for incref'ing `key` and `value`.
+*/
+static void
+insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,
+ PyObject *value)
+{
+ register size_t i;
+ register size_t perturb;
+ register size_t mask = (size_t)mp->ma_mask;
+ PyDictEntry *ep0 = mp->ma_table;
+ register PyDictEntry *ep;
+
+ i = hash & mask;
+ ep = &ep0[i];
+ for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
+ i = (i << 2) + i + perturb + 1;
+ ep = &ep0[i & mask];
+ }
+ assert(ep->me_value == NULL);
+ mp->ma_fill++;
+ ep->me_key = key;
+ ep->me_hash = (Py_ssize_t)hash;
+ ep->me_value = value;
+ mp->ma_used++;
+}
+
+/*
+Restructure the table by allocating a new table and reinserting all
+items again. When entries have been deleted, the new table may
+actually be smaller than the old one.
+*/
+static int
+dictresize(PyDictObject *mp, Py_ssize_t minused)
+{
+ Py_ssize_t newsize;
+ PyDictEntry *oldtable, *newtable, *ep;
+ Py_ssize_t i;
+ int is_oldtable_malloced;
+ PyDictEntry small_copy[PyDict_MINSIZE];
+
+ assert(minused >= 0);
+
+ /* Find the smallest table size > minused. */
+ for (newsize = PyDict_MINSIZE;
+ newsize <= minused && newsize > 0;
+ newsize <<= 1)
+ ;
+ if (newsize <= 0) {
+ PyErr_NoMemory();
+ return -1;
+ }
+
+ /* Get space for a new table. */
+ oldtable = mp->ma_table;
+ assert(oldtable != NULL);
+ is_oldtable_malloced = oldtable != mp->ma_smalltable;
+
+ if (newsize == PyDict_MINSIZE) {
+ /* A large table is shrinking, or we can't get any smaller. */
+ newtable = mp->ma_smalltable;
+ if (newtable == oldtable) {
+ if (mp->ma_fill == mp->ma_used) {
+ /* No dummies, so no point doing anything. */
+ return 0;
+ }
+ /* We're not going to resize it, but rebuild the
+ table anyway to purge old dummy entries.
+ Subtle: This is *necessary* if fill==size,
+ as lookdict needs at least one virgin slot to
+ terminate failing searches. If fill < size, it's
+ merely desirable, as dummies slow searches. */
+ assert(mp->ma_fill > mp->ma_used);
+ memcpy(small_copy, oldtable, sizeof(small_copy));
+ oldtable = small_copy;
+ }
+ }
+ else {
+ newtable = PyMem_NEW(PyDictEntry, newsize);
+ if (newtable == NULL) {
+ PyErr_NoMemory();
+ return -1;
+ }
+ }
+
+ /* Make the dict empty, using the new table. */
+ assert(newtable != oldtable);
+ mp->ma_table = newtable;
+ mp->ma_mask = newsize - 1;
+ memset(newtable, 0, sizeof(PyDictEntry) * newsize);
+ mp->ma_used = 0;
+ i = mp->ma_fill;
+ mp->ma_fill = 0;
+
+ /* Copy the data over; this is refcount-neutral for active entries;
+ dummy entries aren't copied over, of course */
+ for (ep = oldtable; i > 0; ep++) {
+ if (ep->me_value != NULL) { /* active entry */
+ --i;
+ insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
+ ep->me_value);
+ }
+ else if (ep->me_key != NULL) { /* dummy entry */
+ --i;
+ assert(ep->me_key == dummy);
+ Py_DECREF(ep->me_key);
+ }
+ /* else key == value == NULL: nothing to do */
+ }
+
+ if (is_oldtable_malloced)
+ PyMem_DEL(oldtable);
+ return 0;
+}
+
+/* Create a new dictionary pre-sized to hold an estimated number of elements.
+ Underestimates are okay because the dictionary will resize as necessary.
+ Overestimates just mean the dictionary will be more sparse than usual.
+*/
+
+PyObject *
+_PyDict_NewPresized(Py_ssize_t minused)
+{
+ PyObject *op = PyDict_New();
+
+ if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
+ Py_DECREF(op);
+ return NULL;
+ }
+ return op;
+}
+
+/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
+ * that may occur (originally dicts supported only string keys, and exceptions
+ * weren't possible). So, while the original intent was that a NULL return
+ * meant the key wasn't present, in reality it can mean that, or that an error
+ * (suppressed) occurred while computing the key's hash, or that some error
+ * (suppressed) occurred when comparing keys in the dict's internal probe
+ * sequence. A nasty example of the latter is when a Python-coded comparison
+ * function hits a stack-depth error, which can cause this to return NULL
+ * even if the key is present.
+ */
+PyObject *
+PyDict_GetItem(PyObject *op, PyObject *key)
+{
+ long hash;
+ PyDictObject *mp = (PyDictObject *)op;
+ PyDictEntry *ep;
+ PyThreadState *tstate;
+ if (!PyDict_Check(op))
+ return NULL;
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1)
+ {
+ hash = PyObject_Hash(key);
+ if (hash == -1) {
+ PyErr_Clear();
+ return NULL;
+ }
+ }
+
+ /* We can arrive here with a NULL tstate during initialization:
+ try running "python -Wi" for an example related to string
+ interning. Let's just hope that no exception occurs then... */
+ tstate = _PyThreadState_Current;
+ if (tstate != NULL && tstate->curexc_type != NULL) {
+ /* preserve the existing exception */
+ PyObject *err_type, *err_value, *err_tb;
+ PyErr_Fetch(&err_type, &err_value, &err_tb);
+ ep = (mp->ma_lookup)(mp, key, hash);
+ /* ignore errors */
+ PyErr_Restore(err_type, err_value, err_tb);
+ if (ep == NULL)
+ return NULL;
+ }
+ else {
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL) {
+ PyErr_Clear();
+ return NULL;
+ }
+ }
+ return ep->me_value;
+}
+
+/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
+ * dictionary if it's merely replacing the value for an existing key.
+ * This means that it's safe to loop over a dictionary with PyDict_Next()
+ * and occasionally replace a value -- but you can't insert new keys or
+ * remove them.
+ */
+int
+PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
+{
+ register PyDictObject *mp;
+ register long hash;
+ register Py_ssize_t n_used;
+
+ if (!PyDict_Check(op)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ assert(key);
+ assert(value);
+ mp = (PyDictObject *)op;
+ if (PyString_CheckExact(key)) {
+ hash = ((PyStringObject *)key)->ob_shash;
+ if (hash == -1)
+ hash = PyObject_Hash(key);
+ }
+ else {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -1;
+ }
+ assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */
+ n_used = mp->ma_used;
+ Py_INCREF(value);
+ Py_INCREF(key);
+ if (insertdict(mp, key, hash, value) != 0)
+ return -1;
+ /* If we added a key, we can safely resize. Otherwise just return!
+ * If fill >= 2/3 size, adjust size. Normally, this doubles or
+ * quaduples the size, but it's also possible for the dict to shrink
+ * (if ma_fill is much larger than ma_used, meaning a lot of dict
+ * keys have been * deleted).
+ *
+ * Quadrupling the size improves average dictionary sparseness
+ * (reducing collisions) at the cost of some memory and iteration
+ * speed (which loops over every possible entry). It also halves
+ * the number of expensive resize operations in a growing dictionary.
+ *
+ * Very large dictionaries (over 50K items) use doubling instead.
+ * This may help applications with severe memory constraints.
+ */
+ if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
+ return 0;
+ return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
+}
+
+int
+PyDict_DelItem(PyObject *op, PyObject *key)
+{
+ register PyDictObject *mp;
+ register long hash;
+ register PyDictEntry *ep;
+ PyObject *old_value, *old_key;
+
+ if (!PyDict_Check(op)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ assert(key);
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -1;
+ }
+ mp = (PyDictObject *)op;
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return -1;
+ if (ep->me_value == NULL) {
+ set_key_error(key);
+ return -1;
+ }
+ old_key = ep->me_key;
+ Py_INCREF(dummy);
+ ep->me_key = dummy;
+ old_value = ep->me_value;
+ ep->me_value = NULL;
+ mp->ma_used--;
+ Py_DECREF(old_value);
+ Py_DECREF(old_key);
+ return 0;
+}
+
+void
+PyDict_Clear(PyObject *op)
+{
+ PyDictObject *mp;
+ PyDictEntry *ep, *table;
+ int table_is_malloced;
+ Py_ssize_t fill;
+ PyDictEntry small_copy[PyDict_MINSIZE];
+#ifdef Py_DEBUG
+ Py_ssize_t i, n;
+#endif
+
+ if (!PyDict_Check(op))
+ return;
+ mp = (PyDictObject *)op;
+#ifdef Py_DEBUG
+ n = mp->ma_mask + 1;
+ i = 0;
+#endif
+
+ table = mp->ma_table;
+ assert(table != NULL);
+ table_is_malloced = table != mp->ma_smalltable;
+
+ /* This is delicate. During the process of clearing the dict,
+ * decrefs can cause the dict to mutate. To avoid fatal confusion
+ * (voice of experience), we have to make the dict empty before
+ * clearing the slots, and never refer to anything via mp->xxx while
+ * clearing.
+ */
+ fill = mp->ma_fill;
+ if (table_is_malloced)
+ EMPTY_TO_MINSIZE(mp);
+
+ else if (fill > 0) {
+ /* It's a small table with something that needs to be cleared.
+ * Afraid the only safe way is to copy the dict entries into
+ * another small table first.
+ */
+ memcpy(small_copy, table, sizeof(small_copy));
+ table = small_copy;
+ EMPTY_TO_MINSIZE(mp);
+ }
+ /* else it's a small table that's already empty */
+
+ /* Now we can finally clear things. If C had refcounts, we could
+ * assert that the refcount on table is 1 now, i.e. that this function
+ * has unique access to it, so decref side-effects can't alter it.
+ */
+ for (ep = table; fill > 0; ++ep) {
+#ifdef Py_DEBUG
+ assert(i < n);
+ ++i;
+#endif
+ if (ep->me_key) {
+ --fill;
+ Py_DECREF(ep->me_key);
+ Py_XDECREF(ep->me_value);
+ }
+#ifdef Py_DEBUG
+ else
+ assert(ep->me_value == NULL);
+#endif
+ }
+
+ if (table_is_malloced)
+ PyMem_DEL(table);
+}
+
+/*
+ * Iterate over a dict. Use like so:
+ *
+ * Py_ssize_t i;
+ * PyObject *key, *value;
+ * i = 0; # important! i should not otherwise be changed by you
+ * while (PyDict_Next(yourdict, &i, &key, &value)) {
+ * Refer to borrowed references in key and value.
+ * }
+ *
+ * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
+ * mutates the dict. One exception: it is safe if the loop merely changes
+ * the values associated with the keys (but doesn't insert new keys or
+ * delete keys), via PyDict_SetItem().
+ */
+int
+PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
+{
+ register Py_ssize_t i;
+ register Py_ssize_t mask;
+ register PyDictEntry *ep;
+
+ if (!PyDict_Check(op))
+ return 0;
+ i = *ppos;
+ if (i < 0)
+ return 0;
+ ep = ((PyDictObject *)op)->ma_table;
+ mask = ((PyDictObject *)op)->ma_mask;
+ while (i <= mask && ep[i].me_value == NULL)
+ i++;
+ *ppos = i+1;
+ if (i > mask)
+ return 0;
+ if (pkey)
+ *pkey = ep[i].me_key;
+ if (pvalue)
+ *pvalue = ep[i].me_value;
+ return 1;
+}
+
+/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
+int
+_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)
+{
+ register Py_ssize_t i;
+ register Py_ssize_t mask;
+ register PyDictEntry *ep;
+
+ if (!PyDict_Check(op))
+ return 0;
+ i = *ppos;
+ if (i < 0)
+ return 0;
+ ep = ((PyDictObject *)op)->ma_table;
+ mask = ((PyDictObject *)op)->ma_mask;
+ while (i <= mask && ep[i].me_value == NULL)
+ i++;
+ *ppos = i+1;
+ if (i > mask)
+ return 0;
+ *phash = (long)(ep[i].me_hash);
+ if (pkey)
+ *pkey = ep[i].me_key;
+ if (pvalue)
+ *pvalue = ep[i].me_value;
+ return 1;
+}
+
+/* Methods */
+
+static void
+dict_dealloc(register PyDictObject *mp)
+{
+ register PyDictEntry *ep;
+ Py_ssize_t fill = mp->ma_fill;
+ PyObject_GC_UnTrack(mp);
+ Py_TRASHCAN_SAFE_BEGIN(mp)
+ for (ep = mp->ma_table; fill > 0; ep++) {
+ if (ep->me_key) {
+ --fill;
+ Py_DECREF(ep->me_key);
+ Py_XDECREF(ep->me_value);
+ }
+ }
+ if (mp->ma_table != mp->ma_smalltable)
+ PyMem_DEL(mp->ma_table);
+ if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
+ free_list[numfree++] = mp;
+ else
+ Py_TYPE(mp)->tp_free((PyObject *)mp);
+ Py_TRASHCAN_SAFE_END(mp)
+}
+
+static int
+dict_print(register PyDictObject *mp, register FILE *fp, register int flags)
+{
+ register Py_ssize_t i;
+ register Py_ssize_t any;
+ int status;
+
+ status = Py_ReprEnter((PyObject*)mp);
+ if (status != 0) {
+ if (status < 0)
+ return status;
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "{...}");
+ Py_END_ALLOW_THREADS
+ return 0;
+ }
+
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "{");
+ Py_END_ALLOW_THREADS
+ any = 0;
+ for (i = 0; i <= mp->ma_mask; i++) {
+ PyDictEntry *ep = mp->ma_table + i;
+ PyObject *pvalue = ep->me_value;
+ if (pvalue != NULL) {
+ /* Prevent PyObject_Repr from deleting value during
+ key format */
+ Py_INCREF(pvalue);
+ if (any++ > 0) {
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, ", ");
+ Py_END_ALLOW_THREADS
+ }
+ if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {
+ Py_DECREF(pvalue);
+ Py_ReprLeave((PyObject*)mp);
+ return -1;
+ }
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, ": ");
+ Py_END_ALLOW_THREADS
+ if (PyObject_Print(pvalue, fp, 0) != 0) {
+ Py_DECREF(pvalue);
+ Py_ReprLeave((PyObject*)mp);
+ return -1;
+ }
+ Py_DECREF(pvalue);
+ }
+ }
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "}");
+ Py_END_ALLOW_THREADS
+ Py_ReprLeave((PyObject*)mp);
+ return 0;
+}
+
+static PyObject *
+dict_repr(PyDictObject *mp)
+{
+ Py_ssize_t i;
+ PyObject *s, *temp, *colon = NULL;
+ PyObject *pieces = NULL, *result = NULL;
+ PyObject *key, *value;
+
+ i = Py_ReprEnter((PyObject *)mp);
+ if (i != 0) {
+ return i > 0 ? PyString_FromString("{...}") : NULL;
+ }
+
+ if (mp->ma_used == 0) {
+ result = PyString_FromString("{}");
+ goto Done;
+ }
+
+ pieces = PyList_New(0);
+ if (pieces == NULL)
+ goto Done;
+
+ colon = PyString_FromString(": ");
+ if (colon == NULL)
+ goto Done;
+
+ /* Do repr() on each key+value pair, and insert ": " between them.
+ Note that repr may mutate the dict. */
+ i = 0;
+ while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
+ int status;
+ /* Prevent repr from deleting value during key format. */
+ Py_INCREF(value);
+ s = PyObject_Repr(key);
+ PyString_Concat(&s, colon);
+ PyString_ConcatAndDel(&s, PyObject_Repr(value));
+ Py_DECREF(value);
+ if (s == NULL)
+ goto Done;
+ status = PyList_Append(pieces, s);
+ Py_DECREF(s); /* append created a new ref */
+ if (status < 0)
+ goto Done;
+ }
+
+ /* Add "{}" decorations to the first and last items. */
+ assert(PyList_GET_SIZE(pieces) > 0);
+ s = PyString_FromString("{");
+ if (s == NULL)
+ goto Done;
+ temp = PyList_GET_ITEM(pieces, 0);
+ PyString_ConcatAndDel(&s, temp);
+ PyList_SET_ITEM(pieces, 0, s);
+ if (s == NULL)
+ goto Done;
+
+ s = PyString_FromString("}");
+ if (s == NULL)
+ goto Done;
+ temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
+ PyString_ConcatAndDel(&temp, s);
+ PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
+ if (temp == NULL)
+ goto Done;
+
+ /* Paste them all together with ", " between. */
+ s = PyString_FromString(", ");
+ if (s == NULL)
+ goto Done;
+ result = _PyString_Join(s, pieces);
+ Py_DECREF(s);
+
+Done:
+ Py_XDECREF(pieces);
+ Py_XDECREF(colon);
+ Py_ReprLeave((PyObject *)mp);
+ return result;
+}
+
+static Py_ssize_t
+dict_length(PyDictObject *mp)
+{
+ return mp->ma_used;
+}
+
+static PyObject *
+dict_subscript(PyDictObject *mp, register PyObject *key)
+{
+ PyObject *v;
+ long hash;
+ PyDictEntry *ep;
+ assert(mp->ma_table != NULL);
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return NULL;
+ v = ep->me_value;
+ if (v == NULL) {
+ if (!PyDict_CheckExact(mp)) {
+ /* Look up __missing__ method if we're a subclass. */
+ PyObject *missing;
+ static PyObject *missing_str = NULL;
+ if (missing_str == NULL)
+ missing_str =
+ PyString_InternFromString("__missing__");
+ missing = _PyType_Lookup(Py_TYPE(mp), missing_str);
+ if (missing != NULL)
+ return PyObject_CallFunctionObjArgs(missing,
+ (PyObject *)mp, key, NULL);
+ }
+ set_key_error(key);
+ return NULL;
+ }
+ else
+ Py_INCREF(v);
+ return v;
+}
+
+static int
+dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
+{
+ if (w == NULL)
+ return PyDict_DelItem((PyObject *)mp, v);
+ else
+ return PyDict_SetItem((PyObject *)mp, v, w);
+}
+
+static PyMappingMethods dict_as_mapping = {
+ (lenfunc)dict_length, /*mp_length*/
+ (binaryfunc)dict_subscript, /*mp_subscript*/
+ (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
+};
+
+static PyObject *
+dict_keys(register PyDictObject *mp)
+{
+ register PyObject *v;
+ register Py_ssize_t i, j;
+ PyDictEntry *ep;
+ Py_ssize_t mask, n;
+
+ again:
+ n = mp->ma_used;
+ v = PyList_New(n);
+ if (v == NULL)
+ return NULL;
+ if (n != mp->ma_used) {
+ /* Durnit. The allocations caused the dict to resize.
+ * Just start over, this shouldn't normally happen.
+ */
+ Py_DECREF(v);
+ goto again;
+ }
+ ep = mp->ma_table;
+ mask = mp->ma_mask;
+ for (i = 0, j = 0; i <= mask; i++) {
+ if (ep[i].me_value != NULL) {
+ PyObject *key = ep[i].me_key;
+ Py_INCREF(key);
+ PyList_SET_ITEM(v, j, key);
+ j++;
+ }
+ }
+ assert(j == n);
+ return v;
+}
+
+static PyObject *
+dict_values(register PyDictObject *mp)
+{
+ register PyObject *v;
+ register Py_ssize_t i, j;
+ PyDictEntry *ep;
+ Py_ssize_t mask, n;
+
+ again:
+ n = mp->ma_used;
+ v = PyList_New(n);
+ if (v == NULL)
+ return NULL;
+ if (n != mp->ma_used) {
+ /* Durnit. The allocations caused the dict to resize.
+ * Just start over, this shouldn't normally happen.
+ */
+ Py_DECREF(v);
+ goto again;
+ }
+ ep = mp->ma_table;
+ mask = mp->ma_mask;
+ for (i = 0, j = 0; i <= mask; i++) {
+ if (ep[i].me_value != NULL) {
+ PyObject *value = ep[i].me_value;
+ Py_INCREF(value);
+ PyList_SET_ITEM(v, j, value);
+ j++;
+ }
+ }
+ assert(j == n);
+ return v;
+}
+
+static PyObject *
+dict_items(register PyDictObject *mp)
+{
+ register PyObject *v;
+ register Py_ssize_t i, j, n;
+ Py_ssize_t mask;
+ PyObject *item, *key, *value;
+ PyDictEntry *ep;
+
+ /* Preallocate the list of tuples, to avoid allocations during
+ * the loop over the items, which could trigger GC, which
+ * could resize the dict. :-(
+ */
+ again:
+ n = mp->ma_used;
+ v = PyList_New(n);
+ if (v == NULL)
+ return NULL;
+ for (i = 0; i < n; i++) {
+ item = PyTuple_New(2);
+ if (item == NULL) {
+ Py_DECREF(v);
+ return NULL;
+ }
+ PyList_SET_ITEM(v, i, item);
+ }
+ if (n != mp->ma_used) {
+ /* Durnit. The allocations caused the dict to resize.
+ * Just start over, this shouldn't normally happen.
+ */
+ Py_DECREF(v);
+ goto again;
+ }
+ /* Nothing we do below makes any function calls. */
+ ep = mp->ma_table;
+ mask = mp->ma_mask;
+ for (i = 0, j = 0; i <= mask; i++) {
+ if ((value=ep[i].me_value) != NULL) {
+ key = ep[i].me_key;
+ item = PyList_GET_ITEM(v, j);
+ Py_INCREF(key);
+ PyTuple_SET_ITEM(item, 0, key);
+ Py_INCREF(value);
+ PyTuple_SET_ITEM(item, 1, value);
+ j++;
+ }
+ }
+ assert(j == n);
+ return v;
+}
+
+static PyObject *
+dict_fromkeys(PyObject *cls, PyObject *args)
+{
+ PyObject *seq;
+ PyObject *value = Py_None;
+ PyObject *it; /* iter(seq) */
+ PyObject *key;
+ PyObject *d;
+ int status;
+
+ if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))
+ return NULL;
+
+ d = PyObject_CallObject(cls, NULL);
+ if (d == NULL)
+ return NULL;
+
+ if (PyDict_CheckExact(d) && PyDict_CheckExact(seq)) {
+ PyDictObject *mp = (PyDictObject *)d;
+ PyObject *oldvalue;
+ Py_ssize_t pos = 0;
+ PyObject *key;
+ long hash;
+
+ if (dictresize(mp, Py_SIZE(seq)))
+ return NULL;
+
+ while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {
+ Py_INCREF(key);
+ Py_INCREF(value);
+ if (insertdict(mp, key, hash, value))
+ return NULL;
+ }
+ return d;
+ }
+
+ if (PyDict_CheckExact(d) && PyAnySet_CheckExact(seq)) {
+ PyDictObject *mp = (PyDictObject *)d;
+ Py_ssize_t pos = 0;
+ PyObject *key;
+ long hash;
+
+ if (dictresize(mp, PySet_GET_SIZE(seq)))
+ return NULL;
+
+ while (_PySet_NextEntry(seq, &pos, &key, &hash)) {
+ Py_INCREF(key);
+ Py_INCREF(value);
+ if (insertdict(mp, key, hash, value))
+ return NULL;
+ }
+ return d;
+ }
+
+ it = PyObject_GetIter(seq);
+ if (it == NULL){
+ Py_DECREF(d);
+ return NULL;
+ }
+
+ if (PyDict_CheckExact(d)) {
+ while ((key = PyIter_Next(it)) != NULL) {
+ status = PyDict_SetItem(d, key, value);
+ Py_DECREF(key);
+ if (status < 0)
+ goto Fail;
+ }
+ } else {
+ while ((key = PyIter_Next(it)) != NULL) {
+ status = PyObject_SetItem(d, key, value);
+ Py_DECREF(key);
+ if (status < 0)
+ goto Fail;
+ }
+ }
+
+ if (PyErr_Occurred())
+ goto Fail;
+ Py_DECREF(it);
+ return d;
+
+Fail:
+ Py_DECREF(it);
+ Py_DECREF(d);
+ return NULL;
+}
+
+static int
+dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)
+{
+ PyObject *arg = NULL;
+ int result = 0;
+
+ if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
+ result = -1;
+
+ else if (arg != NULL) {
+ if (PyObject_HasAttrString(arg, "keys"))
+ result = PyDict_Merge(self, arg, 1);
+ else
+ result = PyDict_MergeFromSeq2(self, arg, 1);
+ }
+ if (result == 0 && kwds != NULL)
+ result = PyDict_Merge(self, kwds, 1);
+ return result;
+}
+
+static PyObject *
+dict_update(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ if (dict_update_common(self, args, kwds, "update") != -1)
+ Py_RETURN_NONE;
+ return NULL;
+}
+
+/* Update unconditionally replaces existing items.
+ Merge has a 3rd argument 'override'; if set, it acts like Update,
+ otherwise it leaves existing items unchanged.
+
+ PyDict_{Update,Merge} update/merge from a mapping object.
+
+ PyDict_MergeFromSeq2 updates/merges from any iterable object
+ producing iterable objects of length 2.
+*/
+
+int
+PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
+{
+ PyObject *it; /* iter(seq2) */
+ Py_ssize_t i; /* index into seq2 of current element */
+ PyObject *item; /* seq2[i] */
+ PyObject *fast; /* item as a 2-tuple or 2-list */
+
+ assert(d != NULL);
+ assert(PyDict_Check(d));
+ assert(seq2 != NULL);
+
+ it = PyObject_GetIter(seq2);
+ if (it == NULL)
+ return -1;
+
+ for (i = 0; ; ++i) {
+ PyObject *key, *value;
+ Py_ssize_t n;
+
+ fast = NULL;
+ item = PyIter_Next(it);
+ if (item == NULL) {
+ if (PyErr_Occurred())
+ goto Fail;
+ break;
+ }
+
+ /* Convert item to sequence, and verify length 2. */
+ fast = PySequence_Fast(item, "");
+ if (fast == NULL) {
+ if (PyErr_ExceptionMatches(PyExc_TypeError))
+ PyErr_Format(PyExc_TypeError,
+ "cannot convert dictionary update "
+ "sequence element #%zd to a sequence",
+ i);
+ goto Fail;
+ }
+ n = PySequence_Fast_GET_SIZE(fast);
+ if (n != 2) {
+ PyErr_Format(PyExc_ValueError,
+ "dictionary update sequence element #%zd "
+ "has length %zd; 2 is required",
+ i, n);
+ goto Fail;
+ }
+
+ /* Update/merge with this (key, value) pair. */
+ key = PySequence_Fast_GET_ITEM(fast, 0);
+ value = PySequence_Fast_GET_ITEM(fast, 1);
+ if (override || PyDict_GetItem(d, key) == NULL) {
+ int status = PyDict_SetItem(d, key, value);
+ if (status < 0)
+ goto Fail;
+ }
+ Py_DECREF(fast);
+ Py_DECREF(item);
+ }
+
+ i = 0;
+ goto Return;
+Fail:
+ Py_XDECREF(item);
+ Py_XDECREF(fast);
+ i = -1;
+Return:
+ Py_DECREF(it);
+ return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
+}
+
+int
+PyDict_Update(PyObject *a, PyObject *b)
+{
+ return PyDict_Merge(a, b, 1);
+}
+
+int
+PyDict_Merge(PyObject *a, PyObject *b, int override)
+{
+ register PyDictObject *mp, *other;
+ register Py_ssize_t i;
+ PyDictEntry *entry;
+
+ /* We accept for the argument either a concrete dictionary object,
+ * or an abstract "mapping" object. For the former, we can do
+ * things quite efficiently. For the latter, we only require that
+ * PyMapping_Keys() and PyObject_GetItem() be supported.
+ */
+ if (a == NULL || !PyDict_Check(a) || b == NULL) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ mp = (PyDictObject*)a;
+ if (PyDict_Check(b)) {
+ other = (PyDictObject*)b;
+ if (other == mp || other->ma_used == 0)
+ /* a.update(a) or a.update({}); nothing to do */
+ return 0;
+ if (mp->ma_used == 0)
+ /* Since the target dict is empty, PyDict_GetItem()
+ * always returns NULL. Setting override to 1
+ * skips the unnecessary test.
+ */
+ override = 1;
+ /* Do one big resize at the start, rather than
+ * incrementally resizing as we insert new items. Expect
+ * that there will be no (or few) overlapping keys.
+ */
+ if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {
+ if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)
+ return -1;
+ }
+ for (i = 0; i <= other->ma_mask; i++) {
+ entry = &other->ma_table[i];
+ if (entry->me_value != NULL &&
+ (override ||
+ PyDict_GetItem(a, entry->me_key) == NULL)) {
+ Py_INCREF(entry->me_key);
+ Py_INCREF(entry->me_value);
+ if (insertdict(mp, entry->me_key,
+ (long)entry->me_hash,
+ entry->me_value) != 0)
+ return -1;
+ }
+ }
+ }
+ else {
+ /* Do it the generic, slower way */
+ PyObject *keys = PyMapping_Keys(b);
+ PyObject *iter;
+ PyObject *key, *value;
+ int status;
+
+ if (keys == NULL)
+ /* Docstring says this is equivalent to E.keys() so
+ * if E doesn't have a .keys() method we want
+ * AttributeError to percolate up. Might as well
+ * do the same for any other error.
+ */
+ return -1;
+
+ iter = PyObject_GetIter(keys);
+ Py_DECREF(keys);
+ if (iter == NULL)
+ return -1;
+
+ for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
+ if (!override && PyDict_GetItem(a, key) != NULL) {
+ Py_DECREF(key);
+ continue;
+ }
+ value = PyObject_GetItem(b, key);
+ if (value == NULL) {
+ Py_DECREF(iter);
+ Py_DECREF(key);
+ return -1;
+ }
+ status = PyDict_SetItem(a, key, value);
+ Py_DECREF(key);
+ Py_DECREF(value);
+ if (status < 0) {
+ Py_DECREF(iter);
+ return -1;
+ }
+ }
+ Py_DECREF(iter);
+ if (PyErr_Occurred())
+ /* Iterator completed, via error */
+ return -1;
+ }
+ return 0;
+}
+
+static PyObject *
+dict_copy(register PyDictObject *mp)
+{
+ return PyDict_Copy((PyObject*)mp);
+}
+
+PyObject *
+PyDict_Copy(PyObject *o)
+{
+ PyObject *copy;
+
+ if (o == NULL || !PyDict_Check(o)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ copy = PyDict_New();
+ if (copy == NULL)
+ return NULL;
+ if (PyDict_Merge(copy, o, 1) == 0)
+ return copy;
+ Py_DECREF(copy);
+ return NULL;
+}
+
+Py_ssize_t
+PyDict_Size(PyObject *mp)
+{
+ if (mp == NULL || !PyDict_Check(mp)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ return ((PyDictObject *)mp)->ma_used;
+}
+
+PyObject *
+PyDict_Keys(PyObject *mp)
+{
+ if (mp == NULL || !PyDict_Check(mp)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ return dict_keys((PyDictObject *)mp);
+}
+
+PyObject *
+PyDict_Values(PyObject *mp)
+{
+ if (mp == NULL || !PyDict_Check(mp)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ return dict_values((PyDictObject *)mp);
+}
+
+PyObject *
+PyDict_Items(PyObject *mp)
+{
+ if (mp == NULL || !PyDict_Check(mp)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ return dict_items((PyDictObject *)mp);
+}
+
+/* Subroutine which returns the smallest key in a for which b's value
+ is different or absent. The value is returned too, through the
+ pval argument. Both are NULL if no key in a is found for which b's status
+ differs. The refcounts on (and only on) non-NULL *pval and function return
+ values must be decremented by the caller (characterize() increments them
+ to ensure that mutating comparison and PyDict_GetItem calls can't delete
+ them before the caller is done looking at them). */
+
+static PyObject *
+characterize(PyDictObject *a, PyDictObject *b, PyObject **pval)
+{
+ PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */
+ PyObject *aval = NULL; /* a[akey] */
+ Py_ssize_t i;
+ int cmp;
+
+ for (i = 0; i <= a->ma_mask; i++) {
+ PyObject *thiskey, *thisaval, *thisbval;
+ if (a->ma_table[i].me_value == NULL)
+ continue;
+ thiskey = a->ma_table[i].me_key;
+ Py_INCREF(thiskey); /* keep alive across compares */
+ if (akey != NULL) {
+ cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);
+ if (cmp < 0) {
+ Py_DECREF(thiskey);
+ goto Fail;
+ }
+ if (cmp > 0 ||
+ i > a->ma_mask ||
+ a->ma_table[i].me_value == NULL)
+ {
+ /* Not the *smallest* a key; or maybe it is
+ * but the compare shrunk the dict so we can't
+ * find its associated value anymore; or
+ * maybe it is but the compare deleted the
+ * a[thiskey] entry.
+ */
+ Py_DECREF(thiskey);
+ continue;
+ }
+ }
+
+ /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
+ thisaval = a->ma_table[i].me_value;
+ assert(thisaval);
+ Py_INCREF(thisaval); /* keep alive */
+ thisbval = PyDict_GetItem((PyObject *)b, thiskey);
+ if (thisbval == NULL)
+ cmp = 0;
+ else {
+ /* both dicts have thiskey: same values? */
+ cmp = PyObject_RichCompareBool(
+ thisaval, thisbval, Py_EQ);
+ if (cmp < 0) {
+ Py_DECREF(thiskey);
+ Py_DECREF(thisaval);
+ goto Fail;
+ }
+ }
+ if (cmp == 0) {
+ /* New winner. */
+ Py_XDECREF(akey);
+ Py_XDECREF(aval);
+ akey = thiskey;
+ aval = thisaval;
+ }
+ else {
+ Py_DECREF(thiskey);
+ Py_DECREF(thisaval);
+ }
+ }
+ *pval = aval;
+ return akey;
+
+Fail:
+ Py_XDECREF(akey);
+ Py_XDECREF(aval);
+ *pval = NULL;
+ return NULL;
+}
+
+static int
+dict_compare(PyDictObject *a, PyDictObject *b)
+{
+ PyObject *adiff, *bdiff, *aval, *bval;
+ int res;
+
+ /* Compare lengths first */
+ if (a->ma_used < b->ma_used)
+ return -1; /* a is shorter */
+ else if (a->ma_used > b->ma_used)
+ return 1; /* b is shorter */
+
+ /* Same length -- check all keys */
+ bdiff = bval = NULL;
+ adiff = characterize(a, b, &aval);
+ if (adiff == NULL) {
+ assert(!aval);
+ /* Either an error, or a is a subset with the same length so
+ * must be equal.
+ */
+ res = PyErr_Occurred() ? -1 : 0;
+ goto Finished;
+ }
+ bdiff = characterize(b, a, &bval);
+ if (bdiff == NULL && PyErr_Occurred()) {
+ assert(!bval);
+ res = -1;
+ goto Finished;
+ }
+ res = 0;
+ if (bdiff) {
+ /* bdiff == NULL "should be" impossible now, but perhaps
+ * the last comparison done by the characterize() on a had
+ * the side effect of making the dicts equal!
+ */
+ res = PyObject_Compare(adiff, bdiff);
+ }
+ if (res == 0 && bval != NULL)
+ res = PyObject_Compare(aval, bval);
+
+Finished:
+ Py_XDECREF(adiff);
+ Py_XDECREF(bdiff);
+ Py_XDECREF(aval);
+ Py_XDECREF(bval);
+ return res;
+}
+
+/* Return 1 if dicts equal, 0 if not, -1 if error.
+ * Gets out as soon as any difference is detected.
+ * Uses only Py_EQ comparison.
+ */
+static int
+dict_equal(PyDictObject *a, PyDictObject *b)
+{
+ Py_ssize_t i;
+
+ if (a->ma_used != b->ma_used)
+ /* can't be equal if # of entries differ */
+ return 0;
+
+ /* Same # of entries -- check all of 'em. Exit early on any diff. */
+ for (i = 0; i <= a->ma_mask; i++) {
+ PyObject *aval = a->ma_table[i].me_value;
+ if (aval != NULL) {
+ int cmp;
+ PyObject *bval;
+ PyObject *key = a->ma_table[i].me_key;
+ /* temporarily bump aval's refcount to ensure it stays
+ alive until we're done with it */
+ Py_INCREF(aval);
+ /* ditto for key */
+ Py_INCREF(key);
+ bval = PyDict_GetItem((PyObject *)b, key);
+ Py_DECREF(key);
+ if (bval == NULL) {
+ Py_DECREF(aval);
+ return 0;
+ }
+ cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
+ Py_DECREF(aval);
+ if (cmp <= 0) /* error or not equal */
+ return cmp;
+ }
+ }
+ return 1;
+ }
+
+static PyObject *
+dict_richcompare(PyObject *v, PyObject *w, int op)
+{
+ int cmp;
+ PyObject *res;
+
+ if (!PyDict_Check(v) || !PyDict_Check(w)) {
+ res = Py_NotImplemented;
+ }
+ else if (op == Py_EQ || op == Py_NE) {
+ cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
+ if (cmp < 0)
+ return NULL;
+ res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
+ }
+ else {
+ /* Py3K warning if comparison isn't == or != */
+ if (PyErr_WarnPy3k("dict inequality comparisons not supported "
+ "in 3.x", 1) < 0) {
+ return NULL;
+ }
+ res = Py_NotImplemented;
+ }
+ Py_INCREF(res);
+ return res;
+ }
+
+static PyObject *
+dict_contains(register PyDictObject *mp, PyObject *key)
+{
+ long hash;
+ PyDictEntry *ep;
+
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return NULL;
+ return PyBool_FromLong(ep->me_value != NULL);
+}
+
+static PyObject *
+dict_has_key(register PyDictObject *mp, PyObject *key)
+{
+ if (PyErr_WarnPy3k("dict.has_key() not supported in 3.x; "
+ "use the in operator", 1) < 0)
+ return NULL;
+ return dict_contains(mp, key);
+}
+
+static PyObject *
+dict_get(register PyDictObject *mp, PyObject *args)
+{
+ PyObject *key;
+ PyObject *failobj = Py_None;
+ PyObject *val = NULL;
+ long hash;
+ PyDictEntry *ep;
+
+ if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))
+ return NULL;
+
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return NULL;
+ val = ep->me_value;
+ if (val == NULL)
+ val = failobj;
+ Py_INCREF(val);
+ return val;
+}
+
+
+static PyObject *
+dict_setdefault(register PyDictObject *mp, PyObject *args)
+{
+ PyObject *key;
+ PyObject *failobj = Py_None;
+ PyObject *val = NULL;
+ long hash;
+ PyDictEntry *ep;
+
+ if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))
+ return NULL;
+
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return NULL;
+ val = ep->me_value;
+ if (val == NULL) {
+ val = failobj;
+ if (PyDict_SetItem((PyObject*)mp, key, failobj))
+ val = NULL;
+ }
+ Py_XINCREF(val);
+ return val;
+}
+
+
+static PyObject *
+dict_clear(register PyDictObject *mp)
+{
+ PyDict_Clear((PyObject *)mp);
+ Py_RETURN_NONE;
+}
+
+static PyObject *
+dict_pop(PyDictObject *mp, PyObject *args)
+{
+ long hash;
+ PyDictEntry *ep;
+ PyObject *old_value, *old_key;
+ PyObject *key, *deflt = NULL;
+
+ if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
+ return NULL;
+ if (mp->ma_used == 0) {
+ if (deflt) {
+ Py_INCREF(deflt);
+ return deflt;
+ }
+ PyErr_SetString(PyExc_KeyError,
+ "pop(): dictionary is empty");
+ return NULL;
+ }
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return NULL;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ if (ep == NULL)
+ return NULL;
+ if (ep->me_value == NULL) {
+ if (deflt) {
+ Py_INCREF(deflt);
+ return deflt;
+ }
+ set_key_error(key);
+ return NULL;
+ }
+ old_key = ep->me_key;
+ Py_INCREF(dummy);
+ ep->me_key = dummy;
+ old_value = ep->me_value;
+ ep->me_value = NULL;
+ mp->ma_used--;
+ Py_DECREF(old_key);
+ return old_value;
+}
+
+static PyObject *
+dict_popitem(PyDictObject *mp)
+{
+ Py_ssize_t i = 0;
+ PyDictEntry *ep;
+ PyObject *res;
+
+ /* Allocate the result tuple before checking the size. Believe it
+ * or not, this allocation could trigger a garbage collection which
+ * could empty the dict, so if we checked the size first and that
+ * happened, the result would be an infinite loop (searching for an
+ * entry that no longer exists). Note that the usual popitem()
+ * idiom is "while d: k, v = d.popitem()". so needing to throw the
+ * tuple away if the dict *is* empty isn't a significant
+ * inefficiency -- possible, but unlikely in practice.
+ */
+ res = PyTuple_New(2);
+ if (res == NULL)
+ return NULL;
+ if (mp->ma_used == 0) {
+ Py_DECREF(res);
+ PyErr_SetString(PyExc_KeyError,
+ "popitem(): dictionary is empty");
+ return NULL;
+ }
+ /* Set ep to "the first" dict entry with a value. We abuse the hash
+ * field of slot 0 to hold a search finger:
+ * If slot 0 has a value, use slot 0.
+ * Else slot 0 is being used to hold a search finger,
+ * and we use its hash value as the first index to look.
+ */
+ ep = &mp->ma_table[0];
+ if (ep->me_value == NULL) {
+ i = ep->me_hash;
+ /* The hash field may be a real hash value, or it may be a
+ * legit search finger, or it may be a once-legit search
+ * finger that's out of bounds now because it wrapped around
+ * or the table shrunk -- simply make sure it's in bounds now.
+ */
+ if (i > mp->ma_mask || i < 1)
+ i = 1; /* skip slot 0 */
+ while ((ep = &mp->ma_table[i])->me_value == NULL) {
+ i++;
+ if (i > mp->ma_mask)
+ i = 1;
+ }
+ }
+ PyTuple_SET_ITEM(res, 0, ep->me_key);
+ PyTuple_SET_ITEM(res, 1, ep->me_value);
+ Py_INCREF(dummy);
+ ep->me_key = dummy;
+ ep->me_value = NULL;
+ mp->ma_used--;
+ assert(mp->ma_table[0].me_value == NULL);
+ mp->ma_table[0].me_hash = i + 1; /* next place to start */
+ return res;
+}
+
+static int
+dict_traverse(PyObject *op, visitproc visit, void *arg)
+{
+ Py_ssize_t i = 0;
+ PyObject *pk;
+ PyObject *pv;
+
+ while (PyDict_Next(op, &i, &pk, &pv)) {
+ Py_VISIT(pk);
+ Py_VISIT(pv);
+ }
+ return 0;
+}
+
+static int
+dict_tp_clear(PyObject *op)
+{
+ PyDict_Clear(op);
+ return 0;
+}
+
+
+extern PyTypeObject PyDictIterKey_Type; /* Forward */
+extern PyTypeObject PyDictIterValue_Type; /* Forward */
+extern PyTypeObject PyDictIterItem_Type; /* Forward */
+static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
+
+static PyObject *
+dict_iterkeys(PyDictObject *dict)
+{
+ return dictiter_new(dict, &PyDictIterKey_Type);
+}
+
+static PyObject *
+dict_itervalues(PyDictObject *dict)
+{
+ return dictiter_new(dict, &PyDictIterValue_Type);
+}
+
+static PyObject *
+dict_iteritems(PyDictObject *dict)
+{
+ return dictiter_new(dict, &PyDictIterItem_Type);
+}
+
+static PyObject *
+dict_sizeof(PyDictObject *mp)
+{
+ Py_ssize_t res;
+
+ res = sizeof(PyDictObject);
+ if (mp->ma_table != mp->ma_smalltable)
+ res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
+ return PyInt_FromSsize_t(res);
+}
+
+PyDoc_STRVAR(has_key__doc__,
+"D.has_key(k) -> True if D has a key k, else False");
+
+PyDoc_STRVAR(contains__doc__,
+"D.__contains__(k) -> True if D has a key k, else False");
+
+PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
+
+PyDoc_STRVAR(sizeof__doc__,
+"D.__sizeof__() -> size of D in memory, in bytes");
+
+PyDoc_STRVAR(get__doc__,
+"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
+
+PyDoc_STRVAR(setdefault_doc__,
+"D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");
+
+PyDoc_STRVAR(pop__doc__,
+"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
+If key is not found, d is returned if given, otherwise KeyError is raised");
+
+PyDoc_STRVAR(popitem__doc__,
+"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
+2-tuple; but raise KeyError if D is empty.");
+
+PyDoc_STRVAR(keys__doc__,
+"D.keys() -> list of D's keys");
+
+PyDoc_STRVAR(items__doc__,
+"D.items() -> list of D's (key, value) pairs, as 2-tuples");
+
+PyDoc_STRVAR(values__doc__,
+"D.values() -> list of D's values");
+
+PyDoc_STRVAR(update__doc__,
+"D.update(E, **F) -> None. Update D from dict/iterable E and F.\n"
+"If E has a .keys() method, does: for k in E: D[k] = E[k]\n\
+If E lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
+In either case, this is followed by: for k in F: D[k] = F[k]");
+
+PyDoc_STRVAR(fromkeys__doc__,
+"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
+v defaults to None.");
+
+PyDoc_STRVAR(clear__doc__,
+"D.clear() -> None. Remove all items from D.");
+
+PyDoc_STRVAR(copy__doc__,
+"D.copy() -> a shallow copy of D");
+
+PyDoc_STRVAR(iterkeys__doc__,
+"D.iterkeys() -> an iterator over the keys of D");
+
+PyDoc_STRVAR(itervalues__doc__,
+"D.itervalues() -> an iterator over the values of D");
+
+PyDoc_STRVAR(iteritems__doc__,
+"D.iteritems() -> an iterator over the (key, value) items of D");
+
+static PyMethodDef mapp_methods[] = {
+ {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
+ contains__doc__},
+ {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
+ getitem__doc__},
+ {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
+ sizeof__doc__},
+ {"has_key", (PyCFunction)dict_has_key, METH_O,
+ has_key__doc__},
+ {"get", (PyCFunction)dict_get, METH_VARARGS,
+ get__doc__},
+ {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,
+ setdefault_doc__},
+ {"pop", (PyCFunction)dict_pop, METH_VARARGS,
+ pop__doc__},
+ {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
+ popitem__doc__},
+ {"keys", (PyCFunction)dict_keys, METH_NOARGS,
+ keys__doc__},
+ {"items", (PyCFunction)dict_items, METH_NOARGS,
+ items__doc__},
+ {"values", (PyCFunction)dict_values, METH_NOARGS,
+ values__doc__},
+ {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
+ update__doc__},
+ {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
+ fromkeys__doc__},
+ {"clear", (PyCFunction)dict_clear, METH_NOARGS,
+ clear__doc__},
+ {"copy", (PyCFunction)dict_copy, METH_NOARGS,
+ copy__doc__},
+ {"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,
+ iterkeys__doc__},
+ {"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,
+ itervalues__doc__},
+ {"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,
+ iteritems__doc__},
+ {NULL, NULL} /* sentinel */
+};
+
+/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
+int
+PyDict_Contains(PyObject *op, PyObject *key)
+{
+ long hash;
+ PyDictObject *mp = (PyDictObject *)op;
+ PyDictEntry *ep;
+
+ if (!PyString_CheckExact(key) ||
+ (hash = ((PyStringObject *) key)->ob_shash) == -1) {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -1;
+ }
+ ep = (mp->ma_lookup)(mp, key, hash);
+ return ep == NULL ? -1 : (ep->me_value != NULL);
+}
+
+/* Internal version of PyDict_Contains used when the hash value is already known */
+int
+_PyDict_Contains(PyObject *op, PyObject *key, long hash)
+{
+ PyDictObject *mp = (PyDictObject *)op;
+ PyDictEntry *ep;
+
+ ep = (mp->ma_lookup)(mp, key, hash);
+ return ep == NULL ? -1 : (ep->me_value != NULL);
+}
+
+/* Hack to implement "key in dict" */
+static PySequenceMethods dict_as_sequence = {
+ 0, /* sq_length */
+ 0, /* sq_concat */
+ 0, /* sq_repeat */
+ 0, /* sq_item */
+ 0, /* sq_slice */
+ 0, /* sq_ass_item */
+ 0, /* sq_ass_slice */
+ PyDict_Contains, /* sq_contains */
+ 0, /* sq_inplace_concat */
+ 0, /* sq_inplace_repeat */
+};
+
+static PyObject *
+dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+ PyObject *self;
+
+ assert(type != NULL && type->tp_alloc != NULL);
+ self = type->tp_alloc(type, 0);
+ if (self != NULL) {
+ PyDictObject *d = (PyDictObject *)self;
+ /* It's guaranteed that tp->alloc zeroed out the struct. */
+ assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
+ INIT_NONZERO_DICT_SLOTS(d);
+ d->ma_lookup = lookdict_string;
+#ifdef SHOW_CONVERSION_COUNTS
+ ++created;
+#endif
+ }
+ return self;
+}
+
+static int
+dict_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ return dict_update_common(self, args, kwds, "dict");
+}
+
+static PyObject *
+dict_iter(PyDictObject *dict)
+{
+ return dictiter_new(dict, &PyDictIterKey_Type);
+}
+
+PyDoc_STRVAR(dictionary_doc,
+"dict() -> new empty dictionary.\n"
+"dict(mapping) -> new dictionary initialized from a mapping object's\n"
+" (key, value) pairs.\n"
+"dict(seq) -> new dictionary initialized as if via:\n"
+" d = {}\n"
+" for k, v in seq:\n"
+" d[k] = v\n"
+"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
+" in the keyword argument list. For example: dict(one=1, two=2)");
+
+PyTypeObject PyDict_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "dict",
+ sizeof(PyDictObject),
+ 0,
+ (destructor)dict_dealloc, /* tp_dealloc */
+ (printfunc)dict_print, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ (cmpfunc)dict_compare, /* tp_compare */
+ (reprfunc)dict_repr, /* tp_repr */
+ 0, /* tp_as_number */
+ &dict_as_sequence, /* tp_as_sequence */
+ &dict_as_mapping, /* tp_as_mapping */
+ (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
+ dictionary_doc, /* tp_doc */
+ dict_traverse, /* tp_traverse */
+ dict_tp_clear, /* tp_clear */
+ dict_richcompare, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ (getiterfunc)dict_iter, /* tp_iter */
+ 0, /* tp_iternext */
+ mapp_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ dict_init, /* tp_init */
+ PyType_GenericAlloc, /* tp_alloc */
+ dict_new, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+};
+
+/* For backward compatibility with old dictionary interface */
+
+PyObject *
+PyDict_GetItemString(PyObject *v, const char *key)
+{
+ PyObject *kv, *rv;
+ kv = PyString_FromString(key);
+ if (kv == NULL)
+ return NULL;
+ rv = PyDict_GetItem(v, kv);
+ Py_DECREF(kv);
+ return rv;
+}
+
+int
+PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
+{
+ PyObject *kv;
+ int err;
+ kv = PyString_FromString(key);
+ if (kv == NULL)
+ return -1;
+ PyString_InternInPlace(&kv); /* XXX Should we really? */
+ err = PyDict_SetItem(v, kv, item);
+ Py_DECREF(kv);
+ return err;
+}
+
+int
+PyDict_DelItemString(PyObject *v, const char *key)
+{
+ PyObject *kv;
+ int err;
+ kv = PyString_FromString(key);
+ if (kv == NULL)
+ return -1;
+ err = PyDict_DelItem(v, kv);
+ Py_DECREF(kv);
+ return err;
+}
+
+/* Dictionary iterator types */
+
+typedef struct {
+ PyObject_HEAD
+ PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
+ Py_ssize_t di_used;
+ Py_ssize_t di_pos;
+ PyObject* di_result; /* reusable result tuple for iteritems */
+ Py_ssize_t len;
+} dictiterobject;
+
+static PyObject *
+dictiter_new(PyDictObject *dict, PyTypeObject *itertype)
+{
+ dictiterobject *di;
+ di = PyObject_New(dictiterobject, itertype);
+ if (di == NULL)
+ return NULL;
+ Py_INCREF(dict);
+ di->di_dict = dict;
+ di->di_used = dict->ma_used;
+ di->di_pos = 0;
+ di->len = dict->ma_used;
+ if (itertype == &PyDictIterItem_Type) {
+ di->di_result = PyTuple_Pack(2, Py_None, Py_None);
+ if (di->di_result == NULL) {
+ Py_DECREF(di);
+ return NULL;
+ }
+ }
+ else
+ di->di_result = NULL;
+ return (PyObject *)di;
+}
+
+static void
+dictiter_dealloc(dictiterobject *di)
+{
+ Py_XDECREF(di->di_dict);
+ Py_XDECREF(di->di_result);
+ PyObject_Del(di);
+}
+
+static PyObject *
+dictiter_len(dictiterobject *di)
+{
+ Py_ssize_t len = 0;
+ if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
+ len = di->len;
+ return PyInt_FromSize_t(len);
+}
+
+PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
+
+static PyMethodDef dictiter_methods[] = {
+ {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS, length_hint_doc},
+ {NULL, NULL} /* sentinel */
+};
+
+static PyObject *dictiter_iternextkey(dictiterobject *di)
+{
+ PyObject *key;
+ register Py_ssize_t i, mask;
+ register PyDictEntry *ep;
+ PyDictObject *d = di->di_dict;
+
+ if (d == NULL)
+ return NULL;
+ assert (PyDict_Check(d));
+
+ if (di->di_used != d->ma_used) {
+ PyErr_SetString(PyExc_RuntimeError,
+ "dictionary changed size during iteration");
+ di->di_used = -1; /* Make this state sticky */
+ return NULL;
+ }
+
+ i = di->di_pos;
+ if (i < 0)
+ goto fail;
+ ep = d->ma_table;
+ mask = d->ma_mask;
+ while (i <= mask && ep[i].me_value == NULL)
+ i++;
+ di->di_pos = i+1;
+ if (i > mask)
+ goto fail;
+ di->len--;
+ key = ep[i].me_key;
+ Py_INCREF(key);
+ return key;
+
+fail:
+ Py_DECREF(d);
+ di->di_dict = NULL;
+ return NULL;
+}
+
+PyTypeObject PyDictIterKey_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "dictionary-keyiterator", /* tp_name */
+ sizeof(dictiterobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)dictiter_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ 0, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)dictiter_iternextkey, /* tp_iternext */
+ dictiter_methods, /* tp_methods */
+ 0,
+};
+
+static PyObject *dictiter_iternextvalue(dictiterobject *di)
+{
+ PyObject *value;
+ register Py_ssize_t i, mask;
+ register PyDictEntry *ep;
+ PyDictObject *d = di->di_dict;
+
+ if (d == NULL)
+ return NULL;
+ assert (PyDict_Check(d));
+
+ if (di->di_used != d->ma_used) {
+ PyErr_SetString(PyExc_RuntimeError,
+ "dictionary changed size during iteration");
+ di->di_used = -1; /* Make this state sticky */
+ return NULL;
+ }
+
+ i = di->di_pos;
+ mask = d->ma_mask;
+ if (i < 0 || i > mask)
+ goto fail;
+ ep = d->ma_table;
+ while ((value=ep[i].me_value) == NULL) {
+ i++;
+ if (i > mask)
+ goto fail;
+ }
+ di->di_pos = i+1;
+ di->len--;
+ Py_INCREF(value);
+ return value;
+
+fail:
+ Py_DECREF(d);
+ di->di_dict = NULL;
+ return NULL;
+}
+
+PyTypeObject PyDictIterValue_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "dictionary-valueiterator", /* tp_name */
+ sizeof(dictiterobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)dictiter_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ 0, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
+ dictiter_methods, /* tp_methods */
+ 0,
+};
+
+static PyObject *dictiter_iternextitem(dictiterobject *di)
+{
+ PyObject *key, *value, *result = di->di_result;
+ register Py_ssize_t i, mask;
+ register PyDictEntry *ep;
+ PyDictObject *d = di->di_dict;
+
+ if (d == NULL)
+ return NULL;
+ assert (PyDict_Check(d));
+
+ if (di->di_used != d->ma_used) {
+ PyErr_SetString(PyExc_RuntimeError,
+ "dictionary changed size during iteration");
+ di->di_used = -1; /* Make this state sticky */
+ return NULL;
+ }
+
+ i = di->di_pos;
+ if (i < 0)
+ goto fail;
+ ep = d->ma_table;
+ mask = d->ma_mask;
+ while (i <= mask && ep[i].me_value == NULL)
+ i++;
+ di->di_pos = i+1;
+ if (i > mask)
+ goto fail;
+
+ if (result->ob_refcnt == 1) {
+ Py_INCREF(result);
+ Py_DECREF(PyTuple_GET_ITEM(result, 0));
+ Py_DECREF(PyTuple_GET_ITEM(result, 1));
+ } else {
+ result = PyTuple_New(2);
+ if (result == NULL)
+ return NULL;
+ }
+ di->len--;
+ key = ep[i].me_key;
+ value = ep[i].me_value;
+ Py_INCREF(key);
+ Py_INCREF(value);
+ PyTuple_SET_ITEM(result, 0, key);
+ PyTuple_SET_ITEM(result, 1, value);
+ return result;
+
+fail:
+ Py_DECREF(d);
+ di->di_dict = NULL;
+ return NULL;
+}
+
+PyTypeObject PyDictIterItem_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "dictionary-itemiterator", /* tp_name */
+ sizeof(dictiterobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)dictiter_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ 0, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)dictiter_iternextitem, /* tp_iternext */
+ dictiter_methods, /* tp_methods */
+ 0,
+};