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