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 "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]
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 _Py_IDENTIFIER(items);
529
530 /* Return the index into the hash table, regardless of a valid node. */
531 static Py_ssize_t
_odict_get_index_raw(PyODictObject * od,PyObject * key,Py_hash_t hash)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. */
549 static int
_odict_resize(PyODictObject * od)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. */
585 static Py_ssize_t
_odict_get_index(PyODictObject * od,PyObject * key,Py_hash_t hash)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. */
605 static _ODictNode *
_odict_find_node_hash(PyODictObject * od,PyObject * key,Py_hash_t hash)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
619 static _ODictNode *
_odict_find_node(PyODictObject * od,PyObject * key)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
637 static void
_odict_add_head(PyODictObject * od,_ODictNode * node)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
650 static void
_odict_add_tail(PyODictObject * od,_ODictNode * node)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 */
664 static int
_odict_add_new_node(PyODictObject * od,PyObject * key,Py_hash_t hash)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. */
708 static void
_odict_remove_node(PyODictObject * od,_ODictNode * node)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 */
742 static int
_odict_clear_node(PyODictObject * od,_ODictNode * node,PyObject * key,Py_hash_t hash)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
774 static void
_odict_clear_nodes(PyODictObject * od)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
797 static int
_odict_keys_equal(PyODictObject * a,PyODictObject * b)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
835 static int
odict_mp_ass_sub(PyODictObject * od,PyObject * v,PyObject * w)836 odict_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
846 static 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
857 static int mutablemapping_update_arg(PyObject*, PyObject*);
858
859 static PyObject *
odict_or(PyObject * left,PyObject * right)860 odict_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
886 static PyObject *
odict_inplace_or(PyObject * self,PyObject * other)887 odict_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
898 static 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
912 OrderedDict.fromkeys
913
914 iterable as seq: object
915 value: object = None
916
917 Create a new ordered dictionary with keys from iterable and values set to value.
918 [clinic start generated code]*/
919
920 static PyObject *
OrderedDict_fromkeys_impl(PyTypeObject * type,PyObject * seq,PyObject * value)921 OrderedDict_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. */
930 PyDoc_STRVAR(odict_sizeof__doc__, "");
931
932 static PyObject *
odict_sizeof(PyODictObject * od,PyObject * Py_UNUSED (ignored))933 odict_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
945 PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling");
946
947 static PyObject *
odict_reduce(register PyODictObject * od,PyObject * Py_UNUSED (ignored))948 odict_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
986 Done:
987 Py_XDECREF(dict);
988 Py_XDECREF(args);
989
990 return result;
991 }
992
993 /* setdefault(): Skips __missing__() calls. */
994
995
996 /*[clinic input]
997 OrderedDict.setdefault
998
999 key: object
1000 default: object = None
1001
1002 Insert key with a value of default if key is not in the dictionary.
1003
1004 Return the value for key if key is in the dictionary, else default.
1005 [clinic start generated code]*/
1006
1007 static PyObject *
OrderedDict_setdefault_impl(PyODictObject * self,PyObject * key,PyObject * default_value)1008 OrderedDict_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 */
1049 static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *);
1050
1051 /* Skips __missing__() calls. */
1052 /*[clinic input]
1053 OrderedDict.pop
1054
1055 key: object
1056 default: object = NULL
1057
1058 od.pop(key[,default]) -> v, remove specified key and return the corresponding value.
1059
1060 If the key is not found, return the default if given; otherwise,
1061 raise a KeyError.
1062 [clinic start generated code]*/
1063
1064 static PyObject *
OrderedDict_pop_impl(PyODictObject * self,PyObject * key,PyObject * default_value)1065 OrderedDict_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
1072 static PyObject *
_odict_popkey_hash(PyObject * od,PyObject * key,PyObject * failobj,Py_hash_t hash)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
1135 static PyObject *
_odict_popkey(PyObject * od,PyObject * key,PyObject * failobj)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]
1149 OrderedDict.popitem
1150
1151 last: bool = True
1152
1153 Remove and return a (key, value) pair from the dictionary.
1154
1155 Pairs are returned in LIFO order if last is true or FIFO order if false.
1156 [clinic start generated code]*/
1157
1158 static PyObject *
OrderedDict_popitem_impl(PyODictObject * self,int last)1159 OrderedDict_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. */
1187 PyDoc_STRVAR(odict_keys__doc__, "");
1188
1189 static PyObject * odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1190
1191 /* values() */
1192
1193 /* MutableMapping.values() does not have a docstring. */
1194 PyDoc_STRVAR(odict_values__doc__, "");
1195
1196 static PyObject * odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1197
1198 /* items() */
1199
1200 /* MutableMapping.items() does not have a docstring. */
1201 PyDoc_STRVAR(odict_items__doc__, "");
1202
1203 static PyObject * odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1204
1205 /* update() */
1206
1207 /* MutableMapping.update() does not have a docstring. */
1208 PyDoc_STRVAR(odict_update__doc__, "");
1209
1210 /* forward */
1211 static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *);
1212
1213 #define odict_update mutablemapping_update
1214
1215 /* clear() */
1216
1217 PyDoc_STRVAR(odict_clear__doc__,
1218 "od.clear() -> None. Remove all items from od.");
1219
1220 static PyObject *
odict_clear(register PyODictObject * od,PyObject * Py_UNUSED (ignored))1221 odict_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 */
1231 static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *,
1232 Py_hash_t);
1233
1234 PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od");
1235
1236 static PyObject *
odict_copy(register PyODictObject * od,PyObject * Py_UNUSED (ignored))1237 odict_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
1279 fail:
1280 Py_DECREF(od_copy);
1281 return NULL;
1282 }
1283
1284 /* __reversed__() */
1285
1286 PyDoc_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
1292 /* forward */
1293 static PyObject * odictiter_new(PyODictObject *, int);
1294
1295 static PyObject *
odict_reversed(PyODictObject * od,PyObject * Py_UNUSED (ignored))1296 odict_reversed(PyODictObject *od, PyObject *Py_UNUSED(ignored))
1297 {
1298 return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED);
1299 }
1300
1301
1302 /* move_to_end() */
1303
1304 /*[clinic input]
1305 OrderedDict.move_to_end
1306
1307 key: object
1308 last: bool = True
1309
1310 Move an existing element to the end (or beginning if last is false).
1311
1312 Raise KeyError if the element does not exist.
1313 [clinic start generated code]*/
1314
1315 static PyObject *
OrderedDict_move_to_end_impl(PyODictObject * self,PyObject * key,int last)1316 OrderedDict_move_to_end_impl(PyODictObject *self, PyObject *key, int last)
1317 /*[clinic end generated code: output=fafa4c5cc9b92f20 input=d6ceff7132a2fcd7]*/
1318 {
1319 _ODictNode *node;
1320
1321 if (_odict_EMPTY(self)) {
1322 PyErr_SetObject(PyExc_KeyError, key);
1323 return NULL;
1324 }
1325 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1326 if (key != _odictnode_KEY(node)) {
1327 node = _odict_find_node(self, key);
1328 if (node == NULL) {
1329 if (!PyErr_Occurred())
1330 PyErr_SetObject(PyExc_KeyError, key);
1331 return NULL;
1332 }
1333 if (last) {
1334 /* Only move if not already the last one. */
1335 if (node != _odict_LAST(self)) {
1336 _odict_remove_node(self, node);
1337 _odict_add_tail(self, node);
1338 }
1339 }
1340 else {
1341 /* Only move if not already the first one. */
1342 if (node != _odict_FIRST(self)) {
1343 _odict_remove_node(self, node);
1344 _odict_add_head(self, node);
1345 }
1346 }
1347 }
1348 Py_RETURN_NONE;
1349 }
1350
1351
1352 /* tp_methods */
1353
1354 static PyMethodDef odict_methods[] = {
1355
1356 /* overridden dict methods */
1357 ORDEREDDICT_FROMKEYS_METHODDEF
1358 {"__sizeof__", (PyCFunction)odict_sizeof, METH_NOARGS,
1359 odict_sizeof__doc__},
1360 {"__reduce__", (PyCFunction)odict_reduce, METH_NOARGS,
1361 odict_reduce__doc__},
1362 ORDEREDDICT_SETDEFAULT_METHODDEF
1363 ORDEREDDICT_POP_METHODDEF
1364 ORDEREDDICT_POPITEM_METHODDEF
1365 {"keys", odictkeys_new, METH_NOARGS,
1366 odict_keys__doc__},
1367 {"values", odictvalues_new, METH_NOARGS,
1368 odict_values__doc__},
1369 {"items", odictitems_new, METH_NOARGS,
1370 odict_items__doc__},
1371 {"update", (PyCFunction)(void(*)(void))odict_update, METH_VARARGS | METH_KEYWORDS,
1372 odict_update__doc__},
1373 {"clear", (PyCFunction)odict_clear, METH_NOARGS,
1374 odict_clear__doc__},
1375 {"copy", (PyCFunction)odict_copy, METH_NOARGS,
1376 odict_copy__doc__},
1377
1378 /* new methods */
1379 {"__reversed__", (PyCFunction)odict_reversed, METH_NOARGS,
1380 odict_reversed__doc__},
1381 ORDEREDDICT_MOVE_TO_END_METHODDEF
1382
1383 {NULL, NULL} /* sentinel */
1384 };
1385
1386
1387 /* ----------------------------------------------
1388 * OrderedDict members
1389 */
1390
1391 /* tp_getset */
1392
1393 static PyGetSetDef odict_getset[] = {
1394 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
1395 {NULL}
1396 };
1397
1398 /* ----------------------------------------------
1399 * OrderedDict type slot methods
1400 */
1401
1402 /* tp_dealloc */
1403
1404 static void
odict_dealloc(PyODictObject * self)1405 odict_dealloc(PyODictObject *self)
1406 {
1407 PyObject_GC_UnTrack(self);
1408 Py_TRASHCAN_BEGIN(self, odict_dealloc)
1409
1410 Py_XDECREF(self->od_inst_dict);
1411 if (self->od_weakreflist != NULL)
1412 PyObject_ClearWeakRefs((PyObject *)self);
1413
1414 _odict_clear_nodes(self);
1415 PyDict_Type.tp_dealloc((PyObject *)self);
1416
1417 Py_TRASHCAN_END
1418 }
1419
1420 /* tp_repr */
1421
1422 static PyObject *
odict_repr(PyODictObject * self)1423 odict_repr(PyODictObject *self)
1424 {
1425 int i;
1426 PyObject *pieces = NULL, *result = NULL;
1427
1428 if (PyODict_SIZE(self) == 0)
1429 return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self)));
1430
1431 i = Py_ReprEnter((PyObject *)self);
1432 if (i != 0) {
1433 return i > 0 ? PyUnicode_FromString("...") : NULL;
1434 }
1435
1436 if (PyODict_CheckExact(self)) {
1437 Py_ssize_t count = 0;
1438 _ODictNode *node;
1439 pieces = PyList_New(PyODict_SIZE(self));
1440 if (pieces == NULL)
1441 goto Done;
1442
1443 _odict_FOREACH(self, node) {
1444 PyObject *pair;
1445 PyObject *key = _odictnode_KEY(node);
1446 PyObject *value = _odictnode_VALUE(node, self);
1447 if (value == NULL) {
1448 if (!PyErr_Occurred())
1449 PyErr_SetObject(PyExc_KeyError, key);
1450 goto Done;
1451 }
1452 pair = PyTuple_Pack(2, key, value);
1453 if (pair == NULL)
1454 goto Done;
1455
1456 if (count < PyList_GET_SIZE(pieces))
1457 PyList_SET_ITEM(pieces, count, pair); /* steals reference */
1458 else {
1459 if (PyList_Append(pieces, pair) < 0) {
1460 Py_DECREF(pair);
1461 goto Done;
1462 }
1463 Py_DECREF(pair);
1464 }
1465 count++;
1466 }
1467 if (count < PyList_GET_SIZE(pieces)) {
1468 Py_SET_SIZE(pieces, count);
1469 }
1470 }
1471 else {
1472 PyObject *items = _PyObject_CallMethodIdNoArgs((PyObject *)self,
1473 &PyId_items);
1474 if (items == NULL)
1475 goto Done;
1476 pieces = PySequence_List(items);
1477 Py_DECREF(items);
1478 if (pieces == NULL)
1479 goto Done;
1480 }
1481
1482 result = PyUnicode_FromFormat("%s(%R)",
1483 _PyType_Name(Py_TYPE(self)), pieces);
1484
1485 Done:
1486 Py_XDECREF(pieces);
1487 Py_ReprLeave((PyObject *)self);
1488 return result;
1489 }
1490
1491 /* tp_doc */
1492
1493 PyDoc_STRVAR(odict_doc,
1494 "Dictionary that remembers insertion order");
1495
1496 /* tp_traverse */
1497
1498 static int
odict_traverse(PyODictObject * od,visitproc visit,void * arg)1499 odict_traverse(PyODictObject *od, visitproc visit, void *arg)
1500 {
1501 _ODictNode *node;
1502
1503 Py_VISIT(od->od_inst_dict);
1504 _odict_FOREACH(od, node) {
1505 Py_VISIT(_odictnode_KEY(node));
1506 }
1507 return PyDict_Type.tp_traverse((PyObject *)od, visit, arg);
1508 }
1509
1510 /* tp_clear */
1511
1512 static int
odict_tp_clear(PyODictObject * od)1513 odict_tp_clear(PyODictObject *od)
1514 {
1515 Py_CLEAR(od->od_inst_dict);
1516 PyDict_Clear((PyObject *)od);
1517 _odict_clear_nodes(od);
1518 return 0;
1519 }
1520
1521 /* tp_richcompare */
1522
1523 static PyObject *
odict_richcompare(PyObject * v,PyObject * w,int op)1524 odict_richcompare(PyObject *v, PyObject *w, int op)
1525 {
1526 if (!PyODict_Check(v) || !PyDict_Check(w)) {
1527 Py_RETURN_NOTIMPLEMENTED;
1528 }
1529
1530 if (op == Py_EQ || op == Py_NE) {
1531 PyObject *res, *cmp;
1532 int eq;
1533
1534 cmp = PyDict_Type.tp_richcompare(v, w, op);
1535 if (cmp == NULL)
1536 return NULL;
1537 if (!PyODict_Check(w))
1538 return cmp;
1539 if (op == Py_EQ && cmp == Py_False)
1540 return cmp;
1541 if (op == Py_NE && cmp == Py_True)
1542 return cmp;
1543 Py_DECREF(cmp);
1544
1545 /* Try comparing odict keys. */
1546 eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w);
1547 if (eq < 0)
1548 return NULL;
1549
1550 res = (eq == (op == Py_EQ)) ? Py_True : Py_False;
1551 Py_INCREF(res);
1552 return res;
1553 } else {
1554 Py_RETURN_NOTIMPLEMENTED;
1555 }
1556 }
1557
1558 /* tp_iter */
1559
1560 static PyObject *
odict_iter(PyODictObject * od)1561 odict_iter(PyODictObject *od)
1562 {
1563 return odictiter_new(od, _odict_ITER_KEYS);
1564 }
1565
1566 /* tp_init */
1567
1568 static int
odict_init(PyObject * self,PyObject * args,PyObject * kwds)1569 odict_init(PyObject *self, PyObject *args, PyObject *kwds)
1570 {
1571 PyObject *res;
1572 Py_ssize_t len = PyObject_Length(args);
1573
1574 if (len == -1)
1575 return -1;
1576 if (len > 1) {
1577 const char *msg = "expected at most 1 arguments, got %zd";
1578 PyErr_Format(PyExc_TypeError, msg, len);
1579 return -1;
1580 }
1581
1582 /* __init__() triggering update() is just the way things are! */
1583 res = odict_update(self, args, kwds);
1584 if (res == NULL) {
1585 return -1;
1586 } else {
1587 Py_DECREF(res);
1588 return 0;
1589 }
1590 }
1591
1592 /* PyODict_Type */
1593
1594 PyTypeObject PyODict_Type = {
1595 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1596 "collections.OrderedDict", /* tp_name */
1597 sizeof(PyODictObject), /* tp_basicsize */
1598 0, /* tp_itemsize */
1599 (destructor)odict_dealloc, /* tp_dealloc */
1600 0, /* tp_vectorcall_offset */
1601 0, /* tp_getattr */
1602 0, /* tp_setattr */
1603 0, /* tp_as_async */
1604 (reprfunc)odict_repr, /* tp_repr */
1605 &odict_as_number, /* tp_as_number */
1606 0, /* tp_as_sequence */
1607 &odict_as_mapping, /* tp_as_mapping */
1608 0, /* tp_hash */
1609 0, /* tp_call */
1610 0, /* tp_str */
1611 0, /* tp_getattro */
1612 0, /* tp_setattro */
1613 0, /* tp_as_buffer */
1614 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1615 odict_doc, /* tp_doc */
1616 (traverseproc)odict_traverse, /* tp_traverse */
1617 (inquiry)odict_tp_clear, /* tp_clear */
1618 (richcmpfunc)odict_richcompare, /* tp_richcompare */
1619 offsetof(PyODictObject, od_weakreflist), /* tp_weaklistoffset */
1620 (getiterfunc)odict_iter, /* tp_iter */
1621 0, /* tp_iternext */
1622 odict_methods, /* tp_methods */
1623 0, /* tp_members */
1624 odict_getset, /* tp_getset */
1625 &PyDict_Type, /* tp_base */
1626 0, /* tp_dict */
1627 0, /* tp_descr_get */
1628 0, /* tp_descr_set */
1629 offsetof(PyODictObject, od_inst_dict), /* tp_dictoffset */
1630 (initproc)odict_init, /* tp_init */
1631 PyType_GenericAlloc, /* tp_alloc */
1632 0, /* tp_new */
1633 0, /* tp_free */
1634 };
1635
1636
1637 /* ----------------------------------------------
1638 * the public OrderedDict API
1639 */
1640
1641 PyObject *
PyODict_New(void)1642 PyODict_New(void)
1643 {
1644 return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL);
1645 }
1646
1647 static int
_PyODict_SetItem_KnownHash(PyObject * od,PyObject * key,PyObject * value,Py_hash_t hash)1648 _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,
1649 Py_hash_t hash)
1650 {
1651 int res = _PyDict_SetItem_KnownHash(od, key, value, hash);
1652 if (res == 0) {
1653 res = _odict_add_new_node((PyODictObject *)od, key, hash);
1654 if (res < 0) {
1655 /* Revert setting the value on the dict */
1656 PyObject *exc, *val, *tb;
1657 PyErr_Fetch(&exc, &val, &tb);
1658 (void) _PyDict_DelItem_KnownHash(od, key, hash);
1659 _PyErr_ChainExceptions(exc, val, tb);
1660 }
1661 }
1662 return res;
1663 }
1664
1665 int
PyODict_SetItem(PyObject * od,PyObject * key,PyObject * value)1666 PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value)
1667 {
1668 Py_hash_t hash = PyObject_Hash(key);
1669 if (hash == -1)
1670 return -1;
1671 return _PyODict_SetItem_KnownHash(od, key, value, hash);
1672 }
1673
1674 int
PyODict_DelItem(PyObject * od,PyObject * key)1675 PyODict_DelItem(PyObject *od, PyObject *key)
1676 {
1677 int res;
1678 Py_hash_t hash = PyObject_Hash(key);
1679 if (hash == -1)
1680 return -1;
1681 res = _odict_clear_node((PyODictObject *)od, NULL, key, hash);
1682 if (res < 0)
1683 return -1;
1684 return _PyDict_DelItem_KnownHash(od, key, hash);
1685 }
1686
1687
1688 /* -------------------------------------------
1689 * The OrderedDict views (keys/values/items)
1690 */
1691
1692 typedef struct {
1693 PyObject_HEAD
1694 int kind;
1695 PyODictObject *di_odict;
1696 Py_ssize_t di_size;
1697 size_t di_state;
1698 PyObject *di_current;
1699 PyObject *di_result; /* reusable result tuple for iteritems */
1700 } odictiterobject;
1701
1702 static void
odictiter_dealloc(odictiterobject * di)1703 odictiter_dealloc(odictiterobject *di)
1704 {
1705 _PyObject_GC_UNTRACK(di);
1706 Py_XDECREF(di->di_odict);
1707 Py_XDECREF(di->di_current);
1708 if (di->kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)) {
1709 Py_DECREF(di->di_result);
1710 }
1711 PyObject_GC_Del(di);
1712 }
1713
1714 static int
odictiter_traverse(odictiterobject * di,visitproc visit,void * arg)1715 odictiter_traverse(odictiterobject *di, visitproc visit, void *arg)
1716 {
1717 Py_VISIT(di->di_odict);
1718 Py_VISIT(di->di_current); /* A key could be any type, not just str. */
1719 Py_VISIT(di->di_result);
1720 return 0;
1721 }
1722
1723 /* In order to protect against modifications during iteration, we track
1724 * the current key instead of the current node. */
1725 static PyObject *
odictiter_nextkey(odictiterobject * di)1726 odictiter_nextkey(odictiterobject *di)
1727 {
1728 PyObject *key = NULL;
1729 _ODictNode *node;
1730 int reversed = di->kind & _odict_ITER_REVERSED;
1731
1732 if (di->di_odict == NULL)
1733 return NULL;
1734 if (di->di_current == NULL)
1735 goto done; /* We're already done. */
1736
1737 /* Check for unsupported changes. */
1738 if (di->di_odict->od_state != di->di_state) {
1739 PyErr_SetString(PyExc_RuntimeError,
1740 "OrderedDict mutated during iteration");
1741 goto done;
1742 }
1743 if (di->di_size != PyODict_SIZE(di->di_odict)) {
1744 PyErr_SetString(PyExc_RuntimeError,
1745 "OrderedDict changed size during iteration");
1746 di->di_size = -1; /* Make this state sticky */
1747 return NULL;
1748 }
1749
1750 /* Get the key. */
1751 node = _odict_find_node(di->di_odict, di->di_current);
1752 if (node == NULL) {
1753 if (!PyErr_Occurred())
1754 PyErr_SetObject(PyExc_KeyError, di->di_current);
1755 /* Must have been deleted. */
1756 Py_CLEAR(di->di_current);
1757 return NULL;
1758 }
1759 key = di->di_current;
1760
1761 /* Advance to the next key. */
1762 node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
1763 if (node == NULL) {
1764 /* Reached the end. */
1765 di->di_current = NULL;
1766 }
1767 else {
1768 di->di_current = _odictnode_KEY(node);
1769 Py_INCREF(di->di_current);
1770 }
1771
1772 return key;
1773
1774 done:
1775 Py_CLEAR(di->di_odict);
1776 return key;
1777 }
1778
1779 static PyObject *
odictiter_iternext(odictiterobject * di)1780 odictiter_iternext(odictiterobject *di)
1781 {
1782 PyObject *result, *value;
1783 PyObject *key = odictiter_nextkey(di); /* new reference */
1784
1785 if (key == NULL)
1786 return NULL;
1787
1788 /* Handle the keys case. */
1789 if (! (di->kind & _odict_ITER_VALUES)) {
1790 return key;
1791 }
1792
1793 value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */
1794 if (value == NULL) {
1795 if (!PyErr_Occurred())
1796 PyErr_SetObject(PyExc_KeyError, key);
1797 Py_DECREF(key);
1798 goto done;
1799 }
1800 Py_INCREF(value);
1801
1802 /* Handle the values case. */
1803 if (!(di->kind & _odict_ITER_KEYS)) {
1804 Py_DECREF(key);
1805 return value;
1806 }
1807
1808 /* Handle the items case. */
1809 result = di->di_result;
1810
1811 if (Py_REFCNT(result) == 1) {
1812 /* not in use so we can reuse it
1813 * (the common case during iteration) */
1814 Py_INCREF(result);
1815 Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */
1816 Py_DECREF(PyTuple_GET_ITEM(result, 1)); /* borrowed */
1817 // bpo-42536: The GC may have untracked this result tuple. Since we're
1818 // recycling it, make sure it's tracked again:
1819 if (!_PyObject_GC_IS_TRACKED(result)) {
1820 _PyObject_GC_TRACK(result);
1821 }
1822 }
1823 else {
1824 result = PyTuple_New(2);
1825 if (result == NULL) {
1826 Py_DECREF(key);
1827 Py_DECREF(value);
1828 goto done;
1829 }
1830 }
1831
1832 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1833 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
1834 return result;
1835
1836 done:
1837 Py_CLEAR(di->di_current);
1838 Py_CLEAR(di->di_odict);
1839 return NULL;
1840 }
1841
1842 /* No need for tp_clear because odictiterobject is not mutable. */
1843
1844 PyDoc_STRVAR(reduce_doc, "Return state information for pickling");
1845
1846 static PyObject *
odictiter_reduce(odictiterobject * di,PyObject * Py_UNUSED (ignored))1847 odictiter_reduce(odictiterobject *di, PyObject *Py_UNUSED(ignored))
1848 {
1849 _Py_IDENTIFIER(iter);
1850 /* copy the iterator state */
1851 odictiterobject tmp = *di;
1852 Py_XINCREF(tmp.di_odict);
1853 Py_XINCREF(tmp.di_current);
1854
1855 /* iterate the temporary into a list */
1856 PyObject *list = PySequence_List((PyObject*)&tmp);
1857 Py_XDECREF(tmp.di_odict);
1858 Py_XDECREF(tmp.di_current);
1859 if (list == NULL) {
1860 return NULL;
1861 }
1862 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
1863 }
1864
1865 static PyMethodDef odictiter_methods[] = {
1866 {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc},
1867 {NULL, NULL} /* sentinel */
1868 };
1869
1870 PyTypeObject PyODictIter_Type = {
1871 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1872 "odict_iterator", /* tp_name */
1873 sizeof(odictiterobject), /* tp_basicsize */
1874 0, /* tp_itemsize */
1875 /* methods */
1876 (destructor)odictiter_dealloc, /* tp_dealloc */
1877 0, /* tp_vectorcall_offset */
1878 0, /* tp_getattr */
1879 0, /* tp_setattr */
1880 0, /* tp_as_async */
1881 0, /* tp_repr */
1882 0, /* tp_as_number */
1883 0, /* tp_as_sequence */
1884 0, /* tp_as_mapping */
1885 0, /* tp_hash */
1886 0, /* tp_call */
1887 0, /* tp_str */
1888 PyObject_GenericGetAttr, /* tp_getattro */
1889 0, /* tp_setattro */
1890 0, /* tp_as_buffer */
1891 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1892 0, /* tp_doc */
1893 (traverseproc)odictiter_traverse, /* tp_traverse */
1894 0, /* tp_clear */
1895 0, /* tp_richcompare */
1896 0, /* tp_weaklistoffset */
1897 PyObject_SelfIter, /* tp_iter */
1898 (iternextfunc)odictiter_iternext, /* tp_iternext */
1899 odictiter_methods, /* tp_methods */
1900 0,
1901 };
1902
1903 static PyObject *
odictiter_new(PyODictObject * od,int kind)1904 odictiter_new(PyODictObject *od, int kind)
1905 {
1906 odictiterobject *di;
1907 _ODictNode *node;
1908 int reversed = kind & _odict_ITER_REVERSED;
1909
1910 di = PyObject_GC_New(odictiterobject, &PyODictIter_Type);
1911 if (di == NULL)
1912 return NULL;
1913
1914 if (kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)){
1915 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
1916 if (di->di_result == NULL) {
1917 Py_DECREF(di);
1918 return NULL;
1919 }
1920 }
1921 else
1922 di->di_result = NULL;
1923
1924 di->kind = kind;
1925 node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
1926 di->di_current = node ? _odictnode_KEY(node) : NULL;
1927 Py_XINCREF(di->di_current);
1928 di->di_size = PyODict_SIZE(od);
1929 di->di_state = od->od_state;
1930 di->di_odict = od;
1931 Py_INCREF(od);
1932
1933 _PyObject_GC_TRACK(di);
1934 return (PyObject *)di;
1935 }
1936
1937 /* keys() */
1938
1939 static PyObject *
odictkeys_iter(_PyDictViewObject * dv)1940 odictkeys_iter(_PyDictViewObject *dv)
1941 {
1942 if (dv->dv_dict == NULL) {
1943 Py_RETURN_NONE;
1944 }
1945 return odictiter_new((PyODictObject *)dv->dv_dict,
1946 _odict_ITER_KEYS);
1947 }
1948
1949 static PyObject *
odictkeys_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))1950 odictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1951 {
1952 if (dv->dv_dict == NULL) {
1953 Py_RETURN_NONE;
1954 }
1955 return odictiter_new((PyODictObject *)dv->dv_dict,
1956 _odict_ITER_KEYS|_odict_ITER_REVERSED);
1957 }
1958
1959 static PyMethodDef odictkeys_methods[] = {
1960 {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL},
1961 {NULL, NULL} /* sentinel */
1962 };
1963
1964 PyTypeObject PyODictKeys_Type = {
1965 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1966 "odict_keys", /* tp_name */
1967 0, /* tp_basicsize */
1968 0, /* tp_itemsize */
1969 0, /* tp_dealloc */
1970 0, /* tp_vectorcall_offset */
1971 0, /* tp_getattr */
1972 0, /* tp_setattr */
1973 0, /* tp_as_async */
1974 0, /* tp_repr */
1975 0, /* tp_as_number */
1976 0, /* tp_as_sequence */
1977 0, /* tp_as_mapping */
1978 0, /* tp_hash */
1979 0, /* tp_call */
1980 0, /* tp_str */
1981 0, /* tp_getattro */
1982 0, /* tp_setattro */
1983 0, /* tp_as_buffer */
1984 0, /* tp_flags */
1985 0, /* tp_doc */
1986 0, /* tp_traverse */
1987 0, /* tp_clear */
1988 0, /* tp_richcompare */
1989 0, /* tp_weaklistoffset */
1990 (getiterfunc)odictkeys_iter, /* tp_iter */
1991 0, /* tp_iternext */
1992 odictkeys_methods, /* tp_methods */
1993 0, /* tp_members */
1994 0, /* tp_getset */
1995 &PyDictKeys_Type, /* tp_base */
1996 };
1997
1998 static PyObject *
odictkeys_new(PyObject * od,PyObject * Py_UNUSED (ignored))1999 odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored))
2000 {
2001 return _PyDictView_New(od, &PyODictKeys_Type);
2002 }
2003
2004 /* items() */
2005
2006 static PyObject *
odictitems_iter(_PyDictViewObject * dv)2007 odictitems_iter(_PyDictViewObject *dv)
2008 {
2009 if (dv->dv_dict == NULL) {
2010 Py_RETURN_NONE;
2011 }
2012 return odictiter_new((PyODictObject *)dv->dv_dict,
2013 _odict_ITER_KEYS|_odict_ITER_VALUES);
2014 }
2015
2016 static PyObject *
odictitems_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))2017 odictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2018 {
2019 if (dv->dv_dict == NULL) {
2020 Py_RETURN_NONE;
2021 }
2022 return odictiter_new((PyODictObject *)dv->dv_dict,
2023 _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED);
2024 }
2025
2026 static PyMethodDef odictitems_methods[] = {
2027 {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL},
2028 {NULL, NULL} /* sentinel */
2029 };
2030
2031 PyTypeObject PyODictItems_Type = {
2032 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2033 "odict_items", /* tp_name */
2034 0, /* tp_basicsize */
2035 0, /* tp_itemsize */
2036 0, /* tp_dealloc */
2037 0, /* tp_vectorcall_offset */
2038 0, /* tp_getattr */
2039 0, /* tp_setattr */
2040 0, /* tp_as_async */
2041 0, /* tp_repr */
2042 0, /* tp_as_number */
2043 0, /* tp_as_sequence */
2044 0, /* tp_as_mapping */
2045 0, /* tp_hash */
2046 0, /* tp_call */
2047 0, /* tp_str */
2048 0, /* tp_getattro */
2049 0, /* tp_setattro */
2050 0, /* tp_as_buffer */
2051 0, /* tp_flags */
2052 0, /* tp_doc */
2053 0, /* tp_traverse */
2054 0, /* tp_clear */
2055 0, /* tp_richcompare */
2056 0, /* tp_weaklistoffset */
2057 (getiterfunc)odictitems_iter, /* tp_iter */
2058 0, /* tp_iternext */
2059 odictitems_methods, /* tp_methods */
2060 0, /* tp_members */
2061 0, /* tp_getset */
2062 &PyDictItems_Type, /* tp_base */
2063 };
2064
2065 static PyObject *
odictitems_new(PyObject * od,PyObject * Py_UNUSED (ignored))2066 odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored))
2067 {
2068 return _PyDictView_New(od, &PyODictItems_Type);
2069 }
2070
2071 /* values() */
2072
2073 static PyObject *
odictvalues_iter(_PyDictViewObject * dv)2074 odictvalues_iter(_PyDictViewObject *dv)
2075 {
2076 if (dv->dv_dict == NULL) {
2077 Py_RETURN_NONE;
2078 }
2079 return odictiter_new((PyODictObject *)dv->dv_dict,
2080 _odict_ITER_VALUES);
2081 }
2082
2083 static PyObject *
odictvalues_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))2084 odictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2085 {
2086 if (dv->dv_dict == NULL) {
2087 Py_RETURN_NONE;
2088 }
2089 return odictiter_new((PyODictObject *)dv->dv_dict,
2090 _odict_ITER_VALUES|_odict_ITER_REVERSED);
2091 }
2092
2093 static PyMethodDef odictvalues_methods[] = {
2094 {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL},
2095 {NULL, NULL} /* sentinel */
2096 };
2097
2098 PyTypeObject PyODictValues_Type = {
2099 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2100 "odict_values", /* tp_name */
2101 0, /* tp_basicsize */
2102 0, /* tp_itemsize */
2103 0, /* tp_dealloc */
2104 0, /* tp_vectorcall_offset */
2105 0, /* tp_getattr */
2106 0, /* tp_setattr */
2107 0, /* tp_as_async */
2108 0, /* tp_repr */
2109 0, /* tp_as_number */
2110 0, /* tp_as_sequence */
2111 0, /* tp_as_mapping */
2112 0, /* tp_hash */
2113 0, /* tp_call */
2114 0, /* tp_str */
2115 0, /* tp_getattro */
2116 0, /* tp_setattro */
2117 0, /* tp_as_buffer */
2118 0, /* tp_flags */
2119 0, /* tp_doc */
2120 0, /* tp_traverse */
2121 0, /* tp_clear */
2122 0, /* tp_richcompare */
2123 0, /* tp_weaklistoffset */
2124 (getiterfunc)odictvalues_iter, /* tp_iter */
2125 0, /* tp_iternext */
2126 odictvalues_methods, /* tp_methods */
2127 0, /* tp_members */
2128 0, /* tp_getset */
2129 &PyDictValues_Type, /* tp_base */
2130 };
2131
2132 static PyObject *
odictvalues_new(PyObject * od,PyObject * Py_UNUSED (ignored))2133 odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored))
2134 {
2135 return _PyDictView_New(od, &PyODictValues_Type);
2136 }
2137
2138
2139 /* ----------------------------------------------
2140 MutableMapping implementations
2141
2142 Mapping:
2143
2144 ============ ===========
2145 method uses
2146 ============ ===========
2147 __contains__ __getitem__
2148 __eq__ items
2149 __getitem__ +
2150 __iter__ +
2151 __len__ +
2152 __ne__ __eq__
2153 get __getitem__
2154 items ItemsView
2155 keys KeysView
2156 values ValuesView
2157 ============ ===========
2158
2159 ItemsView uses __len__, __iter__, and __getitem__.
2160 KeysView uses __len__, __iter__, and __contains__.
2161 ValuesView uses __len__, __iter__, and __getitem__.
2162
2163 MutableMapping:
2164
2165 ============ ===========
2166 method uses
2167 ============ ===========
2168 __delitem__ +
2169 __setitem__ +
2170 clear popitem
2171 pop __getitem__
2172 __delitem__
2173 popitem __iter__
2174 _getitem__
2175 __delitem__
2176 setdefault __getitem__
2177 __setitem__
2178 update __setitem__
2179 ============ ===========
2180 */
2181
2182 static int
mutablemapping_add_pairs(PyObject * self,PyObject * pairs)2183 mutablemapping_add_pairs(PyObject *self, PyObject *pairs)
2184 {
2185 PyObject *pair, *iterator, *unexpected;
2186 int res = 0;
2187
2188 iterator = PyObject_GetIter(pairs);
2189 if (iterator == NULL)
2190 return -1;
2191 PyErr_Clear();
2192
2193 while ((pair = PyIter_Next(iterator)) != NULL) {
2194 /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */
2195 PyObject *key = NULL, *value = NULL;
2196 PyObject *pair_iterator = PyObject_GetIter(pair);
2197 if (pair_iterator == NULL)
2198 goto Done;
2199
2200 key = PyIter_Next(pair_iterator);
2201 if (key == NULL) {
2202 if (!PyErr_Occurred())
2203 PyErr_SetString(PyExc_ValueError,
2204 "need more than 0 values to unpack");
2205 goto Done;
2206 }
2207
2208 value = PyIter_Next(pair_iterator);
2209 if (value == NULL) {
2210 if (!PyErr_Occurred())
2211 PyErr_SetString(PyExc_ValueError,
2212 "need more than 1 value to unpack");
2213 goto Done;
2214 }
2215
2216 unexpected = PyIter_Next(pair_iterator);
2217 if (unexpected != NULL) {
2218 Py_DECREF(unexpected);
2219 PyErr_SetString(PyExc_ValueError,
2220 "too many values to unpack (expected 2)");
2221 goto Done;
2222 }
2223 else if (PyErr_Occurred())
2224 goto Done;
2225
2226 res = PyObject_SetItem(self, key, value);
2227
2228 Done:
2229 Py_DECREF(pair);
2230 Py_XDECREF(pair_iterator);
2231 Py_XDECREF(key);
2232 Py_XDECREF(value);
2233 if (PyErr_Occurred())
2234 break;
2235 }
2236 Py_DECREF(iterator);
2237
2238 if (res < 0 || PyErr_Occurred() != NULL)
2239 return -1;
2240 else
2241 return 0;
2242 }
2243
2244 static int
mutablemapping_update_arg(PyObject * self,PyObject * arg)2245 mutablemapping_update_arg(PyObject *self, PyObject *arg)
2246 {
2247 int res = 0;
2248 if (PyDict_CheckExact(arg)) {
2249 PyObject *items = PyDict_Items(arg);
2250 if (items == NULL) {
2251 return -1;
2252 }
2253 res = mutablemapping_add_pairs(self, items);
2254 Py_DECREF(items);
2255 return res;
2256 }
2257 _Py_IDENTIFIER(keys);
2258 PyObject *func;
2259 if (_PyObject_LookupAttrId(arg, &PyId_keys, &func) < 0) {
2260 return -1;
2261 }
2262 if (func != NULL) {
2263 PyObject *keys = _PyObject_CallNoArg(func);
2264 Py_DECREF(func);
2265 if (keys == NULL) {
2266 return -1;
2267 }
2268 PyObject *iterator = PyObject_GetIter(keys);
2269 Py_DECREF(keys);
2270 if (iterator == NULL) {
2271 return -1;
2272 }
2273 PyObject *key;
2274 while (res == 0 && (key = PyIter_Next(iterator))) {
2275 PyObject *value = PyObject_GetItem(arg, key);
2276 if (value != NULL) {
2277 res = PyObject_SetItem(self, key, value);
2278 Py_DECREF(value);
2279 }
2280 else {
2281 res = -1;
2282 }
2283 Py_DECREF(key);
2284 }
2285 Py_DECREF(iterator);
2286 if (res != 0 || PyErr_Occurred()) {
2287 return -1;
2288 }
2289 return 0;
2290 }
2291 if (_PyObject_LookupAttrId(arg, &PyId_items, &func) < 0) {
2292 return -1;
2293 }
2294 if (func != NULL) {
2295 PyObject *items = _PyObject_CallNoArg(func);
2296 Py_DECREF(func);
2297 if (items == NULL) {
2298 return -1;
2299 }
2300 res = mutablemapping_add_pairs(self, items);
2301 Py_DECREF(items);
2302 return res;
2303 }
2304 res = mutablemapping_add_pairs(self, arg);
2305 return res;
2306 }
2307
2308 static PyObject *
mutablemapping_update(PyObject * self,PyObject * args,PyObject * kwargs)2309 mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs)
2310 {
2311 int res;
2312 /* first handle args, if any */
2313 assert(args == NULL || PyTuple_Check(args));
2314 Py_ssize_t len = (args != NULL) ? PyTuple_GET_SIZE(args) : 0;
2315 if (len > 1) {
2316 const char *msg = "update() takes at most 1 positional argument (%zd given)";
2317 PyErr_Format(PyExc_TypeError, msg, len);
2318 return NULL;
2319 }
2320
2321 if (len) {
2322 PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */
2323 assert(other != NULL);
2324 Py_INCREF(other);
2325 res = mutablemapping_update_arg(self, other);
2326 Py_DECREF(other);
2327 if (res < 0) {
2328 return NULL;
2329 }
2330 }
2331
2332 /* now handle kwargs */
2333 assert(kwargs == NULL || PyDict_Check(kwargs));
2334 if (kwargs != NULL && PyDict_GET_SIZE(kwargs)) {
2335 PyObject *items = PyDict_Items(kwargs);
2336 if (items == NULL)
2337 return NULL;
2338 res = mutablemapping_add_pairs(self, items);
2339 Py_DECREF(items);
2340 if (res == -1)
2341 return NULL;
2342 }
2343
2344 Py_RETURN_NONE;
2345 }
2346