2 /* Dictionary object implementation using a hash table */
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.
11 #include "stringlib/eq.h"
14 /* Set a key error with the specified argument, wrapping it in a
15 * tuple automatically so that tuple keys are not unpacked as the
16 * exception arguments. */
18 set_key_error(PyObject
*arg
)
21 tup
= PyTuple_Pack(1, arg
);
23 return; /* caller will expect error to be set anyway */
24 PyErr_SetObject(PyExc_KeyError
, tup
);
28 /* Define this out if you don't want conversion statistics on exit. */
29 #undef SHOW_CONVERSION_COUNTS
31 /* See large comment block below. This must be >= 1. */
32 #define PERTURB_SHIFT 5
35 Major subtleties ahead: Most hash schemes depend on having a "good" hash
36 function, in the sense of simulating randomness. Python doesn't: its most
37 important hash functions (for strings and ints) are very regular in common
40 >>> map(hash, (0, 1, 2, 3))
42 >>> map(hash, ("namea", "nameb", "namec", "named"))
43 [-1658398457, -1658398460, -1658398459, -1658398462]
46 This isn't necessarily bad! To the contrary, in a table of size 2**i, taking
47 the low-order i bits as the initial table index is extremely fast, and there
48 are no collisions at all for dicts indexed by a contiguous range of ints.
49 The same is approximately true when keys are "consecutive" strings. So this
50 gives better-than-random behavior in common cases, and that's very desirable.
52 OTOH, when collisions occur, the tendency to fill contiguous slices of the
53 hash table makes a good collision resolution strategy crucial. Taking only
54 the last i bits of the hash code is also vulnerable: for example, consider
55 the list [i << 16 for i in range(20000)] as a set of keys. Since ints are
56 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
57 of every hash code are all 0: they *all* map to the same table index.
59 But catering to unusual cases should not slow the usual ones, so we just take
60 the last i bits anyway. It's up to collision resolution to do the rest. If
61 we *usually* find the key we're looking for on the first try (and, it turns
62 out, we usually do -- the table load factor is kept under 2/3, so the odds
63 are solidly in our favor), then it makes best sense to keep the initial index
64 computation dirt cheap.
66 The first half of collision resolution is to visit table indices via this
69 j = ((5*j) + 1) mod 2**i
71 For any initial j in range(2**i), repeating that 2**i times generates each
72 int in range(2**i) exactly once (see any text on random-number generation for
73 proof). By itself, this doesn't help much: like linear probing (setting
74 j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
75 order. This would be bad, except that's not the only thing we do, and it's
76 actually *good* in the common cases where hash keys are consecutive. In an
77 example that's really too small to make this entirely clear, for a table of
78 size 2**3 the order of indices is:
80 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
82 If two things come in at index 5, the first place we look after is index 2,
83 not 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
84 Linear probing is deadly in this case because there the fixed probe order
85 is the *same* as the order consecutive keys are likely to arrive. But it's
86 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
87 and certain that consecutive hash codes do not.
89 The other half of the strategy is to get the other bits of the hash code
90 into play. This is done by initializing a (unsigned) vrbl "perturb" to the
91 full hash code, and changing the recurrence to:
93 j = (5*j) + 1 + perturb;
94 perturb >>= PERTURB_SHIFT;
95 use j % 2**i as the next table index;
97 Now the probe sequence depends (eventually) on every bit in the hash code,
98 and the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
99 because it quickly magnifies small differences in the bits that didn't affect
100 the initial index. Note that because perturb is unsigned, if the recurrence
101 is executed often enough perturb eventually becomes and remains 0. At that
102 point (very rarely reached) the recurrence is on (just) 5*j+1 again, and
103 that's certain to find an empty slot eventually (since it generates every int
104 in range(2**i), and we make sure there's always at least one empty slot).
106 Selecting a good value for PERTURB_SHIFT is a balancing act. You want it
107 small so that the high bits of the hash code continue to affect the probe
108 sequence across iterations; but you want it large so that in really bad cases
109 the high-order hash bits have an effect on early iterations. 5 was "the
110 best" in minimizing total collisions across experiments Tim Peters ran (on
111 both normal and pathological cases), but 4 and 6 weren't significantly worse.
113 Historical: Reimer Behrends contributed the idea of using a polynomial-based
114 approach, using repeated multiplication by x in GF(2**n) where an irreducible
115 polynomial for each table size was chosen such that x was a primitive root.
116 Christian Tismer later extended that to use division by x instead, as an
117 efficient way to get the high bits of the hash code into play. This scheme
118 also gave excellent collision statistics, but was more expensive: two
119 if-tests were required inside the loop; computing "the next" index took about
120 the same number of operations but without as much potential parallelism
121 (e.g., computing 5*j can go on at the same time as computing 1+perturb in the
122 above, and then shifting perturb can be done while the table index is being
123 masked); and the PyDictObject struct required a member to hold the table's
124 polynomial. In Tim's experiments the current scheme ran faster, produced
125 equally good collision statistics, needed less code & used less memory.
127 Theoretical Python 2.5 headache: hash codes are only C "long", but
128 sizeof(Py_ssize_t) > sizeof(long) may be possible. In that case, and if a
129 dict is genuinely huge, then only the slots directly reachable via indexing
130 by a C long can be the first slot in a probe sequence. The probe sequence
131 will still eventually reach every slot in the table, but the collision rate
132 on initial probes may be much higher than this scheme was designed for.
133 Getting a hash code as fat as Py_ssize_t is the only real cure. But in
134 practice, this probably won't make a lick of difference for many years (at
135 which point everyone will have terabytes of RAM on 64-bit boxes).
138 /* Object used as dummy key to fill deleted entries */
139 static PyObject
*dummy
= NULL
; /* Initialized by first call to newPyDictObject() */
149 /* forward declarations */
151 lookdict_unicode(PyDictObject
*mp
, PyObject
*key
, long hash
);
153 #ifdef SHOW_CONVERSION_COUNTS
154 static long created
= 0L;
155 static long converted
= 0L;
160 fprintf(stderr
, "created %ld string dicts\n", created
);
161 fprintf(stderr
, "converted %ld to normal dicts\n", converted
);
162 fprintf(stderr
, "%.2f%% conversion rate\n", (100.0*converted
)/created
);
166 /* Debug statistic to compare allocations with reuse through the free list */
167 #undef SHOW_ALLOC_COUNT
168 #ifdef SHOW_ALLOC_COUNT
169 static size_t count_alloc
= 0;
170 static size_t count_reuse
= 0;
175 fprintf(stderr
, "Dict allocations: %" PY_FORMAT_SIZE_T
"d\n",
177 fprintf(stderr
, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
179 fprintf(stderr
, "%.2f%% reuse rate\n\n",
180 (100.0*count_reuse
/(count_alloc
+count_reuse
)));
184 /* Debug statistic to count GC tracking of dicts */
185 #ifdef SHOW_TRACK_COUNT
186 static Py_ssize_t count_untracked
= 0;
187 static Py_ssize_t count_tracked
= 0;
192 fprintf(stderr
, "Dicts created: %" PY_FORMAT_SIZE_T
"d\n",
193 count_tracked
+ count_untracked
);
194 fprintf(stderr
, "Dicts tracked by the GC: %" PY_FORMAT_SIZE_T
195 "d\n", count_tracked
);
196 fprintf(stderr
, "%.2f%% dict tracking rate\n\n",
197 (100.0*count_tracked
/(count_untracked
+count_tracked
)));
202 /* Initialization macros.
203 There are two ways to create a dict: PyDict_New() is the main C API
204 function, and the tp_new slot maps to dict_new(). In the latter case we
205 can save a little time over what PyDict_New does because it's guaranteed
206 that the PyDictObject struct is already zeroed out.
207 Everyone except dict_new() should use EMPTY_TO_MINSIZE (unless they have
208 an excellent reason not to).
211 #define INIT_NONZERO_DICT_SLOTS(mp) do { \
212 (mp)->ma_table = (mp)->ma_smalltable; \
213 (mp)->ma_mask = PyDict_MINSIZE - 1; \
216 #define EMPTY_TO_MINSIZE(mp) do { \
217 memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable)); \
218 (mp)->ma_used = (mp)->ma_fill = 0; \
219 INIT_NONZERO_DICT_SLOTS(mp); \
222 /* Dictionary reuse scheme to save calls to malloc, free, and memset */
223 #ifndef PyDict_MAXFREELIST
224 #define PyDict_MAXFREELIST 80
226 static PyDictObject
*free_list
[PyDict_MAXFREELIST
];
227 static int numfree
= 0;
235 op
= free_list
[--numfree
];
236 assert(PyDict_CheckExact(op
));
244 register PyDictObject
*mp
;
245 if (dummy
== NULL
) { /* Auto-initialize dummy */
246 dummy
= PyUnicode_FromString("<dummy key>");
249 #ifdef SHOW_CONVERSION_COUNTS
250 Py_AtExit(show_counts
);
252 #ifdef SHOW_ALLOC_COUNT
253 Py_AtExit(show_alloc
);
255 #ifdef SHOW_TRACK_COUNT
256 Py_AtExit(show_track
);
260 mp
= free_list
[--numfree
];
262 assert (Py_TYPE(mp
) == &PyDict_Type
);
263 _Py_NewReference((PyObject
*)mp
);
265 EMPTY_TO_MINSIZE(mp
);
267 /* At least set ma_table and ma_mask; these are wrong
268 if an empty but presized dict is added to freelist */
269 INIT_NONZERO_DICT_SLOTS(mp
);
271 assert (mp
->ma_used
== 0);
272 assert (mp
->ma_table
== mp
->ma_smalltable
);
273 assert (mp
->ma_mask
== PyDict_MINSIZE
- 1);
274 #ifdef SHOW_ALLOC_COUNT
278 mp
= PyObject_GC_New(PyDictObject
, &PyDict_Type
);
281 EMPTY_TO_MINSIZE(mp
);
282 #ifdef SHOW_ALLOC_COUNT
286 mp
->ma_lookup
= lookdict_unicode
;
287 #ifdef SHOW_TRACK_COUNT
290 #ifdef SHOW_CONVERSION_COUNTS
293 return (PyObject
*)mp
;
297 The basic lookup function used by all operations.
298 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
299 Open addressing is preferred over chaining since the link overhead for
300 chaining would be substantial (100% with typical malloc overhead).
302 The initial probe index is computed as hash mod the table size. Subsequent
303 probe indices are computed as explained earlier.
305 All arithmetic on hash should ignore overflow.
307 The details in this version are due to Tim Peters, building on many past
308 contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
311 lookdict() is general-purpose, and may return NULL if (and only if) a
312 comparison raises an exception (this was new in Python 2.5).
313 lookdict_unicode() below is specialized to string keys, comparison of which can
314 never raise an exception; that function can never return NULL. For both, when
315 the key isn't found a PyDictEntry* is returned for which the me_value field is
316 NULL; this is the slot in the dict at which the key would have been found, and
317 the caller can (if it wishes) add the <key, value> pair to the returned
321 lookdict(PyDictObject
*mp
, PyObject
*key
, register long hash
)
324 register size_t perturb
;
325 register PyDictEntry
*freeslot
;
326 register size_t mask
= (size_t)mp
->ma_mask
;
327 PyDictEntry
*ep0
= mp
->ma_table
;
328 register PyDictEntry
*ep
;
332 i
= (size_t)hash
& mask
;
334 if (ep
->me_key
== NULL
|| ep
->me_key
== key
)
337 if (ep
->me_key
== dummy
)
340 if (ep
->me_hash
== hash
) {
341 startkey
= ep
->me_key
;
343 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
347 if (ep0
== mp
->ma_table
&& ep
->me_key
== startkey
) {
352 /* The compare did major nasty stuff to the
354 * XXX A clever adversary could prevent this
355 * XXX from terminating.
357 return lookdict(mp
, key
, hash
);
363 /* In the loop, me_key == dummy is by far (factor of 100s) the
364 least likely outcome, so test for that last. */
365 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
366 i
= (i
<< 2) + i
+ perturb
+ 1;
368 if (ep
->me_key
== NULL
)
369 return freeslot
== NULL
? ep
: freeslot
;
370 if (ep
->me_key
== key
)
372 if (ep
->me_hash
== hash
&& ep
->me_key
!= dummy
) {
373 startkey
= ep
->me_key
;
375 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
379 if (ep0
== mp
->ma_table
&& ep
->me_key
== startkey
) {
384 /* The compare did major nasty stuff to the
386 * XXX A clever adversary could prevent this
387 * XXX from terminating.
389 return lookdict(mp
, key
, hash
);
392 else if (ep
->me_key
== dummy
&& freeslot
== NULL
)
395 assert(0); /* NOT REACHED */
400 * Hacked up version of lookdict which can assume keys are always
401 * unicodes; this assumption allows testing for errors during
402 * PyObject_RichCompareBool() to be dropped; unicode-unicode
403 * comparisons never raise exceptions. This also means we don't need
404 * to go through PyObject_RichCompareBool(); we can always use
405 * unicode_eq() directly.
407 * This is valuable because dicts with only unicode keys are very common.
410 lookdict_unicode(PyDictObject
*mp
, PyObject
*key
, register long hash
)
413 register size_t perturb
;
414 register PyDictEntry
*freeslot
;
415 register size_t mask
= (size_t)mp
->ma_mask
;
416 PyDictEntry
*ep0
= mp
->ma_table
;
417 register PyDictEntry
*ep
;
419 /* Make sure this function doesn't have to handle non-unicode keys,
420 including subclasses of str; e.g., one reason to subclass
421 unicodes is to override __eq__, and for speed we don't cater to
423 if (!PyUnicode_CheckExact(key
)) {
424 #ifdef SHOW_CONVERSION_COUNTS
427 mp
->ma_lookup
= lookdict
;
428 return lookdict(mp
, key
, hash
);
432 if (ep
->me_key
== NULL
|| ep
->me_key
== key
)
434 if (ep
->me_key
== dummy
)
437 if (ep
->me_hash
== hash
&& unicode_eq(ep
->me_key
, key
))
442 /* In the loop, me_key == dummy is by far (factor of 100s) the
443 least likely outcome, so test for that last. */
444 for (perturb
= hash
; ; perturb
>>= PERTURB_SHIFT
) {
445 i
= (i
<< 2) + i
+ perturb
+ 1;
447 if (ep
->me_key
== NULL
)
448 return freeslot
== NULL
? ep
: freeslot
;
449 if (ep
->me_key
== key
450 || (ep
->me_hash
== hash
451 && ep
->me_key
!= dummy
452 && unicode_eq(ep
->me_key
, key
)))
454 if (ep
->me_key
== dummy
&& freeslot
== NULL
)
457 assert(0); /* NOT REACHED */
461 #ifdef SHOW_TRACK_COUNT
462 #define INCREASE_TRACK_COUNT \
463 (count_tracked++, count_untracked--);
464 #define DECREASE_TRACK_COUNT \
465 (count_tracked--, count_untracked++);
467 #define INCREASE_TRACK_COUNT
468 #define DECREASE_TRACK_COUNT
471 #define MAINTAIN_TRACKING(mp, key, value) \
473 if (!_PyObject_GC_IS_TRACKED(mp)) { \
474 if (_PyObject_GC_MAY_BE_TRACKED(key) || \
475 _PyObject_GC_MAY_BE_TRACKED(value)) { \
476 _PyObject_GC_TRACK(mp); \
477 INCREASE_TRACK_COUNT \
483 _PyDict_MaybeUntrack(PyObject
*op
)
490 if (!PyDict_CheckExact(op
) || !_PyObject_GC_IS_TRACKED(op
))
493 mp
= (PyDictObject
*) op
;
496 for (i
= 0; i
<= mask
; i
++) {
497 if ((value
= ep
[i
].me_value
) == NULL
)
499 if (_PyObject_GC_MAY_BE_TRACKED(value
) ||
500 _PyObject_GC_MAY_BE_TRACKED(ep
[i
].me_key
))
504 _PyObject_GC_UNTRACK(op
);
509 Internal routine to insert a new item into the table.
510 Used both by the internal resize routine and by the public insert routine.
511 Eats a reference to key and one to value.
512 Returns -1 if an error occurred, or 0 on success.
515 insertdict(register PyDictObject
*mp
, PyObject
*key
, long hash
, PyObject
*value
)
518 register PyDictEntry
*ep
;
519 typedef PyDictEntry
*(*lookupfunc
)(PyDictObject
*, PyObject
*, long);
521 assert(mp
->ma_lookup
!= NULL
);
522 ep
= mp
->ma_lookup(mp
, key
, hash
);
528 MAINTAIN_TRACKING(mp
, key
, value
);
529 if (ep
->me_value
!= NULL
) {
530 old_value
= ep
->me_value
;
531 ep
->me_value
= value
;
532 Py_DECREF(old_value
); /* which **CAN** re-enter */
536 if (ep
->me_key
== NULL
)
539 assert(ep
->me_key
== dummy
);
543 ep
->me_hash
= (Py_ssize_t
)hash
;
544 ep
->me_value
= value
;
551 Internal routine used by dictresize() to insert an item which is
552 known to be absent from the dict. This routine also assumes that
553 the dict contains no deleted entries. Besides the performance benefit,
554 using insertdict() in dictresize() is dangerous (SF bug #1456209).
555 Note that no refcounts are changed by this routine; if needed, the caller
556 is responsible for incref'ing `key` and `value`.
559 insertdict_clean(register PyDictObject
*mp
, PyObject
*key
, long hash
,
563 register size_t perturb
;
564 register size_t mask
= (size_t)mp
->ma_mask
;
565 PyDictEntry
*ep0
= mp
->ma_table
;
566 register PyDictEntry
*ep
;
568 MAINTAIN_TRACKING(mp
, key
, value
);
571 for (perturb
= hash
; ep
->me_key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
572 i
= (i
<< 2) + i
+ perturb
+ 1;
575 assert(ep
->me_value
== NULL
);
578 ep
->me_hash
= (Py_ssize_t
)hash
;
579 ep
->me_value
= value
;
584 Restructure the table by allocating a new table and reinserting all
585 items again. When entries have been deleted, the new table may
586 actually be smaller than the old one.
589 dictresize(PyDictObject
*mp
, Py_ssize_t minused
)
592 PyDictEntry
*oldtable
, *newtable
, *ep
;
594 int is_oldtable_malloced
;
595 PyDictEntry small_copy
[PyDict_MINSIZE
];
597 assert(minused
>= 0);
599 /* Find the smallest table size > minused. */
600 for (newsize
= PyDict_MINSIZE
;
601 newsize
<= minused
&& newsize
> 0;
609 /* Get space for a new table. */
610 oldtable
= mp
->ma_table
;
611 assert(oldtable
!= NULL
);
612 is_oldtable_malloced
= oldtable
!= mp
->ma_smalltable
;
614 if (newsize
== PyDict_MINSIZE
) {
615 /* A large table is shrinking, or we can't get any smaller. */
616 newtable
= mp
->ma_smalltable
;
617 if (newtable
== oldtable
) {
618 if (mp
->ma_fill
== mp
->ma_used
) {
619 /* No dummies, so no point doing anything. */
622 /* We're not going to resize it, but rebuild the
623 table anyway to purge old dummy entries.
624 Subtle: This is *necessary* if fill==size,
625 as lookdict needs at least one virgin slot to
626 terminate failing searches. If fill < size, it's
627 merely desirable, as dummies slow searches. */
628 assert(mp
->ma_fill
> mp
->ma_used
);
629 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
630 oldtable
= small_copy
;
634 newtable
= PyMem_NEW(PyDictEntry
, newsize
);
635 if (newtable
== NULL
) {
641 /* Make the dict empty, using the new table. */
642 assert(newtable
!= oldtable
);
643 mp
->ma_table
= newtable
;
644 mp
->ma_mask
= newsize
- 1;
645 memset(newtable
, 0, sizeof(PyDictEntry
) * newsize
);
650 /* Copy the data over; this is refcount-neutral for active entries;
651 dummy entries aren't copied over, of course */
652 for (ep
= oldtable
; i
> 0; ep
++) {
653 if (ep
->me_value
!= NULL
) { /* active entry */
655 insertdict_clean(mp
, ep
->me_key
, (long)ep
->me_hash
,
658 else if (ep
->me_key
!= NULL
) { /* dummy entry */
660 assert(ep
->me_key
== dummy
);
661 Py_DECREF(ep
->me_key
);
663 /* else key == value == NULL: nothing to do */
666 if (is_oldtable_malloced
)
671 /* Create a new dictionary pre-sized to hold an estimated number of elements.
672 Underestimates are okay because the dictionary will resize as necessary.
673 Overestimates just mean the dictionary will be more sparse than usual.
677 _PyDict_NewPresized(Py_ssize_t minused
)
679 PyObject
*op
= PyDict_New();
681 if (minused
>5 && op
!= NULL
&& dictresize((PyDictObject
*)op
, minused
) == -1) {
688 /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
689 * that may occur (originally dicts supported only string keys, and exceptions
690 * weren't possible). So, while the original intent was that a NULL return
691 * meant the key wasn't present, in reality it can mean that, or that an error
692 * (suppressed) occurred while computing the key's hash, or that some error
693 * (suppressed) occurred when comparing keys in the dict's internal probe
694 * sequence. A nasty example of the latter is when a Python-coded comparison
695 * function hits a stack-depth error, which can cause this to return NULL
696 * even if the key is present.
699 PyDict_GetItem(PyObject
*op
, PyObject
*key
)
702 PyDictObject
*mp
= (PyDictObject
*)op
;
704 PyThreadState
*tstate
;
705 if (!PyDict_Check(op
))
707 if (!PyUnicode_CheckExact(key
) ||
708 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1)
710 hash
= PyObject_Hash(key
);
717 /* We can arrive here with a NULL tstate during initialization: try
718 running "python -Wi" for an example related to string interning.
719 Let's just hope that no exception occurs then... This must be
720 _PyThreadState_Current and not PyThreadState_GET() because in debug
721 mode, the latter complains if tstate is NULL. */
722 tstate
= _PyThreadState_Current
;
723 if (tstate
!= NULL
&& tstate
->curexc_type
!= NULL
) {
724 /* preserve the existing exception */
725 PyObject
*err_type
, *err_value
, *err_tb
;
726 PyErr_Fetch(&err_type
, &err_value
, &err_tb
);
727 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
729 PyErr_Restore(err_type
, err_value
, err_tb
);
734 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
743 /* Variant of PyDict_GetItem() that doesn't suppress exceptions.
744 This returns NULL *with* an exception set if an exception occurred.
745 It returns NULL *without* an exception set if the key wasn't present.
748 PyDict_GetItemWithError(PyObject
*op
, PyObject
*key
)
751 PyDictObject
*mp
= (PyDictObject
*)op
;
754 if (!PyDict_Check(op
)) {
755 PyErr_BadInternalCall();
758 if (!PyUnicode_CheckExact(key
) ||
759 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1)
761 hash
= PyObject_Hash(key
);
767 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
773 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
774 * dictionary if it's merely replacing the value for an existing key.
775 * This means that it's safe to loop over a dictionary with PyDict_Next()
776 * and occasionally replace a value -- but you can't insert new keys or
780 PyDict_SetItem(register PyObject
*op
, PyObject
*key
, PyObject
*value
)
782 register PyDictObject
*mp
;
784 register Py_ssize_t n_used
;
786 if (!PyDict_Check(op
)) {
787 PyErr_BadInternalCall();
792 mp
= (PyDictObject
*)op
;
793 if (!PyUnicode_CheckExact(key
) ||
794 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1)
796 hash
= PyObject_Hash(key
);
800 assert(mp
->ma_fill
<= mp
->ma_mask
); /* at least one empty slot */
801 n_used
= mp
->ma_used
;
804 if (insertdict(mp
, key
, hash
, value
) != 0)
806 /* If we added a key, we can safely resize. Otherwise just return!
807 * If fill >= 2/3 size, adjust size. Normally, this doubles or
808 * quaduples the size, but it's also possible for the dict to shrink
809 * (if ma_fill is much larger than ma_used, meaning a lot of dict
810 * keys have been * deleted).
812 * Quadrupling the size improves average dictionary sparseness
813 * (reducing collisions) at the cost of some memory and iteration
814 * speed (which loops over every possible entry). It also halves
815 * the number of expensive resize operations in a growing dictionary.
817 * Very large dictionaries (over 50K items) use doubling instead.
818 * This may help applications with severe memory constraints.
820 if (!(mp
->ma_used
> n_used
&& mp
->ma_fill
*3 >= (mp
->ma_mask
+1)*2))
822 return dictresize(mp
, (mp
->ma_used
> 50000 ? 2 : 4) * mp
->ma_used
);
826 PyDict_DelItem(PyObject
*op
, PyObject
*key
)
828 register PyDictObject
*mp
;
830 register PyDictEntry
*ep
;
831 PyObject
*old_value
, *old_key
;
833 if (!PyDict_Check(op
)) {
834 PyErr_BadInternalCall();
838 if (!PyUnicode_CheckExact(key
) ||
839 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
840 hash
= PyObject_Hash(key
);
844 mp
= (PyDictObject
*)op
;
845 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
848 if (ep
->me_value
== NULL
) {
852 old_key
= ep
->me_key
;
855 old_value
= ep
->me_value
;
858 Py_DECREF(old_value
);
864 PyDict_Clear(PyObject
*op
)
867 PyDictEntry
*ep
, *table
;
868 int table_is_malloced
;
870 PyDictEntry small_copy
[PyDict_MINSIZE
];
875 if (!PyDict_Check(op
))
877 mp
= (PyDictObject
*)op
;
883 table
= mp
->ma_table
;
884 assert(table
!= NULL
);
885 table_is_malloced
= table
!= mp
->ma_smalltable
;
887 /* This is delicate. During the process of clearing the dict,
888 * decrefs can cause the dict to mutate. To avoid fatal confusion
889 * (voice of experience), we have to make the dict empty before
890 * clearing the slots, and never refer to anything via mp->xxx while
894 if (table_is_malloced
)
895 EMPTY_TO_MINSIZE(mp
);
898 /* It's a small table with something that needs to be cleared.
899 * Afraid the only safe way is to copy the dict entries into
900 * another small table first.
902 memcpy(small_copy
, table
, sizeof(small_copy
));
904 EMPTY_TO_MINSIZE(mp
);
906 /* else it's a small table that's already empty */
908 /* Now we can finally clear things. If C had refcounts, we could
909 * assert that the refcount on table is 1 now, i.e. that this function
910 * has unique access to it, so decref side-effects can't alter it.
912 for (ep
= table
; fill
> 0; ++ep
) {
919 Py_DECREF(ep
->me_key
);
920 Py_XDECREF(ep
->me_value
);
924 assert(ep
->me_value
== NULL
);
928 if (table_is_malloced
)
933 * Iterate over a dict. Use like so:
936 * PyObject *key, *value;
937 * i = 0; # important! i should not otherwise be changed by you
938 * while (PyDict_Next(yourdict, &i, &key, &value)) {
939 * Refer to borrowed references in key and value.
942 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
943 * mutates the dict. One exception: it is safe if the loop merely changes
944 * the values associated with the keys (but doesn't insert new keys or
945 * delete keys), via PyDict_SetItem().
948 PyDict_Next(PyObject
*op
, Py_ssize_t
*ppos
, PyObject
**pkey
, PyObject
**pvalue
)
950 register Py_ssize_t i
;
951 register Py_ssize_t mask
;
952 register PyDictEntry
*ep
;
954 if (!PyDict_Check(op
))
959 ep
= ((PyDictObject
*)op
)->ma_table
;
960 mask
= ((PyDictObject
*)op
)->ma_mask
;
961 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
967 *pkey
= ep
[i
].me_key
;
969 *pvalue
= ep
[i
].me_value
;
973 /* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
975 _PyDict_Next(PyObject
*op
, Py_ssize_t
*ppos
, PyObject
**pkey
, PyObject
**pvalue
, long *phash
)
977 register Py_ssize_t i
;
978 register Py_ssize_t mask
;
979 register PyDictEntry
*ep
;
981 if (!PyDict_Check(op
))
986 ep
= ((PyDictObject
*)op
)->ma_table
;
987 mask
= ((PyDictObject
*)op
)->ma_mask
;
988 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
993 *phash
= (long)(ep
[i
].me_hash
);
995 *pkey
= ep
[i
].me_key
;
997 *pvalue
= ep
[i
].me_value
;
1004 dict_dealloc(register PyDictObject
*mp
)
1006 register PyDictEntry
*ep
;
1007 Py_ssize_t fill
= mp
->ma_fill
;
1008 PyObject_GC_UnTrack(mp
);
1009 Py_TRASHCAN_SAFE_BEGIN(mp
)
1010 for (ep
= mp
->ma_table
; fill
> 0; ep
++) {
1013 Py_DECREF(ep
->me_key
);
1014 Py_XDECREF(ep
->me_value
);
1017 if (mp
->ma_table
!= mp
->ma_smalltable
)
1018 PyMem_DEL(mp
->ma_table
);
1019 if (numfree
< PyDict_MAXFREELIST
&& Py_TYPE(mp
) == &PyDict_Type
)
1020 free_list
[numfree
++] = mp
;
1022 Py_TYPE(mp
)->tp_free((PyObject
*)mp
);
1023 Py_TRASHCAN_SAFE_END(mp
)
1027 dict_repr(PyDictObject
*mp
)
1030 PyObject
*s
, *temp
, *colon
= NULL
;
1031 PyObject
*pieces
= NULL
, *result
= NULL
;
1032 PyObject
*key
, *value
;
1034 i
= Py_ReprEnter((PyObject
*)mp
);
1036 return i
> 0 ? PyUnicode_FromString("{...}") : NULL
;
1039 if (mp
->ma_used
== 0) {
1040 result
= PyUnicode_FromString("{}");
1044 pieces
= PyList_New(0);
1048 colon
= PyUnicode_FromString(": ");
1052 /* Do repr() on each key+value pair, and insert ": " between them.
1053 Note that repr may mutate the dict. */
1055 while (PyDict_Next((PyObject
*)mp
, &i
, &key
, &value
)) {
1057 /* Prevent repr from deleting value during key format. */
1059 s
= PyObject_Repr(key
);
1060 PyUnicode_Append(&s
, colon
);
1061 PyUnicode_AppendAndDel(&s
, PyObject_Repr(value
));
1065 status
= PyList_Append(pieces
, s
);
1066 Py_DECREF(s
); /* append created a new ref */
1071 /* Add "{}" decorations to the first and last items. */
1072 assert(PyList_GET_SIZE(pieces
) > 0);
1073 s
= PyUnicode_FromString("{");
1076 temp
= PyList_GET_ITEM(pieces
, 0);
1077 PyUnicode_AppendAndDel(&s
, temp
);
1078 PyList_SET_ITEM(pieces
, 0, s
);
1082 s
= PyUnicode_FromString("}");
1085 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
1086 PyUnicode_AppendAndDel(&temp
, s
);
1087 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
1091 /* Paste them all together with ", " between. */
1092 s
= PyUnicode_FromString(", ");
1095 result
= PyUnicode_Join(s
, pieces
);
1101 Py_ReprLeave((PyObject
*)mp
);
1106 dict_length(PyDictObject
*mp
)
1112 dict_subscript(PyDictObject
*mp
, register PyObject
*key
)
1117 assert(mp
->ma_table
!= NULL
);
1118 if (!PyUnicode_CheckExact(key
) ||
1119 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
1120 hash
= PyObject_Hash(key
);
1124 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1129 if (!PyDict_CheckExact(mp
)) {
1130 /* Look up __missing__ method if we're a subclass. */
1131 PyObject
*missing
, *res
;
1132 static PyObject
*missing_str
= NULL
;
1133 missing
= _PyObject_LookupSpecial((PyObject
*)mp
,
1136 if (missing
!= NULL
) {
1137 res
= PyObject_CallFunctionObjArgs(missing
,
1142 else if (PyErr_Occurred())
1154 dict_ass_sub(PyDictObject
*mp
, PyObject
*v
, PyObject
*w
)
1157 return PyDict_DelItem((PyObject
*)mp
, v
);
1159 return PyDict_SetItem((PyObject
*)mp
, v
, w
);
1162 static PyMappingMethods dict_as_mapping
= {
1163 (lenfunc
)dict_length
, /*mp_length*/
1164 (binaryfunc
)dict_subscript
, /*mp_subscript*/
1165 (objobjargproc
)dict_ass_sub
, /*mp_ass_subscript*/
1169 dict_keys(register PyDictObject
*mp
)
1171 register PyObject
*v
;
1172 register Py_ssize_t i
, j
;
1181 if (n
!= mp
->ma_used
) {
1182 /* Durnit. The allocations caused the dict to resize.
1183 * Just start over, this shouldn't normally happen.
1190 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1191 if (ep
[i
].me_value
!= NULL
) {
1192 PyObject
*key
= ep
[i
].me_key
;
1194 PyList_SET_ITEM(v
, j
, key
);
1203 dict_values(register PyDictObject
*mp
)
1205 register PyObject
*v
;
1206 register Py_ssize_t i
, j
;
1215 if (n
!= mp
->ma_used
) {
1216 /* Durnit. The allocations caused the dict to resize.
1217 * Just start over, this shouldn't normally happen.
1224 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1225 if (ep
[i
].me_value
!= NULL
) {
1226 PyObject
*value
= ep
[i
].me_value
;
1228 PyList_SET_ITEM(v
, j
, value
);
1237 dict_items(register PyDictObject
*mp
)
1239 register PyObject
*v
;
1240 register Py_ssize_t i
, j
, n
;
1242 PyObject
*item
, *key
, *value
;
1245 /* Preallocate the list of tuples, to avoid allocations during
1246 * the loop over the items, which could trigger GC, which
1247 * could resize the dict. :-(
1254 for (i
= 0; i
< n
; i
++) {
1255 item
= PyTuple_New(2);
1260 PyList_SET_ITEM(v
, i
, item
);
1262 if (n
!= mp
->ma_used
) {
1263 /* Durnit. The allocations caused the dict to resize.
1264 * Just start over, this shouldn't normally happen.
1269 /* Nothing we do below makes any function calls. */
1272 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1273 if ((value
=ep
[i
].me_value
) != NULL
) {
1275 item
= PyList_GET_ITEM(v
, j
);
1277 PyTuple_SET_ITEM(item
, 0, key
);
1279 PyTuple_SET_ITEM(item
, 1, value
);
1288 dict_fromkeys(PyObject
*cls
, PyObject
*args
)
1291 PyObject
*value
= Py_None
;
1292 PyObject
*it
; /* iter(seq) */
1297 if (!PyArg_UnpackTuple(args
, "fromkeys", 1, 2, &seq
, &value
))
1300 d
= PyObject_CallObject(cls
, NULL
);
1304 if (PyDict_CheckExact(d
) && PyDict_CheckExact(seq
)) {
1305 PyDictObject
*mp
= (PyDictObject
*)d
;
1311 if (dictresize(mp
, Py_SIZE(seq
)))
1314 while (_PyDict_Next(seq
, &pos
, &key
, &oldvalue
, &hash
)) {
1317 if (insertdict(mp
, key
, hash
, value
))
1323 if (PyDict_CheckExact(d
) && PyAnySet_CheckExact(seq
)) {
1324 PyDictObject
*mp
= (PyDictObject
*)d
;
1329 if (dictresize(mp
, PySet_GET_SIZE(seq
)))
1332 while (_PySet_NextEntry(seq
, &pos
, &key
, &hash
)) {
1335 if (insertdict(mp
, key
, hash
, value
))
1341 it
= PyObject_GetIter(seq
);
1347 if (PyDict_CheckExact(d
)) {
1348 while ((key
= PyIter_Next(it
)) != NULL
) {
1349 status
= PyDict_SetItem(d
, key
, value
);
1355 while ((key
= PyIter_Next(it
)) != NULL
) {
1356 status
= PyObject_SetItem(d
, key
, value
);
1363 if (PyErr_Occurred())
1375 dict_update_common(PyObject
*self
, PyObject
*args
, PyObject
*kwds
, char *methname
)
1377 PyObject
*arg
= NULL
;
1380 if (!PyArg_UnpackTuple(args
, methname
, 0, 1, &arg
))
1383 else if (arg
!= NULL
) {
1384 if (PyObject_HasAttrString(arg
, "keys"))
1385 result
= PyDict_Merge(self
, arg
, 1);
1387 result
= PyDict_MergeFromSeq2(self
, arg
, 1);
1389 if (result
== 0 && kwds
!= NULL
)
1390 result
= PyDict_Merge(self
, kwds
, 1);
1395 dict_update(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
1397 if (dict_update_common(self
, args
, kwds
, "update") != -1)
1402 /* Update unconditionally replaces existing items.
1403 Merge has a 3rd argument 'override'; if set, it acts like Update,
1404 otherwise it leaves existing items unchanged.
1406 PyDict_{Update,Merge} update/merge from a mapping object.
1408 PyDict_MergeFromSeq2 updates/merges from any iterable object
1409 producing iterable objects of length 2.
1413 PyDict_MergeFromSeq2(PyObject
*d
, PyObject
*seq2
, int override
)
1415 PyObject
*it
; /* iter(seq2) */
1416 Py_ssize_t i
; /* index into seq2 of current element */
1417 PyObject
*item
; /* seq2[i] */
1418 PyObject
*fast
; /* item as a 2-tuple or 2-list */
1421 assert(PyDict_Check(d
));
1422 assert(seq2
!= NULL
);
1424 it
= PyObject_GetIter(seq2
);
1428 for (i
= 0; ; ++i
) {
1429 PyObject
*key
, *value
;
1433 item
= PyIter_Next(it
);
1435 if (PyErr_Occurred())
1440 /* Convert item to sequence, and verify length 2. */
1441 fast
= PySequence_Fast(item
, "");
1443 if (PyErr_ExceptionMatches(PyExc_TypeError
))
1444 PyErr_Format(PyExc_TypeError
,
1445 "cannot convert dictionary update "
1446 "sequence element #%zd to a sequence",
1450 n
= PySequence_Fast_GET_SIZE(fast
);
1452 PyErr_Format(PyExc_ValueError
,
1453 "dictionary update sequence element #%zd "
1454 "has length %zd; 2 is required",
1459 /* Update/merge with this (key, value) pair. */
1460 key
= PySequence_Fast_GET_ITEM(fast
, 0);
1461 value
= PySequence_Fast_GET_ITEM(fast
, 1);
1462 if (override
|| PyDict_GetItem(d
, key
) == NULL
) {
1463 int status
= PyDict_SetItem(d
, key
, value
);
1479 return Py_SAFE_DOWNCAST(i
, Py_ssize_t
, int);
1483 PyDict_Update(PyObject
*a
, PyObject
*b
)
1485 return PyDict_Merge(a
, b
, 1);
1489 PyDict_Merge(PyObject
*a
, PyObject
*b
, int override
)
1491 register PyDictObject
*mp
, *other
;
1492 register Py_ssize_t i
;
1495 /* We accept for the argument either a concrete dictionary object,
1496 * or an abstract "mapping" object. For the former, we can do
1497 * things quite efficiently. For the latter, we only require that
1498 * PyMapping_Keys() and PyObject_GetItem() be supported.
1500 if (a
== NULL
|| !PyDict_Check(a
) || b
== NULL
) {
1501 PyErr_BadInternalCall();
1504 mp
= (PyDictObject
*)a
;
1505 if (PyDict_Check(b
)) {
1506 other
= (PyDictObject
*)b
;
1507 if (other
== mp
|| other
->ma_used
== 0)
1508 /* a.update(a) or a.update({}); nothing to do */
1510 if (mp
->ma_used
== 0)
1511 /* Since the target dict is empty, PyDict_GetItem()
1512 * always returns NULL. Setting override to 1
1513 * skips the unnecessary test.
1516 /* Do one big resize at the start, rather than
1517 * incrementally resizing as we insert new items. Expect
1518 * that there will be no (or few) overlapping keys.
1520 if ((mp
->ma_fill
+ other
->ma_used
)*3 >= (mp
->ma_mask
+1)*2) {
1521 if (dictresize(mp
, (mp
->ma_used
+ other
->ma_used
)*2) != 0)
1524 for (i
= 0; i
<= other
->ma_mask
; i
++) {
1525 entry
= &other
->ma_table
[i
];
1526 if (entry
->me_value
!= NULL
&&
1528 PyDict_GetItem(a
, entry
->me_key
) == NULL
)) {
1529 Py_INCREF(entry
->me_key
);
1530 Py_INCREF(entry
->me_value
);
1531 if (insertdict(mp
, entry
->me_key
,
1532 (long)entry
->me_hash
,
1533 entry
->me_value
) != 0)
1539 /* Do it the generic, slower way */
1540 PyObject
*keys
= PyMapping_Keys(b
);
1542 PyObject
*key
, *value
;
1546 /* Docstring says this is equivalent to E.keys() so
1547 * if E doesn't have a .keys() method we want
1548 * AttributeError to percolate up. Might as well
1549 * do the same for any other error.
1553 iter
= PyObject_GetIter(keys
);
1558 for (key
= PyIter_Next(iter
); key
; key
= PyIter_Next(iter
)) {
1559 if (!override
&& PyDict_GetItem(a
, key
) != NULL
) {
1563 value
= PyObject_GetItem(b
, key
);
1564 if (value
== NULL
) {
1569 status
= PyDict_SetItem(a
, key
, value
);
1578 if (PyErr_Occurred())
1579 /* Iterator completed, via error */
1586 dict_copy(register PyDictObject
*mp
)
1588 return PyDict_Copy((PyObject
*)mp
);
1592 PyDict_Copy(PyObject
*o
)
1596 if (o
== NULL
|| !PyDict_Check(o
)) {
1597 PyErr_BadInternalCall();
1600 copy
= PyDict_New();
1603 if (PyDict_Merge(copy
, o
, 1) == 0)
1610 PyDict_Size(PyObject
*mp
)
1612 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1613 PyErr_BadInternalCall();
1616 return ((PyDictObject
*)mp
)->ma_used
;
1620 PyDict_Keys(PyObject
*mp
)
1622 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1623 PyErr_BadInternalCall();
1626 return dict_keys((PyDictObject
*)mp
);
1630 PyDict_Values(PyObject
*mp
)
1632 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1633 PyErr_BadInternalCall();
1636 return dict_values((PyDictObject
*)mp
);
1640 PyDict_Items(PyObject
*mp
)
1642 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1643 PyErr_BadInternalCall();
1646 return dict_items((PyDictObject
*)mp
);
1649 /* Return 1 if dicts equal, 0 if not, -1 if error.
1650 * Gets out as soon as any difference is detected.
1651 * Uses only Py_EQ comparison.
1654 dict_equal(PyDictObject
*a
, PyDictObject
*b
)
1658 if (a
->ma_used
!= b
->ma_used
)
1659 /* can't be equal if # of entries differ */
1662 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1663 for (i
= 0; i
<= a
->ma_mask
; i
++) {
1664 PyObject
*aval
= a
->ma_table
[i
].me_value
;
1668 PyObject
*key
= a
->ma_table
[i
].me_key
;
1669 /* temporarily bump aval's refcount to ensure it stays
1670 alive until we're done with it */
1674 bval
= PyDict_GetItemWithError((PyObject
*)b
, key
);
1678 if (PyErr_Occurred())
1682 cmp
= PyObject_RichCompareBool(aval
, bval
, Py_EQ
);
1684 if (cmp
<= 0) /* error or not equal */
1692 dict_richcompare(PyObject
*v
, PyObject
*w
, int op
)
1697 if (!PyDict_Check(v
) || !PyDict_Check(w
)) {
1698 res
= Py_NotImplemented
;
1700 else if (op
== Py_EQ
|| op
== Py_NE
) {
1701 cmp
= dict_equal((PyDictObject
*)v
, (PyDictObject
*)w
);
1704 res
= (cmp
== (op
== Py_EQ
)) ? Py_True
: Py_False
;
1707 res
= Py_NotImplemented
;
1713 dict_contains(register PyDictObject
*mp
, PyObject
*key
)
1718 if (!PyUnicode_CheckExact(key
) ||
1719 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
1720 hash
= PyObject_Hash(key
);
1724 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1727 return PyBool_FromLong(ep
->me_value
!= NULL
);
1731 dict_get(register PyDictObject
*mp
, PyObject
*args
)
1734 PyObject
*failobj
= Py_None
;
1735 PyObject
*val
= NULL
;
1739 if (!PyArg_UnpackTuple(args
, "get", 1, 2, &key
, &failobj
))
1742 if (!PyUnicode_CheckExact(key
) ||
1743 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
1744 hash
= PyObject_Hash(key
);
1748 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1760 dict_setdefault(register PyDictObject
*mp
, PyObject
*args
)
1763 PyObject
*failobj
= Py_None
;
1764 PyObject
*val
= NULL
;
1768 if (!PyArg_UnpackTuple(args
, "setdefault", 1, 2, &key
, &failobj
))
1771 if (!PyUnicode_CheckExact(key
) ||
1772 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
1773 hash
= PyObject_Hash(key
);
1777 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1783 if (PyDict_SetItem((PyObject
*)mp
, key
, failobj
))
1792 dict_clear(register PyDictObject
*mp
)
1794 PyDict_Clear((PyObject
*)mp
);
1799 dict_pop(PyDictObject
*mp
, PyObject
*args
)
1803 PyObject
*old_value
, *old_key
;
1804 PyObject
*key
, *deflt
= NULL
;
1806 if(!PyArg_UnpackTuple(args
, "pop", 1, 2, &key
, &deflt
))
1808 if (mp
->ma_used
== 0) {
1813 PyErr_SetString(PyExc_KeyError
,
1814 "pop(): dictionary is empty");
1817 if (!PyUnicode_CheckExact(key
) ||
1818 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
1819 hash
= PyObject_Hash(key
);
1823 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1826 if (ep
->me_value
== NULL
) {
1834 old_key
= ep
->me_key
;
1837 old_value
= ep
->me_value
;
1838 ep
->me_value
= NULL
;
1845 dict_popitem(PyDictObject
*mp
)
1851 /* Allocate the result tuple before checking the size. Believe it
1852 * or not, this allocation could trigger a garbage collection which
1853 * could empty the dict, so if we checked the size first and that
1854 * happened, the result would be an infinite loop (searching for an
1855 * entry that no longer exists). Note that the usual popitem()
1856 * idiom is "while d: k, v = d.popitem()". so needing to throw the
1857 * tuple away if the dict *is* empty isn't a significant
1858 * inefficiency -- possible, but unlikely in practice.
1860 res
= PyTuple_New(2);
1863 if (mp
->ma_used
== 0) {
1865 PyErr_SetString(PyExc_KeyError
,
1866 "popitem(): dictionary is empty");
1869 /* Set ep to "the first" dict entry with a value. We abuse the hash
1870 * field of slot 0 to hold a search finger:
1871 * If slot 0 has a value, use slot 0.
1872 * Else slot 0 is being used to hold a search finger,
1873 * and we use its hash value as the first index to look.
1875 ep
= &mp
->ma_table
[0];
1876 if (ep
->me_value
== NULL
) {
1878 /* The hash field may be a real hash value, or it may be a
1879 * legit search finger, or it may be a once-legit search
1880 * finger that's out of bounds now because it wrapped around
1881 * or the table shrunk -- simply make sure it's in bounds now.
1883 if (i
> mp
->ma_mask
|| i
< 1)
1884 i
= 1; /* skip slot 0 */
1885 while ((ep
= &mp
->ma_table
[i
])->me_value
== NULL
) {
1887 if (i
> mp
->ma_mask
)
1891 PyTuple_SET_ITEM(res
, 0, ep
->me_key
);
1892 PyTuple_SET_ITEM(res
, 1, ep
->me_value
);
1895 ep
->me_value
= NULL
;
1897 assert(mp
->ma_table
[0].me_value
== NULL
);
1898 mp
->ma_table
[0].me_hash
= i
+ 1; /* next place to start */
1903 dict_traverse(PyObject
*op
, visitproc visit
, void *arg
)
1909 while (PyDict_Next(op
, &i
, &pk
, &pv
)) {
1917 dict_tp_clear(PyObject
*op
)
1923 static PyObject
*dictiter_new(PyDictObject
*, PyTypeObject
*);
1926 dict_sizeof(PyDictObject
*mp
)
1930 res
= sizeof(PyDictObject
);
1931 if (mp
->ma_table
!= mp
->ma_smalltable
)
1932 res
= res
+ (mp
->ma_mask
+ 1) * sizeof(PyDictEntry
);
1933 return PyLong_FromSsize_t(res
);
1936 PyDoc_STRVAR(contains__doc__
,
1937 "D.__contains__(k) -> True if D has a key k, else False");
1939 PyDoc_STRVAR(getitem__doc__
, "x.__getitem__(y) <==> x[y]");
1941 PyDoc_STRVAR(sizeof__doc__
,
1942 "D.__sizeof__() -> size of D in memory, in bytes");
1944 PyDoc_STRVAR(get__doc__
,
1945 "D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
1947 PyDoc_STRVAR(setdefault_doc__
,
1948 "D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");
1950 PyDoc_STRVAR(pop__doc__
,
1951 "D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
1952 If key is not found, d is returned if given, otherwise KeyError is raised");
1954 PyDoc_STRVAR(popitem__doc__
,
1955 "D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
1956 2-tuple; but raise KeyError if D is empty.");
1958 PyDoc_STRVAR(update__doc__
,
1959 "D.update(E, **F) -> None. Update D from dict/iterable E and F.\n"
1960 "If E has a .keys() method, does: for k in E: D[k] = E[k]\n\
1961 If E lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
1962 In either case, this is followed by: for k in F: D[k] = F[k]");
1964 PyDoc_STRVAR(fromkeys__doc__
,
1965 "dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
1966 v defaults to None.");
1968 PyDoc_STRVAR(clear__doc__
,
1969 "D.clear() -> None. Remove all items from D.");
1971 PyDoc_STRVAR(copy__doc__
,
1972 "D.copy() -> a shallow copy of D");
1975 static PyObject
*dictkeys_new(PyObject
*);
1976 static PyObject
*dictitems_new(PyObject
*);
1977 static PyObject
*dictvalues_new(PyObject
*);
1979 PyDoc_STRVAR(keys__doc__
,
1980 "D.keys() -> a set-like object providing a view on D's keys");
1981 PyDoc_STRVAR(items__doc__
,
1982 "D.items() -> a set-like object providing a view on D's items");
1983 PyDoc_STRVAR(values__doc__
,
1984 "D.values() -> an object providing a view on D's values");
1986 static PyMethodDef mapp_methods
[] = {
1987 {"__contains__",(PyCFunction
)dict_contains
, METH_O
| METH_COEXIST
,
1989 {"__getitem__", (PyCFunction
)dict_subscript
, METH_O
| METH_COEXIST
,
1991 {"__sizeof__", (PyCFunction
)dict_sizeof
, METH_NOARGS
,
1993 {"get", (PyCFunction
)dict_get
, METH_VARARGS
,
1995 {"setdefault", (PyCFunction
)dict_setdefault
, METH_VARARGS
,
1997 {"pop", (PyCFunction
)dict_pop
, METH_VARARGS
,
1999 {"popitem", (PyCFunction
)dict_popitem
, METH_NOARGS
,
2001 {"keys", (PyCFunction
)dictkeys_new
, METH_NOARGS
,
2003 {"items", (PyCFunction
)dictitems_new
, METH_NOARGS
,
2005 {"values", (PyCFunction
)dictvalues_new
, METH_NOARGS
,
2007 {"update", (PyCFunction
)dict_update
, METH_VARARGS
| METH_KEYWORDS
,
2009 {"fromkeys", (PyCFunction
)dict_fromkeys
, METH_VARARGS
| METH_CLASS
,
2011 {"clear", (PyCFunction
)dict_clear
, METH_NOARGS
,
2013 {"copy", (PyCFunction
)dict_copy
, METH_NOARGS
,
2015 {NULL
, NULL
} /* sentinel */
2018 /* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
2020 PyDict_Contains(PyObject
*op
, PyObject
*key
)
2023 PyDictObject
*mp
= (PyDictObject
*)op
;
2026 if (!PyUnicode_CheckExact(key
) ||
2027 (hash
= ((PyUnicodeObject
*) key
)->hash
) == -1) {
2028 hash
= PyObject_Hash(key
);
2032 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
2033 return ep
== NULL
? -1 : (ep
->me_value
!= NULL
);
2036 /* Internal version of PyDict_Contains used when the hash value is already known */
2038 _PyDict_Contains(PyObject
*op
, PyObject
*key
, long hash
)
2040 PyDictObject
*mp
= (PyDictObject
*)op
;
2043 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
2044 return ep
== NULL
? -1 : (ep
->me_value
!= NULL
);
2047 /* Hack to implement "key in dict" */
2048 static PySequenceMethods dict_as_sequence
= {
2054 0, /* sq_ass_item */
2055 0, /* sq_ass_slice */
2056 PyDict_Contains
, /* sq_contains */
2057 0, /* sq_inplace_concat */
2058 0, /* sq_inplace_repeat */
2062 dict_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2066 assert(type
!= NULL
&& type
->tp_alloc
!= NULL
);
2067 self
= type
->tp_alloc(type
, 0);
2069 PyDictObject
*d
= (PyDictObject
*)self
;
2070 /* It's guaranteed that tp->alloc zeroed out the struct. */
2071 assert(d
->ma_table
== NULL
&& d
->ma_fill
== 0 && d
->ma_used
== 0);
2072 INIT_NONZERO_DICT_SLOTS(d
);
2073 d
->ma_lookup
= lookdict_unicode
;
2074 /* The object has been implicitely tracked by tp_alloc */
2075 if (type
== &PyDict_Type
)
2076 _PyObject_GC_UNTRACK(d
);
2077 #ifdef SHOW_CONVERSION_COUNTS
2080 #ifdef SHOW_TRACK_COUNT
2081 if (_PyObject_GC_IS_TRACKED(d
))
2091 dict_init(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
2093 return dict_update_common(self
, args
, kwds
, "dict");
2097 dict_iter(PyDictObject
*dict
)
2099 return dictiter_new(dict
, &PyDictIterKey_Type
);
2102 PyDoc_STRVAR(dictionary_doc
,
2103 "dict() -> new empty dictionary\n"
2104 "dict(mapping) -> new dictionary initialized from a mapping object's\n"
2105 " (key, value) pairs\n"
2106 "dict(iterable) -> new dictionary initialized as if via:\n"
2108 " for k, v in iterable:\n"
2110 "dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2111 " in the keyword argument list. For example: dict(one=1, two=2)");
2113 PyTypeObject PyDict_Type
= {
2114 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2116 sizeof(PyDictObject
),
2118 (destructor
)dict_dealloc
, /* tp_dealloc */
2122 0, /* tp_reserved */
2123 (reprfunc
)dict_repr
, /* tp_repr */
2124 0, /* tp_as_number */
2125 &dict_as_sequence
, /* tp_as_sequence */
2126 &dict_as_mapping
, /* tp_as_mapping */
2127 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2130 PyObject_GenericGetAttr
, /* tp_getattro */
2131 0, /* tp_setattro */
2132 0, /* tp_as_buffer */
2133 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2134 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_DICT_SUBCLASS
, /* tp_flags */
2135 dictionary_doc
, /* tp_doc */
2136 dict_traverse
, /* tp_traverse */
2137 dict_tp_clear
, /* tp_clear */
2138 dict_richcompare
, /* tp_richcompare */
2139 0, /* tp_weaklistoffset */
2140 (getiterfunc
)dict_iter
, /* tp_iter */
2141 0, /* tp_iternext */
2142 mapp_methods
, /* tp_methods */
2147 0, /* tp_descr_get */
2148 0, /* tp_descr_set */
2149 0, /* tp_dictoffset */
2150 dict_init
, /* tp_init */
2151 PyType_GenericAlloc
, /* tp_alloc */
2152 dict_new
, /* tp_new */
2153 PyObject_GC_Del
, /* tp_free */
2156 /* For backward compatibility with old dictionary interface */
2159 PyDict_GetItemString(PyObject
*v
, const char *key
)
2162 kv
= PyUnicode_FromString(key
);
2165 rv
= PyDict_GetItem(v
, kv
);
2171 PyDict_SetItemString(PyObject
*v
, const char *key
, PyObject
*item
)
2175 kv
= PyUnicode_FromString(key
);
2178 PyUnicode_InternInPlace(&kv
); /* XXX Should we really? */
2179 err
= PyDict_SetItem(v
, kv
, item
);
2185 PyDict_DelItemString(PyObject
*v
, const char *key
)
2189 kv
= PyUnicode_FromString(key
);
2192 err
= PyDict_DelItem(v
, kv
);
2197 /* Dictionary iterator types */
2201 PyDictObject
*di_dict
; /* Set to NULL when iterator is exhausted */
2204 PyObject
* di_result
; /* reusable result tuple for iteritems */
2209 dictiter_new(PyDictObject
*dict
, PyTypeObject
*itertype
)
2212 di
= PyObject_GC_New(dictiterobject
, itertype
);
2217 di
->di_used
= dict
->ma_used
;
2219 di
->len
= dict
->ma_used
;
2220 if (itertype
== &PyDictIterItem_Type
) {
2221 di
->di_result
= PyTuple_Pack(2, Py_None
, Py_None
);
2222 if (di
->di_result
== NULL
) {
2228 di
->di_result
= NULL
;
2229 _PyObject_GC_TRACK(di
);
2230 return (PyObject
*)di
;
2234 dictiter_dealloc(dictiterobject
*di
)
2236 Py_XDECREF(di
->di_dict
);
2237 Py_XDECREF(di
->di_result
);
2238 PyObject_GC_Del(di
);
2242 dictiter_traverse(dictiterobject
*di
, visitproc visit
, void *arg
)
2244 Py_VISIT(di
->di_dict
);
2245 Py_VISIT(di
->di_result
);
2250 dictiter_len(dictiterobject
*di
)
2253 if (di
->di_dict
!= NULL
&& di
->di_used
== di
->di_dict
->ma_used
)
2255 return PyLong_FromSize_t(len
);
2258 PyDoc_STRVAR(length_hint_doc
,
2259 "Private method returning an estimate of len(list(it)).");
2261 static PyMethodDef dictiter_methods
[] = {
2262 {"__length_hint__", (PyCFunction
)dictiter_len
, METH_NOARGS
,
2264 {NULL
, NULL
} /* sentinel */
2267 static PyObject
*dictiter_iternextkey(dictiterobject
*di
)
2270 register Py_ssize_t i
, mask
;
2271 register PyDictEntry
*ep
;
2272 PyDictObject
*d
= di
->di_dict
;
2276 assert (PyDict_Check(d
));
2278 if (di
->di_used
!= d
->ma_used
) {
2279 PyErr_SetString(PyExc_RuntimeError
,
2280 "dictionary changed size during iteration");
2281 di
->di_used
= -1; /* Make this state sticky */
2290 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
2306 PyTypeObject PyDictIterKey_Type
= {
2307 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2308 "dict_keyiterator", /* tp_name */
2309 sizeof(dictiterobject
), /* tp_basicsize */
2310 0, /* tp_itemsize */
2312 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2316 0, /* tp_reserved */
2318 0, /* tp_as_number */
2319 0, /* tp_as_sequence */
2320 0, /* tp_as_mapping */
2324 PyObject_GenericGetAttr
, /* tp_getattro */
2325 0, /* tp_setattro */
2326 0, /* tp_as_buffer */
2327 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2329 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2331 0, /* tp_richcompare */
2332 0, /* tp_weaklistoffset */
2333 PyObject_SelfIter
, /* tp_iter */
2334 (iternextfunc
)dictiter_iternextkey
, /* tp_iternext */
2335 dictiter_methods
, /* tp_methods */
2339 static PyObject
*dictiter_iternextvalue(dictiterobject
*di
)
2342 register Py_ssize_t i
, mask
;
2343 register PyDictEntry
*ep
;
2344 PyDictObject
*d
= di
->di_dict
;
2348 assert (PyDict_Check(d
));
2350 if (di
->di_used
!= d
->ma_used
) {
2351 PyErr_SetString(PyExc_RuntimeError
,
2352 "dictionary changed size during iteration");
2353 di
->di_used
= -1; /* Make this state sticky */
2359 if (i
< 0 || i
> mask
)
2362 while ((value
=ep
[i
].me_value
) == NULL
) {
2378 PyTypeObject PyDictIterValue_Type
= {
2379 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2380 "dict_valueiterator", /* tp_name */
2381 sizeof(dictiterobject
), /* tp_basicsize */
2382 0, /* tp_itemsize */
2384 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2388 0, /* tp_reserved */
2390 0, /* tp_as_number */
2391 0, /* tp_as_sequence */
2392 0, /* tp_as_mapping */
2396 PyObject_GenericGetAttr
, /* tp_getattro */
2397 0, /* tp_setattro */
2398 0, /* tp_as_buffer */
2399 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2401 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2403 0, /* tp_richcompare */
2404 0, /* tp_weaklistoffset */
2405 PyObject_SelfIter
, /* tp_iter */
2406 (iternextfunc
)dictiter_iternextvalue
, /* tp_iternext */
2407 dictiter_methods
, /* tp_methods */
2411 static PyObject
*dictiter_iternextitem(dictiterobject
*di
)
2413 PyObject
*key
, *value
, *result
= di
->di_result
;
2414 register Py_ssize_t i
, mask
;
2415 register PyDictEntry
*ep
;
2416 PyDictObject
*d
= di
->di_dict
;
2420 assert (PyDict_Check(d
));
2422 if (di
->di_used
!= d
->ma_used
) {
2423 PyErr_SetString(PyExc_RuntimeError
,
2424 "dictionary changed size during iteration");
2425 di
->di_used
= -1; /* Make this state sticky */
2434 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
2440 if (result
->ob_refcnt
== 1) {
2442 Py_DECREF(PyTuple_GET_ITEM(result
, 0));
2443 Py_DECREF(PyTuple_GET_ITEM(result
, 1));
2445 result
= PyTuple_New(2);
2451 value
= ep
[i
].me_value
;
2454 PyTuple_SET_ITEM(result
, 0, key
);
2455 PyTuple_SET_ITEM(result
, 1, value
);
2464 PyTypeObject PyDictIterItem_Type
= {
2465 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2466 "dict_itemiterator", /* tp_name */
2467 sizeof(dictiterobject
), /* tp_basicsize */
2468 0, /* tp_itemsize */
2470 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2474 0, /* tp_reserved */
2476 0, /* tp_as_number */
2477 0, /* tp_as_sequence */
2478 0, /* tp_as_mapping */
2482 PyObject_GenericGetAttr
, /* tp_getattro */
2483 0, /* tp_setattro */
2484 0, /* tp_as_buffer */
2485 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2487 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2489 0, /* tp_richcompare */
2490 0, /* tp_weaklistoffset */
2491 PyObject_SelfIter
, /* tp_iter */
2492 (iternextfunc
)dictiter_iternextitem
, /* tp_iternext */
2493 dictiter_methods
, /* tp_methods */
2498 /***********************************************/
2499 /* View objects for keys(), items(), values(). */
2500 /***********************************************/
2502 /* The instance lay-out is the same for all three; but the type differs. */
2506 PyDictObject
*dv_dict
;
2511 dictview_dealloc(dictviewobject
*dv
)
2513 Py_XDECREF(dv
->dv_dict
);
2514 PyObject_GC_Del(dv
);
2518 dictview_traverse(dictviewobject
*dv
, visitproc visit
, void *arg
)
2520 Py_VISIT(dv
->dv_dict
);
2525 dictview_len(dictviewobject
*dv
)
2528 if (dv
->dv_dict
!= NULL
)
2529 len
= dv
->dv_dict
->ma_used
;
2534 dictview_new(PyObject
*dict
, PyTypeObject
*type
)
2538 PyErr_BadInternalCall();
2541 if (!PyDict_Check(dict
)) {
2542 /* XXX Get rid of this restriction later */
2543 PyErr_Format(PyExc_TypeError
,
2544 "%s() requires a dict argument, not '%s'",
2545 type
->tp_name
, dict
->ob_type
->tp_name
);
2548 dv
= PyObject_GC_New(dictviewobject
, type
);
2552 dv
->dv_dict
= (PyDictObject
*)dict
;
2553 _PyObject_GC_TRACK(dv
);
2554 return (PyObject
*)dv
;
2557 /* TODO(guido): The views objects are not complete:
2559 * support more set operations
2560 * support arbitrary mappings?
2561 - either these should be static or exported in dictobject.h
2562 - if public then they should probably be in builtins
2565 /* Return 1 if self is a subset of other, iterating over self;
2566 0 if not; -1 if an error occurred. */
2568 all_contained_in(PyObject
*self
, PyObject
*other
)
2570 PyObject
*iter
= PyObject_GetIter(self
);
2576 PyObject
*next
= PyIter_Next(iter
);
2578 if (PyErr_Occurred())
2582 ok
= PySequence_Contains(other
, next
);
2592 dictview_richcompare(PyObject
*self
, PyObject
*other
, int op
)
2594 Py_ssize_t len_self
, len_other
;
2598 assert(self
!= NULL
);
2599 assert(PyDictViewSet_Check(self
));
2600 assert(other
!= NULL
);
2602 if (!PyAnySet_Check(other
) && !PyDictViewSet_Check(other
)) {
2603 Py_INCREF(Py_NotImplemented
);
2604 return Py_NotImplemented
;
2607 len_self
= PyObject_Size(self
);
2610 len_other
= PyObject_Size(other
);
2619 if (len_self
== len_other
)
2620 ok
= all_contained_in(self
, other
);
2621 if (op
== Py_NE
&& ok
>= 0)
2626 if (len_self
< len_other
)
2627 ok
= all_contained_in(self
, other
);
2631 if (len_self
<= len_other
)
2632 ok
= all_contained_in(self
, other
);
2636 if (len_self
> len_other
)
2637 ok
= all_contained_in(other
, self
);
2641 if (len_self
>= len_other
)
2642 ok
= all_contained_in(other
, self
);
2648 result
= ok
? Py_True
: Py_False
;
2654 dictview_repr(dictviewobject
*dv
)
2659 seq
= PySequence_List((PyObject
*)dv
);
2663 result
= PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv
)->tp_name
, seq
);
2671 dictkeys_iter(dictviewobject
*dv
)
2673 if (dv
->dv_dict
== NULL
) {
2676 return dictiter_new(dv
->dv_dict
, &PyDictIterKey_Type
);
2680 dictkeys_contains(dictviewobject
*dv
, PyObject
*obj
)
2682 if (dv
->dv_dict
== NULL
)
2684 return PyDict_Contains((PyObject
*)dv
->dv_dict
, obj
);
2687 static PySequenceMethods dictkeys_as_sequence
= {
2688 (lenfunc
)dictview_len
, /* sq_length */
2693 0, /* sq_ass_item */
2694 0, /* sq_ass_slice */
2695 (objobjproc
)dictkeys_contains
, /* sq_contains */
2699 dictviews_sub(PyObject
* self
, PyObject
*other
)
2701 PyObject
*result
= PySet_New(self
);
2706 tmp
= PyObject_CallMethod(result
, "difference_update", "O", other
);
2717 dictviews_and(PyObject
* self
, PyObject
*other
)
2719 PyObject
*result
= PySet_New(self
);
2724 tmp
= PyObject_CallMethod(result
, "intersection_update", "O", other
);
2735 dictviews_or(PyObject
* self
, PyObject
*other
)
2737 PyObject
*result
= PySet_New(self
);
2742 tmp
= PyObject_CallMethod(result
, "update", "O", other
);
2753 dictviews_xor(PyObject
* self
, PyObject
*other
)
2755 PyObject
*result
= PySet_New(self
);
2760 tmp
= PyObject_CallMethod(result
, "symmetric_difference_update", "O",
2771 static PyNumberMethods dictviews_as_number
= {
2773 (binaryfunc
)dictviews_sub
, /*nb_subtract*/
2785 (binaryfunc
)dictviews_and
, /*nb_and*/
2786 (binaryfunc
)dictviews_xor
, /*nb_xor*/
2787 (binaryfunc
)dictviews_or
, /*nb_or*/
2790 static PyMethodDef dictkeys_methods
[] = {
2791 {NULL
, NULL
} /* sentinel */
2794 PyTypeObject PyDictKeys_Type
= {
2795 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2796 "dict_keys", /* tp_name */
2797 sizeof(dictviewobject
), /* tp_basicsize */
2798 0, /* tp_itemsize */
2800 (destructor
)dictview_dealloc
, /* tp_dealloc */
2804 0, /* tp_reserved */
2805 (reprfunc
)dictview_repr
, /* tp_repr */
2806 &dictviews_as_number
, /* tp_as_number */
2807 &dictkeys_as_sequence
, /* tp_as_sequence */
2808 0, /* tp_as_mapping */
2812 PyObject_GenericGetAttr
, /* tp_getattro */
2813 0, /* tp_setattro */
2814 0, /* tp_as_buffer */
2815 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2817 (traverseproc
)dictview_traverse
, /* tp_traverse */
2819 dictview_richcompare
, /* tp_richcompare */
2820 0, /* tp_weaklistoffset */
2821 (getiterfunc
)dictkeys_iter
, /* tp_iter */
2822 0, /* tp_iternext */
2823 dictkeys_methods
, /* tp_methods */
2828 dictkeys_new(PyObject
*dict
)
2830 return dictview_new(dict
, &PyDictKeys_Type
);
2833 /*** dict_items ***/
2836 dictitems_iter(dictviewobject
*dv
)
2838 if (dv
->dv_dict
== NULL
) {
2841 return dictiter_new(dv
->dv_dict
, &PyDictIterItem_Type
);
2845 dictitems_contains(dictviewobject
*dv
, PyObject
*obj
)
2847 PyObject
*key
, *value
, *found
;
2848 if (dv
->dv_dict
== NULL
)
2850 if (!PyTuple_Check(obj
) || PyTuple_GET_SIZE(obj
) != 2)
2852 key
= PyTuple_GET_ITEM(obj
, 0);
2853 value
= PyTuple_GET_ITEM(obj
, 1);
2854 found
= PyDict_GetItem((PyObject
*)dv
->dv_dict
, key
);
2855 if (found
== NULL
) {
2856 if (PyErr_Occurred())
2860 return PyObject_RichCompareBool(value
, found
, Py_EQ
);
2863 static PySequenceMethods dictitems_as_sequence
= {
2864 (lenfunc
)dictview_len
, /* sq_length */
2869 0, /* sq_ass_item */
2870 0, /* sq_ass_slice */
2871 (objobjproc
)dictitems_contains
, /* sq_contains */
2874 static PyMethodDef dictitems_methods
[] = {
2875 {NULL
, NULL
} /* sentinel */
2878 PyTypeObject PyDictItems_Type
= {
2879 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2880 "dict_items", /* tp_name */
2881 sizeof(dictviewobject
), /* tp_basicsize */
2882 0, /* tp_itemsize */
2884 (destructor
)dictview_dealloc
, /* tp_dealloc */
2888 0, /* tp_reserved */
2889 (reprfunc
)dictview_repr
, /* tp_repr */
2890 &dictviews_as_number
, /* tp_as_number */
2891 &dictitems_as_sequence
, /* tp_as_sequence */
2892 0, /* tp_as_mapping */
2896 PyObject_GenericGetAttr
, /* tp_getattro */
2897 0, /* tp_setattro */
2898 0, /* tp_as_buffer */
2899 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2901 (traverseproc
)dictview_traverse
, /* tp_traverse */
2903 dictview_richcompare
, /* tp_richcompare */
2904 0, /* tp_weaklistoffset */
2905 (getiterfunc
)dictitems_iter
, /* tp_iter */
2906 0, /* tp_iternext */
2907 dictitems_methods
, /* tp_methods */
2912 dictitems_new(PyObject
*dict
)
2914 return dictview_new(dict
, &PyDictItems_Type
);
2917 /*** dict_values ***/
2920 dictvalues_iter(dictviewobject
*dv
)
2922 if (dv
->dv_dict
== NULL
) {
2925 return dictiter_new(dv
->dv_dict
, &PyDictIterValue_Type
);
2928 static PySequenceMethods dictvalues_as_sequence
= {
2929 (lenfunc
)dictview_len
, /* sq_length */
2934 0, /* sq_ass_item */
2935 0, /* sq_ass_slice */
2936 (objobjproc
)0, /* sq_contains */
2939 static PyMethodDef dictvalues_methods
[] = {
2940 {NULL
, NULL
} /* sentinel */
2943 PyTypeObject PyDictValues_Type
= {
2944 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2945 "dict_values", /* tp_name */
2946 sizeof(dictviewobject
), /* tp_basicsize */
2947 0, /* tp_itemsize */
2949 (destructor
)dictview_dealloc
, /* tp_dealloc */
2953 0, /* tp_reserved */
2954 (reprfunc
)dictview_repr
, /* tp_repr */
2955 0, /* tp_as_number */
2956 &dictvalues_as_sequence
, /* tp_as_sequence */
2957 0, /* tp_as_mapping */
2961 PyObject_GenericGetAttr
, /* tp_getattro */
2962 0, /* tp_setattro */
2963 0, /* tp_as_buffer */
2964 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2966 (traverseproc
)dictview_traverse
, /* tp_traverse */
2968 0, /* tp_richcompare */
2969 0, /* tp_weaklistoffset */
2970 (getiterfunc
)dictvalues_iter
, /* tp_iter */
2971 0, /* tp_iternext */
2972 dictvalues_methods
, /* tp_methods */
2977 dictvalues_new(PyObject
*dict
)
2979 return dictview_new(dict
, &PyDictValues_Type
);