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