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.
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. */
17 set_key_error(PyObject
*arg
)
20 tup
= PyTuple_Pack(1, arg
);
22 return; /* caller will expect error to be set anyway */
23 PyErr_SetObject(PyExc_KeyError
, tup
);
27 /* Define this out if you don't want conversion statistics on exit. */
28 #undef SHOW_CONVERSION_COUNTS
30 /* See large comment block below. This must be >= 1. */
31 #define PERTURB_SHIFT 5
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
39 >>> map(hash, (0, 1, 2, 3))
41 >>> map(hash, ("namea", "nameb", "namec", "named"))
42 [-1658398457, -1658398460, -1658398459, -1658398462]
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.
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.
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.
65 The first half of collision resolution is to visit table indices via this
68 j = ((5*j) + 1) mod 2**i
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:
79 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
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.
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:
92 j = (5*j) + 1 + perturb;
93 perturb >>= PERTURB_SHIFT;
94 use j % 2**i as the next table index;
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).
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.
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.
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).
137 /* Object used as dummy key to fill deleted entries */
138 static PyObject
*dummy
= NULL
; /* Initialized by first call to newPyDictObject() */
148 /* forward declarations */
150 lookdict_string(PyDictObject
*mp
, PyObject
*key
, long hash
);
152 #ifdef SHOW_CONVERSION_COUNTS
153 static long created
= 0L;
154 static long converted
= 0L;
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
);
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;
174 fprintf(stderr
, "Dict allocations: %" PY_FORMAT_SIZE_T
"d\n",
176 fprintf(stderr
, "Dict reuse through freelist: %" PY_FORMAT_SIZE_T
178 fprintf(stderr
, "%.2f%% reuse rate\n\n",
179 (100.0*count_reuse
/(count_alloc
+count_reuse
)));
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;
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
)));
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).
210 #define INIT_NONZERO_DICT_SLOTS(mp) do { \
211 (mp)->ma_table = (mp)->ma_smalltable; \
212 (mp)->ma_mask = PyDict_MINSIZE - 1; \
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); \
221 /* Dictionary reuse scheme to save calls to malloc, free, and memset */
222 #ifndef PyDict_MAXFREELIST
223 #define PyDict_MAXFREELIST 80
225 static PyDictObject
*free_list
[PyDict_MAXFREELIST
];
226 static int numfree
= 0;
234 op
= free_list
[--numfree
];
235 assert(PyDict_CheckExact(op
));
243 register PyDictObject
*mp
;
244 if (dummy
== NULL
) { /* Auto-initialize dummy */
245 dummy
= PyString_FromString("<dummy key>");
248 #ifdef SHOW_CONVERSION_COUNTS
249 Py_AtExit(show_counts
);
251 #ifdef SHOW_ALLOC_COUNT
252 Py_AtExit(show_alloc
);
254 #ifdef SHOW_TRACK_COUNT
255 Py_AtExit(show_track
);
259 mp
= free_list
[--numfree
];
261 assert (Py_TYPE(mp
) == &PyDict_Type
);
262 _Py_NewReference((PyObject
*)mp
);
264 EMPTY_TO_MINSIZE(mp
);
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
);
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
277 mp
= PyObject_GC_New(PyDictObject
, &PyDict_Type
);
280 EMPTY_TO_MINSIZE(mp
);
281 #ifdef SHOW_ALLOC_COUNT
285 mp
->ma_lookup
= lookdict_string
;
286 #ifdef SHOW_TRACK_COUNT
289 #ifdef SHOW_CONVERSION_COUNTS
292 return (PyObject
*)mp
;
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).
301 The initial probe index is computed as hash mod the table size. Subsequent
302 probe indices are computed as explained earlier.
304 All arithmetic on hash should ignore overflow.
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
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
320 lookdict(PyDictObject
*mp
, PyObject
*key
, register long hash
)
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
;
331 i
= (size_t)hash
& mask
;
333 if (ep
->me_key
== NULL
|| ep
->me_key
== key
)
336 if (ep
->me_key
== dummy
)
339 if (ep
->me_hash
== hash
) {
340 startkey
= ep
->me_key
;
342 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
346 if (ep0
== mp
->ma_table
&& ep
->me_key
== startkey
) {
351 /* The compare did major nasty stuff to the
353 * XXX A clever adversary could prevent this
354 * XXX from terminating.
356 return lookdict(mp
, key
, hash
);
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;
367 if (ep
->me_key
== NULL
)
368 return freeslot
== NULL
? ep
: freeslot
;
369 if (ep
->me_key
== key
)
371 if (ep
->me_hash
== hash
&& ep
->me_key
!= dummy
) {
372 startkey
= ep
->me_key
;
374 cmp
= PyObject_RichCompareBool(startkey
, key
, Py_EQ
);
378 if (ep0
== mp
->ma_table
&& ep
->me_key
== startkey
) {
383 /* The compare did major nasty stuff to the
385 * XXX A clever adversary could prevent this
386 * XXX from terminating.
388 return lookdict(mp
, key
, hash
);
391 else if (ep
->me_key
== dummy
&& freeslot
== NULL
)
394 assert(0); /* NOT REACHED */
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.
405 * This is valuable because dicts with only string keys are very common.
408 lookdict_string(PyDictObject
*mp
, PyObject
*key
, register long hash
)
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
;
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
421 if (!PyString_CheckExact(key
)) {
422 #ifdef SHOW_CONVERSION_COUNTS
425 mp
->ma_lookup
= lookdict
;
426 return lookdict(mp
, key
, hash
);
430 if (ep
->me_key
== NULL
|| ep
->me_key
== key
)
432 if (ep
->me_key
== dummy
)
435 if (ep
->me_hash
== hash
&& _PyString_Eq(ep
->me_key
, key
))
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;
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
)))
452 if (ep
->me_key
== dummy
&& freeslot
== NULL
)
455 assert(0); /* NOT REACHED */
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++);
465 #define INCREASE_TRACK_COUNT
466 #define DECREASE_TRACK_COUNT
469 #define MAINTAIN_TRACKING(mp, key, value) \
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 \
481 _PyDict_MaybeUntrack(PyObject
*op
)
488 if (!PyDict_CheckExact(op
) || !_PyObject_GC_IS_TRACKED(op
))
491 mp
= (PyDictObject
*) op
;
494 for (i
= 0; i
<= mask
; i
++) {
495 if ((value
= ep
[i
].me_value
) == NULL
)
497 if (_PyObject_GC_MAY_BE_TRACKED(value
) ||
498 _PyObject_GC_MAY_BE_TRACKED(ep
[i
].me_key
))
502 _PyObject_GC_UNTRACK(op
);
507 Internal routine to insert a new item into the table.
508 Used both by the internal resize routine and by the public insert routine.
509 Eats a reference to key and one to value.
510 Returns -1 if an error occurred, or 0 on success.
513 insertdict(register PyDictObject
*mp
, PyObject
*key
, long hash
, PyObject
*value
)
516 register PyDictEntry
*ep
;
517 typedef PyDictEntry
*(*lookupfunc
)(PyDictObject
*, PyObject
*, long);
519 assert(mp
->ma_lookup
!= NULL
);
520 ep
= mp
->ma_lookup(mp
, key
, hash
);
526 MAINTAIN_TRACKING(mp
, key
, value
);
527 if (ep
->me_value
!= NULL
) {
528 old_value
= ep
->me_value
;
529 ep
->me_value
= value
;
530 Py_DECREF(old_value
); /* which **CAN** re-enter */
534 if (ep
->me_key
== NULL
)
537 assert(ep
->me_key
== dummy
);
541 ep
->me_hash
= (Py_ssize_t
)hash
;
542 ep
->me_value
= value
;
549 Internal routine used by dictresize() to insert an item which is
550 known to be absent from the dict. This routine also assumes that
551 the dict contains no deleted entries. Besides the performance benefit,
552 using insertdict() in dictresize() is dangerous (SF bug #1456209).
553 Note that no refcounts are changed by this routine; if needed, the caller
554 is responsible for incref'ing `key` and `value`.
557 insertdict_clean(register PyDictObject
*mp
, PyObject
*key
, long hash
,
561 register size_t perturb
;
562 register size_t mask
= (size_t)mp
->ma_mask
;
563 PyDictEntry
*ep0
= mp
->ma_table
;
564 register PyDictEntry
*ep
;
566 MAINTAIN_TRACKING(mp
, key
, value
);
569 for (perturb
= hash
; ep
->me_key
!= NULL
; perturb
>>= PERTURB_SHIFT
) {
570 i
= (i
<< 2) + i
+ perturb
+ 1;
573 assert(ep
->me_value
== NULL
);
576 ep
->me_hash
= (Py_ssize_t
)hash
;
577 ep
->me_value
= value
;
582 Restructure the table by allocating a new table and reinserting all
583 items again. When entries have been deleted, the new table may
584 actually be smaller than the old one.
587 dictresize(PyDictObject
*mp
, Py_ssize_t minused
)
590 PyDictEntry
*oldtable
, *newtable
, *ep
;
592 int is_oldtable_malloced
;
593 PyDictEntry small_copy
[PyDict_MINSIZE
];
595 assert(minused
>= 0);
597 /* Find the smallest table size > minused. */
598 for (newsize
= PyDict_MINSIZE
;
599 newsize
<= minused
&& newsize
> 0;
607 /* Get space for a new table. */
608 oldtable
= mp
->ma_table
;
609 assert(oldtable
!= NULL
);
610 is_oldtable_malloced
= oldtable
!= mp
->ma_smalltable
;
612 if (newsize
== PyDict_MINSIZE
) {
613 /* A large table is shrinking, or we can't get any smaller. */
614 newtable
= mp
->ma_smalltable
;
615 if (newtable
== oldtable
) {
616 if (mp
->ma_fill
== mp
->ma_used
) {
617 /* No dummies, so no point doing anything. */
620 /* We're not going to resize it, but rebuild the
621 table anyway to purge old dummy entries.
622 Subtle: This is *necessary* if fill==size,
623 as lookdict needs at least one virgin slot to
624 terminate failing searches. If fill < size, it's
625 merely desirable, as dummies slow searches. */
626 assert(mp
->ma_fill
> mp
->ma_used
);
627 memcpy(small_copy
, oldtable
, sizeof(small_copy
));
628 oldtable
= small_copy
;
632 newtable
= PyMem_NEW(PyDictEntry
, newsize
);
633 if (newtable
== NULL
) {
639 /* Make the dict empty, using the new table. */
640 assert(newtable
!= oldtable
);
641 mp
->ma_table
= newtable
;
642 mp
->ma_mask
= newsize
- 1;
643 memset(newtable
, 0, sizeof(PyDictEntry
) * newsize
);
648 /* Copy the data over; this is refcount-neutral for active entries;
649 dummy entries aren't copied over, of course */
650 for (ep
= oldtable
; i
> 0; ep
++) {
651 if (ep
->me_value
!= NULL
) { /* active entry */
653 insertdict_clean(mp
, ep
->me_key
, (long)ep
->me_hash
,
656 else if (ep
->me_key
!= NULL
) { /* dummy entry */
658 assert(ep
->me_key
== dummy
);
659 Py_DECREF(ep
->me_key
);
661 /* else key == value == NULL: nothing to do */
664 if (is_oldtable_malloced
)
669 /* Create a new dictionary pre-sized to hold an estimated number of elements.
670 Underestimates are okay because the dictionary will resize as necessary.
671 Overestimates just mean the dictionary will be more sparse than usual.
675 _PyDict_NewPresized(Py_ssize_t minused
)
677 PyObject
*op
= PyDict_New();
679 if (minused
>5 && op
!= NULL
&& dictresize((PyDictObject
*)op
, minused
) == -1) {
686 /* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
687 * that may occur (originally dicts supported only string keys, and exceptions
688 * weren't possible). So, while the original intent was that a NULL return
689 * meant the key wasn't present, in reality it can mean that, or that an error
690 * (suppressed) occurred while computing the key's hash, or that some error
691 * (suppressed) occurred when comparing keys in the dict's internal probe
692 * sequence. A nasty example of the latter is when a Python-coded comparison
693 * function hits a stack-depth error, which can cause this to return NULL
694 * even if the key is present.
697 PyDict_GetItem(PyObject
*op
, PyObject
*key
)
700 PyDictObject
*mp
= (PyDictObject
*)op
;
702 PyThreadState
*tstate
;
703 if (!PyDict_Check(op
))
705 if (!PyString_CheckExact(key
) ||
706 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1)
708 hash
= PyObject_Hash(key
);
715 /* We can arrive here with a NULL tstate during initialization:
716 try running "python -Wi" for an example related to string
717 interning. Let's just hope that no exception occurs then... */
718 tstate
= PyThreadState_GET();
719 if (tstate
!= NULL
&& tstate
->curexc_type
!= NULL
) {
720 /* preserve the existing exception */
721 PyObject
*err_type
, *err_value
, *err_tb
;
722 PyErr_Fetch(&err_type
, &err_value
, &err_tb
);
723 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
725 PyErr_Restore(err_type
, err_value
, err_tb
);
730 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
739 /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
740 * dictionary if it's merely replacing the value for an existing key.
741 * This means that it's safe to loop over a dictionary with PyDict_Next()
742 * and occasionally replace a value -- but you can't insert new keys or
746 PyDict_SetItem(register PyObject
*op
, PyObject
*key
, PyObject
*value
)
748 register PyDictObject
*mp
;
750 register Py_ssize_t n_used
;
752 if (!PyDict_Check(op
)) {
753 PyErr_BadInternalCall();
758 mp
= (PyDictObject
*)op
;
759 if (PyString_CheckExact(key
)) {
760 hash
= ((PyStringObject
*)key
)->ob_shash
;
762 hash
= PyObject_Hash(key
);
765 hash
= PyObject_Hash(key
);
769 assert(mp
->ma_fill
<= mp
->ma_mask
); /* at least one empty slot */
770 n_used
= mp
->ma_used
;
773 if (insertdict(mp
, key
, hash
, value
) != 0)
775 /* If we added a key, we can safely resize. Otherwise just return!
776 * If fill >= 2/3 size, adjust size. Normally, this doubles or
777 * quaduples the size, but it's also possible for the dict to shrink
778 * (if ma_fill is much larger than ma_used, meaning a lot of dict
779 * keys have been * deleted).
781 * Quadrupling the size improves average dictionary sparseness
782 * (reducing collisions) at the cost of some memory and iteration
783 * speed (which loops over every possible entry). It also halves
784 * the number of expensive resize operations in a growing dictionary.
786 * Very large dictionaries (over 50K items) use doubling instead.
787 * This may help applications with severe memory constraints.
789 if (!(mp
->ma_used
> n_used
&& mp
->ma_fill
*3 >= (mp
->ma_mask
+1)*2))
791 return dictresize(mp
, (mp
->ma_used
> 50000 ? 2 : 4) * mp
->ma_used
);
795 PyDict_DelItem(PyObject
*op
, PyObject
*key
)
797 register PyDictObject
*mp
;
799 register PyDictEntry
*ep
;
800 PyObject
*old_value
, *old_key
;
802 if (!PyDict_Check(op
)) {
803 PyErr_BadInternalCall();
807 if (!PyString_CheckExact(key
) ||
808 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
809 hash
= PyObject_Hash(key
);
813 mp
= (PyDictObject
*)op
;
814 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
817 if (ep
->me_value
== NULL
) {
821 old_key
= ep
->me_key
;
824 old_value
= ep
->me_value
;
827 Py_DECREF(old_value
);
833 PyDict_Clear(PyObject
*op
)
836 PyDictEntry
*ep
, *table
;
837 int table_is_malloced
;
839 PyDictEntry small_copy
[PyDict_MINSIZE
];
844 if (!PyDict_Check(op
))
846 mp
= (PyDictObject
*)op
;
852 table
= mp
->ma_table
;
853 assert(table
!= NULL
);
854 table_is_malloced
= table
!= mp
->ma_smalltable
;
856 /* This is delicate. During the process of clearing the dict,
857 * decrefs can cause the dict to mutate. To avoid fatal confusion
858 * (voice of experience), we have to make the dict empty before
859 * clearing the slots, and never refer to anything via mp->xxx while
863 if (table_is_malloced
)
864 EMPTY_TO_MINSIZE(mp
);
867 /* It's a small table with something that needs to be cleared.
868 * Afraid the only safe way is to copy the dict entries into
869 * another small table first.
871 memcpy(small_copy
, table
, sizeof(small_copy
));
873 EMPTY_TO_MINSIZE(mp
);
875 /* else it's a small table that's already empty */
877 /* Now we can finally clear things. If C had refcounts, we could
878 * assert that the refcount on table is 1 now, i.e. that this function
879 * has unique access to it, so decref side-effects can't alter it.
881 for (ep
= table
; fill
> 0; ++ep
) {
888 Py_DECREF(ep
->me_key
);
889 Py_XDECREF(ep
->me_value
);
893 assert(ep
->me_value
== NULL
);
897 if (table_is_malloced
)
902 * Iterate over a dict. Use like so:
905 * PyObject *key, *value;
906 * i = 0; # important! i should not otherwise be changed by you
907 * while (PyDict_Next(yourdict, &i, &key, &value)) {
908 * Refer to borrowed references in key and value.
911 * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
912 * mutates the dict. One exception: it is safe if the loop merely changes
913 * the values associated with the keys (but doesn't insert new keys or
914 * delete keys), via PyDict_SetItem().
917 PyDict_Next(PyObject
*op
, Py_ssize_t
*ppos
, PyObject
**pkey
, PyObject
**pvalue
)
919 register Py_ssize_t i
;
920 register Py_ssize_t mask
;
921 register PyDictEntry
*ep
;
923 if (!PyDict_Check(op
))
928 ep
= ((PyDictObject
*)op
)->ma_table
;
929 mask
= ((PyDictObject
*)op
)->ma_mask
;
930 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
936 *pkey
= ep
[i
].me_key
;
938 *pvalue
= ep
[i
].me_value
;
942 /* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
944 _PyDict_Next(PyObject
*op
, Py_ssize_t
*ppos
, PyObject
**pkey
, PyObject
**pvalue
, long *phash
)
946 register Py_ssize_t i
;
947 register Py_ssize_t mask
;
948 register PyDictEntry
*ep
;
950 if (!PyDict_Check(op
))
955 ep
= ((PyDictObject
*)op
)->ma_table
;
956 mask
= ((PyDictObject
*)op
)->ma_mask
;
957 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
962 *phash
= (long)(ep
[i
].me_hash
);
964 *pkey
= ep
[i
].me_key
;
966 *pvalue
= ep
[i
].me_value
;
973 dict_dealloc(register PyDictObject
*mp
)
975 register PyDictEntry
*ep
;
976 Py_ssize_t fill
= mp
->ma_fill
;
977 PyObject_GC_UnTrack(mp
);
978 Py_TRASHCAN_SAFE_BEGIN(mp
)
979 for (ep
= mp
->ma_table
; fill
> 0; ep
++) {
982 Py_DECREF(ep
->me_key
);
983 Py_XDECREF(ep
->me_value
);
986 if (mp
->ma_table
!= mp
->ma_smalltable
)
987 PyMem_DEL(mp
->ma_table
);
988 if (numfree
< PyDict_MAXFREELIST
&& Py_TYPE(mp
) == &PyDict_Type
)
989 free_list
[numfree
++] = mp
;
991 Py_TYPE(mp
)->tp_free((PyObject
*)mp
);
992 Py_TRASHCAN_SAFE_END(mp
)
996 dict_print(register PyDictObject
*mp
, register FILE *fp
, register int flags
)
998 register Py_ssize_t i
;
999 register Py_ssize_t any
;
1002 status
= Py_ReprEnter((PyObject
*)mp
);
1006 Py_BEGIN_ALLOW_THREADS
1007 fprintf(fp
, "{...}");
1008 Py_END_ALLOW_THREADS
1012 Py_BEGIN_ALLOW_THREADS
1014 Py_END_ALLOW_THREADS
1016 for (i
= 0; i
<= mp
->ma_mask
; i
++) {
1017 PyDictEntry
*ep
= mp
->ma_table
+ i
;
1018 PyObject
*pvalue
= ep
->me_value
;
1019 if (pvalue
!= NULL
) {
1020 /* Prevent PyObject_Repr from deleting value during
1024 Py_BEGIN_ALLOW_THREADS
1026 Py_END_ALLOW_THREADS
1028 if (PyObject_Print((PyObject
*)ep
->me_key
, fp
, 0)!=0) {
1030 Py_ReprLeave((PyObject
*)mp
);
1033 Py_BEGIN_ALLOW_THREADS
1035 Py_END_ALLOW_THREADS
1036 if (PyObject_Print(pvalue
, fp
, 0) != 0) {
1038 Py_ReprLeave((PyObject
*)mp
);
1044 Py_BEGIN_ALLOW_THREADS
1046 Py_END_ALLOW_THREADS
1047 Py_ReprLeave((PyObject
*)mp
);
1052 dict_repr(PyDictObject
*mp
)
1055 PyObject
*s
, *temp
, *colon
= NULL
;
1056 PyObject
*pieces
= NULL
, *result
= NULL
;
1057 PyObject
*key
, *value
;
1059 i
= Py_ReprEnter((PyObject
*)mp
);
1061 return i
> 0 ? PyString_FromString("{...}") : NULL
;
1064 if (mp
->ma_used
== 0) {
1065 result
= PyString_FromString("{}");
1069 pieces
= PyList_New(0);
1073 colon
= PyString_FromString(": ");
1077 /* Do repr() on each key+value pair, and insert ": " between them.
1078 Note that repr may mutate the dict. */
1080 while (PyDict_Next((PyObject
*)mp
, &i
, &key
, &value
)) {
1082 /* Prevent repr from deleting value during key format. */
1084 s
= PyObject_Repr(key
);
1085 PyString_Concat(&s
, colon
);
1086 PyString_ConcatAndDel(&s
, PyObject_Repr(value
));
1090 status
= PyList_Append(pieces
, s
);
1091 Py_DECREF(s
); /* append created a new ref */
1096 /* Add "{}" decorations to the first and last items. */
1097 assert(PyList_GET_SIZE(pieces
) > 0);
1098 s
= PyString_FromString("{");
1101 temp
= PyList_GET_ITEM(pieces
, 0);
1102 PyString_ConcatAndDel(&s
, temp
);
1103 PyList_SET_ITEM(pieces
, 0, s
);
1107 s
= PyString_FromString("}");
1110 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
1111 PyString_ConcatAndDel(&temp
, s
);
1112 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
1116 /* Paste them all together with ", " between. */
1117 s
= PyString_FromString(", ");
1120 result
= _PyString_Join(s
, pieces
);
1126 Py_ReprLeave((PyObject
*)mp
);
1131 dict_length(PyDictObject
*mp
)
1137 dict_subscript(PyDictObject
*mp
, register PyObject
*key
)
1142 assert(mp
->ma_table
!= NULL
);
1143 if (!PyString_CheckExact(key
) ||
1144 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
1145 hash
= PyObject_Hash(key
);
1149 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1154 if (!PyDict_CheckExact(mp
)) {
1155 /* Look up __missing__ method if we're a subclass. */
1156 PyObject
*missing
, *res
;
1157 static PyObject
*missing_str
= NULL
;
1158 missing
= _PyObject_LookupSpecial((PyObject
*)mp
,
1161 if (missing
!= NULL
) {
1162 res
= PyObject_CallFunctionObjArgs(missing
,
1167 else if (PyErr_Occurred())
1179 dict_ass_sub(PyDictObject
*mp
, PyObject
*v
, PyObject
*w
)
1182 return PyDict_DelItem((PyObject
*)mp
, v
);
1184 return PyDict_SetItem((PyObject
*)mp
, v
, w
);
1187 static PyMappingMethods dict_as_mapping
= {
1188 (lenfunc
)dict_length
, /*mp_length*/
1189 (binaryfunc
)dict_subscript
, /*mp_subscript*/
1190 (objobjargproc
)dict_ass_sub
, /*mp_ass_subscript*/
1194 dict_keys(register PyDictObject
*mp
)
1196 register PyObject
*v
;
1197 register Py_ssize_t i
, j
;
1206 if (n
!= mp
->ma_used
) {
1207 /* Durnit. The allocations caused the dict to resize.
1208 * Just start over, this shouldn't normally happen.
1215 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1216 if (ep
[i
].me_value
!= NULL
) {
1217 PyObject
*key
= ep
[i
].me_key
;
1219 PyList_SET_ITEM(v
, j
, key
);
1228 dict_values(register PyDictObject
*mp
)
1230 register PyObject
*v
;
1231 register Py_ssize_t i
, j
;
1240 if (n
!= mp
->ma_used
) {
1241 /* Durnit. The allocations caused the dict to resize.
1242 * Just start over, this shouldn't normally happen.
1249 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1250 if (ep
[i
].me_value
!= NULL
) {
1251 PyObject
*value
= ep
[i
].me_value
;
1253 PyList_SET_ITEM(v
, j
, value
);
1262 dict_items(register PyDictObject
*mp
)
1264 register PyObject
*v
;
1265 register Py_ssize_t i
, j
, n
;
1267 PyObject
*item
, *key
, *value
;
1270 /* Preallocate the list of tuples, to avoid allocations during
1271 * the loop over the items, which could trigger GC, which
1272 * could resize the dict. :-(
1279 for (i
= 0; i
< n
; i
++) {
1280 item
= PyTuple_New(2);
1285 PyList_SET_ITEM(v
, i
, item
);
1287 if (n
!= mp
->ma_used
) {
1288 /* Durnit. The allocations caused the dict to resize.
1289 * Just start over, this shouldn't normally happen.
1294 /* Nothing we do below makes any function calls. */
1297 for (i
= 0, j
= 0; i
<= mask
; i
++) {
1298 if ((value
=ep
[i
].me_value
) != NULL
) {
1300 item
= PyList_GET_ITEM(v
, j
);
1302 PyTuple_SET_ITEM(item
, 0, key
);
1304 PyTuple_SET_ITEM(item
, 1, value
);
1313 dict_fromkeys(PyObject
*cls
, PyObject
*args
)
1316 PyObject
*value
= Py_None
;
1317 PyObject
*it
; /* iter(seq) */
1322 if (!PyArg_UnpackTuple(args
, "fromkeys", 1, 2, &seq
, &value
))
1325 d
= PyObject_CallObject(cls
, NULL
);
1329 if (PyDict_CheckExact(d
) && PyDict_CheckExact(seq
)) {
1330 PyDictObject
*mp
= (PyDictObject
*)d
;
1336 if (dictresize(mp
, Py_SIZE(seq
)))
1339 while (_PyDict_Next(seq
, &pos
, &key
, &oldvalue
, &hash
)) {
1342 if (insertdict(mp
, key
, hash
, value
))
1348 if (PyDict_CheckExact(d
) && PyAnySet_CheckExact(seq
)) {
1349 PyDictObject
*mp
= (PyDictObject
*)d
;
1354 if (dictresize(mp
, PySet_GET_SIZE(seq
)))
1357 while (_PySet_NextEntry(seq
, &pos
, &key
, &hash
)) {
1360 if (insertdict(mp
, key
, hash
, value
))
1366 it
= PyObject_GetIter(seq
);
1372 if (PyDict_CheckExact(d
)) {
1373 while ((key
= PyIter_Next(it
)) != NULL
) {
1374 status
= PyDict_SetItem(d
, key
, value
);
1380 while ((key
= PyIter_Next(it
)) != NULL
) {
1381 status
= PyObject_SetItem(d
, key
, value
);
1388 if (PyErr_Occurred())
1400 dict_update_common(PyObject
*self
, PyObject
*args
, PyObject
*kwds
, char *methname
)
1402 PyObject
*arg
= NULL
;
1405 if (!PyArg_UnpackTuple(args
, methname
, 0, 1, &arg
))
1408 else if (arg
!= NULL
) {
1409 if (PyObject_HasAttrString(arg
, "keys"))
1410 result
= PyDict_Merge(self
, arg
, 1);
1412 result
= PyDict_MergeFromSeq2(self
, arg
, 1);
1414 if (result
== 0 && kwds
!= NULL
)
1415 result
= PyDict_Merge(self
, kwds
, 1);
1420 dict_update(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
1422 if (dict_update_common(self
, args
, kwds
, "update") != -1)
1427 /* Update unconditionally replaces existing items.
1428 Merge has a 3rd argument 'override'; if set, it acts like Update,
1429 otherwise it leaves existing items unchanged.
1431 PyDict_{Update,Merge} update/merge from a mapping object.
1433 PyDict_MergeFromSeq2 updates/merges from any iterable object
1434 producing iterable objects of length 2.
1438 PyDict_MergeFromSeq2(PyObject
*d
, PyObject
*seq2
, int override
)
1440 PyObject
*it
; /* iter(seq2) */
1441 Py_ssize_t i
; /* index into seq2 of current element */
1442 PyObject
*item
; /* seq2[i] */
1443 PyObject
*fast
; /* item as a 2-tuple or 2-list */
1446 assert(PyDict_Check(d
));
1447 assert(seq2
!= NULL
);
1449 it
= PyObject_GetIter(seq2
);
1453 for (i
= 0; ; ++i
) {
1454 PyObject
*key
, *value
;
1458 item
= PyIter_Next(it
);
1460 if (PyErr_Occurred())
1465 /* Convert item to sequence, and verify length 2. */
1466 fast
= PySequence_Fast(item
, "");
1468 if (PyErr_ExceptionMatches(PyExc_TypeError
))
1469 PyErr_Format(PyExc_TypeError
,
1470 "cannot convert dictionary update "
1471 "sequence element #%zd to a sequence",
1475 n
= PySequence_Fast_GET_SIZE(fast
);
1477 PyErr_Format(PyExc_ValueError
,
1478 "dictionary update sequence element #%zd "
1479 "has length %zd; 2 is required",
1484 /* Update/merge with this (key, value) pair. */
1485 key
= PySequence_Fast_GET_ITEM(fast
, 0);
1486 value
= PySequence_Fast_GET_ITEM(fast
, 1);
1487 if (override
|| PyDict_GetItem(d
, key
) == NULL
) {
1488 int status
= PyDict_SetItem(d
, key
, value
);
1504 return Py_SAFE_DOWNCAST(i
, Py_ssize_t
, int);
1508 PyDict_Update(PyObject
*a
, PyObject
*b
)
1510 return PyDict_Merge(a
, b
, 1);
1514 PyDict_Merge(PyObject
*a
, PyObject
*b
, int override
)
1516 register PyDictObject
*mp
, *other
;
1517 register Py_ssize_t i
;
1520 /* We accept for the argument either a concrete dictionary object,
1521 * or an abstract "mapping" object. For the former, we can do
1522 * things quite efficiently. For the latter, we only require that
1523 * PyMapping_Keys() and PyObject_GetItem() be supported.
1525 if (a
== NULL
|| !PyDict_Check(a
) || b
== NULL
) {
1526 PyErr_BadInternalCall();
1529 mp
= (PyDictObject
*)a
;
1530 if (PyDict_Check(b
)) {
1531 other
= (PyDictObject
*)b
;
1532 if (other
== mp
|| other
->ma_used
== 0)
1533 /* a.update(a) or a.update({}); nothing to do */
1535 if (mp
->ma_used
== 0)
1536 /* Since the target dict is empty, PyDict_GetItem()
1537 * always returns NULL. Setting override to 1
1538 * skips the unnecessary test.
1541 /* Do one big resize at the start, rather than
1542 * incrementally resizing as we insert new items. Expect
1543 * that there will be no (or few) overlapping keys.
1545 if ((mp
->ma_fill
+ other
->ma_used
)*3 >= (mp
->ma_mask
+1)*2) {
1546 if (dictresize(mp
, (mp
->ma_used
+ other
->ma_used
)*2) != 0)
1549 for (i
= 0; i
<= other
->ma_mask
; i
++) {
1550 entry
= &other
->ma_table
[i
];
1551 if (entry
->me_value
!= NULL
&&
1553 PyDict_GetItem(a
, entry
->me_key
) == NULL
)) {
1554 Py_INCREF(entry
->me_key
);
1555 Py_INCREF(entry
->me_value
);
1556 if (insertdict(mp
, entry
->me_key
,
1557 (long)entry
->me_hash
,
1558 entry
->me_value
) != 0)
1564 /* Do it the generic, slower way */
1565 PyObject
*keys
= PyMapping_Keys(b
);
1567 PyObject
*key
, *value
;
1571 /* Docstring says this is equivalent to E.keys() so
1572 * if E doesn't have a .keys() method we want
1573 * AttributeError to percolate up. Might as well
1574 * do the same for any other error.
1578 iter
= PyObject_GetIter(keys
);
1583 for (key
= PyIter_Next(iter
); key
; key
= PyIter_Next(iter
)) {
1584 if (!override
&& PyDict_GetItem(a
, key
) != NULL
) {
1588 value
= PyObject_GetItem(b
, key
);
1589 if (value
== NULL
) {
1594 status
= PyDict_SetItem(a
, key
, value
);
1603 if (PyErr_Occurred())
1604 /* Iterator completed, via error */
1611 dict_copy(register PyDictObject
*mp
)
1613 return PyDict_Copy((PyObject
*)mp
);
1617 PyDict_Copy(PyObject
*o
)
1621 if (o
== NULL
|| !PyDict_Check(o
)) {
1622 PyErr_BadInternalCall();
1625 copy
= PyDict_New();
1628 if (PyDict_Merge(copy
, o
, 1) == 0)
1635 PyDict_Size(PyObject
*mp
)
1637 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1638 PyErr_BadInternalCall();
1641 return ((PyDictObject
*)mp
)->ma_used
;
1645 PyDict_Keys(PyObject
*mp
)
1647 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1648 PyErr_BadInternalCall();
1651 return dict_keys((PyDictObject
*)mp
);
1655 PyDict_Values(PyObject
*mp
)
1657 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1658 PyErr_BadInternalCall();
1661 return dict_values((PyDictObject
*)mp
);
1665 PyDict_Items(PyObject
*mp
)
1667 if (mp
== NULL
|| !PyDict_Check(mp
)) {
1668 PyErr_BadInternalCall();
1671 return dict_items((PyDictObject
*)mp
);
1674 /* Subroutine which returns the smallest key in a for which b's value
1675 is different or absent. The value is returned too, through the
1676 pval argument. Both are NULL if no key in a is found for which b's status
1677 differs. The refcounts on (and only on) non-NULL *pval and function return
1678 values must be decremented by the caller (characterize() increments them
1679 to ensure that mutating comparison and PyDict_GetItem calls can't delete
1680 them before the caller is done looking at them). */
1683 characterize(PyDictObject
*a
, PyDictObject
*b
, PyObject
**pval
)
1685 PyObject
*akey
= NULL
; /* smallest key in a s.t. a[akey] != b[akey] */
1686 PyObject
*aval
= NULL
; /* a[akey] */
1690 for (i
= 0; i
<= a
->ma_mask
; i
++) {
1691 PyObject
*thiskey
, *thisaval
, *thisbval
;
1692 if (a
->ma_table
[i
].me_value
== NULL
)
1694 thiskey
= a
->ma_table
[i
].me_key
;
1695 Py_INCREF(thiskey
); /* keep alive across compares */
1697 cmp
= PyObject_RichCompareBool(akey
, thiskey
, Py_LT
);
1704 a
->ma_table
[i
].me_value
== NULL
)
1706 /* Not the *smallest* a key; or maybe it is
1707 * but the compare shrunk the dict so we can't
1708 * find its associated value anymore; or
1709 * maybe it is but the compare deleted the
1717 /* Compare a[thiskey] to b[thiskey]; cmp <- true iff equal. */
1718 thisaval
= a
->ma_table
[i
].me_value
;
1720 Py_INCREF(thisaval
); /* keep alive */
1721 thisbval
= PyDict_GetItem((PyObject
*)b
, thiskey
);
1722 if (thisbval
== NULL
)
1725 /* both dicts have thiskey: same values? */
1726 cmp
= PyObject_RichCompareBool(
1727 thisaval
, thisbval
, Py_EQ
);
1730 Py_DECREF(thisaval
);
1743 Py_DECREF(thisaval
);
1757 dict_compare(PyDictObject
*a
, PyDictObject
*b
)
1759 PyObject
*adiff
, *bdiff
, *aval
, *bval
;
1762 /* Compare lengths first */
1763 if (a
->ma_used
< b
->ma_used
)
1764 return -1; /* a is shorter */
1765 else if (a
->ma_used
> b
->ma_used
)
1766 return 1; /* b is shorter */
1768 /* Same length -- check all keys */
1769 bdiff
= bval
= NULL
;
1770 adiff
= characterize(a
, b
, &aval
);
1771 if (adiff
== NULL
) {
1773 /* Either an error, or a is a subset with the same length so
1776 res
= PyErr_Occurred() ? -1 : 0;
1779 bdiff
= characterize(b
, a
, &bval
);
1780 if (bdiff
== NULL
&& PyErr_Occurred()) {
1787 /* bdiff == NULL "should be" impossible now, but perhaps
1788 * the last comparison done by the characterize() on a had
1789 * the side effect of making the dicts equal!
1791 res
= PyObject_Compare(adiff
, bdiff
);
1793 if (res
== 0 && bval
!= NULL
)
1794 res
= PyObject_Compare(aval
, bval
);
1804 /* Return 1 if dicts equal, 0 if not, -1 if error.
1805 * Gets out as soon as any difference is detected.
1806 * Uses only Py_EQ comparison.
1809 dict_equal(PyDictObject
*a
, PyDictObject
*b
)
1813 if (a
->ma_used
!= b
->ma_used
)
1814 /* can't be equal if # of entries differ */
1817 /* Same # of entries -- check all of 'em. Exit early on any diff. */
1818 for (i
= 0; i
<= a
->ma_mask
; i
++) {
1819 PyObject
*aval
= a
->ma_table
[i
].me_value
;
1823 PyObject
*key
= a
->ma_table
[i
].me_key
;
1824 /* temporarily bump aval's refcount to ensure it stays
1825 alive until we're done with it */
1829 bval
= PyDict_GetItem((PyObject
*)b
, key
);
1835 cmp
= PyObject_RichCompareBool(aval
, bval
, Py_EQ
);
1837 if (cmp
<= 0) /* error or not equal */
1845 dict_richcompare(PyObject
*v
, PyObject
*w
, int op
)
1850 if (!PyDict_Check(v
) || !PyDict_Check(w
)) {
1851 res
= Py_NotImplemented
;
1853 else if (op
== Py_EQ
|| op
== Py_NE
) {
1854 cmp
= dict_equal((PyDictObject
*)v
, (PyDictObject
*)w
);
1857 res
= (cmp
== (op
== Py_EQ
)) ? Py_True
: Py_False
;
1860 /* Py3K warning if comparison isn't == or != */
1861 if (PyErr_WarnPy3k("dict inequality comparisons not supported "
1865 res
= Py_NotImplemented
;
1872 dict_contains(register PyDictObject
*mp
, PyObject
*key
)
1877 if (!PyString_CheckExact(key
) ||
1878 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
1879 hash
= PyObject_Hash(key
);
1883 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1886 return PyBool_FromLong(ep
->me_value
!= NULL
);
1890 dict_has_key(register PyDictObject
*mp
, PyObject
*key
)
1892 if (PyErr_WarnPy3k("dict.has_key() not supported in 3.x; "
1893 "use the in operator", 1) < 0)
1895 return dict_contains(mp
, key
);
1899 dict_get(register PyDictObject
*mp
, PyObject
*args
)
1902 PyObject
*failobj
= Py_None
;
1903 PyObject
*val
= NULL
;
1907 if (!PyArg_UnpackTuple(args
, "get", 1, 2, &key
, &failobj
))
1910 if (!PyString_CheckExact(key
) ||
1911 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
1912 hash
= PyObject_Hash(key
);
1916 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1928 dict_setdefault(register PyDictObject
*mp
, PyObject
*args
)
1931 PyObject
*failobj
= Py_None
;
1932 PyObject
*val
= NULL
;
1936 if (!PyArg_UnpackTuple(args
, "setdefault", 1, 2, &key
, &failobj
))
1939 if (!PyString_CheckExact(key
) ||
1940 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
1941 hash
= PyObject_Hash(key
);
1945 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1951 if (PyDict_SetItem((PyObject
*)mp
, key
, failobj
))
1960 dict_clear(register PyDictObject
*mp
)
1962 PyDict_Clear((PyObject
*)mp
);
1967 dict_pop(PyDictObject
*mp
, PyObject
*args
)
1971 PyObject
*old_value
, *old_key
;
1972 PyObject
*key
, *deflt
= NULL
;
1974 if(!PyArg_UnpackTuple(args
, "pop", 1, 2, &key
, &deflt
))
1976 if (mp
->ma_used
== 0) {
1981 PyErr_SetString(PyExc_KeyError
,
1982 "pop(): dictionary is empty");
1985 if (!PyString_CheckExact(key
) ||
1986 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
1987 hash
= PyObject_Hash(key
);
1991 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
1994 if (ep
->me_value
== NULL
) {
2002 old_key
= ep
->me_key
;
2005 old_value
= ep
->me_value
;
2006 ep
->me_value
= NULL
;
2013 dict_popitem(PyDictObject
*mp
)
2019 /* Allocate the result tuple before checking the size. Believe it
2020 * or not, this allocation could trigger a garbage collection which
2021 * could empty the dict, so if we checked the size first and that
2022 * happened, the result would be an infinite loop (searching for an
2023 * entry that no longer exists). Note that the usual popitem()
2024 * idiom is "while d: k, v = d.popitem()". so needing to throw the
2025 * tuple away if the dict *is* empty isn't a significant
2026 * inefficiency -- possible, but unlikely in practice.
2028 res
= PyTuple_New(2);
2031 if (mp
->ma_used
== 0) {
2033 PyErr_SetString(PyExc_KeyError
,
2034 "popitem(): dictionary is empty");
2037 /* Set ep to "the first" dict entry with a value. We abuse the hash
2038 * field of slot 0 to hold a search finger:
2039 * If slot 0 has a value, use slot 0.
2040 * Else slot 0 is being used to hold a search finger,
2041 * and we use its hash value as the first index to look.
2043 ep
= &mp
->ma_table
[0];
2044 if (ep
->me_value
== NULL
) {
2046 /* The hash field may be a real hash value, or it may be a
2047 * legit search finger, or it may be a once-legit search
2048 * finger that's out of bounds now because it wrapped around
2049 * or the table shrunk -- simply make sure it's in bounds now.
2051 if (i
> mp
->ma_mask
|| i
< 1)
2052 i
= 1; /* skip slot 0 */
2053 while ((ep
= &mp
->ma_table
[i
])->me_value
== NULL
) {
2055 if (i
> mp
->ma_mask
)
2059 PyTuple_SET_ITEM(res
, 0, ep
->me_key
);
2060 PyTuple_SET_ITEM(res
, 1, ep
->me_value
);
2063 ep
->me_value
= NULL
;
2065 assert(mp
->ma_table
[0].me_value
== NULL
);
2066 mp
->ma_table
[0].me_hash
= i
+ 1; /* next place to start */
2071 dict_traverse(PyObject
*op
, visitproc visit
, void *arg
)
2077 while (PyDict_Next(op
, &i
, &pk
, &pv
)) {
2085 dict_tp_clear(PyObject
*op
)
2092 extern PyTypeObject PyDictIterKey_Type
; /* Forward */
2093 extern PyTypeObject PyDictIterValue_Type
; /* Forward */
2094 extern PyTypeObject PyDictIterItem_Type
; /* Forward */
2095 static PyObject
*dictiter_new(PyDictObject
*, PyTypeObject
*);
2098 dict_iterkeys(PyDictObject
*dict
)
2100 return dictiter_new(dict
, &PyDictIterKey_Type
);
2104 dict_itervalues(PyDictObject
*dict
)
2106 return dictiter_new(dict
, &PyDictIterValue_Type
);
2110 dict_iteritems(PyDictObject
*dict
)
2112 return dictiter_new(dict
, &PyDictIterItem_Type
);
2116 dict_sizeof(PyDictObject
*mp
)
2120 res
= sizeof(PyDictObject
);
2121 if (mp
->ma_table
!= mp
->ma_smalltable
)
2122 res
= res
+ (mp
->ma_mask
+ 1) * sizeof(PyDictEntry
);
2123 return PyInt_FromSsize_t(res
);
2126 PyDoc_STRVAR(has_key__doc__
,
2127 "D.has_key(k) -> True if D has a key k, else False");
2129 PyDoc_STRVAR(contains__doc__
,
2130 "D.__contains__(k) -> True if D has a key k, else False");
2132 PyDoc_STRVAR(getitem__doc__
, "x.__getitem__(y) <==> x[y]");
2134 PyDoc_STRVAR(sizeof__doc__
,
2135 "D.__sizeof__() -> size of D in memory, in bytes");
2137 PyDoc_STRVAR(get__doc__
,
2138 "D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.");
2140 PyDoc_STRVAR(setdefault_doc__
,
2141 "D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D");
2143 PyDoc_STRVAR(pop__doc__
,
2144 "D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
2145 If key is not found, d is returned if given, otherwise KeyError is raised");
2147 PyDoc_STRVAR(popitem__doc__
,
2148 "D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
2149 2-tuple; but raise KeyError if D is empty.");
2151 PyDoc_STRVAR(keys__doc__
,
2152 "D.keys() -> list of D's keys");
2154 PyDoc_STRVAR(items__doc__
,
2155 "D.items() -> list of D's (key, value) pairs, as 2-tuples");
2157 PyDoc_STRVAR(values__doc__
,
2158 "D.values() -> list of D's values");
2160 PyDoc_STRVAR(update__doc__
,
2161 "D.update(E, **F) -> None. Update D from dict/iterable E and F.\n"
2162 "If E has a .keys() method, does: for k in E: D[k] = E[k]\n\
2163 If E lacks .keys() method, does: for (k, v) in E: D[k] = v\n\
2164 In either case, this is followed by: for k in F: D[k] = F[k]");
2166 PyDoc_STRVAR(fromkeys__doc__
,
2167 "dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v.\n\
2168 v defaults to None.");
2170 PyDoc_STRVAR(clear__doc__
,
2171 "D.clear() -> None. Remove all items from D.");
2173 PyDoc_STRVAR(copy__doc__
,
2174 "D.copy() -> a shallow copy of D");
2176 PyDoc_STRVAR(iterkeys__doc__
,
2177 "D.iterkeys() -> an iterator over the keys of D");
2179 PyDoc_STRVAR(itervalues__doc__
,
2180 "D.itervalues() -> an iterator over the values of D");
2182 PyDoc_STRVAR(iteritems__doc__
,
2183 "D.iteritems() -> an iterator over the (key, value) items of D");
2185 static PyMethodDef mapp_methods
[] = {
2186 {"__contains__",(PyCFunction
)dict_contains
, METH_O
| METH_COEXIST
,
2188 {"__getitem__", (PyCFunction
)dict_subscript
, METH_O
| METH_COEXIST
,
2190 {"__sizeof__", (PyCFunction
)dict_sizeof
, METH_NOARGS
,
2192 {"has_key", (PyCFunction
)dict_has_key
, METH_O
,
2194 {"get", (PyCFunction
)dict_get
, METH_VARARGS
,
2196 {"setdefault", (PyCFunction
)dict_setdefault
, METH_VARARGS
,
2198 {"pop", (PyCFunction
)dict_pop
, METH_VARARGS
,
2200 {"popitem", (PyCFunction
)dict_popitem
, METH_NOARGS
,
2202 {"keys", (PyCFunction
)dict_keys
, METH_NOARGS
,
2204 {"items", (PyCFunction
)dict_items
, METH_NOARGS
,
2206 {"values", (PyCFunction
)dict_values
, METH_NOARGS
,
2208 {"update", (PyCFunction
)dict_update
, METH_VARARGS
| METH_KEYWORDS
,
2210 {"fromkeys", (PyCFunction
)dict_fromkeys
, METH_VARARGS
| METH_CLASS
,
2212 {"clear", (PyCFunction
)dict_clear
, METH_NOARGS
,
2214 {"copy", (PyCFunction
)dict_copy
, METH_NOARGS
,
2216 {"iterkeys", (PyCFunction
)dict_iterkeys
, METH_NOARGS
,
2218 {"itervalues", (PyCFunction
)dict_itervalues
, METH_NOARGS
,
2220 {"iteritems", (PyCFunction
)dict_iteritems
, METH_NOARGS
,
2222 {NULL
, NULL
} /* sentinel */
2225 /* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
2227 PyDict_Contains(PyObject
*op
, PyObject
*key
)
2230 PyDictObject
*mp
= (PyDictObject
*)op
;
2233 if (!PyString_CheckExact(key
) ||
2234 (hash
= ((PyStringObject
*) key
)->ob_shash
) == -1) {
2235 hash
= PyObject_Hash(key
);
2239 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
2240 return ep
== NULL
? -1 : (ep
->me_value
!= NULL
);
2243 /* Internal version of PyDict_Contains used when the hash value is already known */
2245 _PyDict_Contains(PyObject
*op
, PyObject
*key
, long hash
)
2247 PyDictObject
*mp
= (PyDictObject
*)op
;
2250 ep
= (mp
->ma_lookup
)(mp
, key
, hash
);
2251 return ep
== NULL
? -1 : (ep
->me_value
!= NULL
);
2254 /* Hack to implement "key in dict" */
2255 static PySequenceMethods dict_as_sequence
= {
2261 0, /* sq_ass_item */
2262 0, /* sq_ass_slice */
2263 PyDict_Contains
, /* sq_contains */
2264 0, /* sq_inplace_concat */
2265 0, /* sq_inplace_repeat */
2269 dict_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
2273 assert(type
!= NULL
&& type
->tp_alloc
!= NULL
);
2274 self
= type
->tp_alloc(type
, 0);
2276 PyDictObject
*d
= (PyDictObject
*)self
;
2277 /* It's guaranteed that tp->alloc zeroed out the struct. */
2278 assert(d
->ma_table
== NULL
&& d
->ma_fill
== 0 && d
->ma_used
== 0);
2279 INIT_NONZERO_DICT_SLOTS(d
);
2280 d
->ma_lookup
= lookdict_string
;
2281 /* The object has been implicitely tracked by tp_alloc */
2282 if (type
== &PyDict_Type
)
2283 _PyObject_GC_UNTRACK(d
);
2284 #ifdef SHOW_CONVERSION_COUNTS
2287 #ifdef SHOW_TRACK_COUNT
2288 if (_PyObject_GC_IS_TRACKED(d
))
2298 dict_init(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
2300 return dict_update_common(self
, args
, kwds
, "dict");
2304 dict_iter(PyDictObject
*dict
)
2306 return dictiter_new(dict
, &PyDictIterKey_Type
);
2309 PyDoc_STRVAR(dictionary_doc
,
2310 "dict() -> new empty dictionary.\n"
2311 "dict(mapping) -> new dictionary initialized from a mapping object's\n"
2312 " (key, value) pairs.\n"
2313 "dict(seq) -> new dictionary initialized as if via:\n"
2315 " for k, v in seq:\n"
2317 "dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
2318 " in the keyword argument list. For example: dict(one=1, two=2)");
2320 PyTypeObject PyDict_Type
= {
2321 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2323 sizeof(PyDictObject
),
2325 (destructor
)dict_dealloc
, /* tp_dealloc */
2326 (printfunc
)dict_print
, /* tp_print */
2329 (cmpfunc
)dict_compare
, /* tp_compare */
2330 (reprfunc
)dict_repr
, /* tp_repr */
2331 0, /* tp_as_number */
2332 &dict_as_sequence
, /* tp_as_sequence */
2333 &dict_as_mapping
, /* tp_as_mapping */
2334 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2337 PyObject_GenericGetAttr
, /* tp_getattro */
2338 0, /* tp_setattro */
2339 0, /* tp_as_buffer */
2340 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2341 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_DICT_SUBCLASS
, /* tp_flags */
2342 dictionary_doc
, /* tp_doc */
2343 dict_traverse
, /* tp_traverse */
2344 dict_tp_clear
, /* tp_clear */
2345 dict_richcompare
, /* tp_richcompare */
2346 0, /* tp_weaklistoffset */
2347 (getiterfunc
)dict_iter
, /* tp_iter */
2348 0, /* tp_iternext */
2349 mapp_methods
, /* tp_methods */
2354 0, /* tp_descr_get */
2355 0, /* tp_descr_set */
2356 0, /* tp_dictoffset */
2357 dict_init
, /* tp_init */
2358 PyType_GenericAlloc
, /* tp_alloc */
2359 dict_new
, /* tp_new */
2360 PyObject_GC_Del
, /* tp_free */
2363 /* For backward compatibility with old dictionary interface */
2366 PyDict_GetItemString(PyObject
*v
, const char *key
)
2369 kv
= PyString_FromString(key
);
2372 rv
= PyDict_GetItem(v
, kv
);
2378 PyDict_SetItemString(PyObject
*v
, const char *key
, PyObject
*item
)
2382 kv
= PyString_FromString(key
);
2385 PyString_InternInPlace(&kv
); /* XXX Should we really? */
2386 err
= PyDict_SetItem(v
, kv
, item
);
2392 PyDict_DelItemString(PyObject
*v
, const char *key
)
2396 kv
= PyString_FromString(key
);
2399 err
= PyDict_DelItem(v
, kv
);
2404 /* Dictionary iterator types */
2408 PyDictObject
*di_dict
; /* Set to NULL when iterator is exhausted */
2411 PyObject
* di_result
; /* reusable result tuple for iteritems */
2416 dictiter_new(PyDictObject
*dict
, PyTypeObject
*itertype
)
2419 di
= PyObject_GC_New(dictiterobject
, itertype
);
2424 di
->di_used
= dict
->ma_used
;
2426 di
->len
= dict
->ma_used
;
2427 if (itertype
== &PyDictIterItem_Type
) {
2428 di
->di_result
= PyTuple_Pack(2, Py_None
, Py_None
);
2429 if (di
->di_result
== NULL
) {
2435 di
->di_result
= NULL
;
2436 _PyObject_GC_TRACK(di
);
2437 return (PyObject
*)di
;
2441 dictiter_dealloc(dictiterobject
*di
)
2443 Py_XDECREF(di
->di_dict
);
2444 Py_XDECREF(di
->di_result
);
2445 PyObject_GC_Del(di
);
2449 dictiter_traverse(dictiterobject
*di
, visitproc visit
, void *arg
)
2451 Py_VISIT(di
->di_dict
);
2452 Py_VISIT(di
->di_result
);
2457 dictiter_len(dictiterobject
*di
)
2460 if (di
->di_dict
!= NULL
&& di
->di_used
== di
->di_dict
->ma_used
)
2462 return PyInt_FromSize_t(len
);
2465 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2467 static PyMethodDef dictiter_methods
[] = {
2468 {"__length_hint__", (PyCFunction
)dictiter_len
, METH_NOARGS
, length_hint_doc
},
2469 {NULL
, NULL
} /* sentinel */
2472 static PyObject
*dictiter_iternextkey(dictiterobject
*di
)
2475 register Py_ssize_t i
, mask
;
2476 register PyDictEntry
*ep
;
2477 PyDictObject
*d
= di
->di_dict
;
2481 assert (PyDict_Check(d
));
2483 if (di
->di_used
!= d
->ma_used
) {
2484 PyErr_SetString(PyExc_RuntimeError
,
2485 "dictionary changed size during iteration");
2486 di
->di_used
= -1; /* Make this state sticky */
2495 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
2511 PyTypeObject PyDictIterKey_Type
= {
2512 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2513 "dictionary-keyiterator", /* tp_name */
2514 sizeof(dictiterobject
), /* tp_basicsize */
2515 0, /* tp_itemsize */
2517 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2523 0, /* tp_as_number */
2524 0, /* tp_as_sequence */
2525 0, /* tp_as_mapping */
2529 PyObject_GenericGetAttr
, /* tp_getattro */
2530 0, /* tp_setattro */
2531 0, /* tp_as_buffer */
2532 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2534 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2536 0, /* tp_richcompare */
2537 0, /* tp_weaklistoffset */
2538 PyObject_SelfIter
, /* tp_iter */
2539 (iternextfunc
)dictiter_iternextkey
, /* tp_iternext */
2540 dictiter_methods
, /* tp_methods */
2544 static PyObject
*dictiter_iternextvalue(dictiterobject
*di
)
2547 register Py_ssize_t i
, mask
;
2548 register PyDictEntry
*ep
;
2549 PyDictObject
*d
= di
->di_dict
;
2553 assert (PyDict_Check(d
));
2555 if (di
->di_used
!= d
->ma_used
) {
2556 PyErr_SetString(PyExc_RuntimeError
,
2557 "dictionary changed size during iteration");
2558 di
->di_used
= -1; /* Make this state sticky */
2564 if (i
< 0 || i
> mask
)
2567 while ((value
=ep
[i
].me_value
) == NULL
) {
2583 PyTypeObject PyDictIterValue_Type
= {
2584 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2585 "dictionary-valueiterator", /* tp_name */
2586 sizeof(dictiterobject
), /* tp_basicsize */
2587 0, /* tp_itemsize */
2589 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2595 0, /* tp_as_number */
2596 0, /* tp_as_sequence */
2597 0, /* tp_as_mapping */
2601 PyObject_GenericGetAttr
, /* tp_getattro */
2602 0, /* tp_setattro */
2603 0, /* tp_as_buffer */
2604 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2606 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2608 0, /* tp_richcompare */
2609 0, /* tp_weaklistoffset */
2610 PyObject_SelfIter
, /* tp_iter */
2611 (iternextfunc
)dictiter_iternextvalue
, /* tp_iternext */
2612 dictiter_methods
, /* tp_methods */
2616 static PyObject
*dictiter_iternextitem(dictiterobject
*di
)
2618 PyObject
*key
, *value
, *result
= di
->di_result
;
2619 register Py_ssize_t i
, mask
;
2620 register PyDictEntry
*ep
;
2621 PyDictObject
*d
= di
->di_dict
;
2625 assert (PyDict_Check(d
));
2627 if (di
->di_used
!= d
->ma_used
) {
2628 PyErr_SetString(PyExc_RuntimeError
,
2629 "dictionary changed size during iteration");
2630 di
->di_used
= -1; /* Make this state sticky */
2639 while (i
<= mask
&& ep
[i
].me_value
== NULL
)
2645 if (result
->ob_refcnt
== 1) {
2647 Py_DECREF(PyTuple_GET_ITEM(result
, 0));
2648 Py_DECREF(PyTuple_GET_ITEM(result
, 1));
2650 result
= PyTuple_New(2);
2656 value
= ep
[i
].me_value
;
2659 PyTuple_SET_ITEM(result
, 0, key
);
2660 PyTuple_SET_ITEM(result
, 1, value
);
2669 PyTypeObject PyDictIterItem_Type
= {
2670 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2671 "dictionary-itemiterator", /* tp_name */
2672 sizeof(dictiterobject
), /* tp_basicsize */
2673 0, /* tp_itemsize */
2675 (destructor
)dictiter_dealloc
, /* tp_dealloc */
2681 0, /* tp_as_number */
2682 0, /* tp_as_sequence */
2683 0, /* tp_as_mapping */
2687 PyObject_GenericGetAttr
, /* tp_getattro */
2688 0, /* tp_setattro */
2689 0, /* tp_as_buffer */
2690 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2692 (traverseproc
)dictiter_traverse
, /* tp_traverse */
2694 0, /* tp_richcompare */
2695 0, /* tp_weaklistoffset */
2696 PyObject_SelfIter
, /* tp_iter */
2697 (iternextfunc
)dictiter_iternextitem
, /* tp_iternext */
2698 dictiter_methods
, /* tp_methods */