• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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