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