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