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