1 /* Ordered Dictionary object implementation.
2
3 This implementation is necessarily explicitly equivalent to the pure Python
4 OrderedDict class in Lib/collections/__init__.py. The strategy there
5 involves using a doubly-linked-list to capture the order. We keep to that
6 strategy, using a lower-level linked-list.
7
8 About the Linked-List
9 =====================
10
11 For the linked list we use a basic doubly-linked-list. Using a circularly-
12 linked-list does have some benefits, but they don't apply so much here
13 since OrderedDict is focused on the ends of the list (for the most part).
14 Furthermore, there are some features of generic linked-lists that we simply
15 don't need for OrderedDict. Thus a simple custom implementation meets our
16 needs. Alternatives to our simple approach include the QCIRCLE_*
17 macros from BSD's queue.h, and the linux's list.h.
18
19 Getting O(1) Node Lookup
20 ------------------------
21
22 One invariant of Python's OrderedDict is that it preserves time complexity
23 of dict's methods, particularly the O(1) operations. Simply adding a
24 linked-list on top of dict is not sufficient here; operations for nodes in
25 the middle of the linked-list implicitly require finding the node first.
26 With a simple linked-list like we're using, that is an O(n) operation.
27 Consequently, methods like __delitem__() would change from O(1) to O(n),
28 which is unacceptable.
29
30 In order to preserve O(1) performance for node removal (finding nodes), we
31 must do better than just looping through the linked-list. Here are options
32 we've considered:
33
34 1. use a second dict to map keys to nodes (a la the pure Python version).
35 2. keep a simple hash table mirroring the order of dict's, mapping each key
36 to the corresponding node in the linked-list.
37 3. use a version of shared keys (split dict) that allows non-unicode keys.
38 4. have the value stored for each key be a (value, node) pair, and adjust
39 __getitem__(), get(), etc. accordingly.
40
41 The approach with the least performance impact (time and space) is #2,
42 mirroring the key order of dict's dk_entries with an array of node pointers.
43 While lookdict() and friends (dk_lookup) don't give us the index into the
44 array, we make use of pointer arithmetic to get that index. An alternative
45 would be to refactor lookdict() to provide the index, explicitly exposing
46 the implementation detail. We could even just use a custom lookup function
47 for OrderedDict that facilitates our need. However, both approaches are
48 significantly more complicated than just using pointer arithmetic.
49
50 The catch with mirroring the hash table ordering is that we have to keep
51 the ordering in sync through any dict resizes. However, that order only
52 matters during node lookup. We can simply defer any potential resizing
53 until we need to do a lookup.
54
55 Linked-List Nodes
56 -----------------
57
58 The current implementation stores a pointer to the associated key only.
59 One alternative would be to store a pointer to the PyDictKeyEntry instead.
60 This would save one pointer de-reference per item, which is nice during
61 calls to values() and items(). However, it adds unnecessary overhead
62 otherwise, so we stick with just the key.
63
64 Linked-List API
65 ---------------
66
67 As noted, the linked-list implemented here does not have all the bells and
68 whistles. However, we recognize that the implementation may need to
69 change to accommodate performance improvements or extra functionality. To
70 that end, we use a simple API to interact with the linked-list. Here's a
71 summary of the methods/macros:
72
73 Node info:
74
75 * _odictnode_KEY(node)
76 * _odictnode_VALUE(od, node)
77 * _odictnode_PREV(node)
78 * _odictnode_NEXT(node)
79
80 Linked-List info:
81
82 * _odict_FIRST(od)
83 * _odict_LAST(od)
84 * _odict_EMPTY(od)
85 * _odict_FOREACH(od, node) - used in place of `for (node=...)`
86
87 For adding nodes:
88
89 * _odict_add_head(od, node)
90 * _odict_add_tail(od, node)
91 * _odict_add_new_node(od, key, hash)
92
93 For removing nodes:
94
95 * _odict_clear_node(od, node, key, hash)
96 * _odict_clear_nodes(od, clear_each)
97
98 Others:
99
100 * _odict_find_node_hash(od, key, hash)
101 * _odict_find_node(od, key)
102 * _odict_keys_equal(od1, od2)
103
104 And here's a look at how the linked-list relates to the OrderedDict API:
105
106 ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
107 method key val prev next mem 1st last empty iter find add rmv clr keq
108 ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
109 __del__ ~ X
110 __delitem__ free ~ node
111 __eq__ ~ X
112 __iter__ X X
113 __new__ X X
114 __reduce__ X ~ X
115 __repr__ X X X
116 __reversed__ X X
117 __setitem__ key
118 __sizeof__ size X
119 clear ~ ~ X
120 copy X X X
121 items X X X
122 keys X X
123 move_to_end X X X ~ h/t key
124 pop free key
125 popitem X X free X X node
126 setdefault ~ ? ~
127 values X X
128 ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
129
130 __delitem__ is the only method that directly relies on finding an arbitrary
131 node in the linked-list. Everything else is iteration or relates to the
132 ends of the linked-list.
133
134 Situation that Endangers Consistency
135 ------------------------------------
136 Using a raw linked-list for OrderedDict exposes a key situation that can
137 cause problems. If a node is stored in a variable, there is a chance that
138 the node may have been deallocated before the variable gets used, thus
139 potentially leading to a segmentation fault. A key place where this shows
140 up is during iteration through the linked list (via _odict_FOREACH or
141 otherwise).
142
143 A number of solutions are available to resolve this situation:
144
145 * defer looking up the node until as late as possible and certainly after
146 any code that could possibly result in a deletion;
147 * if the node is needed both before and after a point where the node might
148 be removed, do a check before using the node at the "after" location to
149 see if the node is still valid;
150 * like the last one, but simply pull the node again to ensure it's right;
151 * keep the key in the variable instead of the node and then look up the
152 node using the key at the point where the node is needed (this is what
153 we do for the iterators).
154
155 Another related problem, preserving consistent ordering during iteration,
156 is described below. That one is not exclusive to using linked-lists.
157
158
159 Challenges from Subclassing dict
160 ================================
161
162 OrderedDict subclasses dict, which is an unusual relationship between two
163 builtin types (other than the base object type). Doing so results in
164 some complication and deserves further explanation. There are two things
165 to consider here. First, in what circumstances or with what adjustments
166 can OrderedDict be used as a drop-in replacement for dict (at the C level)?
167 Second, how can the OrderedDict implementation leverage the dict
168 implementation effectively without introducing unnecessary coupling or
169 inefficiencies?
170
171 This second point is reflected here and in the implementation, so the
172 further focus is on the first point. It is worth noting that for
173 overridden methods, the dict implementation is deferred to as much as
174 possible. Furthermore, coupling is limited to as little as is reasonable.
175
176 Concrete API Compatibility
177 --------------------------
178
179 Use of the concrete C-API for dict (PyDict_*) with OrderedDict is
180 problematic. (See http://bugs.python.org/issue10977.) The concrete API
181 has a number of hard-coded assumptions tied to the dict implementation.
182 This is, in part, due to performance reasons, which is understandable
183 given the part dict plays in Python.
184
185 Any attempt to replace dict with OrderedDict for any role in the
186 interpreter (e.g. **kwds) faces a challenge. Such any effort must
187 recognize that the instances in affected locations currently interact with
188 the concrete API.
189
190 Here are some ways to address this challenge:
191
192 1. Change the relevant usage of the concrete API in CPython and add
193 PyDict_CheckExact() calls to each of the concrete API functions.
194 2. Adjust the relevant concrete API functions to explicitly accommodate
195 OrderedDict.
196 3. As with #1, add the checks, but improve the abstract API with smart fast
197 paths for dict and OrderedDict, and refactor CPython to use the abstract
198 API. Improvements to the abstract API would be valuable regardless.
199
200 Adding the checks to the concrete API would help make any interpreter
201 switch to OrderedDict less painful for extension modules. However, this
202 won't work. The equivalent C API call to `dict.__setitem__(obj, k, v)`
203 is 'PyDict_SetItem(obj, k, v)`. This illustrates how subclasses in C call
204 the base class's methods, since there is no equivalent of super() in the
205 C API. Calling into Python for parent class API would work, but some
206 extension modules already rely on this feature of the concrete API.
207
208 For reference, here is a breakdown of some of the dict concrete API:
209
210 ========================== ============= =======================
211 concrete API uses abstract API
212 ========================== ============= =======================
213 PyDict_Check PyMapping_Check
214 (PyDict_CheckExact) -
215 (PyDict_New) -
216 (PyDictProxy_New) -
217 PyDict_Clear -
218 PyDict_Contains PySequence_Contains
219 PyDict_Copy -
220 PyDict_SetItem PyObject_SetItem
221 PyDict_SetItemString PyMapping_SetItemString
222 PyDict_DelItem PyMapping_DelItem
223 PyDict_DelItemString PyMapping_DelItemString
224 PyDict_GetItem -
225 PyDict_GetItemWithError PyObject_GetItem
226 _PyDict_GetItemIdWithError -
227 PyDict_GetItemString PyMapping_GetItemString
228 PyDict_Items PyMapping_Items
229 PyDict_Keys PyMapping_Keys
230 PyDict_Values PyMapping_Values
231 PyDict_Size PyMapping_Size
232 PyMapping_Length
233 PyDict_Next PyIter_Next
234 _PyDict_Next -
235 PyDict_Merge -
236 PyDict_Update -
237 PyDict_MergeFromSeq2 -
238 PyDict_ClearFreeList -
239 - PyMapping_HasKeyString
240 - PyMapping_HasKey
241 ========================== ============= =======================
242
243
244 The dict Interface Relative to OrderedDict
245 ==========================================
246
247 Since OrderedDict subclasses dict, understanding the various methods and
248 attributes of dict is important for implementing OrderedDict.
249
250 Relevant Type Slots
251 -------------------
252
253 ================= ================ =================== ================
254 slot attribute object dict
255 ================= ================ =================== ================
256 tp_dealloc - object_dealloc dict_dealloc
257 tp_repr __repr__ object_repr dict_repr
258 sq_contains __contains__ - dict_contains
259 mp_length __len__ - dict_length
260 mp_subscript __getitem__ - dict_subscript
261 mp_ass_subscript __setitem__ - dict_ass_sub
262 __delitem__
263 tp_hash __hash__ _Py_HashPointer ..._HashNotImpl
264 tp_str __str__ object_str -
265 tp_getattro __getattribute__ ..._GenericGetAttr (repeated)
266 __getattr__
267 tp_setattro __setattr__ ..._GenericSetAttr (disabled)
268 tp_doc __doc__ (literal) dictionary_doc
269 tp_traverse - - dict_traverse
270 tp_clear - - dict_tp_clear
271 tp_richcompare __eq__ object_richcompare dict_richcompare
272 __ne__
273 tp_weaklistoffset (__weakref__) - -
274 tp_iter __iter__ - dict_iter
275 tp_dictoffset (__dict__) - -
276 tp_init __init__ object_init dict_init
277 tp_alloc - PyType_GenericAlloc (repeated)
278 tp_new __new__ object_new dict_new
279 tp_free - PyObject_Del PyObject_GC_Del
280 ================= ================ =================== ================
281
282 Relevant Methods
283 ----------------
284
285 ================ =================== ===============
286 method object dict
287 ================ =================== ===============
288 __reduce__ object_reduce -
289 __sizeof__ object_sizeof dict_sizeof
290 clear - dict_clear
291 copy - dict_copy
292 fromkeys - dict_fromkeys
293 get - dict_get
294 items - dictitems_new
295 keys - dictkeys_new
296 pop - dict_pop
297 popitem - dict_popitem
298 setdefault - dict_setdefault
299 update - dict_update
300 values - dictvalues_new
301 ================ =================== ===============
302
303
304 Pure Python OrderedDict
305 =======================
306
307 As already noted, compatibility with the pure Python OrderedDict
308 implementation is a key goal of this C implementation. To further that
309 goal, here's a summary of how OrderedDict-specific methods are implemented
310 in collections/__init__.py. Also provided is an indication of which
311 methods directly mutate or iterate the object, as well as any relationship
312 with the underlying linked-list.
313
314 ============= ============== == ================ === === ====
315 method impl used ll uses inq mut iter
316 ============= ============== == ================ === === ====
317 __contains__ dict - - X
318 __delitem__ OrderedDict Y dict.__delitem__ X
319 __eq__ OrderedDict N OrderedDict ~
320 dict.__eq__
321 __iter__
322 __getitem__ dict - - X
323 __iter__ OrderedDict Y - X
324 __init__ OrderedDict N update
325 __len__ dict - - X
326 __ne__ MutableMapping - __eq__ ~
327 __reduce__ OrderedDict N OrderedDict ~
328 __iter__
329 __getitem__
330 __repr__ OrderedDict N __class__ ~
331 items
332 __reversed__ OrderedDict Y - X
333 __setitem__ OrderedDict Y __contains__ X
334 dict.__setitem__
335 __sizeof__ OrderedDict Y __len__ ~
336 __dict__
337 clear OrderedDict Y dict.clear X
338 copy OrderedDict N __class__
339 __init__
340 fromkeys OrderedDict N __setitem__
341 get dict - - ~
342 items MutableMapping - ItemsView X
343 keys MutableMapping - KeysView X
344 move_to_end OrderedDict Y - X
345 pop OrderedDict N __contains__ X
346 __getitem__
347 __delitem__
348 popitem OrderedDict Y dict.pop X
349 setdefault OrderedDict N __contains__ ~
350 __getitem__
351 __setitem__
352 update MutableMapping - __setitem__ ~
353 values MutableMapping - ValuesView X
354 ============= ============== == ================ === === ====
355
356 __reversed__ and move_to_end are both exclusive to OrderedDict.
357
358
359 C OrderedDict Implementation
360 ============================
361
362 ================= ================
363 slot impl
364 ================= ================
365 tp_dealloc odict_dealloc
366 tp_repr odict_repr
367 mp_ass_subscript odict_ass_sub
368 tp_doc odict_doc
369 tp_traverse odict_traverse
370 tp_clear odict_tp_clear
371 tp_richcompare odict_richcompare
372 tp_weaklistoffset (offset)
373 tp_iter odict_iter
374 tp_dictoffset (offset)
375 tp_init odict_init
376 tp_alloc (repeated)
377 ================= ================
378
379 ================= ================
380 method impl
381 ================= ================
382 __reduce__ odict_reduce
383 __sizeof__ odict_sizeof
384 clear odict_clear
385 copy odict_copy
386 fromkeys odict_fromkeys
387 items odictitems_new
388 keys odictkeys_new
389 pop odict_pop
390 popitem odict_popitem
391 setdefault odict_setdefault
392 update odict_update
393 values odictvalues_new
394 ================= ================
395
396 Inherited unchanged from object/dict:
397
398 ================ ==========================
399 method type field
400 ================ ==========================
401 - tp_free
402 __contains__ tp_as_sequence.sq_contains
403 __getattr__ tp_getattro
404 __getattribute__ tp_getattro
405 __getitem__ tp_as_mapping.mp_subscript
406 __hash__ tp_hash
407 __len__ tp_as_mapping.mp_length
408 __setattr__ tp_setattro
409 __str__ tp_str
410 get -
411 ================ ==========================
412
413
414 Other Challenges
415 ================
416
417 Preserving Ordering During Iteration
418 ------------------------------------
419 During iteration through an OrderedDict, it is possible that items could
420 get added, removed, or reordered. For a linked-list implementation, as
421 with some other implementations, that situation may lead to undefined
422 behavior. The documentation for dict mentions this in the `iter()` section
423 of http://docs.python.org/3.4/library/stdtypes.html#dictionary-view-objects.
424 In this implementation we follow dict's lead (as does the pure Python
425 implementation) for __iter__(), keys(), values(), and items().
426
427 For internal iteration (using _odict_FOREACH or not), there is still the
428 risk that not all nodes that we expect to be seen in the loop actually get
429 seen. Thus, we are careful in each of those places to ensure that they
430 are. This comes, of course, at a small price at each location. The
431 solutions are much the same as those detailed in the `Situation that
432 Endangers Consistency` section above.
433
434
435 Potential Optimizations
436 =======================
437
438 * Allocate the nodes as a block via od_fast_nodes instead of individually.
439 - Set node->key to NULL to indicate the node is not-in-use.
440 - Add _odict_EXISTS()?
441 - How to maintain consistency across resizes? Existing node pointers
442 would be invalidated after a resize, which is particularly problematic
443 for the iterators.
444 * Use a more stream-lined implementation of update() and, likely indirectly,
445 __init__().
446
447 */
448
449 /* TODO
450
451 sooner:
452 - reentrancy (make sure everything is at a thread-safe state when calling
453 into Python). I've already checked this multiple times, but want to
454 make one more pass.
455 - add unit tests for reentrancy?
456
457 later:
458 - make the dict views support the full set API (the pure Python impl does)
459 - implement a fuller MutableMapping API in C?
460 - move the MutableMapping implementation to abstract.c?
461 - optimize mutablemapping_update
462 - use PyObject_MALLOC (small object allocator) for odict nodes?
463 - support subclasses better (e.g. in odict_richcompare)
464
465 */
466
467 #include "Python.h"
468 #include "internal/pystate.h"
469 #include "structmember.h"
470 #include "dict-common.h"
471 #include <stddef.h>
472
473 #include "clinic/odictobject.c.h"
474
475 /*[clinic input]
476 class OrderedDict "PyODictObject *" "&PyODict_Type"
477 [clinic start generated code]*/
478 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ca0641cf6143d4af]*/
479
480
481 typedef struct _odictnode _ODictNode;
482
483 /* PyODictObject */
484 struct _odictobject {
485 PyDictObject od_dict; /* the underlying dict */
486 _ODictNode *od_first; /* first node in the linked list, if any */
487 _ODictNode *od_last; /* last node in the linked list, if any */
488 /* od_fast_nodes, od_fast_nodes_size and od_resize_sentinel are managed
489 * by _odict_resize().
490 * Note that we rely on implementation details of dict for both. */
491 _ODictNode **od_fast_nodes; /* hash table that mirrors the dict table */
492 Py_ssize_t od_fast_nodes_size;
493 void *od_resize_sentinel; /* changes if odict should be resized */
494
495 size_t od_state; /* incremented whenever the LL changes */
496 PyObject *od_inst_dict; /* OrderedDict().__dict__ */
497 PyObject *od_weakreflist; /* holds weakrefs to the odict */
498 };
499
500
501 /* ----------------------------------------------
502 * odict keys (a simple doubly-linked list)
503 */
504
505 struct _odictnode {
506 PyObject *key;
507 Py_hash_t hash;
508 _ODictNode *next;
509 _ODictNode *prev;
510 };
511
512 #define _odictnode_KEY(node) \
513 (node->key)
514 #define _odictnode_HASH(node) \
515 (node->hash)
516 /* borrowed reference */
517 #define _odictnode_VALUE(node, od) \
518 PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))
519 #define _odictnode_PREV(node) (node->prev)
520 #define _odictnode_NEXT(node) (node->next)
521
522 #define _odict_FIRST(od) (((PyODictObject *)od)->od_first)
523 #define _odict_LAST(od) (((PyODictObject *)od)->od_last)
524 #define _odict_EMPTY(od) (_odict_FIRST(od) == NULL)
525 #define _odict_FOREACH(od, node) \
526 for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))
527
528 /* Return the index into the hash table, regardless of a valid node. */
529 static Py_ssize_t
_odict_get_index_raw(PyODictObject * od,PyObject * key,Py_hash_t hash)530 _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
531 {
532 PyObject *value = NULL;
533 PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
534 Py_ssize_t ix;
535
536 ix = (keys->dk_lookup)((PyDictObject *)od, key, hash, &value);
537 if (ix == DKIX_EMPTY) {
538 return keys->dk_nentries; /* index of new entry */
539 }
540 if (ix < 0)
541 return -1;
542 /* We use pointer arithmetic to get the entry's index into the table. */
543 return ix;
544 }
545
546 /* Replace od->od_fast_nodes with a new table matching the size of dict's. */
547 static int
_odict_resize(PyODictObject * od)548 _odict_resize(PyODictObject *od)
549 {
550 Py_ssize_t size, i;
551 _ODictNode **fast_nodes, *node;
552
553 /* Initialize a new "fast nodes" table. */
554 size = ((PyDictObject *)od)->ma_keys->dk_size;
555 fast_nodes = PyMem_NEW(_ODictNode *, size);
556 if (fast_nodes == NULL) {
557 PyErr_NoMemory();
558 return -1;
559 }
560 for (i = 0; i < size; i++)
561 fast_nodes[i] = NULL;
562
563 /* Copy the current nodes into the table. */
564 _odict_FOREACH(od, node) {
565 i = _odict_get_index_raw(od, _odictnode_KEY(node),
566 _odictnode_HASH(node));
567 if (i < 0) {
568 PyMem_FREE(fast_nodes);
569 return -1;
570 }
571 fast_nodes[i] = node;
572 }
573
574 /* Replace the old fast nodes table. */
575 PyMem_FREE(od->od_fast_nodes);
576 od->od_fast_nodes = fast_nodes;
577 od->od_fast_nodes_size = size;
578 od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;
579 return 0;
580 }
581
582 /* Return the index into the hash table, regardless of a valid node. */
583 static Py_ssize_t
_odict_get_index(PyODictObject * od,PyObject * key,Py_hash_t hash)584 _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)
585 {
586 PyDictKeysObject *keys;
587
588 assert(key != NULL);
589 keys = ((PyDictObject *)od)->ma_keys;
590
591 /* Ensure od_fast_nodes and dk_entries are in sync. */
592 if (od->od_resize_sentinel != keys ||
593 od->od_fast_nodes_size != keys->dk_size) {
594 int resize_res = _odict_resize(od);
595 if (resize_res < 0)
596 return -1;
597 }
598
599 return _odict_get_index_raw(od, key, hash);
600 }
601
602 /* Returns NULL if there was some error or the key was not found. */
603 static _ODictNode *
_odict_find_node_hash(PyODictObject * od,PyObject * key,Py_hash_t hash)604 _odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash)
605 {
606 Py_ssize_t index;
607
608 if (_odict_EMPTY(od))
609 return NULL;
610 index = _odict_get_index(od, key, hash);
611 if (index < 0)
612 return NULL;
613 assert(od->od_fast_nodes != NULL);
614 return od->od_fast_nodes[index];
615 }
616
617 static _ODictNode *
_odict_find_node(PyODictObject * od,PyObject * key)618 _odict_find_node(PyODictObject *od, PyObject *key)
619 {
620 Py_ssize_t index;
621 Py_hash_t hash;
622
623 if (_odict_EMPTY(od))
624 return NULL;
625 hash = PyObject_Hash(key);
626 if (hash == -1)
627 return NULL;
628 index = _odict_get_index(od, key, hash);
629 if (index < 0)
630 return NULL;
631 assert(od->od_fast_nodes != NULL);
632 return od->od_fast_nodes[index];
633 }
634
635 static void
_odict_add_head(PyODictObject * od,_ODictNode * node)636 _odict_add_head(PyODictObject *od, _ODictNode *node)
637 {
638 _odictnode_PREV(node) = NULL;
639 _odictnode_NEXT(node) = _odict_FIRST(od);
640 if (_odict_FIRST(od) == NULL)
641 _odict_LAST(od) = node;
642 else
643 _odictnode_PREV(_odict_FIRST(od)) = node;
644 _odict_FIRST(od) = node;
645 od->od_state++;
646 }
647
648 static void
_odict_add_tail(PyODictObject * od,_ODictNode * node)649 _odict_add_tail(PyODictObject *od, _ODictNode *node)
650 {
651 _odictnode_PREV(node) = _odict_LAST(od);
652 _odictnode_NEXT(node) = NULL;
653 if (_odict_LAST(od) == NULL)
654 _odict_FIRST(od) = node;
655 else
656 _odictnode_NEXT(_odict_LAST(od)) = node;
657 _odict_LAST(od) = node;
658 od->od_state++;
659 }
660
661 /* adds the node to the end of the list */
662 static int
_odict_add_new_node(PyODictObject * od,PyObject * key,Py_hash_t hash)663 _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
664 {
665 Py_ssize_t i;
666 _ODictNode *node;
667
668 Py_INCREF(key);
669 i = _odict_get_index(od, key, hash);
670 if (i < 0) {
671 if (!PyErr_Occurred())
672 PyErr_SetObject(PyExc_KeyError, key);
673 Py_DECREF(key);
674 return -1;
675 }
676 assert(od->od_fast_nodes != NULL);
677 if (od->od_fast_nodes[i] != NULL) {
678 /* We already have a node for the key so there's no need to add one. */
679 Py_DECREF(key);
680 return 0;
681 }
682
683 /* must not be added yet */
684 node = (_ODictNode *)PyMem_MALLOC(sizeof(_ODictNode));
685 if (node == NULL) {
686 Py_DECREF(key);
687 PyErr_NoMemory();
688 return -1;
689 }
690
691 _odictnode_KEY(node) = key;
692 _odictnode_HASH(node) = hash;
693 _odict_add_tail(od, node);
694 od->od_fast_nodes[i] = node;
695 return 0;
696 }
697
698 /* Putting the decref after the free causes problems. */
699 #define _odictnode_DEALLOC(node) \
700 do { \
701 Py_DECREF(_odictnode_KEY(node)); \
702 PyMem_FREE((void *)node); \
703 } while (0)
704
705 /* Repeated calls on the same node are no-ops. */
706 static void
_odict_remove_node(PyODictObject * od,_ODictNode * node)707 _odict_remove_node(PyODictObject *od, _ODictNode *node)
708 {
709 if (_odict_FIRST(od) == node)
710 _odict_FIRST(od) = _odictnode_NEXT(node);
711 else if (_odictnode_PREV(node) != NULL)
712 _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);
713
714 if (_odict_LAST(od) == node)
715 _odict_LAST(od) = _odictnode_PREV(node);
716 else if (_odictnode_NEXT(node) != NULL)
717 _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node);
718
719 _odictnode_PREV(node) = NULL;
720 _odictnode_NEXT(node) = NULL;
721 od->od_state++;
722 }
723
724 /* If someone calls PyDict_DelItem() directly on an OrderedDict, we'll
725 get all sorts of problems here. In PyODict_DelItem we make sure to
726 call _odict_clear_node first.
727
728 This matters in the case of colliding keys. Suppose we add 3 keys:
729 [A, B, C], where the hash of C collides with A and the next possible
730 index in the hash table is occupied by B. If we remove B then for C
731 the dict's looknode func will give us the old index of B instead of
732 the index we got before deleting B. However, the node for C in
733 od_fast_nodes is still at the old dict index of C. Thus to be sure
734 things don't get out of sync, we clear the node in od_fast_nodes
735 *before* calling PyDict_DelItem.
736
737 The same must be done for any other OrderedDict operations where
738 we modify od_fast_nodes.
739 */
740 static int
_odict_clear_node(PyODictObject * od,_ODictNode * node,PyObject * key,Py_hash_t hash)741 _odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,
742 Py_hash_t hash)
743 {
744 Py_ssize_t i;
745
746 assert(key != NULL);
747 if (_odict_EMPTY(od)) {
748 /* Let later code decide if this is a KeyError. */
749 return 0;
750 }
751
752 i = _odict_get_index(od, key, hash);
753 if (i < 0)
754 return PyErr_Occurred() ? -1 : 0;
755
756 assert(od->od_fast_nodes != NULL);
757 if (node == NULL)
758 node = od->od_fast_nodes[i];
759 assert(node == od->od_fast_nodes[i]);
760 if (node == NULL) {
761 /* Let later code decide if this is a KeyError. */
762 return 0;
763 }
764
765 // Now clear the node.
766 od->od_fast_nodes[i] = NULL;
767 _odict_remove_node(od, node);
768 _odictnode_DEALLOC(node);
769 return 0;
770 }
771
772 static void
_odict_clear_nodes(PyODictObject * od)773 _odict_clear_nodes(PyODictObject *od)
774 {
775 _ODictNode *node, *next;
776
777 PyMem_FREE(od->od_fast_nodes);
778 od->od_fast_nodes = NULL;
779 od->od_fast_nodes_size = 0;
780 od->od_resize_sentinel = NULL;
781
782 node = _odict_FIRST(od);
783 _odict_FIRST(od) = NULL;
784 _odict_LAST(od) = NULL;
785 while (node != NULL) {
786 next = _odictnode_NEXT(node);
787 _odictnode_DEALLOC(node);
788 node = next;
789 }
790 }
791
792 /* There isn't any memory management of nodes past this point. */
793 #undef _odictnode_DEALLOC
794
795 static int
_odict_keys_equal(PyODictObject * a,PyODictObject * b)796 _odict_keys_equal(PyODictObject *a, PyODictObject *b)
797 {
798 _ODictNode *node_a, *node_b;
799
800 node_a = _odict_FIRST(a);
801 node_b = _odict_FIRST(b);
802 while (1) {
803 if (node_a == NULL && node_b == NULL)
804 /* success: hit the end of each at the same time */
805 return 1;
806 else if (node_a == NULL || node_b == NULL)
807 /* unequal length */
808 return 0;
809 else {
810 int res = PyObject_RichCompareBool(
811 (PyObject *)_odictnode_KEY(node_a),
812 (PyObject *)_odictnode_KEY(node_b),
813 Py_EQ);
814 if (res < 0)
815 return res;
816 else if (res == 0)
817 return 0;
818
819 /* otherwise it must match, so move on to the next one */
820 node_a = _odictnode_NEXT(node_a);
821 node_b = _odictnode_NEXT(node_b);
822 }
823 }
824 }
825
826
827 /* ----------------------------------------------
828 * OrderedDict mapping methods
829 */
830
831 /* mp_ass_subscript: __setitem__() and __delitem__() */
832
833 static int
odict_mp_ass_sub(PyODictObject * od,PyObject * v,PyObject * w)834 odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w)
835 {
836 if (w == NULL)
837 return PyODict_DelItem((PyObject *)od, v);
838 else
839 return PyODict_SetItem((PyObject *)od, v, w);
840 }
841
842 /* tp_as_mapping */
843
844 static PyMappingMethods odict_as_mapping = {
845 0, /*mp_length*/
846 0, /*mp_subscript*/
847 (objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/
848 };
849
850
851 /* ----------------------------------------------
852 * OrderedDict methods
853 */
854
855 /* fromkeys() */
856
857 /*[clinic input]
858 @classmethod
859 OrderedDict.fromkeys
860
861 iterable as seq: object
862 value: object = None
863
864 Create a new ordered dictionary with keys from iterable and values set to value.
865 [clinic start generated code]*/
866
867 static PyObject *
OrderedDict_fromkeys_impl(PyTypeObject * type,PyObject * seq,PyObject * value)868 OrderedDict_fromkeys_impl(PyTypeObject *type, PyObject *seq, PyObject *value)
869 /*[clinic end generated code: output=c10390d452d78d6d input=1a0476c229c597b3]*/
870 {
871 return _PyDict_FromKeys((PyObject *)type, seq, value);
872 }
873
874 /* __sizeof__() */
875
876 /* OrderedDict.__sizeof__() does not have a docstring. */
877 PyDoc_STRVAR(odict_sizeof__doc__, "");
878
879 static PyObject *
odict_sizeof(PyODictObject * od)880 odict_sizeof(PyODictObject *od)
881 {
882 Py_ssize_t res = _PyDict_SizeOf((PyDictObject *)od);
883 res += sizeof(_ODictNode *) * od->od_fast_nodes_size; /* od_fast_nodes */
884 if (!_odict_EMPTY(od)) {
885 res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */
886 }
887 return PyLong_FromSsize_t(res);
888 }
889
890 /* __reduce__() */
891
892 PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling");
893
894 static PyObject *
odict_reduce(register PyODictObject * od)895 odict_reduce(register PyODictObject *od)
896 {
897 _Py_IDENTIFIER(__dict__);
898 _Py_IDENTIFIER(items);
899 PyObject *dict = NULL, *result = NULL;
900 PyObject *items_iter, *items, *args = NULL;
901
902 /* capture any instance state */
903 dict = _PyObject_GetAttrId((PyObject *)od, &PyId___dict__);
904 if (dict == NULL)
905 goto Done;
906 else {
907 /* od.__dict__ isn't necessarily a dict... */
908 Py_ssize_t dict_len = PyObject_Length(dict);
909 if (dict_len == -1)
910 goto Done;
911 if (!dict_len) {
912 /* nothing to pickle in od.__dict__ */
913 Py_CLEAR(dict);
914 }
915 }
916
917 /* build the result */
918 args = PyTuple_New(0);
919 if (args == NULL)
920 goto Done;
921
922 items = _PyObject_CallMethodIdObjArgs((PyObject *)od, &PyId_items, NULL);
923 if (items == NULL)
924 goto Done;
925
926 items_iter = PyObject_GetIter(items);
927 Py_DECREF(items);
928 if (items_iter == NULL)
929 goto Done;
930
931 result = PyTuple_Pack(5, Py_TYPE(od), args, dict ? dict : Py_None, Py_None, items_iter);
932 Py_DECREF(items_iter);
933
934 Done:
935 Py_XDECREF(dict);
936 Py_XDECREF(args);
937
938 return result;
939 }
940
941 /* setdefault(): Skips __missing__() calls. */
942
943
944 /*[clinic input]
945 OrderedDict.setdefault
946
947 key: object
948 default: object = None
949
950 Insert key with a value of default if key is not in the dictionary.
951
952 Return the value for key if key is in the dictionary, else default.
953 [clinic start generated code]*/
954
955 static PyObject *
OrderedDict_setdefault_impl(PyODictObject * self,PyObject * key,PyObject * default_value)956 OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,
957 PyObject *default_value)
958 /*[clinic end generated code: output=97537cb7c28464b6 input=38e098381c1efbc6]*/
959 {
960 PyObject *result = NULL;
961
962 if (PyODict_CheckExact(self)) {
963 result = PyODict_GetItemWithError(self, key); /* borrowed */
964 if (result == NULL) {
965 if (PyErr_Occurred())
966 return NULL;
967 assert(_odict_find_node(self, key) == NULL);
968 if (PyODict_SetItem((PyObject *)self, key, default_value) >= 0) {
969 result = default_value;
970 Py_INCREF(result);
971 }
972 }
973 else {
974 Py_INCREF(result);
975 }
976 }
977 else {
978 int exists = PySequence_Contains((PyObject *)self, key);
979 if (exists < 0) {
980 return NULL;
981 }
982 else if (exists) {
983 result = PyObject_GetItem((PyObject *)self, key);
984 }
985 else if (PyObject_SetItem((PyObject *)self, key, default_value) >= 0) {
986 result = default_value;
987 Py_INCREF(result);
988 }
989 }
990
991 return result;
992 }
993
994 /* pop() */
995
996 PyDoc_STRVAR(odict_pop__doc__,
997 "od.pop(k[,d]) -> v, remove specified key and return the corresponding\n\
998 value. If key is not found, d is returned if given, otherwise KeyError\n\
999 is raised.\n\
1000 \n\
1001 ");
1002
1003 /* forward */
1004 static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *);
1005
1006 /* Skips __missing__() calls. */
1007 static PyObject *
odict_pop(PyObject * od,PyObject * args,PyObject * kwargs)1008 odict_pop(PyObject *od, PyObject *args, PyObject *kwargs)
1009 {
1010 static char *kwlist[] = {"key", "default", 0};
1011 PyObject *key, *failobj = NULL;
1012
1013 /* borrowed */
1014 if (!PyArg_ParseTupleAndKeywords(args, kwargs, "O|O:pop", kwlist,
1015 &key, &failobj)) {
1016 return NULL;
1017 }
1018
1019 return _odict_popkey(od, key, failobj);
1020 }
1021
1022 static PyObject *
_odict_popkey_hash(PyObject * od,PyObject * key,PyObject * failobj,Py_hash_t hash)1023 _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
1024 Py_hash_t hash)
1025 {
1026 _ODictNode *node;
1027 PyObject *value = NULL;
1028
1029 /* Pop the node first to avoid a possible dict resize (due to
1030 eval loop reentrancy) and complications due to hash collision
1031 resolution. */
1032 node = _odict_find_node_hash((PyODictObject *)od, key, hash);
1033 if (node == NULL) {
1034 if (PyErr_Occurred())
1035 return NULL;
1036 }
1037 else {
1038 int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
1039 if (res < 0) {
1040 return NULL;
1041 }
1042 }
1043
1044 /* Now delete the value from the dict. */
1045 if (PyODict_CheckExact(od)) {
1046 if (node != NULL) {
1047 value = _PyDict_GetItem_KnownHash(od, key, hash); /* borrowed */
1048 if (value != NULL) {
1049 Py_INCREF(value);
1050 if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {
1051 Py_DECREF(value);
1052 return NULL;
1053 }
1054 }
1055 }
1056 }
1057 else {
1058 int exists = PySequence_Contains(od, key);
1059 if (exists < 0)
1060 return NULL;
1061 if (exists) {
1062 value = PyObject_GetItem(od, key);
1063 if (value != NULL) {
1064 if (PyObject_DelItem(od, key) == -1) {
1065 Py_CLEAR(value);
1066 }
1067 }
1068 }
1069 }
1070
1071 /* Apply the fallback value, if necessary. */
1072 if (value == NULL && !PyErr_Occurred()) {
1073 if (failobj) {
1074 value = failobj;
1075 Py_INCREF(failobj);
1076 }
1077 else {
1078 PyErr_SetObject(PyExc_KeyError, key);
1079 }
1080 }
1081
1082 return value;
1083 }
1084
1085 static PyObject *
_odict_popkey(PyObject * od,PyObject * key,PyObject * failobj)1086 _odict_popkey(PyObject *od, PyObject *key, PyObject *failobj)
1087 {
1088 Py_hash_t hash = PyObject_Hash(key);
1089 if (hash == -1)
1090 return NULL;
1091
1092 return _odict_popkey_hash(od, key, failobj, hash);
1093 }
1094
1095
1096 /* popitem() */
1097
1098 /*[clinic input]
1099 OrderedDict.popitem
1100
1101 last: bool = True
1102
1103 Remove and return a (key, value) pair from the dictionary.
1104
1105 Pairs are returned in LIFO order if last is true or FIFO order if false.
1106 [clinic start generated code]*/
1107
1108 static PyObject *
OrderedDict_popitem_impl(PyODictObject * self,int last)1109 OrderedDict_popitem_impl(PyODictObject *self, int last)
1110 /*[clinic end generated code: output=98e7d986690d49eb input=d992ac5ee8305e1a]*/
1111 {
1112 PyObject *key, *value, *item = NULL;
1113 _ODictNode *node;
1114
1115 /* pull the item */
1116
1117 if (_odict_EMPTY(self)) {
1118 PyErr_SetString(PyExc_KeyError, "dictionary is empty");
1119 return NULL;
1120 }
1121
1122 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1123 key = _odictnode_KEY(node);
1124 Py_INCREF(key);
1125 value = _odict_popkey_hash((PyObject *)self, key, NULL, _odictnode_HASH(node));
1126 if (value == NULL)
1127 return NULL;
1128 item = PyTuple_Pack(2, key, value);
1129 Py_DECREF(key);
1130 Py_DECREF(value);
1131 return item;
1132 }
1133
1134 /* keys() */
1135
1136 /* MutableMapping.keys() does not have a docstring. */
1137 PyDoc_STRVAR(odict_keys__doc__, "");
1138
1139 static PyObject * odictkeys_new(PyObject *od); /* forward */
1140
1141 /* values() */
1142
1143 /* MutableMapping.values() does not have a docstring. */
1144 PyDoc_STRVAR(odict_values__doc__, "");
1145
1146 static PyObject * odictvalues_new(PyObject *od); /* forward */
1147
1148 /* items() */
1149
1150 /* MutableMapping.items() does not have a docstring. */
1151 PyDoc_STRVAR(odict_items__doc__, "");
1152
1153 static PyObject * odictitems_new(PyObject *od); /* forward */
1154
1155 /* update() */
1156
1157 /* MutableMapping.update() does not have a docstring. */
1158 PyDoc_STRVAR(odict_update__doc__, "");
1159
1160 /* forward */
1161 static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *);
1162
1163 #define odict_update mutablemapping_update
1164
1165 /* clear() */
1166
1167 PyDoc_STRVAR(odict_clear__doc__,
1168 "od.clear() -> None. Remove all items from od.");
1169
1170 static PyObject *
odict_clear(register PyODictObject * od,PyObject * Py_UNUSED (ignored))1171 odict_clear(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
1172 {
1173 PyDict_Clear((PyObject *)od);
1174 _odict_clear_nodes(od);
1175 Py_RETURN_NONE;
1176 }
1177
1178 /* copy() */
1179
1180 /* forward */
1181 static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *,
1182 Py_hash_t);
1183
1184 PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od");
1185
1186 static PyObject *
odict_copy(register PyODictObject * od)1187 odict_copy(register PyODictObject *od)
1188 {
1189 _ODictNode *node;
1190 PyObject *od_copy;
1191
1192 if (PyODict_CheckExact(od))
1193 od_copy = PyODict_New();
1194 else
1195 od_copy = _PyObject_CallNoArg((PyObject *)Py_TYPE(od));
1196 if (od_copy == NULL)
1197 return NULL;
1198
1199 if (PyODict_CheckExact(od)) {
1200 _odict_FOREACH(od, node) {
1201 PyObject *key = _odictnode_KEY(node);
1202 PyObject *value = _odictnode_VALUE(node, od);
1203 if (value == NULL) {
1204 if (!PyErr_Occurred())
1205 PyErr_SetObject(PyExc_KeyError, key);
1206 goto fail;
1207 }
1208 if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value,
1209 _odictnode_HASH(node)) != 0)
1210 goto fail;
1211 }
1212 }
1213 else {
1214 _odict_FOREACH(od, node) {
1215 int res;
1216 PyObject *value = PyObject_GetItem((PyObject *)od,
1217 _odictnode_KEY(node));
1218 if (value == NULL)
1219 goto fail;
1220 res = PyObject_SetItem((PyObject *)od_copy,
1221 _odictnode_KEY(node), value);
1222 Py_DECREF(value);
1223 if (res != 0)
1224 goto fail;
1225 }
1226 }
1227 return od_copy;
1228
1229 fail:
1230 Py_DECREF(od_copy);
1231 return NULL;
1232 }
1233
1234 /* __reversed__() */
1235
1236 PyDoc_STRVAR(odict_reversed__doc__, "od.__reversed__() <==> reversed(od)");
1237
1238 #define _odict_ITER_REVERSED 1
1239 #define _odict_ITER_KEYS 2
1240 #define _odict_ITER_VALUES 4
1241
1242 /* forward */
1243 static PyObject * odictiter_new(PyODictObject *, int);
1244
1245 static PyObject *
odict_reversed(PyODictObject * od)1246 odict_reversed(PyODictObject *od)
1247 {
1248 return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED);
1249 }
1250
1251
1252 /* move_to_end() */
1253
1254 /*[clinic input]
1255 OrderedDict.move_to_end
1256
1257 key: object
1258 last: bool = True
1259
1260 Move an existing element to the end (or beginning if last is false).
1261
1262 Raise KeyError if the element does not exist.
1263 [clinic start generated code]*/
1264
1265 static PyObject *
OrderedDict_move_to_end_impl(PyODictObject * self,PyObject * key,int last)1266 OrderedDict_move_to_end_impl(PyODictObject *self, PyObject *key, int last)
1267 /*[clinic end generated code: output=fafa4c5cc9b92f20 input=d6ceff7132a2fcd7]*/
1268 {
1269 _ODictNode *node;
1270
1271 if (_odict_EMPTY(self)) {
1272 PyErr_SetObject(PyExc_KeyError, key);
1273 return NULL;
1274 }
1275 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1276 if (key != _odictnode_KEY(node)) {
1277 node = _odict_find_node(self, key);
1278 if (node == NULL) {
1279 if (!PyErr_Occurred())
1280 PyErr_SetObject(PyExc_KeyError, key);
1281 return NULL;
1282 }
1283 if (last) {
1284 /* Only move if not already the last one. */
1285 if (node != _odict_LAST(self)) {
1286 _odict_remove_node(self, node);
1287 _odict_add_tail(self, node);
1288 }
1289 }
1290 else {
1291 /* Only move if not already the first one. */
1292 if (node != _odict_FIRST(self)) {
1293 _odict_remove_node(self, node);
1294 _odict_add_head(self, node);
1295 }
1296 }
1297 }
1298 Py_RETURN_NONE;
1299 }
1300
1301
1302 /* tp_methods */
1303
1304 static PyMethodDef odict_methods[] = {
1305
1306 /* overridden dict methods */
1307 ORDEREDDICT_FROMKEYS_METHODDEF
1308 {"__sizeof__", (PyCFunction)odict_sizeof, METH_NOARGS,
1309 odict_sizeof__doc__},
1310 {"__reduce__", (PyCFunction)odict_reduce, METH_NOARGS,
1311 odict_reduce__doc__},
1312 ORDEREDDICT_SETDEFAULT_METHODDEF
1313 {"pop", (PyCFunction)odict_pop,
1314 METH_VARARGS | METH_KEYWORDS, odict_pop__doc__},
1315 ORDEREDDICT_POPITEM_METHODDEF
1316 {"keys", (PyCFunction)odictkeys_new, METH_NOARGS,
1317 odict_keys__doc__},
1318 {"values", (PyCFunction)odictvalues_new, METH_NOARGS,
1319 odict_values__doc__},
1320 {"items", (PyCFunction)odictitems_new, METH_NOARGS,
1321 odict_items__doc__},
1322 {"update", (PyCFunction)odict_update, METH_VARARGS | METH_KEYWORDS,
1323 odict_update__doc__},
1324 {"clear", (PyCFunction)odict_clear, METH_NOARGS,
1325 odict_clear__doc__},
1326 {"copy", (PyCFunction)odict_copy, METH_NOARGS,
1327 odict_copy__doc__},
1328
1329 /* new methods */
1330 {"__reversed__", (PyCFunction)odict_reversed, METH_NOARGS,
1331 odict_reversed__doc__},
1332 ORDEREDDICT_MOVE_TO_END_METHODDEF
1333
1334 {NULL, NULL} /* sentinel */
1335 };
1336
1337
1338 /* ----------------------------------------------
1339 * OrderedDict members
1340 */
1341
1342 /* tp_getset */
1343
1344 static PyGetSetDef odict_getset[] = {
1345 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
1346 {NULL}
1347 };
1348
1349 /* ----------------------------------------------
1350 * OrderedDict type slot methods
1351 */
1352
1353 /* tp_dealloc */
1354
1355 static void
odict_dealloc(PyODictObject * self)1356 odict_dealloc(PyODictObject *self)
1357 {
1358 PyThreadState *tstate = PyThreadState_GET();
1359
1360 PyObject_GC_UnTrack(self);
1361 Py_TRASHCAN_SAFE_BEGIN(self)
1362
1363 Py_XDECREF(self->od_inst_dict);
1364 if (self->od_weakreflist != NULL)
1365 PyObject_ClearWeakRefs((PyObject *)self);
1366
1367 _odict_clear_nodes(self);
1368
1369 /* Call the base tp_dealloc(). Since it too uses the trashcan mechanism,
1370 * temporarily decrement trash_delete_nesting to prevent triggering it
1371 * and putting the partially deallocated object on the trashcan's
1372 * to-be-deleted-later list.
1373 */
1374 --tstate->trash_delete_nesting;
1375 assert(_tstate->trash_delete_nesting < PyTrash_UNWIND_LEVEL);
1376 PyDict_Type.tp_dealloc((PyObject *)self);
1377 ++tstate->trash_delete_nesting;
1378
1379 Py_TRASHCAN_SAFE_END(self)
1380 }
1381
1382 /* tp_repr */
1383
1384 static PyObject *
odict_repr(PyODictObject * self)1385 odict_repr(PyODictObject *self)
1386 {
1387 int i;
1388 _Py_IDENTIFIER(items);
1389 PyObject *pieces = NULL, *result = NULL;
1390
1391 if (PyODict_SIZE(self) == 0)
1392 return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self)));
1393
1394 i = Py_ReprEnter((PyObject *)self);
1395 if (i != 0) {
1396 return i > 0 ? PyUnicode_FromString("...") : NULL;
1397 }
1398
1399 if (PyODict_CheckExact(self)) {
1400 Py_ssize_t count = 0;
1401 _ODictNode *node;
1402 pieces = PyList_New(PyODict_SIZE(self));
1403 if (pieces == NULL)
1404 goto Done;
1405
1406 _odict_FOREACH(self, node) {
1407 PyObject *pair;
1408 PyObject *key = _odictnode_KEY(node);
1409 PyObject *value = _odictnode_VALUE(node, self);
1410 if (value == NULL) {
1411 if (!PyErr_Occurred())
1412 PyErr_SetObject(PyExc_KeyError, key);
1413 goto Done;
1414 }
1415 pair = PyTuple_Pack(2, key, value);
1416 if (pair == NULL)
1417 goto Done;
1418
1419 if (count < PyList_GET_SIZE(pieces))
1420 PyList_SET_ITEM(pieces, count, pair); /* steals reference */
1421 else {
1422 if (PyList_Append(pieces, pair) < 0) {
1423 Py_DECREF(pair);
1424 goto Done;
1425 }
1426 Py_DECREF(pair);
1427 }
1428 count++;
1429 }
1430 if (count < PyList_GET_SIZE(pieces))
1431 Py_SIZE(pieces) = count;
1432 }
1433 else {
1434 PyObject *items = _PyObject_CallMethodIdObjArgs((PyObject *)self,
1435 &PyId_items, NULL);
1436 if (items == NULL)
1437 goto Done;
1438 pieces = PySequence_List(items);
1439 Py_DECREF(items);
1440 if (pieces == NULL)
1441 goto Done;
1442 }
1443
1444 result = PyUnicode_FromFormat("%s(%R)",
1445 _PyType_Name(Py_TYPE(self)), pieces);
1446
1447 Done:
1448 Py_XDECREF(pieces);
1449 Py_ReprLeave((PyObject *)self);
1450 return result;
1451 }
1452
1453 /* tp_doc */
1454
1455 PyDoc_STRVAR(odict_doc,
1456 "Dictionary that remembers insertion order");
1457
1458 /* tp_traverse */
1459
1460 static int
odict_traverse(PyODictObject * od,visitproc visit,void * arg)1461 odict_traverse(PyODictObject *od, visitproc visit, void *arg)
1462 {
1463 _ODictNode *node;
1464
1465 Py_VISIT(od->od_inst_dict);
1466 Py_VISIT(od->od_weakreflist);
1467 _odict_FOREACH(od, node) {
1468 Py_VISIT(_odictnode_KEY(node));
1469 }
1470 return PyDict_Type.tp_traverse((PyObject *)od, visit, arg);
1471 }
1472
1473 /* tp_clear */
1474
1475 static int
odict_tp_clear(PyODictObject * od)1476 odict_tp_clear(PyODictObject *od)
1477 {
1478 Py_CLEAR(od->od_inst_dict);
1479 Py_CLEAR(od->od_weakreflist);
1480 PyDict_Clear((PyObject *)od);
1481 _odict_clear_nodes(od);
1482 return 0;
1483 }
1484
1485 /* tp_richcompare */
1486
1487 static PyObject *
odict_richcompare(PyObject * v,PyObject * w,int op)1488 odict_richcompare(PyObject *v, PyObject *w, int op)
1489 {
1490 if (!PyODict_Check(v) || !PyDict_Check(w)) {
1491 Py_RETURN_NOTIMPLEMENTED;
1492 }
1493
1494 if (op == Py_EQ || op == Py_NE) {
1495 PyObject *res, *cmp;
1496 int eq;
1497
1498 cmp = PyDict_Type.tp_richcompare(v, w, op);
1499 if (cmp == NULL)
1500 return NULL;
1501 if (!PyODict_Check(w))
1502 return cmp;
1503 if (op == Py_EQ && cmp == Py_False)
1504 return cmp;
1505 if (op == Py_NE && cmp == Py_True)
1506 return cmp;
1507 Py_DECREF(cmp);
1508
1509 /* Try comparing odict keys. */
1510 eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w);
1511 if (eq < 0)
1512 return NULL;
1513
1514 res = (eq == (op == Py_EQ)) ? Py_True : Py_False;
1515 Py_INCREF(res);
1516 return res;
1517 } else {
1518 Py_RETURN_NOTIMPLEMENTED;
1519 }
1520 }
1521
1522 /* tp_iter */
1523
1524 static PyObject *
odict_iter(PyODictObject * od)1525 odict_iter(PyODictObject *od)
1526 {
1527 return odictiter_new(od, _odict_ITER_KEYS);
1528 }
1529
1530 /* tp_init */
1531
1532 static int
odict_init(PyObject * self,PyObject * args,PyObject * kwds)1533 odict_init(PyObject *self, PyObject *args, PyObject *kwds)
1534 {
1535 PyObject *res;
1536 Py_ssize_t len = PyObject_Length(args);
1537
1538 if (len == -1)
1539 return -1;
1540 if (len > 1) {
1541 const char *msg = "expected at most 1 arguments, got %d";
1542 PyErr_Format(PyExc_TypeError, msg, len);
1543 return -1;
1544 }
1545
1546 /* __init__() triggering update() is just the way things are! */
1547 res = odict_update(self, args, kwds);
1548 if (res == NULL) {
1549 return -1;
1550 } else {
1551 Py_DECREF(res);
1552 return 0;
1553 }
1554 }
1555
1556 /* PyODict_Type */
1557
1558 PyTypeObject PyODict_Type = {
1559 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1560 "collections.OrderedDict", /* tp_name */
1561 sizeof(PyODictObject), /* tp_basicsize */
1562 0, /* tp_itemsize */
1563 (destructor)odict_dealloc, /* tp_dealloc */
1564 0, /* tp_print */
1565 0, /* tp_getattr */
1566 0, /* tp_setattr */
1567 0, /* tp_reserved */
1568 (reprfunc)odict_repr, /* tp_repr */
1569 0, /* tp_as_number */
1570 0, /* tp_as_sequence */
1571 &odict_as_mapping, /* tp_as_mapping */
1572 0, /* tp_hash */
1573 0, /* tp_call */
1574 0, /* tp_str */
1575 0, /* tp_getattro */
1576 0, /* tp_setattro */
1577 0, /* tp_as_buffer */
1578 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1579 odict_doc, /* tp_doc */
1580 (traverseproc)odict_traverse, /* tp_traverse */
1581 (inquiry)odict_tp_clear, /* tp_clear */
1582 (richcmpfunc)odict_richcompare, /* tp_richcompare */
1583 offsetof(PyODictObject, od_weakreflist), /* tp_weaklistoffset */
1584 (getiterfunc)odict_iter, /* tp_iter */
1585 0, /* tp_iternext */
1586 odict_methods, /* tp_methods */
1587 0, /* tp_members */
1588 odict_getset, /* tp_getset */
1589 &PyDict_Type, /* tp_base */
1590 0, /* tp_dict */
1591 0, /* tp_descr_get */
1592 0, /* tp_descr_set */
1593 offsetof(PyODictObject, od_inst_dict), /* tp_dictoffset */
1594 (initproc)odict_init, /* tp_init */
1595 PyType_GenericAlloc, /* tp_alloc */
1596 0, /* tp_new */
1597 0, /* tp_free */
1598 };
1599
1600
1601 /* ----------------------------------------------
1602 * the public OrderedDict API
1603 */
1604
1605 PyObject *
PyODict_New(void)1606 PyODict_New(void)
1607 {
1608 return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL);
1609 }
1610
1611 static int
_PyODict_SetItem_KnownHash(PyObject * od,PyObject * key,PyObject * value,Py_hash_t hash)1612 _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,
1613 Py_hash_t hash)
1614 {
1615 int res = _PyDict_SetItem_KnownHash(od, key, value, hash);
1616 if (res == 0) {
1617 res = _odict_add_new_node((PyODictObject *)od, key, hash);
1618 if (res < 0) {
1619 /* Revert setting the value on the dict */
1620 PyObject *exc, *val, *tb;
1621 PyErr_Fetch(&exc, &val, &tb);
1622 (void) _PyDict_DelItem_KnownHash(od, key, hash);
1623 _PyErr_ChainExceptions(exc, val, tb);
1624 }
1625 }
1626 return res;
1627 }
1628
1629 int
PyODict_SetItem(PyObject * od,PyObject * key,PyObject * value)1630 PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value)
1631 {
1632 Py_hash_t hash = PyObject_Hash(key);
1633 if (hash == -1)
1634 return -1;
1635 return _PyODict_SetItem_KnownHash(od, key, value, hash);
1636 }
1637
1638 int
PyODict_DelItem(PyObject * od,PyObject * key)1639 PyODict_DelItem(PyObject *od, PyObject *key)
1640 {
1641 int res;
1642 Py_hash_t hash = PyObject_Hash(key);
1643 if (hash == -1)
1644 return -1;
1645 res = _odict_clear_node((PyODictObject *)od, NULL, key, hash);
1646 if (res < 0)
1647 return -1;
1648 return _PyDict_DelItem_KnownHash(od, key, hash);
1649 }
1650
1651
1652 /* -------------------------------------------
1653 * The OrderedDict views (keys/values/items)
1654 */
1655
1656 typedef struct {
1657 PyObject_HEAD
1658 int kind;
1659 PyODictObject *di_odict;
1660 Py_ssize_t di_size;
1661 size_t di_state;
1662 PyObject *di_current;
1663 PyObject *di_result; /* reusable result tuple for iteritems */
1664 } odictiterobject;
1665
1666 static void
odictiter_dealloc(odictiterobject * di)1667 odictiter_dealloc(odictiterobject *di)
1668 {
1669 _PyObject_GC_UNTRACK(di);
1670 Py_XDECREF(di->di_odict);
1671 Py_XDECREF(di->di_current);
1672 if (di->kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)) {
1673 Py_DECREF(di->di_result);
1674 }
1675 PyObject_GC_Del(di);
1676 }
1677
1678 static int
odictiter_traverse(odictiterobject * di,visitproc visit,void * arg)1679 odictiter_traverse(odictiterobject *di, visitproc visit, void *arg)
1680 {
1681 Py_VISIT(di->di_odict);
1682 Py_VISIT(di->di_current); /* A key could be any type, not just str. */
1683 Py_VISIT(di->di_result);
1684 return 0;
1685 }
1686
1687 /* In order to protect against modifications during iteration, we track
1688 * the current key instead of the current node. */
1689 static PyObject *
odictiter_nextkey(odictiterobject * di)1690 odictiter_nextkey(odictiterobject *di)
1691 {
1692 PyObject *key = NULL;
1693 _ODictNode *node;
1694 int reversed = di->kind & _odict_ITER_REVERSED;
1695
1696 if (di->di_odict == NULL)
1697 return NULL;
1698 if (di->di_current == NULL)
1699 goto done; /* We're already done. */
1700
1701 /* Check for unsupported changes. */
1702 if (di->di_odict->od_state != di->di_state) {
1703 PyErr_SetString(PyExc_RuntimeError,
1704 "OrderedDict mutated during iteration");
1705 goto done;
1706 }
1707 if (di->di_size != PyODict_SIZE(di->di_odict)) {
1708 PyErr_SetString(PyExc_RuntimeError,
1709 "OrderedDict changed size during iteration");
1710 di->di_size = -1; /* Make this state sticky */
1711 return NULL;
1712 }
1713
1714 /* Get the key. */
1715 node = _odict_find_node(di->di_odict, di->di_current);
1716 if (node == NULL) {
1717 if (!PyErr_Occurred())
1718 PyErr_SetObject(PyExc_KeyError, di->di_current);
1719 /* Must have been deleted. */
1720 Py_CLEAR(di->di_current);
1721 return NULL;
1722 }
1723 key = di->di_current;
1724
1725 /* Advance to the next key. */
1726 node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
1727 if (node == NULL) {
1728 /* Reached the end. */
1729 di->di_current = NULL;
1730 }
1731 else {
1732 di->di_current = _odictnode_KEY(node);
1733 Py_INCREF(di->di_current);
1734 }
1735
1736 return key;
1737
1738 done:
1739 Py_CLEAR(di->di_odict);
1740 return key;
1741 }
1742
1743 static PyObject *
odictiter_iternext(odictiterobject * di)1744 odictiter_iternext(odictiterobject *di)
1745 {
1746 PyObject *result, *value;
1747 PyObject *key = odictiter_nextkey(di); /* new reference */
1748
1749 if (key == NULL)
1750 return NULL;
1751
1752 /* Handle the keys case. */
1753 if (! (di->kind & _odict_ITER_VALUES)) {
1754 return key;
1755 }
1756
1757 value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */
1758 if (value == NULL) {
1759 if (!PyErr_Occurred())
1760 PyErr_SetObject(PyExc_KeyError, key);
1761 Py_DECREF(key);
1762 goto done;
1763 }
1764 Py_INCREF(value);
1765
1766 /* Handle the values case. */
1767 if (!(di->kind & _odict_ITER_KEYS)) {
1768 Py_DECREF(key);
1769 return value;
1770 }
1771
1772 /* Handle the items case. */
1773 result = di->di_result;
1774
1775 if (Py_REFCNT(result) == 1) {
1776 /* not in use so we can reuse it
1777 * (the common case during iteration) */
1778 Py_INCREF(result);
1779 Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */
1780 Py_DECREF(PyTuple_GET_ITEM(result, 1)); /* borrowed */
1781 }
1782 else {
1783 result = PyTuple_New(2);
1784 if (result == NULL) {
1785 Py_DECREF(key);
1786 Py_DECREF(value);
1787 goto done;
1788 }
1789 }
1790
1791 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1792 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
1793 return result;
1794
1795 done:
1796 Py_CLEAR(di->di_current);
1797 Py_CLEAR(di->di_odict);
1798 return NULL;
1799 }
1800
1801 /* No need for tp_clear because odictiterobject is not mutable. */
1802
1803 PyDoc_STRVAR(reduce_doc, "Return state information for pickling");
1804
1805 static PyObject *
odictiter_reduce(odictiterobject * di,PyObject * Py_UNUSED (ignored))1806 odictiter_reduce(odictiterobject *di, PyObject *Py_UNUSED(ignored))
1807 {
1808 /* copy the iterator state */
1809 odictiterobject tmp = *di;
1810 Py_XINCREF(tmp.di_odict);
1811 Py_XINCREF(tmp.di_current);
1812
1813 /* iterate the temporary into a list */
1814 PyObject *list = PySequence_List((PyObject*)&tmp);
1815 Py_XDECREF(tmp.di_odict);
1816 Py_XDECREF(tmp.di_current);
1817 if (list == NULL) {
1818 return NULL;
1819 }
1820 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
1821 }
1822
1823 static PyMethodDef odictiter_methods[] = {
1824 {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc},
1825 {NULL, NULL} /* sentinel */
1826 };
1827
1828 PyTypeObject PyODictIter_Type = {
1829 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1830 "odict_iterator", /* tp_name */
1831 sizeof(odictiterobject), /* tp_basicsize */
1832 0, /* tp_itemsize */
1833 /* methods */
1834 (destructor)odictiter_dealloc, /* tp_dealloc */
1835 0, /* tp_print */
1836 0, /* tp_getattr */
1837 0, /* tp_setattr */
1838 0, /* tp_reserved */
1839 0, /* tp_repr */
1840 0, /* tp_as_number */
1841 0, /* tp_as_sequence */
1842 0, /* tp_as_mapping */
1843 0, /* tp_hash */
1844 0, /* tp_call */
1845 0, /* tp_str */
1846 PyObject_GenericGetAttr, /* tp_getattro */
1847 0, /* tp_setattro */
1848 0, /* tp_as_buffer */
1849 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1850 0, /* tp_doc */
1851 (traverseproc)odictiter_traverse, /* tp_traverse */
1852 0, /* tp_clear */
1853 0, /* tp_richcompare */
1854 0, /* tp_weaklistoffset */
1855 PyObject_SelfIter, /* tp_iter */
1856 (iternextfunc)odictiter_iternext, /* tp_iternext */
1857 odictiter_methods, /* tp_methods */
1858 0,
1859 };
1860
1861 static PyObject *
odictiter_new(PyODictObject * od,int kind)1862 odictiter_new(PyODictObject *od, int kind)
1863 {
1864 odictiterobject *di;
1865 _ODictNode *node;
1866 int reversed = kind & _odict_ITER_REVERSED;
1867
1868 di = PyObject_GC_New(odictiterobject, &PyODictIter_Type);
1869 if (di == NULL)
1870 return NULL;
1871
1872 if (kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)){
1873 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
1874 if (di->di_result == NULL) {
1875 Py_DECREF(di);
1876 return NULL;
1877 }
1878 }
1879 else
1880 di->di_result = NULL;
1881
1882 di->kind = kind;
1883 node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
1884 di->di_current = node ? _odictnode_KEY(node) : NULL;
1885 Py_XINCREF(di->di_current);
1886 di->di_size = PyODict_SIZE(od);
1887 di->di_state = od->od_state;
1888 di->di_odict = od;
1889 Py_INCREF(od);
1890
1891 _PyObject_GC_TRACK(di);
1892 return (PyObject *)di;
1893 }
1894
1895 /* keys() */
1896
1897 static PyObject *
odictkeys_iter(_PyDictViewObject * dv)1898 odictkeys_iter(_PyDictViewObject *dv)
1899 {
1900 if (dv->dv_dict == NULL) {
1901 Py_RETURN_NONE;
1902 }
1903 return odictiter_new((PyODictObject *)dv->dv_dict,
1904 _odict_ITER_KEYS);
1905 }
1906
1907 static PyObject *
odictkeys_reversed(_PyDictViewObject * dv)1908 odictkeys_reversed(_PyDictViewObject *dv)
1909 {
1910 if (dv->dv_dict == NULL) {
1911 Py_RETURN_NONE;
1912 }
1913 return odictiter_new((PyODictObject *)dv->dv_dict,
1914 _odict_ITER_KEYS|_odict_ITER_REVERSED);
1915 }
1916
1917 static PyMethodDef odictkeys_methods[] = {
1918 {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL},
1919 {NULL, NULL} /* sentinel */
1920 };
1921
1922 PyTypeObject PyODictKeys_Type = {
1923 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1924 "odict_keys", /* tp_name */
1925 0, /* tp_basicsize */
1926 0, /* tp_itemsize */
1927 0, /* tp_dealloc */
1928 0, /* tp_print */
1929 0, /* tp_getattr */
1930 0, /* tp_setattr */
1931 0, /* tp_reserved */
1932 0, /* tp_repr */
1933 0, /* tp_as_number */
1934 0, /* tp_as_sequence */
1935 0, /* tp_as_mapping */
1936 0, /* tp_hash */
1937 0, /* tp_call */
1938 0, /* tp_str */
1939 0, /* tp_getattro */
1940 0, /* tp_setattro */
1941 0, /* tp_as_buffer */
1942 0, /* tp_flags */
1943 0, /* tp_doc */
1944 0, /* tp_traverse */
1945 0, /* tp_clear */
1946 0, /* tp_richcompare */
1947 0, /* tp_weaklistoffset */
1948 (getiterfunc)odictkeys_iter, /* tp_iter */
1949 0, /* tp_iternext */
1950 odictkeys_methods, /* tp_methods */
1951 0, /* tp_members */
1952 0, /* tp_getset */
1953 &PyDictKeys_Type, /* tp_base */
1954 };
1955
1956 static PyObject *
odictkeys_new(PyObject * od)1957 odictkeys_new(PyObject *od)
1958 {
1959 return _PyDictView_New(od, &PyODictKeys_Type);
1960 }
1961
1962 /* items() */
1963
1964 static PyObject *
odictitems_iter(_PyDictViewObject * dv)1965 odictitems_iter(_PyDictViewObject *dv)
1966 {
1967 if (dv->dv_dict == NULL) {
1968 Py_RETURN_NONE;
1969 }
1970 return odictiter_new((PyODictObject *)dv->dv_dict,
1971 _odict_ITER_KEYS|_odict_ITER_VALUES);
1972 }
1973
1974 static PyObject *
odictitems_reversed(_PyDictViewObject * dv)1975 odictitems_reversed(_PyDictViewObject *dv)
1976 {
1977 if (dv->dv_dict == NULL) {
1978 Py_RETURN_NONE;
1979 }
1980 return odictiter_new((PyODictObject *)dv->dv_dict,
1981 _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED);
1982 }
1983
1984 static PyMethodDef odictitems_methods[] = {
1985 {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL},
1986 {NULL, NULL} /* sentinel */
1987 };
1988
1989 PyTypeObject PyODictItems_Type = {
1990 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1991 "odict_items", /* tp_name */
1992 0, /* tp_basicsize */
1993 0, /* tp_itemsize */
1994 0, /* tp_dealloc */
1995 0, /* tp_print */
1996 0, /* tp_getattr */
1997 0, /* tp_setattr */
1998 0, /* tp_reserved */
1999 0, /* tp_repr */
2000 0, /* tp_as_number */
2001 0, /* tp_as_sequence */
2002 0, /* tp_as_mapping */
2003 0, /* tp_hash */
2004 0, /* tp_call */
2005 0, /* tp_str */
2006 0, /* tp_getattro */
2007 0, /* tp_setattro */
2008 0, /* tp_as_buffer */
2009 0, /* tp_flags */
2010 0, /* tp_doc */
2011 0, /* tp_traverse */
2012 0, /* tp_clear */
2013 0, /* tp_richcompare */
2014 0, /* tp_weaklistoffset */
2015 (getiterfunc)odictitems_iter, /* tp_iter */
2016 0, /* tp_iternext */
2017 odictitems_methods, /* tp_methods */
2018 0, /* tp_members */
2019 0, /* tp_getset */
2020 &PyDictItems_Type, /* tp_base */
2021 };
2022
2023 static PyObject *
odictitems_new(PyObject * od)2024 odictitems_new(PyObject *od)
2025 {
2026 return _PyDictView_New(od, &PyODictItems_Type);
2027 }
2028
2029 /* values() */
2030
2031 static PyObject *
odictvalues_iter(_PyDictViewObject * dv)2032 odictvalues_iter(_PyDictViewObject *dv)
2033 {
2034 if (dv->dv_dict == NULL) {
2035 Py_RETURN_NONE;
2036 }
2037 return odictiter_new((PyODictObject *)dv->dv_dict,
2038 _odict_ITER_VALUES);
2039 }
2040
2041 static PyObject *
odictvalues_reversed(_PyDictViewObject * dv)2042 odictvalues_reversed(_PyDictViewObject *dv)
2043 {
2044 if (dv->dv_dict == NULL) {
2045 Py_RETURN_NONE;
2046 }
2047 return odictiter_new((PyODictObject *)dv->dv_dict,
2048 _odict_ITER_VALUES|_odict_ITER_REVERSED);
2049 }
2050
2051 static PyMethodDef odictvalues_methods[] = {
2052 {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL},
2053 {NULL, NULL} /* sentinel */
2054 };
2055
2056 PyTypeObject PyODictValues_Type = {
2057 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2058 "odict_values", /* tp_name */
2059 0, /* tp_basicsize */
2060 0, /* tp_itemsize */
2061 0, /* tp_dealloc */
2062 0, /* tp_print */
2063 0, /* tp_getattr */
2064 0, /* tp_setattr */
2065 0, /* tp_reserved */
2066 0, /* tp_repr */
2067 0, /* tp_as_number */
2068 0, /* tp_as_sequence */
2069 0, /* tp_as_mapping */
2070 0, /* tp_hash */
2071 0, /* tp_call */
2072 0, /* tp_str */
2073 0, /* tp_getattro */
2074 0, /* tp_setattro */
2075 0, /* tp_as_buffer */
2076 0, /* tp_flags */
2077 0, /* tp_doc */
2078 0, /* tp_traverse */
2079 0, /* tp_clear */
2080 0, /* tp_richcompare */
2081 0, /* tp_weaklistoffset */
2082 (getiterfunc)odictvalues_iter, /* tp_iter */
2083 0, /* tp_iternext */
2084 odictvalues_methods, /* tp_methods */
2085 0, /* tp_members */
2086 0, /* tp_getset */
2087 &PyDictValues_Type, /* tp_base */
2088 };
2089
2090 static PyObject *
odictvalues_new(PyObject * od)2091 odictvalues_new(PyObject *od)
2092 {
2093 return _PyDictView_New(od, &PyODictValues_Type);
2094 }
2095
2096
2097 /* ----------------------------------------------
2098 MutableMapping implementations
2099
2100 Mapping:
2101
2102 ============ ===========
2103 method uses
2104 ============ ===========
2105 __contains__ __getitem__
2106 __eq__ items
2107 __getitem__ +
2108 __iter__ +
2109 __len__ +
2110 __ne__ __eq__
2111 get __getitem__
2112 items ItemsView
2113 keys KeysView
2114 values ValuesView
2115 ============ ===========
2116
2117 ItemsView uses __len__, __iter__, and __getitem__.
2118 KeysView uses __len__, __iter__, and __contains__.
2119 ValuesView uses __len__, __iter__, and __getitem__.
2120
2121 MutableMapping:
2122
2123 ============ ===========
2124 method uses
2125 ============ ===========
2126 __delitem__ +
2127 __setitem__ +
2128 clear popitem
2129 pop __getitem__
2130 __delitem__
2131 popitem __iter__
2132 _getitem__
2133 __delitem__
2134 setdefault __getitem__
2135 __setitem__
2136 update __setitem__
2137 ============ ===========
2138 */
2139
2140 static int
mutablemapping_add_pairs(PyObject * self,PyObject * pairs)2141 mutablemapping_add_pairs(PyObject *self, PyObject *pairs)
2142 {
2143 PyObject *pair, *iterator, *unexpected;
2144 int res = 0;
2145
2146 iterator = PyObject_GetIter(pairs);
2147 if (iterator == NULL)
2148 return -1;
2149 PyErr_Clear();
2150
2151 while ((pair = PyIter_Next(iterator)) != NULL) {
2152 /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */
2153 PyObject *key = NULL, *value = NULL;
2154 PyObject *pair_iterator = PyObject_GetIter(pair);
2155 if (pair_iterator == NULL)
2156 goto Done;
2157
2158 key = PyIter_Next(pair_iterator);
2159 if (key == NULL) {
2160 if (!PyErr_Occurred())
2161 PyErr_SetString(PyExc_ValueError,
2162 "need more than 0 values to unpack");
2163 goto Done;
2164 }
2165
2166 value = PyIter_Next(pair_iterator);
2167 if (value == NULL) {
2168 if (!PyErr_Occurred())
2169 PyErr_SetString(PyExc_ValueError,
2170 "need more than 1 value to unpack");
2171 goto Done;
2172 }
2173
2174 unexpected = PyIter_Next(pair_iterator);
2175 if (unexpected != NULL) {
2176 Py_DECREF(unexpected);
2177 PyErr_SetString(PyExc_ValueError,
2178 "too many values to unpack (expected 2)");
2179 goto Done;
2180 }
2181 else if (PyErr_Occurred())
2182 goto Done;
2183
2184 res = PyObject_SetItem(self, key, value);
2185
2186 Done:
2187 Py_DECREF(pair);
2188 Py_XDECREF(pair_iterator);
2189 Py_XDECREF(key);
2190 Py_XDECREF(value);
2191 if (PyErr_Occurred())
2192 break;
2193 }
2194 Py_DECREF(iterator);
2195
2196 if (res < 0 || PyErr_Occurred() != NULL)
2197 return -1;
2198 else
2199 return 0;
2200 }
2201
2202 static PyObject *
mutablemapping_update(PyObject * self,PyObject * args,PyObject * kwargs)2203 mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs)
2204 {
2205 int res = 0;
2206 Py_ssize_t len;
2207 _Py_IDENTIFIER(items);
2208 _Py_IDENTIFIER(keys);
2209
2210 /* first handle args, if any */
2211 assert(args == NULL || PyTuple_Check(args));
2212 len = (args != NULL) ? PyTuple_GET_SIZE(args) : 0;
2213 if (len > 1) {
2214 const char *msg = "update() takes at most 1 positional argument (%d given)";
2215 PyErr_Format(PyExc_TypeError, msg, len);
2216 return NULL;
2217 }
2218
2219 if (len) {
2220 PyObject *func;
2221 PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */
2222 assert(other != NULL);
2223 Py_INCREF(other);
2224 if (PyDict_CheckExact(other)) {
2225 PyObject *items = PyDict_Items(other);
2226 Py_DECREF(other);
2227 if (items == NULL)
2228 return NULL;
2229 res = mutablemapping_add_pairs(self, items);
2230 Py_DECREF(items);
2231 if (res == -1)
2232 return NULL;
2233 goto handle_kwargs;
2234 }
2235
2236 if (_PyObject_LookupAttrId(other, &PyId_keys, &func) < 0) {
2237 Py_DECREF(other);
2238 return NULL;
2239 }
2240 if (func != NULL) {
2241 PyObject *keys, *iterator, *key;
2242 keys = _PyObject_CallNoArg(func);
2243 Py_DECREF(func);
2244 if (keys == NULL) {
2245 Py_DECREF(other);
2246 return NULL;
2247 }
2248 iterator = PyObject_GetIter(keys);
2249 Py_DECREF(keys);
2250 if (iterator == NULL) {
2251 Py_DECREF(other);
2252 return NULL;
2253 }
2254 while (res == 0 && (key = PyIter_Next(iterator))) {
2255 PyObject *value = PyObject_GetItem(other, key);
2256 if (value != NULL) {
2257 res = PyObject_SetItem(self, key, value);
2258 Py_DECREF(value);
2259 }
2260 else {
2261 res = -1;
2262 }
2263 Py_DECREF(key);
2264 }
2265 Py_DECREF(other);
2266 Py_DECREF(iterator);
2267 if (res != 0 || PyErr_Occurred())
2268 return NULL;
2269 goto handle_kwargs;
2270 }
2271
2272 if (_PyObject_LookupAttrId(other, &PyId_items, &func) < 0) {
2273 Py_DECREF(other);
2274 return NULL;
2275 }
2276 if (func != NULL) {
2277 PyObject *items;
2278 Py_DECREF(other);
2279 items = _PyObject_CallNoArg(func);
2280 Py_DECREF(func);
2281 if (items == NULL)
2282 return NULL;
2283 res = mutablemapping_add_pairs(self, items);
2284 Py_DECREF(items);
2285 if (res == -1)
2286 return NULL;
2287 goto handle_kwargs;
2288 }
2289
2290 res = mutablemapping_add_pairs(self, other);
2291 Py_DECREF(other);
2292 if (res != 0)
2293 return NULL;
2294 }
2295
2296 handle_kwargs:
2297 /* now handle kwargs */
2298 assert(kwargs == NULL || PyDict_Check(kwargs));
2299 if (kwargs != NULL && PyDict_GET_SIZE(kwargs)) {
2300 PyObject *items = PyDict_Items(kwargs);
2301 if (items == NULL)
2302 return NULL;
2303 res = mutablemapping_add_pairs(self, items);
2304 Py_DECREF(items);
2305 if (res == -1)
2306 return NULL;
2307 }
2308
2309 Py_RETURN_NONE;
2310 }
2311