]> git.proxmox.com Git - mirror_edk2.git/blame - AppPkg/Applications/Python/Python-2.7.10/Objects/dictobject.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS
[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Objects / dictobject.c
CommitLineData
53b2ba57
DM		 1\r
2/* Dictionary object implementation using a hash table */\r
3\r
4/* The distribution includes a separate file, Objects/dictnotes.txt,\r
5 describing explorations into dictionary design and optimization.\r
6 It covers typical dictionary use patterns, the parameters for\r
7 tuning dictionaries, and several ideas for possible optimizations.\r
8*/\r
9\r
10#include "Python.h"\r
11\r
12\r
13/* Set a key error with the specified argument, wrapping it in a\r
14 * tuple automatically so that tuple keys are not unpacked as the\r
15 * exception arguments. */\r
16static void\r
17set_key_error(PyObject *arg)\r
18{\r
19 PyObject *tup;\r
20 tup = PyTuple_Pack(1, arg);\r
21 if (!tup)\r
22 return; /* caller will expect error to be set anyway */\r
23 PyErr_SetObject(PyExc_KeyError, tup);\r
24 Py_DECREF(tup);\r
25}\r
26\r
27/* Define this out if you don't want conversion statistics on exit. */\r
28#undef SHOW_CONVERSION_COUNTS\r
29\r
30/* See large comment block below. This must be >= 1. */\r
31#define PERTURB_SHIFT 5\r
32\r
33/*\r
34Major subtleties ahead: Most hash schemes depend on having a "good" hash\r
35function, in the sense of simulating randomness. Python doesn't: its most\r
36important hash functions (for strings and ints) are very regular in common\r
37cases:\r
38\r
39>>> map(hash, (0, 1, 2, 3))\r
40[0, 1, 2, 3]\r
41>>> map(hash, ("namea", "nameb", "namec", "named"))\r
42[-1658398457, -1658398460, -1658398459, -1658398462]\r
43>>>\r
44\r
45This isn't necessarily bad! To the contrary, in a table of size 2**i, taking\r
46the low-order i bits as the initial table index is extremely fast, and there\r
47are no collisions at all for dicts indexed by a contiguous range of ints.\r
48The same is approximately true when keys are "consecutive" strings. So this\r
49gives better-than-random behavior in common cases, and that's very desirable.\r
50\r
51OTOH, when collisions occur, the tendency to fill contiguous slices of the\r
52hash table makes a good collision resolution strategy crucial. Taking only\r
53the last i bits of the hash code is also vulnerable: for example, consider\r
54[i << 16 for i in range(20000)] as a set of keys. Since ints are their own\r
55hash codes, and this fits in a dict of size 2**15, the last 15 bits of every\r
56hash code are all 0: they *all* map to the same table index.\r
57\r
58But catering to unusual cases should not slow the usual ones, so we just take\r
59the last i bits anyway. It's up to collision resolution to do the rest. If\r
60we *usually* find the key we're looking for on the first try (and, it turns\r
61out, we usually do -- the table load factor is kept under 2/3, so the odds\r
62are solidly in our favor), then it makes best sense to keep the initial index\r
63computation dirt cheap.\r
64\r
65The first half of collision resolution is to visit table indices via this\r
66recurrence:\r
67\r
68 j = ((5*j) + 1) mod 2**i\r
69\r
70For any initial j in range(2**i), repeating that 2**i times generates each\r
71int in range(2**i) exactly once (see any text on random-number generation for\r
72proof). By itself, this doesn't help much: like linear probing (setting\r
73j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed\r
74order. This would be bad, except that's not the only thing we do, and it's\r
75actually *good* in the common cases where hash keys are consecutive. In an\r
76example that's really too small to make this entirely clear, for a table of\r
77size 2**3 the order of indices is:\r
78\r
79 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]\r
80\r
81If two things come in at index 5, the first place we look after is index 2,\r
82not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.\r
83Linear probing is deadly in this case because there the fixed probe order\r
84is the *same* as the order consecutive keys are likely to arrive. But it's\r
85extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,\r
86and certain that consecutive hash codes do not.\r
87\r
88The other half of the strategy is to get the other bits of the hash code\r
89into play. This is done by initializing a (unsigned) vrbl "perturb" to the\r
90full hash code, and changing the recurrence to:\r
91\r
92 j = (5*j) + 1 + perturb;\r
93 perturb >>= PERTURB_SHIFT;\r
94 use j % 2**i as the next table index;\r
95\r
96Now the probe sequence depends (eventually) on every bit in the hash code,\r
97and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,\r
98because it quickly magnifies small differences in the bits that didn't affect\r
99the initial index. Note that because perturb is unsigned, if the recurrence\r
100is executed often enough perturb eventually becomes and remains 0. At that\r
101point (very rarely reached) the recurrence is on (just) 5*j+1 again, and\r
102that's certain to find an empty slot eventually (since it generates every int\r
103in range(2**i), and we make sure there's always at least one empty slot).\r
104\r
105Selecting a good value for PERTURB_SHIFT is a balancing act. You want it\r
106small so that the high bits of the hash code continue to affect the probe\r
107sequence across iterations; but you want it large so that in really bad cases\r
108the high-order hash bits have an effect on early iterations. 5 was "the\r
109best" in minimizing total collisions across experiments Tim Peters ran (on\r
110both normal and pathological cases), but 4 and 6 weren't significantly worse.\r
111\r
112Historical: Reimer Behrends contributed the idea of using a polynomial-based\r
113approach, using repeated multiplication by x in GF(2**n) where an irreducible\r
114polynomial for each table size was chosen such that x was a primitive root.\r
115Christian Tismer later extended that to use division by x instead, as an\r
116efficient way to get the high bits of the hash code into play. This scheme\r
117also gave excellent collision statistics, but was more expensive: two\r
118if-tests were required inside the loop; computing "the next" index took about\r
119the same number of operations but without as much potential parallelism\r
120(e.g., computing 5*j can go on at the same time as computing 1+perturb in the\r
121above, and then shifting perturb can be done while the table index is being\r
122masked); and the PyDictObject struct required a member to hold the table's\r
123polynomial. In Tim's experiments the current scheme ran faster, produced\r
124equally good collision statistics, needed less code & used less memory.\r
125\r
126Theoretical Python 2.5 headache: hash codes are only C "long", but\r
127sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a\r
128dict is genuinely huge, then only the slots directly reachable via indexing\r
129by a C long can be the first slot in a probe sequence. The probe sequence\r
130will still eventually reach every slot in the table, but the collision rate\r
131on initial probes may be much higher than this scheme was designed for.\r
132Getting a hash code as fat as Py_ssize_t is the only real cure. But in\r
133practice, this probably won't make a lick of difference for many years (at\r
134which point everyone will have terabytes of RAM on 64-bit boxes).\r
135*/\r
136\r
137/* Object used as dummy key to fill deleted entries */\r
138static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */\r
139\r
140#ifdef Py_REF_DEBUG\r
141PyObject *\r
142_PyDict_Dummy(void)\r
143{\r
144 return dummy;\r
145}\r
146#endif\r
147\r
148/* forward declarations */\r
149static PyDictEntry *\r
150lookdict_string(PyDictObject *mp, PyObject *key, long hash);\r
151\r
152#ifdef SHOW_CONVERSION_COUNTS\r
153static long created = 0L;\r
154static long converted = 0L;\r
155\r
156static void\r
157show_counts(void)\r
158{\r
159 fprintf(stderr, "created %ld string dicts\n", created);\r
160 fprintf(stderr, "converted %ld to normal dicts\n", converted);\r
161 fprintf(stderr, "%.2f%% conversion rate\n", (100.0*converted)/created);\r
162}\r
163#endif\r
164\r
165/* Debug statistic to compare allocations with reuse through the free list */\r
166#undef SHOW_ALLOC_COUNT\r
167#ifdef SHOW_ALLOC_COUNT\r
168static size_t count_alloc = 0;\r
169static size_t count_reuse = 0;\r
170\r
171static void\r
172show_alloc(void)\r
173{\r
174 fprintf(stderr, "Dict allocations: %" PY_FORMAT_SIZE_T "d\n",\r
175 count_alloc);\r
176 fprintf(stderr, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T\r
177 "d\n", count_reuse);\r
178 fprintf(stderr, "%.2f%% reuse rate\n\n",\r
179 (100.0*count_reuse/(count_alloc+count_reuse)));\r
180}\r
181#endif\r
182\r
183/* Debug statistic to count GC tracking of dicts */\r
184#ifdef SHOW_TRACK_COUNT\r
185static Py_ssize_t count_untracked = 0;\r
186static Py_ssize_t count_tracked = 0;\r
187\r
188static void\r
189show_track(void)\r
190{\r
191 fprintf(stderr, "Dicts created: %" PY_FORMAT_SIZE_T "d\n",\r
192 count_tracked + count_untracked);\r
193 fprintf(stderr, "Dicts tracked by the GC: %" PY_FORMAT_SIZE_T\r
194 "d\n", count_tracked);\r
195 fprintf(stderr, "%.2f%% dict tracking rate\n\n",\r
196 (100.0*count_tracked/(count_untracked+count_tracked)));\r
197}\r
198#endif\r
199\r
200\r
201/* Initialization macros.\r
202 There are two ways to create a dict: PyDict_New() is the main C API\r
203 function, and the tp_new slot maps to dict_new(). In the latter case we\r
204 can save a little time over what PyDict_New does because it's guaranteed\r
205 that the PyDictObject struct is already zeroed out.\r
206 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have\r
207 an excellent reason not to).\r
208*/\r
209\r
210#define INIT_NONZERO_DICT_SLOTS(mp) do { \\r
211 (mp)->ma_table = (mp)->ma_smalltable; \\r
212 (mp)->ma_mask = PyDict_MINSIZE - 1; \\r
213 } while(0)\r
214\r
215#define EMPTY_TO_MINSIZE(mp) do { \\r
216 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \\r
217 (mp)->ma_used = (mp)->ma_fill = 0; \\r
218 INIT_NONZERO_DICT_SLOTS(mp); \\r
219 } while(0)\r
220\r
221/* Dictionary reuse scheme to save calls to malloc, free, and memset */\r
222#ifndef PyDict_MAXFREELIST\r
223#define PyDict_MAXFREELIST 80\r
224#endif\r
225static PyDictObject *free_list[PyDict_MAXFREELIST];\r
226static int numfree = 0;\r
227\r
228void\r
229PyDict_Fini(void)\r
230{\r
231 PyDictObject *op;\r
232\r
233 while (numfree) {\r
234 op = free_list[--numfree];\r
235 assert(PyDict_CheckExact(op));\r
236 PyObject_GC_Del(op);\r
237 }\r
238}\r
239\r
240PyObject *\r
241PyDict_New(void)\r
242{\r
243 register PyDictObject *mp;\r
244 if (dummy == NULL) { /* Auto-initialize dummy */\r
245 dummy = PyString_FromString("<dummy key>");\r
246 if (dummy == NULL)\r
247 return NULL;\r
248#ifdef SHOW_CONVERSION_COUNTS\r
249 Py_AtExit(show_counts);\r
250#endif\r
251#ifdef SHOW_ALLOC_COUNT\r
252 Py_AtExit(show_alloc);\r
253#endif\r
254#ifdef SHOW_TRACK_COUNT\r
255 Py_AtExit(show_track);\r
256#endif\r
257 }\r
258 if (numfree) {\r
259 mp = free_list[--numfree];\r
260 assert (mp != NULL);\r
261 assert (Py_TYPE(mp) == &PyDict_Type);\r
262 _Py_NewReference((PyObject *)mp);\r
263 if (mp->ma_fill) {\r
264 EMPTY_TO_MINSIZE(mp);\r
265 } else {\r
266 /* At least set ma_table and ma_mask; these are wrong\r
267 if an empty but presized dict is added to freelist */\r
268 INIT_NONZERO_DICT_SLOTS(mp);\r
269 }\r
270 assert (mp->ma_used == 0);\r
271 assert (mp->ma_table == mp->ma_smalltable);\r
272 assert (mp->ma_mask == PyDict_MINSIZE - 1);\r
273#ifdef SHOW_ALLOC_COUNT\r
274 count_reuse++;\r
275#endif\r
276 } else {\r
277 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);\r
278 if (mp == NULL)\r
279 return NULL;\r
280 EMPTY_TO_MINSIZE(mp);\r
281#ifdef SHOW_ALLOC_COUNT\r
282 count_alloc++;\r
283#endif\r
284 }\r
285 mp->ma_lookup = lookdict_string;\r
286#ifdef SHOW_TRACK_COUNT\r
287 count_untracked++;\r
288#endif\r
289#ifdef SHOW_CONVERSION_COUNTS\r
290 ++created;\r
291#endif\r
292 return (PyObject *)mp;\r
293}\r
294\r
295/*\r
296The basic lookup function used by all operations.\r
297This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.\r
298Open addressing is preferred over chaining since the link overhead for\r
299chaining would be substantial (100% with typical malloc overhead).\r
300\r
301The initial probe index is computed as hash mod the table size. Subsequent\r
302probe indices are computed as explained earlier.\r
303\r
304All arithmetic on hash should ignore overflow.\r
305\r
306(The details in this version are due to Tim Peters, building on many past\r
307contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and\r
308Christian Tismer).\r
309\r
310lookdict() is general-purpose, and may return NULL if (and only if) a\r
311comparison raises an exception (this was new in Python 2.5).\r
312lookdict_string() below is specialized to string keys, comparison of which can\r
313never raise an exception; that function can never return NULL. For both, when\r
314the key isn't found a PyDictEntry* is returned for which the me_value field is\r
315NULL; this is the slot in the dict at which the key would have been found, and\r
316the caller can (if it wishes) add the <key, value> pair to the returned\r
317PyDictEntry*.\r
318*/\r
319static PyDictEntry *\r
320lookdict(PyDictObject *mp, PyObject *key, register long hash)\r
321{\r
322 register size_t i;\r
323 register size_t perturb;\r
324 register PyDictEntry *freeslot;\r
325 register size_t mask = (size_t)mp->ma_mask;\r
326 PyDictEntry *ep0 = mp->ma_table;\r
327 register PyDictEntry *ep;\r
328 register int cmp;\r
329 PyObject *startkey;\r
330\r
331 i = (size_t)hash & mask;\r
332 ep = &ep0[i];\r
333 if (ep->me_key == NULL || ep->me_key == key)\r
334 return ep;\r
335\r
336 if (ep->me_key == dummy)\r
337 freeslot = ep;\r
338 else {\r
339 if (ep->me_hash == hash) {\r
340 startkey = ep->me_key;\r
341 Py_INCREF(startkey);\r
342 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);\r
343 Py_DECREF(startkey);\r
344 if (cmp < 0)\r
345 return NULL;\r
346 if (ep0 == mp->ma_table && ep->me_key == startkey) {\r
347 if (cmp > 0)\r
348 return ep;\r
349 }\r
350 else {\r
351 /* The compare did major nasty stuff to the\r
352 * dict: start over.\r
353 * XXX A clever adversary could prevent this\r
354 * XXX from terminating.\r
355 */\r
356 return lookdict(mp, key, hash);\r
357 }\r
358 }\r
359 freeslot = NULL;\r
360 }\r
361\r
362 /* In the loop, me_key == dummy is by far (factor of 100s) the\r
363 least likely outcome, so test for that last. */\r
364 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {\r
365 i = (i << 2) + i + perturb + 1;\r
366 ep = &ep0[i & mask];\r
367 if (ep->me_key == NULL)\r
368 return freeslot == NULL ? ep : freeslot;\r
369 if (ep->me_key == key)\r
370 return ep;\r
371 if (ep->me_hash == hash && ep->me_key != dummy) {\r
372 startkey = ep->me_key;\r
373 Py_INCREF(startkey);\r
374 cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);\r
375 Py_DECREF(startkey);\r
376 if (cmp < 0)\r
377 return NULL;\r
378 if (ep0 == mp->ma_table && ep->me_key == startkey) {\r
379 if (cmp > 0)\r
380 return ep;\r
381 }\r
382 else {\r
383 /* The compare did major nasty stuff to the\r
384 * dict: start over.\r
385 * XXX A clever adversary could prevent this\r
386 * XXX from terminating.\r
387 */\r
388 return lookdict(mp, key, hash);\r
389 }\r
390 }\r
391 else if (ep->me_key == dummy && freeslot == NULL)\r
392 freeslot = ep;\r
393 }\r
394 assert(0); /* NOT REACHED */\r
395 return 0;\r
396}\r
397\r
398/*\r
399 * Hacked up version of lookdict which can assume keys are always strings;\r
400 * this assumption allows testing for errors during PyObject_RichCompareBool()\r
401 * to be dropped; string-string comparisons never raise exceptions. This also\r
402 * means we don't need to go through PyObject_RichCompareBool(); we can always\r
403 * use _PyString_Eq() directly.\r
404 *\r
405 * This is valuable because dicts with only string keys are very common.\r
406 */\r
407static PyDictEntry *\r
408lookdict_string(PyDictObject *mp, PyObject *key, register long hash)\r
409{\r
410 register size_t i;\r
411 register size_t perturb;\r
412 register PyDictEntry *freeslot;\r
413 register size_t mask = (size_t)mp->ma_mask;\r
414 PyDictEntry *ep0 = mp->ma_table;\r
415 register PyDictEntry *ep;\r
416\r
417 /* Make sure this function doesn't have to handle non-string keys,\r
418 including subclasses of str; e.g., one reason to subclass\r
419 strings is to override __eq__, and for speed we don't cater to\r
420 that here. */\r
421 if (!PyString_CheckExact(key)) {\r
422#ifdef SHOW_CONVERSION_COUNTS\r
423 ++converted;\r
424#endif\r
425 mp->ma_lookup = lookdict;\r
426 return lookdict(mp, key, hash);\r
427 }\r
428 i = hash & mask;\r
429 ep = &ep0[i];\r
430 if (ep->me_key == NULL || ep->me_key == key)\r
431 return ep;\r
432 if (ep->me_key == dummy)\r
433 freeslot = ep;\r
434 else {\r
435 if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))\r
436 return ep;\r
437 freeslot = NULL;\r
438 }\r
439\r
440 /* In the loop, me_key == dummy is by far (factor of 100s) the\r
441 least likely outcome, so test for that last. */\r
442 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {\r
443 i = (i << 2) + i + perturb + 1;\r
444 ep = &ep0[i & mask];\r
445 if (ep->me_key == NULL)\r
446 return freeslot == NULL ? ep : freeslot;\r
447 if (ep->me_key == key\r
448 || (ep->me_hash == hash\r
449 && ep->me_key != dummy\r
450 && _PyString_Eq(ep->me_key, key)))\r
451 return ep;\r
452 if (ep->me_key == dummy && freeslot == NULL)\r
453 freeslot = ep;\r
454 }\r
455 assert(0); /* NOT REACHED */\r
456 return 0;\r
457}\r
458\r
459#ifdef SHOW_TRACK_COUNT\r
460#define INCREASE_TRACK_COUNT \\r
461 (count_tracked++, count_untracked--);\r
462#define DECREASE_TRACK_COUNT \\r
463 (count_tracked--, count_untracked++);\r
464#else\r
465#define INCREASE_TRACK_COUNT\r
466#define DECREASE_TRACK_COUNT\r
467#endif\r
468\r
469#define MAINTAIN_TRACKING(mp, key, value) \\r
470 do { \\r
471 if (!_PyObject_GC_IS_TRACKED(mp)) { \\r
472 if (_PyObject_GC_MAY_BE_TRACKED(key) || \\r
473 _PyObject_GC_MAY_BE_TRACKED(value)) { \\r
474 _PyObject_GC_TRACK(mp); \\r
475 INCREASE_TRACK_COUNT \\r
476 } \\r
477 } \\r
478 } while(0)\r
479\r
480void\r
481_PyDict_MaybeUntrack(PyObject *op)\r
482{\r
483 PyDictObject *mp;\r
484 PyObject *value;\r
485 Py_ssize_t mask, i;\r
486 PyDictEntry *ep;\r
487\r
488 if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))\r
489 return;\r
490\r
491 mp = (PyDictObject *) op;\r
492 ep = mp->ma_table;\r
493 mask = mp->ma_mask;\r
494 for (i = 0; i <= mask; i++) {\r
495 if ((value = ep[i].me_value) == NULL)\r
496 continue;\r
497 if (_PyObject_GC_MAY_BE_TRACKED(value) ||\r
498 _PyObject_GC_MAY_BE_TRACKED(ep[i].me_key))\r
499 return;\r
500 }\r
501 DECREASE_TRACK_COUNT\r
502 _PyObject_GC_UNTRACK(op);\r
503}\r
504\r
505/*\r
506Internal routine to insert a new item into the table when you have entry object.\r
507Used by insertdict.\r
508*/\r
509static int\r
510insertdict_by_entry(register PyDictObject *mp, PyObject *key, long hash,\r
511 PyDictEntry *ep, PyObject *value)\r
512{\r
513 PyObject *old_value;\r
514\r
515 MAINTAIN_TRACKING(mp, key, value);\r
516 if (ep->me_value != NULL) {\r
517 old_value = ep->me_value;\r
518 ep->me_value = value;\r
519 Py_DECREF(old_value); /* which **CAN** re-enter */\r
520 Py_DECREF(key);\r
521 }\r
522 else {\r
523 if (ep->me_key == NULL)\r
524 mp->ma_fill++;\r
525 else {\r
526 assert(ep->me_key == dummy);\r
527 Py_DECREF(dummy);\r
528 }\r
529 ep->me_key = key;\r
530 ep->me_hash = (Py_ssize_t)hash;\r
531 ep->me_value = value;\r
532 mp->ma_used++;\r
533 }\r
534 return 0;\r
535}\r
536\r
537\r
538/*\r
539Internal routine to insert a new item into the table.\r
540Used both by the internal resize routine and by the public insert routine.\r
541Eats a reference to key and one to value.\r
542Returns -1 if an error occurred, or 0 on success.\r
543*/\r
544static int\r
545insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)\r
546{\r
547 register PyDictEntry *ep;\r
548\r
549 assert(mp->ma_lookup != NULL);\r
550 ep = mp->ma_lookup(mp, key, hash);\r
551 if (ep == NULL) {\r
552 Py_DECREF(key);\r
553 Py_DECREF(value);\r
554 return -1;\r
555 }\r
556 return insertdict_by_entry(mp, key, hash, ep, value);\r
557}\r
558\r
559/*\r
560Internal routine used by dictresize() to insert an item which is\r
561known to be absent from the dict. This routine also assumes that\r
562the dict contains no deleted entries. Besides the performance benefit,\r
563using insertdict() in dictresize() is dangerous (SF bug #1456209).\r
564Note that no refcounts are changed by this routine; if needed, the caller\r
565is responsible for incref'ing `key` and `value`.\r
566*/\r
567static void\r
568insertdict_clean(register PyDictObject *mp, PyObject *key, long hash,\r
569 PyObject *value)\r
570{\r
571 register size_t i;\r
572 register size_t perturb;\r
573 register size_t mask = (size_t)mp->ma_mask;\r
574 PyDictEntry *ep0 = mp->ma_table;\r
575 register PyDictEntry *ep;\r
576\r
577 MAINTAIN_TRACKING(mp, key, value);\r
578 i = hash & mask;\r
579 ep = &ep0[i];\r
580 for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {\r
581 i = (i << 2) + i + perturb + 1;\r
582 ep = &ep0[i & mask];\r
583 }\r
584 assert(ep->me_value == NULL);\r
585 mp->ma_fill++;\r
586 ep->me_key = key;\r
587 ep->me_hash = (Py_ssize_t)hash;\r
588 ep->me_value = value;\r
589 mp->ma_used++;\r
590}\r
591\r
592/*\r
593Restructure the table by allocating a new table and reinserting all\r
594items again. When entries have been deleted, the new table may\r
595actually be smaller than the old one.\r
596*/\r
597static int\r
598dictresize(PyDictObject *mp, Py_ssize_t minused)\r
599{\r
600 Py_ssize_t newsize;\r
601 PyDictEntry *oldtable, *newtable, *ep;\r
602 Py_ssize_t i;\r
603 int is_oldtable_malloced;\r
604 PyDictEntry small_copy[PyDict_MINSIZE];\r
605\r
606 assert(minused >= 0);\r
607\r
608 /* Find the smallest table size > minused. */\r
609 for (newsize = PyDict_MINSIZE;\r
610 newsize <= minused && newsize > 0;\r
611 newsize <<= 1)\r
612 ;\r
613 if (newsize <= 0) {\r
614 PyErr_NoMemory();\r
615 return -1;\r
616 }\r
617\r
618 /* Get space for a new table. */\r
619 oldtable = mp->ma_table;\r
620 assert(oldtable != NULL);\r
621 is_oldtable_malloced = oldtable != mp->ma_smalltable;\r
622\r
623 if (newsize == PyDict_MINSIZE) {\r
624 /* A large table is shrinking, or we can't get any smaller. */\r
625 newtable = mp->ma_smalltable;\r
626 if (newtable == oldtable) {\r
627 if (mp->ma_fill == mp->ma_used) {\r
628 /* No dummies, so no point doing anything. */\r
629 return 0;\r
630 }\r
631 /* We're not going to resize it, but rebuild the\r
632 table anyway to purge old dummy entries.\r
633 Subtle: This is *necessary* if fill==size,\r
634 as lookdict needs at least one virgin slot to\r
635 terminate failing searches. If fill < size, it's\r
636 merely desirable, as dummies slow searches. */\r
637 assert(mp->ma_fill > mp->ma_used);\r
638 memcpy(small_copy, oldtable, sizeof(small_copy));\r
639 oldtable = small_copy;\r
640 }\r
641 }\r
642 else {\r
643 newtable = PyMem_NEW(PyDictEntry, newsize);\r
644 if (newtable == NULL) {\r
645 PyErr_NoMemory();\r
646 return -1;\r
647 }\r
648 }\r
649\r
650 /* Make the dict empty, using the new table. */\r
651 assert(newtable != oldtable);\r
652 mp->ma_table = newtable;\r
653 mp->ma_mask = newsize - 1;\r
654 memset(newtable, 0, sizeof(PyDictEntry) * newsize);\r
655 mp->ma_used = 0;\r
656 i = mp->ma_fill;\r
657 mp->ma_fill = 0;\r
658\r
659 /* Copy the data over; this is refcount-neutral for active entries;\r
660 dummy entries aren't copied over, of course */\r
661 for (ep = oldtable; i > 0; ep++) {\r
662 if (ep->me_value != NULL) { /* active entry */\r
663 --i;\r
664 insertdict_clean(mp, ep->me_key, (long)ep->me_hash,\r
665 ep->me_value);\r
666 }\r
667 else if (ep->me_key != NULL) { /* dummy entry */\r
668 --i;\r
669 assert(ep->me_key == dummy);\r
670 Py_DECREF(ep->me_key);\r
671 }\r
672 /* else key == value == NULL: nothing to do */\r
673 }\r
674\r
675 if (is_oldtable_malloced)\r
676 PyMem_DEL(oldtable);\r
677 return 0;\r
678}\r
679\r
680/* Create a new dictionary pre-sized to hold an estimated number of elements.\r
681 Underestimates are okay because the dictionary will resize as necessary.\r
682 Overestimates just mean the dictionary will be more sparse than usual.\r
683*/\r
684\r
685PyObject *\r
686_PyDict_NewPresized(Py_ssize_t minused)\r
687{\r
688 PyObject *op = PyDict_New();\r
689\r
690 if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {\r
691 Py_DECREF(op);\r
692 return NULL;\r
693 }\r
694 return op;\r
695}\r
696\r
697/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors\r
698 * that may occur (originally dicts supported only string keys, and exceptions\r
699 * weren't possible). So, while the original intent was that a NULL return\r
700 * meant the key wasn't present, in reality it can mean that, or that an error\r
701 * (suppressed) occurred while computing the key's hash, or that some error\r
702 * (suppressed) occurred when comparing keys in the dict's internal probe\r
703 * sequence. A nasty example of the latter is when a Python-coded comparison\r
704 * function hits a stack-depth error, which can cause this to return NULL\r
705 * even if the key is present.\r
706 */\r
707PyObject *\r
708PyDict_GetItem(PyObject *op, PyObject *key)\r
709{\r
710 long hash;\r
711 PyDictObject *mp = (PyDictObject *)op;\r
712 PyDictEntry *ep;\r
713 PyThreadState *tstate;\r
714 if (!PyDict_Check(op))\r
715 return NULL;\r
716 if (!PyString_CheckExact(key) ||\r
717 (hash = ((PyStringObject *) key)->ob_shash) == -1)\r
718 {\r
719 hash = PyObject_Hash(key);\r
720 if (hash == -1) {\r
721 PyErr_Clear();\r
722 return NULL;\r
723 }\r
724 }\r
725\r
726 /* We can arrive here with a NULL tstate during initialization: try\r
727 running "python -Wi" for an example related to string interning.\r
728 Let's just hope that no exception occurs then... This must be\r
729 _PyThreadState_Current and not PyThreadState_GET() because in debug\r
730 mode, the latter complains if tstate is NULL. */\r
731 tstate = _PyThreadState_Current;\r
732 if (tstate != NULL && tstate->curexc_type != NULL) {\r
733 /* preserve the existing exception */\r
734 PyObject *err_type, *err_value, *err_tb;\r
735 PyErr_Fetch(&err_type, &err_value, &err_tb);\r
736 ep = (mp->ma_lookup)(mp, key, hash);\r
737 /* ignore errors */\r
738 PyErr_Restore(err_type, err_value, err_tb);\r
739 if (ep == NULL)\r
740 return NULL;\r
741 }\r
742 else {\r
743 ep = (mp->ma_lookup)(mp, key, hash);\r
744 if (ep == NULL) {\r
745 PyErr_Clear();\r
746 return NULL;\r
747 }\r
748 }\r
749 return ep->me_value;\r
750}\r
751\r
752static int\r
753dict_set_item_by_hash_or_entry(register PyObject *op, PyObject *key,\r
754 long hash, PyDictEntry *ep, PyObject *value)\r
755{\r
756 register PyDictObject *mp;\r
757 register Py_ssize_t n_used;\r
758\r
759 mp = (PyDictObject *)op;\r
760 assert(mp->ma_fill <= mp->ma_mask); /* at least one empty slot */\r
761 n_used = mp->ma_used;\r
762 Py_INCREF(value);\r
763 Py_INCREF(key);\r
764 if (ep == NULL) {\r
765 if (insertdict(mp, key, hash, value) != 0)\r
766 return -1;\r
767 }\r
768 else {\r
769 if (insertdict_by_entry(mp, key, hash, ep, value) != 0)\r
770 return -1;\r
771 }\r
772 /* If we added a key, we can safely resize. Otherwise just return!\r
773 * If fill >= 2/3 size, adjust size. Normally, this doubles or\r
774 * quaduples the size, but it's also possible for the dict to shrink\r
775 * (if ma_fill is much larger than ma_used, meaning a lot of dict\r
776 * keys have been * deleted).\r
777 *\r
778 * Quadrupling the size improves average dictionary sparseness\r
779 * (reducing collisions) at the cost of some memory and iteration\r
780 * speed (which loops over every possible entry). It also halves\r
781 * the number of expensive resize operations in a growing dictionary.\r
782 *\r
783 * Very large dictionaries (over 50K items) use doubling instead.\r
784 * This may help applications with severe memory constraints.\r
785 */\r
786 if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))\r
787 return 0;\r
788 return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);\r
789}\r
790\r
791/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the\r
792 * dictionary if it's merely replacing the value for an existing key.\r
793 * This means that it's safe to loop over a dictionary with PyDict_Next()\r
794 * and occasionally replace a value -- but you can't insert new keys or\r
795 * remove them.\r
796 */\r
797int\r
798PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)\r
799{\r
800 register long hash;\r
801\r
802 if (!PyDict_Check(op)) {\r
803 PyErr_BadInternalCall();\r
804 return -1;\r
805 }\r
806 assert(key);\r
807 assert(value);\r
808 if (PyString_CheckExact(key)) {\r
809 hash = ((PyStringObject *)key)->ob_shash;\r
810 if (hash == -1)\r
811 hash = PyObject_Hash(key);\r
812 }\r
813 else {\r
814 hash = PyObject_Hash(key);\r
815 if (hash == -1)\r
816 return -1;\r
817 }\r
818 return dict_set_item_by_hash_or_entry(op, key, hash, NULL, value);\r
819}\r
820\r
821int\r
822PyDict_DelItem(PyObject *op, PyObject *key)\r
823{\r
824 register PyDictObject *mp;\r
825 register long hash;\r
826 register PyDictEntry *ep;\r
827 PyObject *old_value, *old_key;\r
828\r
829 if (!PyDict_Check(op)) {\r
830 PyErr_BadInternalCall();\r
831 return -1;\r
832 }\r
833 assert(key);\r
834 if (!PyString_CheckExact(key) ||\r
835 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
836 hash = PyObject_Hash(key);\r
837 if (hash == -1)\r
838 return -1;\r
839 }\r
840 mp = (PyDictObject *)op;\r
841 ep = (mp->ma_lookup)(mp, key, hash);\r
842 if (ep == NULL)\r
843 return -1;\r
844 if (ep->me_value == NULL) {\r
845 set_key_error(key);\r
846 return -1;\r
847 }\r
848 old_key = ep->me_key;\r
849 Py_INCREF(dummy);\r
850 ep->me_key = dummy;\r
851 old_value = ep->me_value;\r
852 ep->me_value = NULL;\r
853 mp->ma_used--;\r
854 Py_DECREF(old_value);\r
855 Py_DECREF(old_key);\r
856 return 0;\r
857}\r
858\r
859void\r
860PyDict_Clear(PyObject *op)\r
861{\r
862 PyDictObject *mp;\r
863 PyDictEntry *ep, *table;\r
864 int table_is_malloced;\r
865 Py_ssize_t fill;\r
866 PyDictEntry small_copy[PyDict_MINSIZE];\r
867#ifdef Py_DEBUG\r
868 Py_ssize_t i, n;\r
869#endif\r
870\r
871 if (!PyDict_Check(op))\r
872 return;\r
873 mp = (PyDictObject *)op;\r
874#ifdef Py_DEBUG\r
875 n = mp->ma_mask + 1;\r
876 i = 0;\r
877#endif\r
878\r
879 table = mp->ma_table;\r
880 assert(table != NULL);\r
881 table_is_malloced = table != mp->ma_smalltable;\r
882\r
883 /* This is delicate. During the process of clearing the dict,\r
884 * decrefs can cause the dict to mutate. To avoid fatal confusion\r
885 * (voice of experience), we have to make the dict empty before\r
886 * clearing the slots, and never refer to anything via mp->xxx while\r
887 * clearing.\r
888 */\r
889 fill = mp->ma_fill;\r
890 if (table_is_malloced)\r
891 EMPTY_TO_MINSIZE(mp);\r
892\r
893 else if (fill > 0) {\r
894 /* It's a small table with something that needs to be cleared.\r
895 * Afraid the only safe way is to copy the dict entries into\r
896 * another small table first.\r
897 */\r
898 memcpy(small_copy, table, sizeof(small_copy));\r
899 table = small_copy;\r
900 EMPTY_TO_MINSIZE(mp);\r
901 }\r
902 /* else it's a small table that's already empty */\r
903\r
904 /* Now we can finally clear things. If C had refcounts, we could\r
905 * assert that the refcount on table is 1 now, i.e. that this function\r
906 * has unique access to it, so decref side-effects can't alter it.\r
907 */\r
908 for (ep = table; fill > 0; ++ep) {\r
909#ifdef Py_DEBUG\r
910 assert(i < n);\r
911 ++i;\r
912#endif\r
913 if (ep->me_key) {\r
914 --fill;\r
915 Py_DECREF(ep->me_key);\r
916 Py_XDECREF(ep->me_value);\r
917 }\r
918#ifdef Py_DEBUG\r
919 else\r
920 assert(ep->me_value == NULL);\r
921#endif\r
922 }\r
923\r
924 if (table_is_malloced)\r
925 PyMem_DEL(table);\r
926}\r
927\r
928/*\r
929 * Iterate over a dict. Use like so:\r
930 *\r
931 * Py_ssize_t i;\r
932 * PyObject *key, *value;\r
933 * i = 0; # important! i should not otherwise be changed by you\r
934 * while (PyDict_Next(yourdict, &i, &key, &value)) {\r
935 * Refer to borrowed references in key and value.\r
936 * }\r
937 *\r
938 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that\r
939 * mutates the dict. One exception: it is safe if the loop merely changes\r
940 * the values associated with the keys (but doesn't insert new keys or\r
941 * delete keys), via PyDict_SetItem().\r
942 */\r
943int\r
944PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)\r
945{\r
946 register Py_ssize_t i;\r
947 register Py_ssize_t mask;\r
948 register PyDictEntry *ep;\r
949\r
950 if (!PyDict_Check(op))\r
951 return 0;\r
952 i = *ppos;\r
953 if (i < 0)\r
954 return 0;\r
955 ep = ((PyDictObject *)op)->ma_table;\r
956 mask = ((PyDictObject *)op)->ma_mask;\r
957 while (i <= mask && ep[i].me_value == NULL)\r
958 i++;\r
959 *ppos = i+1;\r
960 if (i > mask)\r
961 return 0;\r
962 if (pkey)\r
963 *pkey = ep[i].me_key;\r
964 if (pvalue)\r
965 *pvalue = ep[i].me_value;\r
966 return 1;\r
967}\r
968\r
969/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/\r
970int\r
971_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)\r
972{\r
973 register Py_ssize_t i;\r
974 register Py_ssize_t mask;\r
975 register PyDictEntry *ep;\r
976\r
977 if (!PyDict_Check(op))\r
978 return 0;\r
979 i = *ppos;\r
980 if (i < 0)\r
981 return 0;\r
982 ep = ((PyDictObject *)op)->ma_table;\r
983 mask = ((PyDictObject *)op)->ma_mask;\r
984 while (i <= mask && ep[i].me_value == NULL)\r
985 i++;\r
986 *ppos = i+1;\r
987 if (i > mask)\r
988 return 0;\r
989 *phash = (long)(ep[i].me_hash);\r
990 if (pkey)\r
991 *pkey = ep[i].me_key;\r
992 if (pvalue)\r
993 *pvalue = ep[i].me_value;\r
994 return 1;\r
995}\r
996\r
997/* Methods */\r
998\r
999static void\r
1000dict_dealloc(register PyDictObject *mp)\r
1001{\r
1002 register PyDictEntry *ep;\r
1003 Py_ssize_t fill = mp->ma_fill;\r
1004 PyObject_GC_UnTrack(mp);\r
1005 Py_TRASHCAN_SAFE_BEGIN(mp)\r
1006 for (ep = mp->ma_table; fill > 0; ep++) {\r
1007 if (ep->me_key) {\r
1008 --fill;\r
1009 Py_DECREF(ep->me_key);\r
1010 Py_XDECREF(ep->me_value);\r
1011 }\r
1012 }\r
1013 if (mp->ma_table != mp->ma_smalltable)\r
1014 PyMem_DEL(mp->ma_table);\r
1015 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)\r
1016 free_list[numfree++] = mp;\r
1017 else\r
1018 Py_TYPE(mp)->tp_free((PyObject *)mp);\r
1019 Py_TRASHCAN_SAFE_END(mp)\r
1020}\r
1021\r
1022static int\r
1023dict_print(register PyDictObject *mp, register FILE *fp, register int flags)\r
1024{\r
1025 register Py_ssize_t i;\r
1026 register Py_ssize_t any;\r
1027 int status;\r
1028\r
1029 status = Py_ReprEnter((PyObject*)mp);\r
1030 if (status != 0) {\r
1031 if (status < 0)\r
1032 return status;\r
1033 Py_BEGIN_ALLOW_THREADS\r
1034 fprintf(fp, "{...}");\r
1035 Py_END_ALLOW_THREADS\r
1036 return 0;\r
1037 }\r
1038\r
1039 Py_BEGIN_ALLOW_THREADS\r
1040 fprintf(fp, "{");\r
1041 Py_END_ALLOW_THREADS\r
1042 any = 0;\r
1043 for (i = 0; i <= mp->ma_mask; i++) {\r
1044 PyDictEntry *ep = mp->ma_table + i;\r
1045 PyObject *pvalue = ep->me_value;\r
1046 if (pvalue != NULL) {\r
1047 /* Prevent PyObject_Repr from deleting value during\r
1048 key format */\r
1049 Py_INCREF(pvalue);\r
1050 if (any++ > 0) {\r
1051 Py_BEGIN_ALLOW_THREADS\r
1052 fprintf(fp, ", ");\r
1053 Py_END_ALLOW_THREADS\r
1054 }\r
1055 if (PyObject_Print((PyObject *)ep->me_key, fp, 0)!=0) {\r
1056 Py_DECREF(pvalue);\r
1057 Py_ReprLeave((PyObject*)mp);\r
1058 return -1;\r
1059 }\r
1060 Py_BEGIN_ALLOW_THREADS\r
1061 fprintf(fp, ": ");\r
1062 Py_END_ALLOW_THREADS\r
1063 if (PyObject_Print(pvalue, fp, 0) != 0) {\r
1064 Py_DECREF(pvalue);\r
1065 Py_ReprLeave((PyObject*)mp);\r
1066 return -1;\r
1067 }\r
1068 Py_DECREF(pvalue);\r
1069 }\r
1070 }\r
1071 Py_BEGIN_ALLOW_THREADS\r
1072 fprintf(fp, "}");\r
1073 Py_END_ALLOW_THREADS\r
1074 Py_ReprLeave((PyObject*)mp);\r
1075 return 0;\r
1076}\r
1077\r
1078static PyObject *\r
1079dict_repr(PyDictObject *mp)\r
1080{\r
1081 Py_ssize_t i;\r
1082 PyObject *s, *temp, *colon = NULL;\r
1083 PyObject *pieces = NULL, *result = NULL;\r
1084 PyObject *key, *value;\r
1085\r
1086 i = Py_ReprEnter((PyObject *)mp);\r
1087 if (i != 0) {\r
1088 return i > 0 ? PyString_FromString("{...}") : NULL;\r
1089 }\r
1090\r
1091 if (mp->ma_used == 0) {\r
1092 result = PyString_FromString("{}");\r
1093 goto Done;\r
1094 }\r
1095\r
1096 pieces = PyList_New(0);\r
1097 if (pieces == NULL)\r
1098 goto Done;\r
1099\r
1100 colon = PyString_FromString(": ");\r
1101 if (colon == NULL)\r
1102 goto Done;\r
1103\r
1104 /* Do repr() on each key+value pair, and insert ": " between them.\r
1105 Note that repr may mutate the dict. */\r
1106 i = 0;\r
1107 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {\r
1108 int status;\r
1109 /* Prevent repr from deleting value during key format. */\r
1110 Py_INCREF(value);\r
1111 s = PyObject_Repr(key);\r
1112 PyString_Concat(&s, colon);\r
1113 PyString_ConcatAndDel(&s, PyObject_Repr(value));\r
1114 Py_DECREF(value);\r
1115 if (s == NULL)\r
1116 goto Done;\r
1117 status = PyList_Append(pieces, s);\r
1118 Py_DECREF(s); /* append created a new ref */\r
1119 if (status < 0)\r
1120 goto Done;\r
1121 }\r
1122\r
1123 /* Add "{}" decorations to the first and last items. */\r
1124 assert(PyList_GET_SIZE(pieces) > 0);\r
1125 s = PyString_FromString("{");\r
1126 if (s == NULL)\r
1127 goto Done;\r
1128 temp = PyList_GET_ITEM(pieces, 0);\r
1129 PyString_ConcatAndDel(&s, temp);\r
1130 PyList_SET_ITEM(pieces, 0, s);\r
1131 if (s == NULL)\r
1132 goto Done;\r
1133\r
1134 s = PyString_FromString("}");\r
1135 if (s == NULL)\r
1136 goto Done;\r
1137 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);\r
1138 PyString_ConcatAndDel(&temp, s);\r
1139 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);\r
1140 if (temp == NULL)\r
1141 goto Done;\r
1142\r
1143 /* Paste them all together with ", " between. */\r
1144 s = PyString_FromString(", ");\r
1145 if (s == NULL)\r
1146 goto Done;\r
1147 result = _PyString_Join(s, pieces);\r
1148 Py_DECREF(s);\r
1149\r
1150Done:\r
1151 Py_XDECREF(pieces);\r
1152 Py_XDECREF(colon);\r
1153 Py_ReprLeave((PyObject *)mp);\r
1154 return result;\r
1155}\r
1156\r
1157static Py_ssize_t\r
1158dict_length(PyDictObject *mp)\r
1159{\r
1160 return mp->ma_used;\r
1161}\r
1162\r
1163static PyObject *\r
1164dict_subscript(PyDictObject *mp, register PyObject *key)\r
1165{\r
1166 PyObject *v;\r
1167 long hash;\r
1168 PyDictEntry *ep;\r
1169 assert(mp->ma_table != NULL);\r
1170 if (!PyString_CheckExact(key) ||\r
1171 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
1172 hash = PyObject_Hash(key);\r
1173 if (hash == -1)\r
1174 return NULL;\r
1175 }\r
1176 ep = (mp->ma_lookup)(mp, key, hash);\r
1177 if (ep == NULL)\r
1178 return NULL;\r
1179 v = ep->me_value;\r
1180 if (v == NULL) {\r
1181 if (!PyDict_CheckExact(mp)) {\r
1182 /* Look up __missing__ method if we're a subclass. */\r
1183 PyObject *missing, *res;\r
1184 static PyObject *missing_str = NULL;\r
1185 missing = _PyObject_LookupSpecial((PyObject *)mp,\r
1186 "__missing__",\r
1187 &missing_str);\r
1188 if (missing != NULL) {\r
1189 res = PyObject_CallFunctionObjArgs(missing,\r
1190 key, NULL);\r
1191 Py_DECREF(missing);\r
1192 return res;\r
1193 }\r
1194 else if (PyErr_Occurred())\r
1195 return NULL;\r
1196 }\r
1197 set_key_error(key);\r
1198 return NULL;\r
1199 }\r
1200 else\r
1201 Py_INCREF(v);\r
1202 return v;\r
1203}\r
1204\r
1205static int\r
1206dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)\r
1207{\r
1208 if (w == NULL)\r
1209 return PyDict_DelItem((PyObject *)mp, v);\r
1210 else\r
1211 return PyDict_SetItem((PyObject *)mp, v, w);\r
1212}\r
1213\r
1214static PyMappingMethods dict_as_mapping = {\r
1215 (lenfunc)dict_length, /*mp_length*/\r
1216 (binaryfunc)dict_subscript, /*mp_subscript*/\r
1217 (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/\r
1218};\r
1219\r
1220static PyObject *\r
1221dict_keys(register PyDictObject *mp)\r
1222{\r
1223 register PyObject *v;\r
1224 register Py_ssize_t i, j;\r
1225 PyDictEntry *ep;\r
1226 Py_ssize_t mask, n;\r
1227\r
1228 again:\r
1229 n = mp->ma_used;\r
1230 v = PyList_New(n);\r
1231 if (v == NULL)\r
1232 return NULL;\r
1233 if (n != mp->ma_used) {\r
1234 /* Durnit. The allocations caused the dict to resize.\r
1235 * Just start over, this shouldn't normally happen.\r
1236 */\r
1237 Py_DECREF(v);\r
1238 goto again;\r
1239 }\r
1240 ep = mp->ma_table;\r
1241 mask = mp->ma_mask;\r
1242 for (i = 0, j = 0; i <= mask; i++) {\r
1243 if (ep[i].me_value != NULL) {\r
1244 PyObject *key = ep[i].me_key;\r
1245 Py_INCREF(key);\r
1246 PyList_SET_ITEM(v, j, key);\r
1247 j++;\r
1248 }\r
1249 }\r
1250 assert(j == n);\r
1251 return v;\r
1252}\r
1253\r
1254static PyObject *\r
1255dict_values(register PyDictObject *mp)\r
1256{\r
1257 register PyObject *v;\r
1258 register Py_ssize_t i, j;\r
1259 PyDictEntry *ep;\r
1260 Py_ssize_t mask, n;\r
1261\r
1262 again:\r
1263 n = mp->ma_used;\r
1264 v = PyList_New(n);\r
1265 if (v == NULL)\r
1266 return NULL;\r
1267 if (n != mp->ma_used) {\r
1268 /* Durnit. The allocations caused the dict to resize.\r
1269 * Just start over, this shouldn't normally happen.\r
1270 */\r
1271 Py_DECREF(v);\r
1272 goto again;\r
1273 }\r
1274 ep = mp->ma_table;\r
1275 mask = mp->ma_mask;\r
1276 for (i = 0, j = 0; i <= mask; i++) {\r
1277 if (ep[i].me_value != NULL) {\r
1278 PyObject *value = ep[i].me_value;\r
1279 Py_INCREF(value);\r
1280 PyList_SET_ITEM(v, j, value);\r
1281 j++;\r
1282 }\r
1283 }\r
1284 assert(j == n);\r
1285 return v;\r
1286}\r
1287\r
1288static PyObject *\r
1289dict_items(register PyDictObject *mp)\r
1290{\r
1291 register PyObject *v;\r
1292 register Py_ssize_t i, j, n;\r
1293 Py_ssize_t mask;\r
1294 PyObject *item, *key, *value;\r
1295 PyDictEntry *ep;\r
1296\r
1297 /* Preallocate the list of tuples, to avoid allocations during\r
1298 * the loop over the items, which could trigger GC, which\r
1299 * could resize the dict. :-(\r
1300 */\r
1301 again:\r
1302 n = mp->ma_used;\r
1303 v = PyList_New(n);\r
1304 if (v == NULL)\r
1305 return NULL;\r
1306 for (i = 0; i < n; i++) {\r
1307 item = PyTuple_New(2);\r
1308 if (item == NULL) {\r
1309 Py_DECREF(v);\r
1310 return NULL;\r
1311 }\r
1312 PyList_SET_ITEM(v, i, item);\r
1313 }\r
1314 if (n != mp->ma_used) {\r
1315 /* Durnit. The allocations caused the dict to resize.\r
1316 * Just start over, this shouldn't normally happen.\r
1317 */\r
1318 Py_DECREF(v);\r
1319 goto again;\r
1320 }\r
1321 /* Nothing we do below makes any function calls. */\r
1322 ep = mp->ma_table;\r
1323 mask = mp->ma_mask;\r
1324 for (i = 0, j = 0; i <= mask; i++) {\r
1325 if ((value=ep[i].me_value) != NULL) {\r
1326 key = ep[i].me_key;\r
1327 item = PyList_GET_ITEM(v, j);\r
1328 Py_INCREF(key);\r
1329 PyTuple_SET_ITEM(item, 0, key);\r
1330 Py_INCREF(value);\r
1331 PyTuple_SET_ITEM(item, 1, value);\r
1332 j++;\r
1333 }\r
1334 }\r
1335 assert(j == n);\r
1336 return v;\r
1337}\r
1338\r
1339static PyObject *\r
1340dict_fromkeys(PyObject *cls, PyObject *args)\r
1341{\r
1342 PyObject *seq;\r
1343 PyObject *value = Py_None;\r
1344 PyObject *it; /* iter(seq) */\r
1345 PyObject *key;\r
1346 PyObject *d;\r
1347 int status;\r
1348\r
1349 if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value))\r
1350 return NULL;\r
1351\r
1352 d = PyObject_CallObject(cls, NULL);\r
1353 if (d == NULL)\r
1354 return NULL;\r
1355\r
1356 if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) {\r
1357 if (PyDict_CheckExact(seq)) {\r
1358 PyDictObject *mp = (PyDictObject *)d;\r
1359 PyObject *oldvalue;\r
1360 Py_ssize_t pos = 0;\r
1361 PyObject *key;\r
1362 long hash;\r
1363\r
1364 if (dictresize(mp, Py_SIZE(seq))) {\r
1365 Py_DECREF(d);\r
1366 return NULL;\r
1367 }\r
1368\r
1369 while (_PyDict_Next(seq, &pos, &key, &oldvalue, &hash)) {\r
1370 Py_INCREF(key);\r
1371 Py_INCREF(value);\r
1372 if (insertdict(mp, key, hash, value)) {\r
1373 Py_DECREF(d);\r
1374 return NULL;\r
1375 }\r
1376 }\r
1377 return d;\r
1378 }\r
1379 if (PyAnySet_CheckExact(seq)) {\r
1380 PyDictObject *mp = (PyDictObject *)d;\r
1381 Py_ssize_t pos = 0;\r
1382 PyObject *key;\r
1383 long hash;\r
1384\r
1385 if (dictresize(mp, PySet_GET_SIZE(seq))) {\r
1386 Py_DECREF(d);\r
1387 return NULL;\r
1388 }\r
1389\r
1390 while (_PySet_NextEntry(seq, &pos, &key, &hash)) {\r
1391 Py_INCREF(key);\r
1392 Py_INCREF(value);\r
1393 if (insertdict(mp, key, hash, value)) {\r
1394 Py_DECREF(d);\r
1395 return NULL;\r
1396 }\r
1397 }\r
1398 return d;\r
1399 }\r
1400 }\r
1401\r
1402 it = PyObject_GetIter(seq);\r
1403 if (it == NULL){\r
1404 Py_DECREF(d);\r
1405 return NULL;\r
1406 }\r
1407\r
1408 if (PyDict_CheckExact(d)) {\r
1409 while ((key = PyIter_Next(it)) != NULL) {\r
1410 status = PyDict_SetItem(d, key, value);\r
1411 Py_DECREF(key);\r
1412 if (status < 0)\r
1413 goto Fail;\r
1414 }\r
1415 } else {\r
1416 while ((key = PyIter_Next(it)) != NULL) {\r
1417 status = PyObject_SetItem(d, key, value);\r
1418 Py_DECREF(key);\r
1419 if (status < 0)\r
1420 goto Fail;\r
1421 }\r
1422 }\r
1423\r
1424 if (PyErr_Occurred())\r
1425 goto Fail;\r
1426 Py_DECREF(it);\r
1427 return d;\r
1428\r
1429Fail:\r
1430 Py_DECREF(it);\r
1431 Py_DECREF(d);\r
1432 return NULL;\r
1433}\r
1434\r
1435static int\r
1436dict_update_common(PyObject *self, PyObject *args, PyObject *kwds, char *methname)\r
1437{\r
1438 PyObject *arg = NULL;\r
1439 int result = 0;\r
1440\r
1441 if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))\r
1442 result = -1;\r
1443\r
1444 else if (arg != NULL) {\r
1445 if (PyObject_HasAttrString(arg, "keys"))\r
1446 result = PyDict_Merge(self, arg, 1);\r
1447 else\r
1448 result = PyDict_MergeFromSeq2(self, arg, 1);\r
1449 }\r
1450 if (result == 0 && kwds != NULL)\r
1451 result = PyDict_Merge(self, kwds, 1);\r
1452 return result;\r
1453}\r
1454\r
1455static PyObject *\r
1456dict_update(PyObject *self, PyObject *args, PyObject *kwds)\r
1457{\r
1458 if (dict_update_common(self, args, kwds, "update") != -1)\r
1459 Py_RETURN_NONE;\r
1460 return NULL;\r
1461}\r
1462\r
1463/* Update unconditionally replaces existing items.\r
1464 Merge has a 3rd argument 'override'; if set, it acts like Update,\r
1465 otherwise it leaves existing items unchanged.\r
1466\r
1467 PyDict_{Update,Merge} update/merge from a mapping object.\r
1468\r
1469 PyDict_MergeFromSeq2 updates/merges from any iterable object\r
1470 producing iterable objects of length 2.\r
1471*/\r
1472\r
1473int\r
1474PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)\r
1475{\r
1476 PyObject *it; /* iter(seq2) */\r
1477 Py_ssize_t i; /* index into seq2 of current element */\r
1478 PyObject *item; /* seq2[i] */\r
1479 PyObject *fast; /* item as a 2-tuple or 2-list */\r
1480\r
1481 assert(d != NULL);\r
1482 assert(PyDict_Check(d));\r
1483 assert(seq2 != NULL);\r
1484\r
1485 it = PyObject_GetIter(seq2);\r
1486 if (it == NULL)\r
1487 return -1;\r
1488\r
1489 for (i = 0; ; ++i) {\r
1490 PyObject *key, *value;\r
1491 Py_ssize_t n;\r
1492\r
1493 fast = NULL;\r
1494 item = PyIter_Next(it);\r
1495 if (item == NULL) {\r
1496 if (PyErr_Occurred())\r
1497 goto Fail;\r
1498 break;\r
1499 }\r
1500\r
1501 /* Convert item to sequence, and verify length 2. */\r
1502 fast = PySequence_Fast(item, "");\r
1503 if (fast == NULL) {\r
1504 if (PyErr_ExceptionMatches(PyExc_TypeError))\r
1505 PyErr_Format(PyExc_TypeError,\r
1506 "cannot convert dictionary update "\r
1507 "sequence element #%zd to a sequence",\r
1508 i);\r
1509 goto Fail;\r
1510 }\r
1511 n = PySequence_Fast_GET_SIZE(fast);\r
1512 if (n != 2) {\r
1513 PyErr_Format(PyExc_ValueError,\r
1514 "dictionary update sequence element #%zd "\r
1515 "has length %zd; 2 is required",\r
1516 i, n);\r
1517 goto Fail;\r
1518 }\r
1519\r
1520 /* Update/merge with this (key, value) pair. */\r
1521 key = PySequence_Fast_GET_ITEM(fast, 0);\r
1522 value = PySequence_Fast_GET_ITEM(fast, 1);\r
1523 if (override || PyDict_GetItem(d, key) == NULL) {\r
1524 int status = PyDict_SetItem(d, key, value);\r
1525 if (status < 0)\r
1526 goto Fail;\r
1527 }\r
1528 Py_DECREF(fast);\r
1529 Py_DECREF(item);\r
1530 }\r
1531\r
1532 i = 0;\r
1533 goto Return;\r
1534Fail:\r
1535 Py_XDECREF(item);\r
1536 Py_XDECREF(fast);\r
1537 i = -1;\r
1538Return:\r
1539 Py_DECREF(it);\r
1540 return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);\r
1541}\r
1542\r
1543int\r
1544PyDict_Update(PyObject *a, PyObject *b)\r
1545{\r
1546 return PyDict_Merge(a, b, 1);\r
1547}\r
1548\r
1549int\r
1550PyDict_Merge(PyObject *a, PyObject *b, int override)\r
1551{\r
1552 register PyDictObject *mp, *other;\r
1553 register Py_ssize_t i;\r
1554 PyDictEntry *entry;\r
1555\r
1556 /* We accept for the argument either a concrete dictionary object,\r
1557 * or an abstract "mapping" object. For the former, we can do\r
1558 * things quite efficiently. For the latter, we only require that\r
1559 * PyMapping_Keys() and PyObject_GetItem() be supported.\r
1560 */\r
1561 if (a == NULL || !PyDict_Check(a) || b == NULL) {\r
1562 PyErr_BadInternalCall();\r
1563 return -1;\r
1564 }\r
1565 mp = (PyDictObject*)a;\r
1566 if (PyDict_Check(b)) {\r
1567 other = (PyDictObject*)b;\r
1568 if (other == mp || other->ma_used == 0)\r
1569 /* a.update(a) or a.update({}); nothing to do */\r
1570 return 0;\r
1571 if (mp->ma_used == 0)\r
1572 /* Since the target dict is empty, PyDict_GetItem()\r
1573 * always returns NULL. Setting override to 1\r
1574 * skips the unnecessary test.\r
1575 */\r
1576 override = 1;\r
1577 /* Do one big resize at the start, rather than\r
1578 * incrementally resizing as we insert new items. Expect\r
1579 * that there will be no (or few) overlapping keys.\r
1580 */\r
1581 if ((mp->ma_fill + other->ma_used)*3 >= (mp->ma_mask+1)*2) {\r
1582 if (dictresize(mp, (mp->ma_used + other->ma_used)*2) != 0)\r
1583 return -1;\r
1584 }\r
1585 for (i = 0; i <= other->ma_mask; i++) {\r
1586 entry = &other->ma_table[i];\r
1587 if (entry->me_value != NULL &&\r
1588 (override ||\r
1589 PyDict_GetItem(a, entry->me_key) == NULL)) {\r
1590 Py_INCREF(entry->me_key);\r
1591 Py_INCREF(entry->me_value);\r
1592 if (insertdict(mp, entry->me_key,\r
1593 (long)entry->me_hash,\r
1594 entry->me_value) != 0)\r
1595 return -1;\r
1596 }\r
1597 }\r
1598 }\r
1599 else {\r
1600 /* Do it the generic, slower way */\r
1601 PyObject *keys = PyMapping_Keys(b);\r
1602 PyObject *iter;\r
1603 PyObject *key, *value;\r
1604 int status;\r
1605\r
1606 if (keys == NULL)\r
1607 /* Docstring says this is equivalent to E.keys() so\r
1608 * if E doesn't have a .keys() method we want\r
1609 * AttributeError to percolate up. Might as well\r
1610 * do the same for any other error.\r
1611 */\r
1612 return -1;\r
1613\r
1614 iter = PyObject_GetIter(keys);\r
1615 Py_DECREF(keys);\r
1616 if (iter == NULL)\r
1617 return -1;\r
1618\r
1619 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {\r
1620 if (!override && PyDict_GetItem(a, key) != NULL) {\r
1621 Py_DECREF(key);\r
1622 continue;\r
1623 }\r
1624 value = PyObject_GetItem(b, key);\r
1625 if (value == NULL) {\r
1626 Py_DECREF(iter);\r
1627 Py_DECREF(key);\r
1628 return -1;\r
1629 }\r
1630 status = PyDict_SetItem(a, key, value);\r
1631 Py_DECREF(key);\r
1632 Py_DECREF(value);\r
1633 if (status < 0) {\r
1634 Py_DECREF(iter);\r
1635 return -1;\r
1636 }\r
1637 }\r
1638 Py_DECREF(iter);\r
1639 if (PyErr_Occurred())\r
1640 /* Iterator completed, via error */\r
1641 return -1;\r
1642 }\r
1643 return 0;\r
1644}\r
1645\r
1646static PyObject *\r
1647dict_copy(register PyDictObject *mp)\r
1648{\r
1649 return PyDict_Copy((PyObject*)mp);\r
1650}\r
1651\r
1652PyObject *\r
1653PyDict_Copy(PyObject *o)\r
1654{\r
1655 PyObject *copy;\r
1656\r
1657 if (o == NULL || !PyDict_Check(o)) {\r
1658 PyErr_BadInternalCall();\r
1659 return NULL;\r
1660 }\r
1661 copy = PyDict_New();\r
1662 if (copy == NULL)\r
1663 return NULL;\r
1664 if (PyDict_Merge(copy, o, 1) == 0)\r
1665 return copy;\r
1666 Py_DECREF(copy);\r
1667 return NULL;\r
1668}\r
1669\r
1670Py_ssize_t\r
1671PyDict_Size(PyObject *mp)\r
1672{\r
1673 if (mp == NULL || !PyDict_Check(mp)) {\r
1674 PyErr_BadInternalCall();\r
1675 return -1;\r
1676 }\r
1677 return ((PyDictObject *)mp)->ma_used;\r
1678}\r
1679\r
1680PyObject *\r
1681PyDict_Keys(PyObject *mp)\r
1682{\r
1683 if (mp == NULL || !PyDict_Check(mp)) {\r
1684 PyErr_BadInternalCall();\r
1685 return NULL;\r
1686 }\r
1687 return dict_keys((PyDictObject *)mp);\r
1688}\r
1689\r
1690PyObject *\r
1691PyDict_Values(PyObject *mp)\r
1692{\r
1693 if (mp == NULL || !PyDict_Check(mp)) {\r
1694 PyErr_BadInternalCall();\r
1695 return NULL;\r
1696 }\r
1697 return dict_values((PyDictObject *)mp);\r
1698}\r
1699\r
1700PyObject *\r
1701PyDict_Items(PyObject *mp)\r
1702{\r
1703 if (mp == NULL || !PyDict_Check(mp)) {\r
1704 PyErr_BadInternalCall();\r
1705 return NULL;\r
1706 }\r
1707 return dict_items((PyDictObject *)mp);\r
1708}\r
1709\r
1710/* Subroutine which returns the smallest key in a for which b's value\r
1711 is different or absent. The value is returned too, through the\r
1712 pval argument. Both are NULL if no key in a is found for which b's status\r
1713 differs. The refcounts on (and only on) non-NULL *pval and function return\r
1714 values must be decremented by the caller (characterize() increments them\r
1715 to ensure that mutating comparison and PyDict_GetItem calls can't delete\r
1716 them before the caller is done looking at them). */\r
1717\r
1718static PyObject *\r
1719characterize(PyDictObject *a, PyDictObject *b, PyObject **pval)\r
1720{\r
1721 PyObject *akey = NULL; /* smallest key in a s.t. a[akey] != b[akey] */\r
1722 PyObject *aval = NULL; /* a[akey] */\r
1723 Py_ssize_t i;\r
1724 int cmp;\r
1725\r
1726 for (i = 0; i <= a->ma_mask; i++) {\r
1727 PyObject *thiskey, *thisaval, *thisbval;\r
1728 if (a->ma_table[i].me_value == NULL)\r
1729 continue;\r
1730 thiskey = a->ma_table[i].me_key;\r
1731 Py_INCREF(thiskey); /* keep alive across compares */\r
1732 if (akey != NULL) {\r
1733 cmp = PyObject_RichCompareBool(akey, thiskey, Py_LT);\r
1734 if (cmp < 0) {\r
1735 Py_DECREF(thiskey);\r
1736 goto Fail;\r
1737 }\r
1738 if (cmp > 0 ||\r
1739 i > a->ma_mask ||\r
1740 a->ma_table[i].me_value == NULL)\r
1741 {\r
1742 /* Not the *smallest* a key; or maybe it is\r
1743 * but the compare shrunk the dict so we can't\r
1744 * find its associated value anymore; or\r
1745 * maybe it is but the compare deleted the\r
1746 * a[thiskey] entry.\r
1747 */\r
1748 Py_DECREF(thiskey);\r
1749 continue;\r
1750 }\r
1751 }\r
1752\r
1753 /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */\r
1754 thisaval = a->ma_table[i].me_value;\r
1755 assert(thisaval);\r
1756 Py_INCREF(thisaval); /* keep alive */\r
1757 thisbval = PyDict_GetItem((PyObject *)b, thiskey);\r
1758 if (thisbval == NULL)\r
1759 cmp = 0;\r
1760 else {\r
1761 /* both dicts have thiskey: same values? */\r
1762 cmp = PyObject_RichCompareBool(\r
1763 thisaval, thisbval, Py_EQ);\r
1764 if (cmp < 0) {\r
1765 Py_DECREF(thiskey);\r
1766 Py_DECREF(thisaval);\r
1767 goto Fail;\r
1768 }\r
1769 }\r
1770 if (cmp == 0) {\r
1771 /* New winner. */\r
1772 Py_XDECREF(akey);\r
1773 Py_XDECREF(aval);\r
1774 akey = thiskey;\r
1775 aval = thisaval;\r
1776 }\r
1777 else {\r
1778 Py_DECREF(thiskey);\r
1779 Py_DECREF(thisaval);\r
1780 }\r
1781 }\r
1782 *pval = aval;\r
1783 return akey;\r
1784\r
1785Fail:\r
1786 Py_XDECREF(akey);\r
1787 Py_XDECREF(aval);\r
1788 *pval = NULL;\r
1789 return NULL;\r
1790}\r
1791\r
1792static int\r
1793dict_compare(PyDictObject *a, PyDictObject *b)\r
1794{\r
1795 PyObject *adiff, *bdiff, *aval, *bval;\r
1796 int res;\r
1797\r
1798 /* Compare lengths first */\r
1799 if (a->ma_used < b->ma_used)\r
1800 return -1; /* a is shorter */\r
1801 else if (a->ma_used > b->ma_used)\r
1802 return 1; /* b is shorter */\r
1803\r
1804 /* Same length -- check all keys */\r
1805 bdiff = bval = NULL;\r
1806 adiff = characterize(a, b, &aval);\r
1807 if (adiff == NULL) {\r
1808 assert(!aval);\r
1809 /* Either an error, or a is a subset with the same length so\r
1810 * must be equal.\r
1811 */\r
1812 res = PyErr_Occurred() ? -1 : 0;\r
1813 goto Finished;\r
1814 }\r
1815 bdiff = characterize(b, a, &bval);\r
1816 if (bdiff == NULL && PyErr_Occurred()) {\r
1817 assert(!bval);\r
1818 res = -1;\r
1819 goto Finished;\r
1820 }\r
1821 res = 0;\r
1822 if (bdiff) {\r
1823 /* bdiff == NULL "should be" impossible now, but perhaps\r
1824 * the last comparison done by the characterize() on a had\r
1825 * the side effect of making the dicts equal!\r
1826 */\r
1827 res = PyObject_Compare(adiff, bdiff);\r
1828 }\r
1829 if (res == 0 && bval != NULL)\r
1830 res = PyObject_Compare(aval, bval);\r
1831\r
1832Finished:\r
1833 Py_XDECREF(adiff);\r
1834 Py_XDECREF(bdiff);\r
1835 Py_XDECREF(aval);\r
1836 Py_XDECREF(bval);\r
1837 return res;\r
1838}\r
1839\r
1840/* Return 1 if dicts equal, 0 if not, -1 if error.\r
1841 * Gets out as soon as any difference is detected.\r
1842 * Uses only Py_EQ comparison.\r
1843 */\r
1844static int\r
1845dict_equal(PyDictObject *a, PyDictObject *b)\r
1846{\r
1847 Py_ssize_t i;\r
1848\r
1849 if (a->ma_used != b->ma_used)\r
1850 /* can't be equal if # of entries differ */\r
1851 return 0;\r
1852\r
1853 /* Same # of entries -- check all of 'em. Exit early on any diff. */\r
1854 for (i = 0; i <= a->ma_mask; i++) {\r
1855 PyObject *aval = a->ma_table[i].me_value;\r
1856 if (aval != NULL) {\r
1857 int cmp;\r
1858 PyObject *bval;\r
1859 PyObject *key = a->ma_table[i].me_key;\r
1860 /* temporarily bump aval's refcount to ensure it stays\r
1861 alive until we're done with it */\r
1862 Py_INCREF(aval);\r
1863 /* ditto for key */\r
1864 Py_INCREF(key);\r
1865 bval = PyDict_GetItem((PyObject *)b, key);\r
1866 Py_DECREF(key);\r
1867 if (bval == NULL) {\r
1868 Py_DECREF(aval);\r
1869 return 0;\r
1870 }\r
1871 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);\r
1872 Py_DECREF(aval);\r
1873 if (cmp <= 0) /* error or not equal */\r
1874 return cmp;\r
1875 }\r
1876 }\r
1877 return 1;\r
1878 }\r
1879\r
1880static PyObject *\r
1881dict_richcompare(PyObject *v, PyObject *w, int op)\r
1882{\r
1883 int cmp;\r
1884 PyObject *res;\r
1885\r
1886 if (!PyDict_Check(v) || !PyDict_Check(w)) {\r
1887 res = Py_NotImplemented;\r
1888 }\r
1889 else if (op == Py_EQ || op == Py_NE) {\r
1890 cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);\r
1891 if (cmp < 0)\r
1892 return NULL;\r
1893 res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;\r
1894 }\r
1895 else {\r
1896 /* Py3K warning if comparison isn't == or != */\r
1897 if (PyErr_WarnPy3k("dict inequality comparisons not supported "\r
1898 "in 3.x", 1) < 0) {\r
1899 return NULL;\r
1900 }\r
1901 res = Py_NotImplemented;\r
1902 }\r
1903 Py_INCREF(res);\r
1904 return res;\r
1905 }\r
1906\r
1907static PyObject *\r
1908dict_contains(register PyDictObject *mp, PyObject *key)\r
1909{\r
1910 long hash;\r
1911 PyDictEntry *ep;\r
1912\r
1913 if (!PyString_CheckExact(key) ||\r
1914 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
1915 hash = PyObject_Hash(key);\r
1916 if (hash == -1)\r
1917 return NULL;\r
1918 }\r
1919 ep = (mp->ma_lookup)(mp, key, hash);\r
1920 if (ep == NULL)\r
1921 return NULL;\r
1922 return PyBool_FromLong(ep->me_value != NULL);\r
1923}\r
1924\r
1925static PyObject *\r
1926dict_has_key(register PyDictObject *mp, PyObject *key)\r
1927{\r
1928 if (PyErr_WarnPy3k("dict.has_key() not supported in 3.x; "\r
1929 "use the in operator", 1) < 0)\r
1930 return NULL;\r
1931 return dict_contains(mp, key);\r
1932}\r
1933\r
1934static PyObject *\r
1935dict_get(register PyDictObject *mp, PyObject *args)\r
1936{\r
1937 PyObject *key;\r
1938 PyObject *failobj = Py_None;\r
1939 PyObject *val = NULL;\r
1940 long hash;\r
1941 PyDictEntry *ep;\r
1942\r
1943 if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &failobj))\r
1944 return NULL;\r
1945\r
1946 if (!PyString_CheckExact(key) ||\r
1947 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
1948 hash = PyObject_Hash(key);\r
1949 if (hash == -1)\r
1950 return NULL;\r
1951 }\r
1952 ep = (mp->ma_lookup)(mp, key, hash);\r
1953 if (ep == NULL)\r
1954 return NULL;\r
1955 val = ep->me_value;\r
1956 if (val == NULL)\r
1957 val = failobj;\r
1958 Py_INCREF(val);\r
1959 return val;\r
1960}\r
1961\r
1962\r
1963static PyObject *\r
1964dict_setdefault(register PyDictObject *mp, PyObject *args)\r
1965{\r
1966 PyObject *key;\r
1967 PyObject *failobj = Py_None;\r
1968 PyObject *val = NULL;\r
1969 long hash;\r
1970 PyDictEntry *ep;\r
1971\r
1972 if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj))\r
1973 return NULL;\r
1974\r
1975 if (!PyString_CheckExact(key) ||\r
1976 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
1977 hash = PyObject_Hash(key);\r
1978 if (hash == -1)\r
1979 return NULL;\r
1980 }\r
1981 ep = (mp->ma_lookup)(mp, key, hash);\r
1982 if (ep == NULL)\r
1983 return NULL;\r
1984 val = ep->me_value;\r
1985 if (val == NULL) {\r
1986 if (dict_set_item_by_hash_or_entry((PyObject*)mp, key, hash, ep,\r
1987 failobj) == 0)\r
1988 val = failobj;\r
1989 }\r
1990 Py_XINCREF(val);\r
1991 return val;\r
1992}\r
1993\r
1994\r
1995static PyObject *\r
1996dict_clear(register PyDictObject *mp)\r
1997{\r
1998 PyDict_Clear((PyObject *)mp);\r
1999 Py_RETURN_NONE;\r
2000}\r
2001\r
2002static PyObject *\r
2003dict_pop(PyDictObject *mp, PyObject *args)\r
2004{\r
2005 long hash;\r
2006 PyDictEntry *ep;\r
2007 PyObject *old_value, *old_key;\r
2008 PyObject *key, *deflt = NULL;\r
2009\r
2010 if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))\r
2011 return NULL;\r
2012 if (mp->ma_used == 0) {\r
2013 if (deflt) {\r
2014 Py_INCREF(deflt);\r
2015 return deflt;\r
2016 }\r
2017 set_key_error(key);\r
2018 return NULL;\r
2019 }\r
2020 if (!PyString_CheckExact(key) ||\r
2021 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
2022 hash = PyObject_Hash(key);\r
2023 if (hash == -1)\r
2024 return NULL;\r
2025 }\r
2026 ep = (mp->ma_lookup)(mp, key, hash);\r
2027 if (ep == NULL)\r
2028 return NULL;\r
2029 if (ep->me_value == NULL) {\r
2030 if (deflt) {\r
2031 Py_INCREF(deflt);\r
2032 return deflt;\r
2033 }\r
2034 set_key_error(key);\r
2035 return NULL;\r
2036 }\r
2037 old_key = ep->me_key;\r
2038 Py_INCREF(dummy);\r
2039 ep->me_key = dummy;\r
2040 old_value = ep->me_value;\r
2041 ep->me_value = NULL;\r
2042 mp->ma_used--;\r
2043 Py_DECREF(old_key);\r
2044 return old_value;\r
2045}\r
2046\r
2047static PyObject *\r
2048dict_popitem(PyDictObject *mp)\r
2049{\r
2050 Py_ssize_t i = 0;\r
2051 PyDictEntry *ep;\r
2052 PyObject *res;\r
2053\r
2054 /* Allocate the result tuple before checking the size. Believe it\r
2055 * or not, this allocation could trigger a garbage collection which\r
2056 * could empty the dict, so if we checked the size first and that\r
2057 * happened, the result would be an infinite loop (searching for an\r
2058 * entry that no longer exists). Note that the usual popitem()\r
2059 * idiom is "while d: k, v = d.popitem()". so needing to throw the\r
2060 * tuple away if the dict *is* empty isn't a significant\r
2061 * inefficiency -- possible, but unlikely in practice.\r
2062 */\r
2063 res = PyTuple_New(2);\r
2064 if (res == NULL)\r
2065 return NULL;\r
2066 if (mp->ma_used == 0) {\r
2067 Py_DECREF(res);\r
2068 PyErr_SetString(PyExc_KeyError,\r
2069 "popitem(): dictionary is empty");\r
2070 return NULL;\r
2071 }\r
2072 /* Set ep to "the first" dict entry with a value. We abuse the hash\r
2073 * field of slot 0 to hold a search finger:\r
2074 * If slot 0 has a value, use slot 0.\r
2075 * Else slot 0 is being used to hold a search finger,\r
2076 * and we use its hash value as the first index to look.\r
2077 */\r
2078 ep = &mp->ma_table[0];\r
2079 if (ep->me_value == NULL) {\r
2080 i = ep->me_hash;\r
2081 /* The hash field may be a real hash value, or it may be a\r
2082 * legit search finger, or it may be a once-legit search\r
2083 * finger that's out of bounds now because it wrapped around\r
2084 * or the table shrunk -- simply make sure it's in bounds now.\r
2085 */\r
2086 if (i > mp->ma_mask || i < 1)\r
2087 i = 1; /* skip slot 0 */\r
2088 while ((ep = &mp->ma_table[i])->me_value == NULL) {\r
2089 i++;\r
2090 if (i > mp->ma_mask)\r
2091 i = 1;\r
2092 }\r
2093 }\r
2094 PyTuple_SET_ITEM(res, 0, ep->me_key);\r
2095 PyTuple_SET_ITEM(res, 1, ep->me_value);\r
2096 Py_INCREF(dummy);\r
2097 ep->me_key = dummy;\r
2098 ep->me_value = NULL;\r
2099 mp->ma_used--;\r
2100 assert(mp->ma_table[0].me_value == NULL);\r
2101 mp->ma_table[0].me_hash = i + 1; /* next place to start */\r
2102 return res;\r
2103}\r
2104\r
2105static int\r
2106dict_traverse(PyObject *op, visitproc visit, void *arg)\r
2107{\r
2108 Py_ssize_t i = 0;\r
2109 PyObject *pk;\r
2110 PyObject *pv;\r
2111\r
2112 while (PyDict_Next(op, &i, &pk, &pv)) {\r
2113 Py_VISIT(pk);\r
2114 Py_VISIT(pv);\r
2115 }\r
2116 return 0;\r
2117}\r
2118\r
2119static int\r
2120dict_tp_clear(PyObject *op)\r
2121{\r
2122 PyDict_Clear(op);\r
2123 return 0;\r
2124}\r
2125\r
2126\r
2127extern PyTypeObject PyDictIterKey_Type; /* Forward */\r
2128extern PyTypeObject PyDictIterValue_Type; /* Forward */\r
2129extern PyTypeObject PyDictIterItem_Type; /* Forward */\r
2130static PyObject *dictiter_new(PyDictObject *, PyTypeObject *);\r
2131\r
2132static PyObject *\r
2133dict_iterkeys(PyDictObject *dict)\r
2134{\r
2135 return dictiter_new(dict, &PyDictIterKey_Type);\r
2136}\r
2137\r
2138static PyObject *\r
2139dict_itervalues(PyDictObject *dict)\r
2140{\r
2141 return dictiter_new(dict, &PyDictIterValue_Type);\r
2142}\r
2143\r
2144static PyObject *\r
2145dict_iteritems(PyDictObject *dict)\r
2146{\r
2147 return dictiter_new(dict, &PyDictIterItem_Type);\r
2148}\r
2149\r
2150static PyObject *\r
2151dict_sizeof(PyDictObject *mp)\r
2152{\r
2153 Py_ssize_t res;\r
2154\r
2155 res = sizeof(PyDictObject);\r
2156 if (mp->ma_table != mp->ma_smalltable)\r
2157 res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);\r
2158 return PyInt_FromSsize_t(res);\r
2159}\r
2160\r
2161PyDoc_STRVAR(has_key__doc__,\r
2162"D.has_key(k) -> True if D has a key k, else False");\r
2163\r
2164PyDoc_STRVAR(contains__doc__,\r
2165"D.__contains__(k) -> True if D has a key k, else False");\r
2166\r
2167PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");\r
2168\r
2169PyDoc_STRVAR(sizeof__doc__,\r
2170"D.__sizeof__() -> size of D in memory, in bytes");\r
2171\r
2172PyDoc_STRVAR(get__doc__,\r
2173"D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");\r
2174\r
2175PyDoc_STRVAR(setdefault_doc__,\r
2176"D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");\r
2177\r
2178PyDoc_STRVAR(pop__doc__,\r
2179"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\\r
2180If key is not found, d is returned if given, otherwise KeyError is raised");\r
2181\r
2182PyDoc_STRVAR(popitem__doc__,\r
2183"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\\r
21842-tuple; but raise KeyError if D is empty.");\r
2185\r
2186PyDoc_STRVAR(keys__doc__,\r
2187"D.keys() -> list of D's keys");\r
2188\r
2189PyDoc_STRVAR(items__doc__,\r
2190"D.items() -> list of D's (key, value) pairs, as 2-tuples");\r
2191\r
2192PyDoc_STRVAR(values__doc__,\r
2193"D.values() -> list of D's values");\r
2194\r
2195PyDoc_STRVAR(update__doc__,\r
2196"D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n"\r
2197"If E present and has a .keys() method, does: for k in E: D[k] = E[k]\n\\r
2198If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v\n\\r
2199In either case, this is followed by: for k in F: D[k] = F[k]");\r
2200\r
2201PyDoc_STRVAR(fromkeys__doc__,\r
2202"dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\\r
2203v defaults to None.");\r
2204\r
2205PyDoc_STRVAR(clear__doc__,\r
2206"D.clear() -> None. Remove all items from D.");\r
2207\r
2208PyDoc_STRVAR(copy__doc__,\r
2209"D.copy() -> a shallow copy of D");\r
2210\r
2211PyDoc_STRVAR(iterkeys__doc__,\r
2212"D.iterkeys() -> an iterator over the keys of D");\r
2213\r
2214PyDoc_STRVAR(itervalues__doc__,\r
2215"D.itervalues() -> an iterator over the values of D");\r
2216\r
2217PyDoc_STRVAR(iteritems__doc__,\r
2218"D.iteritems() -> an iterator over the (key, value) items of D");\r
2219\r
2220/* Forward */\r
2221static PyObject *dictkeys_new(PyObject *);\r
2222static PyObject *dictitems_new(PyObject *);\r
2223static PyObject *dictvalues_new(PyObject *);\r
2224\r
2225PyDoc_STRVAR(viewkeys__doc__,\r
2226 "D.viewkeys() -> a set-like object providing a view on D's keys");\r
2227PyDoc_STRVAR(viewitems__doc__,\r
2228 "D.viewitems() -> a set-like object providing a view on D's items");\r
2229PyDoc_STRVAR(viewvalues__doc__,\r
2230 "D.viewvalues() -> an object providing a view on D's values");\r
2231\r
2232static PyMethodDef mapp_methods[] = {\r
2233 {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,\r
2234 contains__doc__},\r
2235 {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,\r
2236 getitem__doc__},\r
2237 {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,\r
2238 sizeof__doc__},\r
2239 {"has_key", (PyCFunction)dict_has_key, METH_O,\r
2240 has_key__doc__},\r
2241 {"get", (PyCFunction)dict_get, METH_VARARGS,\r
2242 get__doc__},\r
2243 {"setdefault", (PyCFunction)dict_setdefault, METH_VARARGS,\r
2244 setdefault_doc__},\r
2245 {"pop", (PyCFunction)dict_pop, METH_VARARGS,\r
2246 pop__doc__},\r
2247 {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,\r
2248 popitem__doc__},\r
2249 {"keys", (PyCFunction)dict_keys, METH_NOARGS,\r
2250 keys__doc__},\r
2251 {"items", (PyCFunction)dict_items, METH_NOARGS,\r
2252 items__doc__},\r
2253 {"values", (PyCFunction)dict_values, METH_NOARGS,\r
2254 values__doc__},\r
2255 {"viewkeys", (PyCFunction)dictkeys_new, METH_NOARGS,\r
2256 viewkeys__doc__},\r
2257 {"viewitems", (PyCFunction)dictitems_new, METH_NOARGS,\r
2258 viewitems__doc__},\r
2259 {"viewvalues", (PyCFunction)dictvalues_new, METH_NOARGS,\r
2260 viewvalues__doc__},\r
2261 {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,\r
2262 update__doc__},\r
2263 {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,\r
2264 fromkeys__doc__},\r
2265 {"clear", (PyCFunction)dict_clear, METH_NOARGS,\r
2266 clear__doc__},\r
2267 {"copy", (PyCFunction)dict_copy, METH_NOARGS,\r
2268 copy__doc__},\r
2269 {"iterkeys", (PyCFunction)dict_iterkeys, METH_NOARGS,\r
2270 iterkeys__doc__},\r
2271 {"itervalues", (PyCFunction)dict_itervalues, METH_NOARGS,\r
2272 itervalues__doc__},\r
2273 {"iteritems", (PyCFunction)dict_iteritems, METH_NOARGS,\r
2274 iteritems__doc__},\r
2275 {NULL, NULL} /* sentinel */\r
2276};\r
2277\r
2278/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */\r
2279int\r
2280PyDict_Contains(PyObject *op, PyObject *key)\r
2281{\r
2282 long hash;\r
2283 PyDictObject *mp = (PyDictObject *)op;\r
2284 PyDictEntry *ep;\r
2285\r
2286 if (!PyString_CheckExact(key) ||\r
2287 (hash = ((PyStringObject *) key)->ob_shash) == -1) {\r
2288 hash = PyObject_Hash(key);\r
2289 if (hash == -1)\r
2290 return -1;\r
2291 }\r
2292 ep = (mp->ma_lookup)(mp, key, hash);\r
2293 return ep == NULL ? -1 : (ep->me_value != NULL);\r
2294}\r
2295\r
2296/* Internal version of PyDict_Contains used when the hash value is already known */\r
2297int\r
2298_PyDict_Contains(PyObject *op, PyObject *key, long hash)\r
2299{\r
2300 PyDictObject *mp = (PyDictObject *)op;\r
2301 PyDictEntry *ep;\r
2302\r
2303 ep = (mp->ma_lookup)(mp, key, hash);\r
2304 return ep == NULL ? -1 : (ep->me_value != NULL);\r
2305}\r
2306\r
2307/* Hack to implement "key in dict" */\r
2308static PySequenceMethods dict_as_sequence = {\r
2309 0, /* sq_length */\r
2310 0, /* sq_concat */\r
2311 0, /* sq_repeat */\r
2312 0, /* sq_item */\r
2313 0, /* sq_slice */\r
2314 0, /* sq_ass_item */\r
2315 0, /* sq_ass_slice */\r
2316 PyDict_Contains, /* sq_contains */\r
2317 0, /* sq_inplace_concat */\r
2318 0, /* sq_inplace_repeat */\r
2319};\r
2320\r
2321static PyObject *\r
2322dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
2323{\r
2324 PyObject *self;\r
2325\r
2326 assert(type != NULL && type->tp_alloc != NULL);\r
2327 self = type->tp_alloc(type, 0);\r
2328 if (self != NULL) {\r
2329 PyDictObject *d = (PyDictObject *)self;\r
2330 /* It's guaranteed that tp->alloc zeroed out the struct. */\r
2331 assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);\r
2332 INIT_NONZERO_DICT_SLOTS(d);\r
2333 d->ma_lookup = lookdict_string;\r
2334 /* The object has been implicitly tracked by tp_alloc */\r
2335 if (type == &PyDict_Type)\r
2336 _PyObject_GC_UNTRACK(d);\r
2337#ifdef SHOW_CONVERSION_COUNTS\r
2338 ++created;\r
2339#endif\r
2340#ifdef SHOW_TRACK_COUNT\r
2341 if (_PyObject_GC_IS_TRACKED(d))\r
2342 count_tracked++;\r
2343 else\r
2344 count_untracked++;\r
2345#endif\r
2346 }\r
2347 return self;\r
2348}\r
2349\r
2350static int\r
2351dict_init(PyObject *self, PyObject *args, PyObject *kwds)\r
2352{\r
2353 return dict_update_common(self, args, kwds, "dict");\r
2354}\r
2355\r
2356static PyObject *\r
2357dict_iter(PyDictObject *dict)\r
2358{\r
2359 return dictiter_new(dict, &PyDictIterKey_Type);\r
2360}\r
2361\r
2362PyDoc_STRVAR(dictionary_doc,\r
2363"dict() -> new empty dictionary\n"\r
2364"dict(mapping) -> new dictionary initialized from a mapping object's\n"\r
2365" (key, value) pairs\n"\r
2366"dict(iterable) -> new dictionary initialized as if via:\n"\r
2367" d = {}\n"\r
2368" for k, v in iterable:\n"\r
2369" d[k] = v\n"\r
2370"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"\r
2371" in the keyword argument list. For example: dict(one=1, two=2)");\r
2372\r
2373PyTypeObject PyDict_Type = {\r
2374 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
2375 "dict",\r
2376 sizeof(PyDictObject),\r
2377 0,\r
2378 (destructor)dict_dealloc, /* tp_dealloc */\r
2379 (printfunc)dict_print, /* tp_print */\r
2380 0, /* tp_getattr */\r
2381 0, /* tp_setattr */\r
2382 (cmpfunc)dict_compare, /* tp_compare */\r
2383 (reprfunc)dict_repr, /* tp_repr */\r
2384 0, /* tp_as_number */\r
2385 &dict_as_sequence, /* tp_as_sequence */\r
2386 &dict_as_mapping, /* tp_as_mapping */\r
2387 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */\r
2388 0, /* tp_call */\r
2389 0, /* tp_str */\r
2390 PyObject_GenericGetAttr, /* tp_getattro */\r
2391 0, /* tp_setattro */\r
2392 0, /* tp_as_buffer */\r
2393 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |\r
2394 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */\r
2395 dictionary_doc, /* tp_doc */\r
2396 dict_traverse, /* tp_traverse */\r
2397 dict_tp_clear, /* tp_clear */\r
2398 dict_richcompare, /* tp_richcompare */\r
2399 0, /* tp_weaklistoffset */\r
2400 (getiterfunc)dict_iter, /* tp_iter */\r
2401 0, /* tp_iternext */\r
2402 mapp_methods, /* tp_methods */\r
2403 0, /* tp_members */\r
2404 0, /* tp_getset */\r
2405 0, /* tp_base */\r
2406 0, /* tp_dict */\r
2407 0, /* tp_descr_get */\r
2408 0, /* tp_descr_set */\r
2409 0, /* tp_dictoffset */\r
2410 dict_init, /* tp_init */\r
2411 PyType_GenericAlloc, /* tp_alloc */\r
2412 dict_new, /* tp_new */\r
2413 PyObject_GC_Del, /* tp_free */\r
2414};\r
2415\r
2416/* For backward compatibility with old dictionary interface */\r
2417\r
2418PyObject *\r
2419PyDict_GetItemString(PyObject *v, const char *key)\r
2420{\r
2421 PyObject *kv, *rv;\r
2422 kv = PyString_FromString(key);\r
2423 if (kv == NULL)\r
2424 return NULL;\r
2425 rv = PyDict_GetItem(v, kv);\r
2426 Py_DECREF(kv);\r
2427 return rv;\r
2428}\r
2429\r
2430int\r
2431PyDict_SetItemString(PyObject *v, const char *key, PyObject *item)\r
2432{\r
2433 PyObject *kv;\r
2434 int err;\r
2435 kv = PyString_FromString(key);\r
2436 if (kv == NULL)\r
2437 return -1;\r
2438 PyString_InternInPlace(&kv); /* XXX Should we really? */\r
2439 err = PyDict_SetItem(v, kv, item);\r
2440 Py_DECREF(kv);\r
2441 return err;\r
2442}\r
2443\r
2444int\r
2445PyDict_DelItemString(PyObject *v, const char *key)\r
2446{\r
2447 PyObject *kv;\r
2448 int err;\r
2449 kv = PyString_FromString(key);\r
2450 if (kv == NULL)\r
2451 return -1;\r
2452 err = PyDict_DelItem(v, kv);\r
2453 Py_DECREF(kv);\r
2454 return err;\r
2455}\r
2456\r
2457/* Dictionary iterator types */\r
2458\r
2459typedef struct {\r
2460 PyObject_HEAD\r
2461 PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */\r
2462 Py_ssize_t di_used;\r
2463 Py_ssize_t di_pos;\r
2464 PyObject* di_result; /* reusable result tuple for iteritems */\r
2465 Py_ssize_t len;\r
2466} dictiterobject;\r
2467\r
2468static PyObject *\r
2469dictiter_new(PyDictObject *dict, PyTypeObject *itertype)\r
2470{\r
2471 dictiterobject *di;\r
2472 di = PyObject_GC_New(dictiterobject, itertype);\r
2473 if (di == NULL)\r
2474 return NULL;\r
2475 Py_INCREF(dict);\r
2476 di->di_dict = dict;\r
2477 di->di_used = dict->ma_used;\r
2478 di->di_pos = 0;\r
2479 di->len = dict->ma_used;\r
2480 if (itertype == &PyDictIterItem_Type) {\r
2481 di->di_result = PyTuple_Pack(2, Py_None, Py_None);\r
2482 if (di->di_result == NULL) {\r
2483 Py_DECREF(di);\r
2484 return NULL;\r
2485 }\r
2486 }\r
2487 else\r
2488 di->di_result = NULL;\r
2489 _PyObject_GC_TRACK(di);\r
2490 return (PyObject *)di;\r
2491}\r
2492\r
2493static void\r
2494dictiter_dealloc(dictiterobject *di)\r
2495{\r
2496 Py_XDECREF(di->di_dict);\r
2497 Py_XDECREF(di->di_result);\r
2498 PyObject_GC_Del(di);\r
2499}\r
2500\r
2501static int\r
2502dictiter_traverse(dictiterobject *di, visitproc visit, void *arg)\r
2503{\r
2504 Py_VISIT(di->di_dict);\r
2505 Py_VISIT(di->di_result);\r
2506 return 0;\r
2507}\r
2508\r
2509static PyObject *\r
2510dictiter_len(dictiterobject *di)\r
2511{\r
2512 Py_ssize_t len = 0;\r
2513 if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)\r
2514 len = di->len;\r
2515 return PyInt_FromSize_t(len);\r
2516}\r
2517\r
2518PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r
2519\r
2520static PyMethodDef dictiter_methods[] = {\r
2521 {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS, length_hint_doc},\r
2522 {NULL, NULL} /* sentinel */\r
2523};\r
2524\r
2525static PyObject *dictiter_iternextkey(dictiterobject *di)\r
2526{\r
2527 PyObject *key;\r
2528 register Py_ssize_t i, mask;\r
2529 register PyDictEntry *ep;\r
2530 PyDictObject *d = di->di_dict;\r
2531\r
2532 if (d == NULL)\r
2533 return NULL;\r
2534 assert (PyDict_Check(d));\r
2535\r
2536 if (di->di_used != d->ma_used) {\r
2537 PyErr_SetString(PyExc_RuntimeError,\r
2538 "dictionary changed size during iteration");\r
2539 di->di_used = -1; /* Make this state sticky */\r
2540 return NULL;\r
2541 }\r
2542\r
2543 i = di->di_pos;\r
2544 if (i < 0)\r
2545 goto fail;\r
2546 ep = d->ma_table;\r
2547 mask = d->ma_mask;\r
2548 while (i <= mask && ep[i].me_value == NULL)\r
2549 i++;\r
2550 di->di_pos = i+1;\r
2551 if (i > mask)\r
2552 goto fail;\r
2553 di->len--;\r
2554 key = ep[i].me_key;\r
2555 Py_INCREF(key);\r
2556 return key;\r
2557\r
2558fail:\r
2559 Py_DECREF(d);\r
2560 di->di_dict = NULL;\r
2561 return NULL;\r
2562}\r
2563\r
2564PyTypeObject PyDictIterKey_Type = {\r
2565 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
2566 "dictionary-keyiterator", /* tp_name */\r
2567 sizeof(dictiterobject), /* tp_basicsize */\r
2568 0, /* tp_itemsize */\r
2569 /* methods */\r
2570 (destructor)dictiter_dealloc, /* tp_dealloc */\r
2571 0, /* tp_print */\r
2572 0, /* tp_getattr */\r
2573 0, /* tp_setattr */\r
2574 0, /* tp_compare */\r
2575 0, /* tp_repr */\r
2576 0, /* tp_as_number */\r
2577 0, /* tp_as_sequence */\r
2578 0, /* tp_as_mapping */\r
2579 0, /* tp_hash */\r
2580 0, /* tp_call */\r
2581 0, /* tp_str */\r
2582 PyObject_GenericGetAttr, /* tp_getattro */\r
2583 0, /* tp_setattro */\r
2584 0, /* tp_as_buffer */\r
2585 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
2586 0, /* tp_doc */\r
2587 (traverseproc)dictiter_traverse, /* tp_traverse */\r
2588 0, /* tp_clear */\r
2589 0, /* tp_richcompare */\r
2590 0, /* tp_weaklistoffset */\r
2591 PyObject_SelfIter, /* tp_iter */\r
2592 (iternextfunc)dictiter_iternextkey, /* tp_iternext */\r
2593 dictiter_methods, /* tp_methods */\r
2594 0,\r
2595};\r
2596\r
2597static PyObject *dictiter_iternextvalue(dictiterobject *di)\r
2598{\r
2599 PyObject *value;\r
2600 register Py_ssize_t i, mask;\r
2601 register PyDictEntry *ep;\r
2602 PyDictObject *d = di->di_dict;\r
2603\r
2604 if (d == NULL)\r
2605 return NULL;\r
2606 assert (PyDict_Check(d));\r
2607\r
2608 if (di->di_used != d->ma_used) {\r
2609 PyErr_SetString(PyExc_RuntimeError,\r
2610 "dictionary changed size during iteration");\r
2611 di->di_used = -1; /* Make this state sticky */\r
2612 return NULL;\r
2613 }\r
2614\r
2615 i = di->di_pos;\r
2616 mask = d->ma_mask;\r
2617 if (i < 0 || i > mask)\r
2618 goto fail;\r
2619 ep = d->ma_table;\r
2620 while ((value=ep[i].me_value) == NULL) {\r
2621 i++;\r
2622 if (i > mask)\r
2623 goto fail;\r
2624 }\r
2625 di->di_pos = i+1;\r
2626 di->len--;\r
2627 Py_INCREF(value);\r
2628 return value;\r
2629\r
2630fail:\r
2631 Py_DECREF(d);\r
2632 di->di_dict = NULL;\r
2633 return NULL;\r
2634}\r
2635\r
2636PyTypeObject PyDictIterValue_Type = {\r
2637 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
2638 "dictionary-valueiterator", /* tp_name */\r
2639 sizeof(dictiterobject), /* tp_basicsize */\r
2640 0, /* tp_itemsize */\r
2641 /* methods */\r
2642 (destructor)dictiter_dealloc, /* tp_dealloc */\r
2643 0, /* tp_print */\r
2644 0, /* tp_getattr */\r
2645 0, /* tp_setattr */\r
2646 0, /* tp_compare */\r
2647 0, /* tp_repr */\r
2648 0, /* tp_as_number */\r
2649 0, /* tp_as_sequence */\r
2650 0, /* tp_as_mapping */\r
2651 0, /* tp_hash */\r
2652 0, /* tp_call */\r
2653 0, /* tp_str */\r
2654 PyObject_GenericGetAttr, /* tp_getattro */\r
2655 0, /* tp_setattro */\r
2656 0, /* tp_as_buffer */\r
2657 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
2658 0, /* tp_doc */\r
2659 (traverseproc)dictiter_traverse, /* tp_traverse */\r
2660 0, /* tp_clear */\r
2661 0, /* tp_richcompare */\r
2662 0, /* tp_weaklistoffset */\r
2663 PyObject_SelfIter, /* tp_iter */\r
2664 (iternextfunc)dictiter_iternextvalue, /* tp_iternext */\r
2665 dictiter_methods, /* tp_methods */\r
2666 0,\r
2667};\r
2668\r
2669static PyObject *dictiter_iternextitem(dictiterobject *di)\r
2670{\r
2671 PyObject *key, *value, *result = di->di_result;\r
2672 register Py_ssize_t i, mask;\r
2673 register PyDictEntry *ep;\r
2674 PyDictObject *d = di->di_dict;\r
2675\r
2676 if (d == NULL)\r
2677 return NULL;\r
2678 assert (PyDict_Check(d));\r
2679\r
2680 if (di->di_used != d->ma_used) {\r
2681 PyErr_SetString(PyExc_RuntimeError,\r
2682 "dictionary changed size during iteration");\r
2683 di->di_used = -1; /* Make this state sticky */\r
2684 return NULL;\r
2685 }\r
2686\r
2687 i = di->di_pos;\r
2688 if (i < 0)\r
2689 goto fail;\r
2690 ep = d->ma_table;\r
2691 mask = d->ma_mask;\r
2692 while (i <= mask && ep[i].me_value == NULL)\r
2693 i++;\r
2694 di->di_pos = i+1;\r
2695 if (i > mask)\r
2696 goto fail;\r
2697\r
2698 if (result->ob_refcnt == 1) {\r
2699 Py_INCREF(result);\r
2700 Py_DECREF(PyTuple_GET_ITEM(result, 0));\r
2701 Py_DECREF(PyTuple_GET_ITEM(result, 1));\r
2702 } else {\r
2703 result = PyTuple_New(2);\r
2704 if (result == NULL)\r
2705 return NULL;\r
2706 }\r
2707 di->len--;\r
2708 key = ep[i].me_key;\r
2709 value = ep[i].me_value;\r
2710 Py_INCREF(key);\r
2711 Py_INCREF(value);\r
2712 PyTuple_SET_ITEM(result, 0, key);\r
2713 PyTuple_SET_ITEM(result, 1, value);\r
2714 return result;\r
2715\r
2716fail:\r
2717 Py_DECREF(d);\r
2718 di->di_dict = NULL;\r
2719 return NULL;\r
2720}\r
2721\r
2722PyTypeObject PyDictIterItem_Type = {\r
2723 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
2724 "dictionary-itemiterator", /* tp_name */\r
2725 sizeof(dictiterobject), /* tp_basicsize */\r
2726 0, /* tp_itemsize */\r
2727 /* methods */\r
2728 (destructor)dictiter_dealloc, /* tp_dealloc */\r
2729 0, /* tp_print */\r
2730 0, /* tp_getattr */\r
2731 0, /* tp_setattr */\r
2732 0, /* tp_compare */\r
2733 0, /* tp_repr */\r
2734 0, /* tp_as_number */\r
2735 0, /* tp_as_sequence */\r
2736 0, /* tp_as_mapping */\r
2737 0, /* tp_hash */\r
2738 0, /* tp_call */\r
2739 0, /* tp_str */\r
2740 PyObject_GenericGetAttr, /* tp_getattro */\r
2741 0, /* tp_setattro */\r
2742 0, /* tp_as_buffer */\r
2743 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
2744 0, /* tp_doc */\r
2745 (traverseproc)dictiter_traverse, /* tp_traverse */\r
2746 0, /* tp_clear */\r
2747 0, /* tp_richcompare */\r
2748 0, /* tp_weaklistoffset */\r
2749 PyObject_SelfIter, /* tp_iter */\r
2750 (iternextfunc)dictiter_iternextitem, /* tp_iternext */\r
2751 dictiter_methods, /* tp_methods */\r
2752 0,\r
2753};\r
2754\r
2755/***********************************************/\r
2756/* View objects for keys(), items(), values(). */\r
2757/***********************************************/\r
2758\r
2759/* The instance lay-out is the same for all three; but the type differs. */\r
2760\r
2761typedef struct {\r
2762 PyObject_HEAD\r
2763 PyDictObject *dv_dict;\r
2764} dictviewobject;\r
2765\r
2766\r
2767static void\r
2768dictview_dealloc(dictviewobject *dv)\r
2769{\r
2770 Py_XDECREF(dv->dv_dict);\r
2771 PyObject_GC_Del(dv);\r
2772}\r
2773\r
2774static int\r
2775dictview_traverse(dictviewobject *dv, visitproc visit, void *arg)\r
2776{\r
2777 Py_VISIT(dv->dv_dict);\r
2778 return 0;\r
2779}\r
2780\r
2781static Py_ssize_t\r
2782dictview_len(dictviewobject *dv)\r
2783{\r
2784 Py_ssize_t len = 0;\r
2785 if (dv->dv_dict != NULL)\r
2786 len = dv->dv_dict->ma_used;\r
2787 return len;\r
2788}\r
2789\r
2790static PyObject *\r
2791dictview_new(PyObject *dict, PyTypeObject *type)\r
2792{\r
2793 dictviewobject *dv;\r
2794 if (dict == NULL) {\r
2795 PyErr_BadInternalCall();\r
2796 return NULL;\r
2797 }\r
2798 if (!PyDict_Check(dict)) {\r
2799 /* XXX Get rid of this restriction later */\r
2800 PyErr_Format(PyExc_TypeError,\r
2801 "%s() requires a dict argument, not '%s'",\r
2802 type->tp_name, dict->ob_type->tp_name);\r
2803 return NULL;\r
2804 }\r
2805 dv = PyObject_GC_New(dictviewobject, type);\r
2806 if (dv == NULL)\r
2807 return NULL;\r
2808 Py_INCREF(dict);\r
2809 dv->dv_dict = (PyDictObject *)dict;\r
2810 _PyObject_GC_TRACK(dv);\r
2811 return (PyObject *)dv;\r
2812}\r
2813\r
2814/* TODO(guido): The views objects are not complete:\r
2815\r
2816 * support more set operations\r
2817 * support arbitrary mappings?\r
2818 - either these should be static or exported in dictobject.h\r
2819 - if public then they should probably be in builtins\r
2820*/\r
2821\r
2822/* Return 1 if self is a subset of other, iterating over self;\r
2823 0 if not; -1 if an error occurred. */\r
2824static int\r
2825all_contained_in(PyObject *self, PyObject *other)\r
2826{\r
2827 PyObject *iter = PyObject_GetIter(self);\r
2828 int ok = 1;\r
2829\r
2830 if (iter == NULL)\r
2831 return -1;\r
2832 for (;;) {\r
2833 PyObject *next = PyIter_Next(iter);\r
2834 if (next == NULL) {\r
2835 if (PyErr_Occurred())\r
2836 ok = -1;\r
2837 break;\r
2838 }\r
2839 ok = PySequence_Contains(other, next);\r
2840 Py_DECREF(next);\r
2841 if (ok <= 0)\r
2842 break;\r
2843 }\r
2844 Py_DECREF(iter);\r
2845 return ok;\r
2846}\r
2847\r
2848static PyObject *\r
2849dictview_richcompare(PyObject *self, PyObject *other, int op)\r
2850{\r
2851 Py_ssize_t len_self, len_other;\r
2852 int ok;\r
2853 PyObject *result;\r
2854\r
2855 assert(self != NULL);\r
2856 assert(PyDictViewSet_Check(self));\r
2857 assert(other != NULL);\r
2858\r
2859 if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other)) {\r
2860 Py_INCREF(Py_NotImplemented);\r
2861 return Py_NotImplemented;\r
2862 }\r
2863\r
2864 len_self = PyObject_Size(self);\r
2865 if (len_self < 0)\r
2866 return NULL;\r
2867 len_other = PyObject_Size(other);\r
2868 if (len_other < 0)\r
2869 return NULL;\r
2870\r
2871 ok = 0;\r
2872 switch(op) {\r
2873\r
2874 case Py_NE:\r
2875 case Py_EQ:\r
2876 if (len_self == len_other)\r
2877 ok = all_contained_in(self, other);\r
2878 if (op == Py_NE && ok >= 0)\r
2879 ok = !ok;\r
2880 break;\r
2881\r
2882 case Py_LT:\r
2883 if (len_self < len_other)\r
2884 ok = all_contained_in(self, other);\r
2885 break;\r
2886\r
2887 case Py_LE:\r
2888 if (len_self <= len_other)\r
2889 ok = all_contained_in(self, other);\r
2890 break;\r
2891\r
2892 case Py_GT:\r
2893 if (len_self > len_other)\r
2894 ok = all_contained_in(other, self);\r
2895 break;\r
2896\r
2897 case Py_GE:\r
2898 if (len_self >= len_other)\r
2899 ok = all_contained_in(other, self);\r
2900 break;\r
2901\r
2902 }\r
2903 if (ok < 0)\r
2904 return NULL;\r
2905 result = ok ? Py_True : Py_False;\r
2906 Py_INCREF(result);\r
2907 return result;\r
2908}\r
2909\r
2910static PyObject *\r
2911dictview_repr(dictviewobject *dv)\r
2912{\r
2913 PyObject *seq;\r
2914 PyObject *seq_str;\r
2915 PyObject *result;\r
2916\r
2917 seq = PySequence_List((PyObject *)dv);\r
2918 if (seq == NULL)\r
2919 return NULL;\r
2920\r
2921 seq_str = PyObject_Repr(seq);\r
2922 if (seq_str == NULL) {\r
2923 Py_DECREF(seq);\r
2924 return NULL;\r
2925 }\r
2926 result = PyString_FromFormat("%s(%s)", Py_TYPE(dv)->tp_name,\r
2927 PyString_AS_STRING(seq_str));\r
2928 Py_DECREF(seq_str);\r
2929 Py_DECREF(seq);\r
2930 return result;\r
2931}\r
2932\r
2933/*** dict_keys ***/\r
2934\r
2935static PyObject *\r
2936dictkeys_iter(dictviewobject *dv)\r
2937{\r
2938 if (dv->dv_dict == NULL) {\r
2939 Py_RETURN_NONE;\r
2940 }\r
2941 return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);\r
2942}\r
2943\r
2944static int\r
2945dictkeys_contains(dictviewobject *dv, PyObject *obj)\r
2946{\r
2947 if (dv->dv_dict == NULL)\r
2948 return 0;\r
2949 return PyDict_Contains((PyObject *)dv->dv_dict, obj);\r
2950}\r
2951\r
2952static PySequenceMethods dictkeys_as_sequence = {\r
2953 (lenfunc)dictview_len, /* sq_length */\r
2954 0, /* sq_concat */\r
2955 0, /* sq_repeat */\r
2956 0, /* sq_item */\r
2957 0, /* sq_slice */\r
2958 0, /* sq_ass_item */\r
2959 0, /* sq_ass_slice */\r
2960 (objobjproc)dictkeys_contains, /* sq_contains */\r
2961};\r
2962\r
2963static PyObject*\r
2964dictviews_sub(PyObject* self, PyObject *other)\r
2965{\r
2966 PyObject *result = PySet_New(self);\r
2967 PyObject *tmp;\r
2968 if (result == NULL)\r
2969 return NULL;\r
2970\r
2971 tmp = PyObject_CallMethod(result, "difference_update", "O", other);\r
2972 if (tmp == NULL) {\r
2973 Py_DECREF(result);\r
2974 return NULL;\r
2975 }\r
2976\r
2977 Py_DECREF(tmp);\r
2978 return result;\r
2979}\r
2980\r
2981static PyObject*\r
2982dictviews_and(PyObject* self, PyObject *other)\r
2983{\r
2984 PyObject *result = PySet_New(self);\r
2985 PyObject *tmp;\r
2986 if (result == NULL)\r
2987 return NULL;\r
2988\r
2989 tmp = PyObject_CallMethod(result, "intersection_update", "O", other);\r
2990 if (tmp == NULL) {\r
2991 Py_DECREF(result);\r
2992 return NULL;\r
2993 }\r
2994\r
2995 Py_DECREF(tmp);\r
2996 return result;\r
2997}\r
2998\r
2999static PyObject*\r
3000dictviews_or(PyObject* self, PyObject *other)\r
3001{\r
3002 PyObject *result = PySet_New(self);\r
3003 PyObject *tmp;\r
3004 if (result == NULL)\r
3005 return NULL;\r
3006\r
3007 tmp = PyObject_CallMethod(result, "update", "O", other);\r
3008 if (tmp == NULL) {\r
3009 Py_DECREF(result);\r
3010 return NULL;\r
3011 }\r
3012\r
3013 Py_DECREF(tmp);\r
3014 return result;\r
3015}\r
3016\r
3017static PyObject*\r
3018dictviews_xor(PyObject* self, PyObject *other)\r
3019{\r
3020 PyObject *result = PySet_New(self);\r
3021 PyObject *tmp;\r
3022 if (result == NULL)\r
3023 return NULL;\r
3024\r
3025 tmp = PyObject_CallMethod(result, "symmetric_difference_update", "O",\r
3026 other);\r
3027 if (tmp == NULL) {\r
3028 Py_DECREF(result);\r
3029 return NULL;\r
3030 }\r
3031\r
3032 Py_DECREF(tmp);\r
3033 return result;\r
3034}\r
3035\r
3036static PyNumberMethods dictviews_as_number = {\r
3037 0, /*nb_add*/\r
3038 (binaryfunc)dictviews_sub, /*nb_subtract*/\r
3039 0, /*nb_multiply*/\r
3040 0, /*nb_divide*/\r
3041 0, /*nb_remainder*/\r
3042 0, /*nb_divmod*/\r
3043 0, /*nb_power*/\r
3044 0, /*nb_negative*/\r
3045 0, /*nb_positive*/\r
3046 0, /*nb_absolute*/\r
3047 0, /*nb_nonzero*/\r
3048 0, /*nb_invert*/\r
3049 0, /*nb_lshift*/\r
3050 0, /*nb_rshift*/\r
3051 (binaryfunc)dictviews_and, /*nb_and*/\r
3052 (binaryfunc)dictviews_xor, /*nb_xor*/\r
3053 (binaryfunc)dictviews_or, /*nb_or*/\r
3054};\r
3055\r
3056static PyMethodDef dictkeys_methods[] = {\r
3057 {NULL, NULL} /* sentinel */\r
3058};\r
3059\r
3060PyTypeObject PyDictKeys_Type = {\r
3061 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
3062 "dict_keys", /* tp_name */\r
3063 sizeof(dictviewobject), /* tp_basicsize */\r
3064 0, /* tp_itemsize */\r
3065 /* methods */\r
3066 (destructor)dictview_dealloc, /* tp_dealloc */\r
3067 0, /* tp_print */\r
3068 0, /* tp_getattr */\r
3069 0, /* tp_setattr */\r
3070 0, /* tp_reserved */\r
3071 (reprfunc)dictview_repr, /* tp_repr */\r
3072 &dictviews_as_number, /* tp_as_number */\r
3073 &dictkeys_as_sequence, /* tp_as_sequence */\r
3074 0, /* tp_as_mapping */\r
3075 0, /* tp_hash */\r
3076 0, /* tp_call */\r
3077 0, /* tp_str */\r
3078 PyObject_GenericGetAttr, /* tp_getattro */\r
3079 0, /* tp_setattro */\r
3080 0, /* tp_as_buffer */\r
3081 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |\r
3082 Py_TPFLAGS_CHECKTYPES, /* tp_flags */\r
3083 0, /* tp_doc */\r
3084 (traverseproc)dictview_traverse, /* tp_traverse */\r
3085 0, /* tp_clear */\r
3086 dictview_richcompare, /* tp_richcompare */\r
3087 0, /* tp_weaklistoffset */\r
3088 (getiterfunc)dictkeys_iter, /* tp_iter */\r
3089 0, /* tp_iternext */\r
3090 dictkeys_methods, /* tp_methods */\r
3091 0,\r
3092};\r
3093\r
3094static PyObject *\r
3095dictkeys_new(PyObject *dict)\r
3096{\r
3097 return dictview_new(dict, &PyDictKeys_Type);\r
3098}\r
3099\r
3100/*** dict_items ***/\r
3101\r
3102static PyObject *\r
3103dictitems_iter(dictviewobject *dv)\r
3104{\r
3105 if (dv->dv_dict == NULL) {\r
3106 Py_RETURN_NONE;\r
3107 }\r
3108 return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);\r
3109}\r
3110\r
3111static int\r
3112dictitems_contains(dictviewobject *dv, PyObject *obj)\r
3113{\r
3114 PyObject *key, *value, *found;\r
3115 if (dv->dv_dict == NULL)\r
3116 return 0;\r
3117 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)\r
3118 return 0;\r
3119 key = PyTuple_GET_ITEM(obj, 0);\r
3120 value = PyTuple_GET_ITEM(obj, 1);\r
3121 found = PyDict_GetItem((PyObject *)dv->dv_dict, key);\r
3122 if (found == NULL) {\r
3123 if (PyErr_Occurred())\r
3124 return -1;\r
3125 return 0;\r
3126 }\r
3127 return PyObject_RichCompareBool(value, found, Py_EQ);\r
3128}\r
3129\r
3130static PySequenceMethods dictitems_as_sequence = {\r
3131 (lenfunc)dictview_len, /* sq_length */\r
3132 0, /* sq_concat */\r
3133 0, /* sq_repeat */\r
3134 0, /* sq_item */\r
3135 0, /* sq_slice */\r
3136 0, /* sq_ass_item */\r
3137 0, /* sq_ass_slice */\r
3138 (objobjproc)dictitems_contains, /* sq_contains */\r
3139};\r
3140\r
3141static PyMethodDef dictitems_methods[] = {\r
3142 {NULL, NULL} /* sentinel */\r
3143};\r
3144\r
3145PyTypeObject PyDictItems_Type = {\r
3146 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
3147 "dict_items", /* tp_name */\r
3148 sizeof(dictviewobject), /* tp_basicsize */\r
3149 0, /* tp_itemsize */\r
3150 /* methods */\r
3151 (destructor)dictview_dealloc, /* tp_dealloc */\r
3152 0, /* tp_print */\r
3153 0, /* tp_getattr */\r
3154 0, /* tp_setattr */\r
3155 0, /* tp_reserved */\r
3156 (reprfunc)dictview_repr, /* tp_repr */\r
3157 &dictviews_as_number, /* tp_as_number */\r
3158 &dictitems_as_sequence, /* tp_as_sequence */\r
3159 0, /* tp_as_mapping */\r
3160 0, /* tp_hash */\r
3161 0, /* tp_call */\r
3162 0, /* tp_str */\r
3163 PyObject_GenericGetAttr, /* tp_getattro */\r
3164 0, /* tp_setattro */\r
3165 0, /* tp_as_buffer */\r
3166 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |\r
3167 Py_TPFLAGS_CHECKTYPES, /* tp_flags */\r
3168 0, /* tp_doc */\r
3169 (traverseproc)dictview_traverse, /* tp_traverse */\r
3170 0, /* tp_clear */\r
3171 dictview_richcompare, /* tp_richcompare */\r
3172 0, /* tp_weaklistoffset */\r
3173 (getiterfunc)dictitems_iter, /* tp_iter */\r
3174 0, /* tp_iternext */\r
3175 dictitems_methods, /* tp_methods */\r
3176 0,\r
3177};\r
3178\r
3179static PyObject *\r
3180dictitems_new(PyObject *dict)\r
3181{\r
3182 return dictview_new(dict, &PyDictItems_Type);\r
3183}\r
3184\r
3185/*** dict_values ***/\r
3186\r
3187static PyObject *\r
3188dictvalues_iter(dictviewobject *dv)\r
3189{\r
3190 if (dv->dv_dict == NULL) {\r
3191 Py_RETURN_NONE;\r
3192 }\r
3193 return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);\r
3194}\r
3195\r
3196static PySequenceMethods dictvalues_as_sequence = {\r
3197 (lenfunc)dictview_len, /* sq_length */\r
3198 0, /* sq_concat */\r
3199 0, /* sq_repeat */\r
3200 0, /* sq_item */\r
3201 0, /* sq_slice */\r
3202 0, /* sq_ass_item */\r
3203 0, /* sq_ass_slice */\r
3204 (objobjproc)0, /* sq_contains */\r
3205};\r
3206\r
3207static PyMethodDef dictvalues_methods[] = {\r
3208 {NULL, NULL} /* sentinel */\r
3209};\r
3210\r
3211PyTypeObject PyDictValues_Type = {\r
3212 PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
3213 "dict_values", /* tp_name */\r
3214 sizeof(dictviewobject), /* tp_basicsize */\r
3215 0, /* tp_itemsize */\r
3216 /* methods */\r
3217 (destructor)dictview_dealloc, /* tp_dealloc */\r
3218 0, /* tp_print */\r
3219 0, /* tp_getattr */\r
3220 0, /* tp_setattr */\r
3221 0, /* tp_reserved */\r
3222 (reprfunc)dictview_repr, /* tp_repr */\r
3223 0, /* tp_as_number */\r
3224 &dictvalues_as_sequence, /* tp_as_sequence */\r
3225 0, /* tp_as_mapping */\r
3226 0, /* tp_hash */\r
3227 0, /* tp_call */\r
3228 0, /* tp_str */\r
3229 PyObject_GenericGetAttr, /* tp_getattro */\r
3230 0, /* tp_setattro */\r
3231 0, /* tp_as_buffer */\r
3232 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
3233 0, /* tp_doc */\r
3234 (traverseproc)dictview_traverse, /* tp_traverse */\r
3235 0, /* tp_clear */\r
3236 0, /* tp_richcompare */\r
3237 0, /* tp_weaklistoffset */\r
3238 (getiterfunc)dictvalues_iter, /* tp_iter */\r
3239 0, /* tp_iternext */\r
3240 dictvalues_methods, /* tp_methods */\r
3241 0,\r
3242};\r
3243\r
3244static PyObject *\r
3245dictvalues_new(PyObject *dict)\r
3246{\r
3247 return dictview_new(dict, &PyDictValues_Type);\r
3248}\r
EFI Development Kit II mirror for PVE