diff -r ffa851df0825 -r 2fb8b9db1c86 symbian-qemu-0.9.1-12/python-2.6.1/Objects/dictobject.c --- /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(""); + 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 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, +};