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 _Py_dict_lookup() does not give us the index into the array,
44 we make use of pointer arithmetic to get that index. An alternative would
45 be to refactor _Py_dict_lookup() 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_call.h" // _PyObject_CallNoArgs()
469 #include "pycore_ceval.h" // _PyEval_GetBuiltin()
470 #include "pycore_critical_section.h" //_Py_BEGIN_CRITICAL_SECTION
471 #include "pycore_dict.h" // _Py_dict_lookup()
472 #include "pycore_object.h" // _PyObject_GC_UNTRACK()
473 #include "pycore_pyerrors.h" // _PyErr_ChainExceptions1()
474 #include <stddef.h> // offsetof()
475
476 #include "clinic/odictobject.c.h"
477
478 /*[clinic input]
479 class OrderedDict "PyODictObject *" "&PyODict_Type"
480 [clinic start generated code]*/
481 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ca0641cf6143d4af]*/
482
483
484 typedef struct _odictnode _ODictNode;
485
486 /* PyODictObject */
487 struct _odictobject {
488 PyDictObject od_dict; /* the underlying dict */
489 _ODictNode *od_first; /* first node in the linked list, if any */
490 _ODictNode *od_last; /* last node in the linked list, if any */
491 /* od_fast_nodes, od_fast_nodes_size and od_resize_sentinel are managed
492 * by _odict_resize().
493 * Note that we rely on implementation details of dict for both. */
494 _ODictNode **od_fast_nodes; /* hash table that mirrors the dict table */
495 Py_ssize_t od_fast_nodes_size;
496 void *od_resize_sentinel; /* changes if odict should be resized */
497
498 size_t od_state; /* incremented whenever the LL changes */
499 PyObject *od_inst_dict; /* OrderedDict().__dict__ */
500 PyObject *od_weakreflist; /* holds weakrefs to the odict */
501 };
502
503
504 /* ----------------------------------------------
505 * odict keys (a simple doubly-linked list)
506 */
507
508 struct _odictnode {
509 PyObject *key;
510 Py_hash_t hash;
511 _ODictNode *next;
512 _ODictNode *prev;
513 };
514
515 #define _odictnode_KEY(node) \
516 (node->key)
517 #define _odictnode_HASH(node) \
518 (node->hash)
519 /* borrowed reference */
520 #define _odictnode_VALUE(node, od) \
521 PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))
522 #define _odictnode_PREV(node) (node->prev)
523 #define _odictnode_NEXT(node) (node->next)
524
525 #define _odict_FIRST(od) (((PyODictObject *)od)->od_first)
526 #define _odict_LAST(od) (((PyODictObject *)od)->od_last)
527 #define _odict_EMPTY(od) (_odict_FIRST(od) == NULL)
528 #define _odict_FOREACH(od, node) \
529 for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))
530
531 /* Return the index into the hash table, regardless of a valid node. */
532 static Py_ssize_t
_odict_get_index_raw(PyODictObject * od,PyObject * key,Py_hash_t hash)533 _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
534 {
535 PyObject *value = NULL;
536 PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
537 Py_ssize_t ix;
538 #ifdef Py_GIL_DISABLED
539 ix = _Py_dict_lookup_threadsafe((PyDictObject *)od, key, hash, &value);
540 Py_XDECREF(value);
541 #else
542 ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);
543 #endif
544 if (ix == DKIX_EMPTY) {
545 return keys->dk_nentries; /* index of new entry */
546 }
547 if (ix < 0)
548 return -1;
549 /* We use pointer arithmetic to get the entry's index into the table. */
550 return ix;
551 }
552
553 #define ONE ((Py_ssize_t)1)
554
555 /* Replace od->od_fast_nodes with a new table matching the size of dict's. */
556 static int
_odict_resize(PyODictObject * od)557 _odict_resize(PyODictObject *od)
558 {
559 Py_ssize_t size, i;
560 _ODictNode **fast_nodes, *node;
561
562 /* Initialize a new "fast nodes" table. */
563 size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_size);
564 fast_nodes = PyMem_NEW(_ODictNode *, size);
565 if (fast_nodes == NULL) {
566 PyErr_NoMemory();
567 return -1;
568 }
569 for (i = 0; i < size; i++)
570 fast_nodes[i] = NULL;
571
572 /* Copy the current nodes into the table. */
573 _odict_FOREACH(od, node) {
574 i = _odict_get_index_raw(od, _odictnode_KEY(node),
575 _odictnode_HASH(node));
576 if (i < 0) {
577 PyMem_Free(fast_nodes);
578 return -1;
579 }
580 fast_nodes[i] = node;
581 }
582
583 /* Replace the old fast nodes table. */
584 PyMem_Free(od->od_fast_nodes);
585 od->od_fast_nodes = fast_nodes;
586 od->od_fast_nodes_size = size;
587 od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;
588 return 0;
589 }
590
591 /* Return the index into the hash table, regardless of a valid node. */
592 static Py_ssize_t
_odict_get_index(PyODictObject * od,PyObject * key,Py_hash_t hash)593 _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)
594 {
595 PyDictKeysObject *keys;
596
597 assert(key != NULL);
598 keys = ((PyDictObject *)od)->ma_keys;
599
600 /* Ensure od_fast_nodes and dk_entries are in sync. */
601 if (od->od_resize_sentinel != keys ||
602 od->od_fast_nodes_size != (ONE << (keys->dk_log2_size))) {
603 int resize_res = _odict_resize(od);
604 if (resize_res < 0)
605 return -1;
606 }
607
608 return _odict_get_index_raw(od, key, hash);
609 }
610
611 /* Returns NULL if there was some error or the key was not found. */
612 static _ODictNode *
_odict_find_node_hash(PyODictObject * od,PyObject * key,Py_hash_t hash)613 _odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash)
614 {
615 Py_ssize_t index;
616
617 if (_odict_EMPTY(od))
618 return NULL;
619 index = _odict_get_index(od, key, hash);
620 if (index < 0)
621 return NULL;
622 assert(od->od_fast_nodes != NULL);
623 return od->od_fast_nodes[index];
624 }
625
626 static _ODictNode *
_odict_find_node(PyODictObject * od,PyObject * key)627 _odict_find_node(PyODictObject *od, PyObject *key)
628 {
629 Py_ssize_t index;
630 Py_hash_t hash;
631
632 if (_odict_EMPTY(od))
633 return NULL;
634 hash = PyObject_Hash(key);
635 if (hash == -1)
636 return NULL;
637 index = _odict_get_index(od, key, hash);
638 if (index < 0)
639 return NULL;
640 assert(od->od_fast_nodes != NULL);
641 return od->od_fast_nodes[index];
642 }
643
644 static void
_odict_add_head(PyODictObject * od,_ODictNode * node)645 _odict_add_head(PyODictObject *od, _ODictNode *node)
646 {
647 _odictnode_PREV(node) = NULL;
648 _odictnode_NEXT(node) = _odict_FIRST(od);
649 if (_odict_FIRST(od) == NULL)
650 _odict_LAST(od) = node;
651 else
652 _odictnode_PREV(_odict_FIRST(od)) = node;
653 _odict_FIRST(od) = node;
654 od->od_state++;
655 }
656
657 static void
_odict_add_tail(PyODictObject * od,_ODictNode * node)658 _odict_add_tail(PyODictObject *od, _ODictNode *node)
659 {
660 _odictnode_PREV(node) = _odict_LAST(od);
661 _odictnode_NEXT(node) = NULL;
662 if (_odict_LAST(od) == NULL)
663 _odict_FIRST(od) = node;
664 else
665 _odictnode_NEXT(_odict_LAST(od)) = node;
666 _odict_LAST(od) = node;
667 od->od_state++;
668 }
669
670 /* adds the node to the end of the list */
671 static int
_odict_add_new_node(PyODictObject * od,PyObject * key,Py_hash_t hash)672 _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
673 {
674 Py_ssize_t i;
675 _ODictNode *node;
676
677 Py_INCREF(key);
678 i = _odict_get_index(od, key, hash);
679 if (i < 0) {
680 if (!PyErr_Occurred())
681 PyErr_SetObject(PyExc_KeyError, key);
682 Py_DECREF(key);
683 return -1;
684 }
685 assert(od->od_fast_nodes != NULL);
686 if (od->od_fast_nodes[i] != NULL) {
687 /* We already have a node for the key so there's no need to add one. */
688 Py_DECREF(key);
689 return 0;
690 }
691
692 /* must not be added yet */
693 node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode));
694 if (node == NULL) {
695 Py_DECREF(key);
696 PyErr_NoMemory();
697 return -1;
698 }
699
700 _odictnode_KEY(node) = key;
701 _odictnode_HASH(node) = hash;
702 _odict_add_tail(od, node);
703 od->od_fast_nodes[i] = node;
704 return 0;
705 }
706
707 /* Putting the decref after the free causes problems. */
708 #define _odictnode_DEALLOC(node) \
709 do { \
710 Py_DECREF(_odictnode_KEY(node)); \
711 PyMem_Free((void *)node); \
712 } while (0)
713
714 /* Repeated calls on the same node are no-ops. */
715 static void
_odict_remove_node(PyODictObject * od,_ODictNode * node)716 _odict_remove_node(PyODictObject *od, _ODictNode *node)
717 {
718 if (_odict_FIRST(od) == node)
719 _odict_FIRST(od) = _odictnode_NEXT(node);
720 else if (_odictnode_PREV(node) != NULL)
721 _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);
722
723 if (_odict_LAST(od) == node)
724 _odict_LAST(od) = _odictnode_PREV(node);
725 else if (_odictnode_NEXT(node) != NULL)
726 _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node);
727
728 _odictnode_PREV(node) = NULL;
729 _odictnode_NEXT(node) = NULL;
730 od->od_state++;
731 }
732
733 /* If someone calls PyDict_DelItem() directly on an OrderedDict, we'll
734 get all sorts of problems here. In PyODict_DelItem we make sure to
735 call _odict_clear_node first.
736
737 This matters in the case of colliding keys. Suppose we add 3 keys:
738 [A, B, C], where the hash of C collides with A and the next possible
739 index in the hash table is occupied by B. If we remove B then for C
740 the dict's looknode func will give us the old index of B instead of
741 the index we got before deleting B. However, the node for C in
742 od_fast_nodes is still at the old dict index of C. Thus to be sure
743 things don't get out of sync, we clear the node in od_fast_nodes
744 *before* calling PyDict_DelItem.
745
746 The same must be done for any other OrderedDict operations where
747 we modify od_fast_nodes.
748 */
749 static int
_odict_clear_node(PyODictObject * od,_ODictNode * node,PyObject * key,Py_hash_t hash)750 _odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,
751 Py_hash_t hash)
752 {
753 Py_ssize_t i;
754
755 assert(key != NULL);
756 if (_odict_EMPTY(od)) {
757 /* Let later code decide if this is a KeyError. */
758 return 0;
759 }
760
761 i = _odict_get_index(od, key, hash);
762 if (i < 0)
763 return PyErr_Occurred() ? -1 : 0;
764
765 assert(od->od_fast_nodes != NULL);
766 if (node == NULL)
767 node = od->od_fast_nodes[i];
768 assert(node == od->od_fast_nodes[i]);
769 if (node == NULL) {
770 /* Let later code decide if this is a KeyError. */
771 return 0;
772 }
773
774 // Now clear the node.
775 od->od_fast_nodes[i] = NULL;
776 _odict_remove_node(od, node);
777 _odictnode_DEALLOC(node);
778 return 0;
779 }
780
781 static void
_odict_clear_nodes(PyODictObject * od)782 _odict_clear_nodes(PyODictObject *od)
783 {
784 _ODictNode *node, *next;
785
786 PyMem_Free(od->od_fast_nodes);
787 od->od_fast_nodes = NULL;
788 od->od_fast_nodes_size = 0;
789 od->od_resize_sentinel = NULL;
790
791 node = _odict_FIRST(od);
792 _odict_FIRST(od) = NULL;
793 _odict_LAST(od) = NULL;
794 while (node != NULL) {
795 next = _odictnode_NEXT(node);
796 _odictnode_DEALLOC(node);
797 node = next;
798 }
799 od->od_state++;
800 }
801
802 /* There isn't any memory management of nodes past this point. */
803 #undef _odictnode_DEALLOC
804
805 static int
_odict_keys_equal(PyODictObject * a,PyODictObject * b)806 _odict_keys_equal(PyODictObject *a, PyODictObject *b)
807 {
808 _ODictNode *node_a, *node_b;
809
810 // keep operands' state to detect undesired mutations
811 const size_t state_a = a->od_state;
812 const size_t state_b = b->od_state;
813
814 node_a = _odict_FIRST(a);
815 node_b = _odict_FIRST(b);
816 while (1) {
817 if (node_a == NULL && node_b == NULL) {
818 /* success: hit the end of each at the same time */
819 return 1;
820 }
821 else if (node_a == NULL || node_b == NULL) {
822 /* unequal length */
823 return 0;
824 }
825 else {
826 PyObject *key_a = Py_NewRef(_odictnode_KEY(node_a));
827 PyObject *key_b = Py_NewRef(_odictnode_KEY(node_b));
828 int res = PyObject_RichCompareBool(key_a, key_b, Py_EQ);
829 Py_DECREF(key_a);
830 Py_DECREF(key_b);
831 if (res < 0) {
832 return res;
833 }
834 else if (a->od_state != state_a || b->od_state != state_b) {
835 PyErr_SetString(PyExc_RuntimeError,
836 "OrderedDict mutated during iteration");
837 return -1;
838 }
839 else if (res == 0) {
840 // This check comes after the check on the state
841 // in order for the exception to be set correctly.
842 return 0;
843 }
844
845 /* otherwise it must match, so move on to the next one */
846 node_a = _odictnode_NEXT(node_a);
847 node_b = _odictnode_NEXT(node_b);
848 }
849 }
850 }
851
852
853 /* ----------------------------------------------
854 * OrderedDict mapping methods
855 */
856
857 /* mp_ass_subscript: __setitem__() and __delitem__() */
858
859 static int
odict_mp_ass_sub(PyODictObject * od,PyObject * v,PyObject * w)860 odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w)
861 {
862 if (w == NULL)
863 return PyODict_DelItem((PyObject *)od, v);
864 else
865 return PyODict_SetItem((PyObject *)od, v, w);
866 }
867
868 /* tp_as_mapping */
869
870 static PyMappingMethods odict_as_mapping = {
871 0, /*mp_length*/
872 0, /*mp_subscript*/
873 (objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/
874 };
875
876
877 /* ----------------------------------------------
878 * OrderedDict number methods
879 */
880
881 static int mutablemapping_update_arg(PyObject*, PyObject*);
882
883 static PyObject *
odict_or(PyObject * left,PyObject * right)884 odict_or(PyObject *left, PyObject *right)
885 {
886 PyTypeObject *type;
887 PyObject *other;
888 if (PyODict_Check(left)) {
889 type = Py_TYPE(left);
890 other = right;
891 }
892 else {
893 type = Py_TYPE(right);
894 other = left;
895 }
896 if (!PyDict_Check(other)) {
897 Py_RETURN_NOTIMPLEMENTED;
898 }
899 PyObject *new = PyObject_CallOneArg((PyObject*)type, left);
900 if (!new) {
901 return NULL;
902 }
903 if (mutablemapping_update_arg(new, right) < 0) {
904 Py_DECREF(new);
905 return NULL;
906 }
907 return new;
908 }
909
910 static PyObject *
odict_inplace_or(PyObject * self,PyObject * other)911 odict_inplace_or(PyObject *self, PyObject *other)
912 {
913 if (mutablemapping_update_arg(self, other) < 0) {
914 return NULL;
915 }
916 return Py_NewRef(self);
917 }
918
919 /* tp_as_number */
920
921 static PyNumberMethods odict_as_number = {
922 .nb_or = odict_or,
923 .nb_inplace_or = odict_inplace_or,
924 };
925
926
927 /* ----------------------------------------------
928 * OrderedDict methods
929 */
930
931 /* fromkeys() */
932
933 /*[clinic input]
934 @classmethod
935 OrderedDict.fromkeys
936
937 iterable as seq: object
938 value: object = None
939
940 Create a new ordered dictionary with keys from iterable and values set to value.
941 [clinic start generated code]*/
942
943 static PyObject *
OrderedDict_fromkeys_impl(PyTypeObject * type,PyObject * seq,PyObject * value)944 OrderedDict_fromkeys_impl(PyTypeObject *type, PyObject *seq, PyObject *value)
945 /*[clinic end generated code: output=c10390d452d78d6d input=1a0476c229c597b3]*/
946 {
947 return _PyDict_FromKeys((PyObject *)type, seq, value);
948 }
949
950 /* __sizeof__() */
951
952 /* OrderedDict.__sizeof__() does not have a docstring. */
953 PyDoc_STRVAR(odict_sizeof__doc__, "");
954
955 static PyObject *
odict_sizeof(PyODictObject * od,PyObject * Py_UNUSED (ignored))956 odict_sizeof(PyODictObject *od, PyObject *Py_UNUSED(ignored))
957 {
958 Py_ssize_t res = _PyDict_SizeOf((PyDictObject *)od);
959 res += sizeof(_ODictNode *) * od->od_fast_nodes_size; /* od_fast_nodes */
960 if (!_odict_EMPTY(od)) {
961 res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */
962 }
963 return PyLong_FromSsize_t(res);
964 }
965
966 /* __reduce__() */
967
968 PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling");
969
970 static PyObject *
odict_reduce(register PyODictObject * od,PyObject * Py_UNUSED (ignored))971 odict_reduce(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
972 {
973 PyObject *state, *result = NULL;
974 PyObject *items_iter, *items, *args = NULL;
975
976 /* capture any instance state */
977 state = _PyObject_GetState((PyObject *)od);
978 if (state == NULL)
979 goto Done;
980
981 /* build the result */
982 args = PyTuple_New(0);
983 if (args == NULL)
984 goto Done;
985
986 items = PyObject_CallMethodNoArgs((PyObject *)od, &_Py_ID(items));
987 if (items == NULL)
988 goto Done;
989
990 items_iter = PyObject_GetIter(items);
991 Py_DECREF(items);
992 if (items_iter == NULL)
993 goto Done;
994
995 result = PyTuple_Pack(5, Py_TYPE(od), args, state, Py_None, items_iter);
996 Py_DECREF(items_iter);
997
998 Done:
999 Py_XDECREF(state);
1000 Py_XDECREF(args);
1001
1002 return result;
1003 }
1004
1005 /* setdefault(): Skips __missing__() calls. */
1006
1007
1008 /*[clinic input]
1009 OrderedDict.setdefault
1010
1011 key: object
1012 default: object = None
1013
1014 Insert key with a value of default if key is not in the dictionary.
1015
1016 Return the value for key if key is in the dictionary, else default.
1017 [clinic start generated code]*/
1018
1019 static PyObject *
OrderedDict_setdefault_impl(PyODictObject * self,PyObject * key,PyObject * default_value)1020 OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,
1021 PyObject *default_value)
1022 /*[clinic end generated code: output=97537cb7c28464b6 input=38e098381c1efbc6]*/
1023 {
1024 PyObject *result = NULL;
1025
1026 if (PyODict_CheckExact(self)) {
1027 result = PyODict_GetItemWithError(self, key); /* borrowed */
1028 if (result == NULL) {
1029 if (PyErr_Occurred())
1030 return NULL;
1031 assert(_odict_find_node(self, key) == NULL);
1032 if (PyODict_SetItem((PyObject *)self, key, default_value) >= 0) {
1033 result = Py_NewRef(default_value);
1034 }
1035 }
1036 else {
1037 Py_INCREF(result);
1038 }
1039 }
1040 else {
1041 int exists = PySequence_Contains((PyObject *)self, key);
1042 if (exists < 0) {
1043 return NULL;
1044 }
1045 else if (exists) {
1046 result = PyObject_GetItem((PyObject *)self, key);
1047 }
1048 else if (PyObject_SetItem((PyObject *)self, key, default_value) >= 0) {
1049 result = Py_NewRef(default_value);
1050 }
1051 }
1052
1053 return result;
1054 }
1055
1056 /* pop() */
1057
1058 static PyObject *
_odict_popkey_hash(PyObject * od,PyObject * key,PyObject * failobj,Py_hash_t hash)1059 _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
1060 Py_hash_t hash)
1061 {
1062 PyObject *value = NULL;
1063
1064 Py_BEGIN_CRITICAL_SECTION(od);
1065
1066 _ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash);
1067 if (node != NULL) {
1068 /* Pop the node first to avoid a possible dict resize (due to
1069 eval loop reentrancy) and complications due to hash collision
1070 resolution. */
1071 int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
1072 if (res < 0) {
1073 goto done;
1074 }
1075 /* Now delete the value from the dict. */
1076 if (_PyDict_Pop_KnownHash((PyDictObject *)od, key, hash,
1077 &value) == 0) {
1078 value = Py_NewRef(failobj);
1079 }
1080 }
1081 else if (value == NULL && !PyErr_Occurred()) {
1082 /* Apply the fallback value, if necessary. */
1083 if (failobj) {
1084 value = Py_NewRef(failobj);
1085 }
1086 else {
1087 PyErr_SetObject(PyExc_KeyError, key);
1088 }
1089 }
1090 Py_END_CRITICAL_SECTION();
1091 done:
1092
1093 return value;
1094 }
1095
1096 /* Skips __missing__() calls. */
1097 /*[clinic input]
1098 OrderedDict.pop
1099
1100 key: object
1101 default: object = NULL
1102
1103 od.pop(key[,default]) -> v, remove specified key and return the corresponding value.
1104
1105 If the key is not found, return the default if given; otherwise,
1106 raise a KeyError.
1107 [clinic start generated code]*/
1108
1109 static PyObject *
OrderedDict_pop_impl(PyODictObject * self,PyObject * key,PyObject * default_value)1110 OrderedDict_pop_impl(PyODictObject *self, PyObject *key,
1111 PyObject *default_value)
1112 /*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/
1113 {
1114 Py_hash_t hash = PyObject_Hash(key);
1115 if (hash == -1)
1116 return NULL;
1117 return _odict_popkey_hash((PyObject *)self, key, default_value, hash);
1118 }
1119
1120
1121 /* popitem() */
1122
1123 /*[clinic input]
1124 OrderedDict.popitem
1125
1126 last: bool = True
1127
1128 Remove and return a (key, value) pair from the dictionary.
1129
1130 Pairs are returned in LIFO order if last is true or FIFO order if false.
1131 [clinic start generated code]*/
1132
1133 static PyObject *
OrderedDict_popitem_impl(PyODictObject * self,int last)1134 OrderedDict_popitem_impl(PyODictObject *self, int last)
1135 /*[clinic end generated code: output=98e7d986690d49eb input=d992ac5ee8305e1a]*/
1136 {
1137 PyObject *key, *value, *item = NULL;
1138 _ODictNode *node;
1139
1140 /* pull the item */
1141
1142 if (_odict_EMPTY(self)) {
1143 PyErr_SetString(PyExc_KeyError, "dictionary is empty");
1144 return NULL;
1145 }
1146
1147 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1148 key = Py_NewRef(_odictnode_KEY(node));
1149 value = _odict_popkey_hash((PyObject *)self, key, NULL, _odictnode_HASH(node));
1150 if (value == NULL)
1151 return NULL;
1152 item = PyTuple_Pack(2, key, value);
1153 Py_DECREF(key);
1154 Py_DECREF(value);
1155 return item;
1156 }
1157
1158 /* keys() */
1159
1160 /* MutableMapping.keys() does not have a docstring. */
1161 PyDoc_STRVAR(odict_keys__doc__, "");
1162
1163 static PyObject * odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1164
1165 /* values() */
1166
1167 /* MutableMapping.values() does not have a docstring. */
1168 PyDoc_STRVAR(odict_values__doc__, "");
1169
1170 static PyObject * odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1171
1172 /* items() */
1173
1174 /* MutableMapping.items() does not have a docstring. */
1175 PyDoc_STRVAR(odict_items__doc__, "");
1176
1177 static PyObject * odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */
1178
1179 /* update() */
1180
1181 /* MutableMapping.update() does not have a docstring. */
1182 PyDoc_STRVAR(odict_update__doc__, "");
1183
1184 /* forward */
1185 static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *);
1186
1187 #define odict_update mutablemapping_update
1188
1189 /* clear() */
1190
1191 PyDoc_STRVAR(odict_clear__doc__,
1192 "od.clear() -> None. Remove all items from od.");
1193
1194 static PyObject *
odict_clear(register PyODictObject * od,PyObject * Py_UNUSED (ignored))1195 odict_clear(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
1196 {
1197 PyDict_Clear((PyObject *)od);
1198 _odict_clear_nodes(od);
1199 Py_RETURN_NONE;
1200 }
1201
1202 /* copy() */
1203
1204 /* forward */
1205 static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *,
1206 Py_hash_t);
1207
1208 PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od");
1209
1210 static PyObject *
odict_copy(register PyODictObject * od,PyObject * Py_UNUSED (ignored))1211 odict_copy(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
1212 {
1213 _ODictNode *node;
1214 PyObject *od_copy;
1215
1216 if (PyODict_CheckExact(od))
1217 od_copy = PyODict_New();
1218 else
1219 od_copy = _PyObject_CallNoArgs((PyObject *)Py_TYPE(od));
1220 if (od_copy == NULL)
1221 return NULL;
1222
1223 if (PyODict_CheckExact(od)) {
1224 _odict_FOREACH(od, node) {
1225 PyObject *key = _odictnode_KEY(node);
1226 PyObject *value = _odictnode_VALUE(node, od);
1227 if (value == NULL) {
1228 if (!PyErr_Occurred())
1229 PyErr_SetObject(PyExc_KeyError, key);
1230 goto fail;
1231 }
1232 if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value,
1233 _odictnode_HASH(node)) != 0)
1234 goto fail;
1235 }
1236 }
1237 else {
1238 _odict_FOREACH(od, node) {
1239 int res;
1240 PyObject *value = PyObject_GetItem((PyObject *)od,
1241 _odictnode_KEY(node));
1242 if (value == NULL)
1243 goto fail;
1244 res = PyObject_SetItem((PyObject *)od_copy,
1245 _odictnode_KEY(node), value);
1246 Py_DECREF(value);
1247 if (res != 0)
1248 goto fail;
1249 }
1250 }
1251 return od_copy;
1252
1253 fail:
1254 Py_DECREF(od_copy);
1255 return NULL;
1256 }
1257
1258 /* __reversed__() */
1259
1260 PyDoc_STRVAR(odict_reversed__doc__, "od.__reversed__() <==> reversed(od)");
1261
1262 #define _odict_ITER_REVERSED 1
1263 #define _odict_ITER_KEYS 2
1264 #define _odict_ITER_VALUES 4
1265 #define _odict_ITER_ITEMS (_odict_ITER_KEYS|_odict_ITER_VALUES)
1266
1267 /* forward */
1268 static PyObject * odictiter_new(PyODictObject *, int);
1269
1270 static PyObject *
odict_reversed(PyODictObject * od,PyObject * Py_UNUSED (ignored))1271 odict_reversed(PyODictObject *od, PyObject *Py_UNUSED(ignored))
1272 {
1273 return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED);
1274 }
1275
1276
1277 /* move_to_end() */
1278
1279 /*[clinic input]
1280 OrderedDict.move_to_end
1281
1282 key: object
1283 last: bool = True
1284
1285 Move an existing element to the end (or beginning if last is false).
1286
1287 Raise KeyError if the element does not exist.
1288 [clinic start generated code]*/
1289
1290 static PyObject *
OrderedDict_move_to_end_impl(PyODictObject * self,PyObject * key,int last)1291 OrderedDict_move_to_end_impl(PyODictObject *self, PyObject *key, int last)
1292 /*[clinic end generated code: output=fafa4c5cc9b92f20 input=d6ceff7132a2fcd7]*/
1293 {
1294 _ODictNode *node;
1295
1296 if (_odict_EMPTY(self)) {
1297 PyErr_SetObject(PyExc_KeyError, key);
1298 return NULL;
1299 }
1300 node = last ? _odict_LAST(self) : _odict_FIRST(self);
1301 if (key != _odictnode_KEY(node)) {
1302 node = _odict_find_node(self, key);
1303 if (node == NULL) {
1304 if (!PyErr_Occurred())
1305 PyErr_SetObject(PyExc_KeyError, key);
1306 return NULL;
1307 }
1308 if (last) {
1309 /* Only move if not already the last one. */
1310 if (node != _odict_LAST(self)) {
1311 _odict_remove_node(self, node);
1312 _odict_add_tail(self, node);
1313 }
1314 }
1315 else {
1316 /* Only move if not already the first one. */
1317 if (node != _odict_FIRST(self)) {
1318 _odict_remove_node(self, node);
1319 _odict_add_head(self, node);
1320 }
1321 }
1322 }
1323 Py_RETURN_NONE;
1324 }
1325
1326
1327 /* tp_methods */
1328
1329 static PyMethodDef odict_methods[] = {
1330
1331 /* overridden dict methods */
1332 ORDEREDDICT_FROMKEYS_METHODDEF
1333 {"__sizeof__", (PyCFunction)odict_sizeof, METH_NOARGS,
1334 odict_sizeof__doc__},
1335 {"__reduce__", (PyCFunction)odict_reduce, METH_NOARGS,
1336 odict_reduce__doc__},
1337 ORDEREDDICT_SETDEFAULT_METHODDEF
1338 ORDEREDDICT_POP_METHODDEF
1339 ORDEREDDICT_POPITEM_METHODDEF
1340 {"keys", odictkeys_new, METH_NOARGS,
1341 odict_keys__doc__},
1342 {"values", odictvalues_new, METH_NOARGS,
1343 odict_values__doc__},
1344 {"items", odictitems_new, METH_NOARGS,
1345 odict_items__doc__},
1346 {"update", _PyCFunction_CAST(odict_update), METH_VARARGS | METH_KEYWORDS,
1347 odict_update__doc__},
1348 {"clear", (PyCFunction)odict_clear, METH_NOARGS,
1349 odict_clear__doc__},
1350 {"copy", (PyCFunction)odict_copy, METH_NOARGS,
1351 odict_copy__doc__},
1352
1353 /* new methods */
1354 {"__reversed__", (PyCFunction)odict_reversed, METH_NOARGS,
1355 odict_reversed__doc__},
1356 ORDEREDDICT_MOVE_TO_END_METHODDEF
1357
1358 {NULL, NULL} /* sentinel */
1359 };
1360
1361
1362 /* ----------------------------------------------
1363 * OrderedDict members
1364 */
1365
1366 /* tp_getset */
1367
1368 static PyGetSetDef odict_getset[] = {
1369 {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
1370 {NULL}
1371 };
1372
1373 /* ----------------------------------------------
1374 * OrderedDict type slot methods
1375 */
1376
1377 /* tp_dealloc */
1378
1379 static void
odict_dealloc(PyODictObject * self)1380 odict_dealloc(PyODictObject *self)
1381 {
1382 PyObject_GC_UnTrack(self);
1383 Py_TRASHCAN_BEGIN(self, odict_dealloc)
1384
1385 Py_XDECREF(self->od_inst_dict);
1386 if (self->od_weakreflist != NULL)
1387 PyObject_ClearWeakRefs((PyObject *)self);
1388
1389 _odict_clear_nodes(self);
1390 PyDict_Type.tp_dealloc((PyObject *)self);
1391
1392 Py_TRASHCAN_END
1393 }
1394
1395 /* tp_repr */
1396
1397 static PyObject *
odict_repr(PyODictObject * self)1398 odict_repr(PyODictObject *self)
1399 {
1400 int i;
1401 PyObject *result = NULL, *dcopy = NULL;
1402
1403 if (PyODict_SIZE(self) == 0)
1404 return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self)));
1405
1406 i = Py_ReprEnter((PyObject *)self);
1407 if (i != 0) {
1408 return i > 0 ? PyUnicode_FromString("...") : NULL;
1409 }
1410
1411 dcopy = PyDict_Copy((PyObject *)self);
1412 if (dcopy == NULL) {
1413 goto Done;
1414 }
1415
1416 result = PyUnicode_FromFormat("%s(%R)",
1417 _PyType_Name(Py_TYPE(self)),
1418 dcopy);
1419 Py_DECREF(dcopy);
1420
1421 Done:
1422 Py_ReprLeave((PyObject *)self);
1423 return result;
1424 }
1425
1426 /* tp_doc */
1427
1428 PyDoc_STRVAR(odict_doc,
1429 "Dictionary that remembers insertion order");
1430
1431 /* tp_traverse */
1432
1433 static int
odict_traverse(PyODictObject * od,visitproc visit,void * arg)1434 odict_traverse(PyODictObject *od, visitproc visit, void *arg)
1435 {
1436 _ODictNode *node;
1437
1438 Py_VISIT(od->od_inst_dict);
1439 _odict_FOREACH(od, node) {
1440 Py_VISIT(_odictnode_KEY(node));
1441 }
1442 return PyDict_Type.tp_traverse((PyObject *)od, visit, arg);
1443 }
1444
1445 /* tp_clear */
1446
1447 static int
odict_tp_clear(PyODictObject * od)1448 odict_tp_clear(PyODictObject *od)
1449 {
1450 Py_CLEAR(od->od_inst_dict);
1451 PyDict_Clear((PyObject *)od);
1452 _odict_clear_nodes(od);
1453 return 0;
1454 }
1455
1456 /* tp_richcompare */
1457
1458 static PyObject *
odict_richcompare(PyObject * v,PyObject * w,int op)1459 odict_richcompare(PyObject *v, PyObject *w, int op)
1460 {
1461 if (!PyODict_Check(v) || !PyDict_Check(w)) {
1462 Py_RETURN_NOTIMPLEMENTED;
1463 }
1464
1465 if (op == Py_EQ || op == Py_NE) {
1466 PyObject *res, *cmp;
1467 int eq;
1468
1469 cmp = PyDict_Type.tp_richcompare(v, w, op);
1470 if (cmp == NULL)
1471 return NULL;
1472 if (!PyODict_Check(w))
1473 return cmp;
1474 if (op == Py_EQ && cmp == Py_False)
1475 return cmp;
1476 if (op == Py_NE && cmp == Py_True)
1477 return cmp;
1478 Py_DECREF(cmp);
1479
1480 /* Try comparing odict keys. */
1481 eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w);
1482 if (eq < 0)
1483 return NULL;
1484
1485 res = (eq == (op == Py_EQ)) ? Py_True : Py_False;
1486 return Py_NewRef(res);
1487 } else {
1488 Py_RETURN_NOTIMPLEMENTED;
1489 }
1490 }
1491
1492 /* tp_iter */
1493
1494 static PyObject *
odict_iter(PyODictObject * od)1495 odict_iter(PyODictObject *od)
1496 {
1497 return odictiter_new(od, _odict_ITER_KEYS);
1498 }
1499
1500 /* tp_init */
1501
1502 static int
odict_init(PyObject * self,PyObject * args,PyObject * kwds)1503 odict_init(PyObject *self, PyObject *args, PyObject *kwds)
1504 {
1505 PyObject *res;
1506 Py_ssize_t len = PyObject_Length(args);
1507
1508 if (len == -1)
1509 return -1;
1510 if (len > 1) {
1511 const char *msg = "expected at most 1 arguments, got %zd";
1512 PyErr_Format(PyExc_TypeError, msg, len);
1513 return -1;
1514 }
1515
1516 /* __init__() triggering update() is just the way things are! */
1517 res = odict_update(self, args, kwds);
1518 if (res == NULL) {
1519 return -1;
1520 } else {
1521 Py_DECREF(res);
1522 return 0;
1523 }
1524 }
1525
1526 /* PyODict_Type */
1527
1528 PyTypeObject PyODict_Type = {
1529 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1530 "collections.OrderedDict", /* tp_name */
1531 sizeof(PyODictObject), /* tp_basicsize */
1532 0, /* tp_itemsize */
1533 (destructor)odict_dealloc, /* tp_dealloc */
1534 0, /* tp_vectorcall_offset */
1535 0, /* tp_getattr */
1536 0, /* tp_setattr */
1537 0, /* tp_as_async */
1538 (reprfunc)odict_repr, /* tp_repr */
1539 &odict_as_number, /* tp_as_number */
1540 0, /* tp_as_sequence */
1541 &odict_as_mapping, /* tp_as_mapping */
1542 0, /* tp_hash */
1543 0, /* tp_call */
1544 0, /* tp_str */
1545 0, /* tp_getattro */
1546 0, /* tp_setattro */
1547 0, /* tp_as_buffer */
1548 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1549 odict_doc, /* tp_doc */
1550 (traverseproc)odict_traverse, /* tp_traverse */
1551 (inquiry)odict_tp_clear, /* tp_clear */
1552 (richcmpfunc)odict_richcompare, /* tp_richcompare */
1553 offsetof(PyODictObject, od_weakreflist), /* tp_weaklistoffset */
1554 (getiterfunc)odict_iter, /* tp_iter */
1555 0, /* tp_iternext */
1556 odict_methods, /* tp_methods */
1557 0, /* tp_members */
1558 odict_getset, /* tp_getset */
1559 &PyDict_Type, /* tp_base */
1560 0, /* tp_dict */
1561 0, /* tp_descr_get */
1562 0, /* tp_descr_set */
1563 offsetof(PyODictObject, od_inst_dict), /* tp_dictoffset */
1564 (initproc)odict_init, /* tp_init */
1565 PyType_GenericAlloc, /* tp_alloc */
1566 0, /* tp_new */
1567 0, /* tp_free */
1568 };
1569
1570
1571 /* ----------------------------------------------
1572 * the public OrderedDict API
1573 */
1574
1575 PyObject *
PyODict_New(void)1576 PyODict_New(void)
1577 {
1578 return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL);
1579 }
1580
1581 static int
_PyODict_SetItem_KnownHash(PyObject * od,PyObject * key,PyObject * value,Py_hash_t hash)1582 _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,
1583 Py_hash_t hash)
1584 {
1585 int res = _PyDict_SetItem_KnownHash(od, key, value, hash);
1586 if (res == 0) {
1587 res = _odict_add_new_node((PyODictObject *)od, key, hash);
1588 if (res < 0) {
1589 /* Revert setting the value on the dict */
1590 PyObject *exc = PyErr_GetRaisedException();
1591 (void) _PyDict_DelItem_KnownHash(od, key, hash);
1592 _PyErr_ChainExceptions1(exc);
1593 }
1594 }
1595 return res;
1596 }
1597
1598 int
PyODict_SetItem(PyObject * od,PyObject * key,PyObject * value)1599 PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value)
1600 {
1601 Py_hash_t hash = PyObject_Hash(key);
1602 if (hash == -1)
1603 return -1;
1604 return _PyODict_SetItem_KnownHash(od, key, value, hash);
1605 }
1606
1607 int
PyODict_DelItem(PyObject * od,PyObject * key)1608 PyODict_DelItem(PyObject *od, PyObject *key)
1609 {
1610 int res;
1611 Py_hash_t hash = PyObject_Hash(key);
1612 if (hash == -1)
1613 return -1;
1614 res = _odict_clear_node((PyODictObject *)od, NULL, key, hash);
1615 if (res < 0)
1616 return -1;
1617 return _PyDict_DelItem_KnownHash(od, key, hash);
1618 }
1619
1620
1621 /* -------------------------------------------
1622 * The OrderedDict views (keys/values/items)
1623 */
1624
1625 typedef struct {
1626 PyObject_HEAD
1627 int kind;
1628 PyODictObject *di_odict;
1629 Py_ssize_t di_size;
1630 size_t di_state;
1631 PyObject *di_current;
1632 PyObject *di_result; /* reusable result tuple for iteritems */
1633 } odictiterobject;
1634
1635 static void
odictiter_dealloc(odictiterobject * di)1636 odictiter_dealloc(odictiterobject *di)
1637 {
1638 _PyObject_GC_UNTRACK(di);
1639 Py_XDECREF(di->di_odict);
1640 Py_XDECREF(di->di_current);
1641 if ((di->kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) {
1642 Py_DECREF(di->di_result);
1643 }
1644 PyObject_GC_Del(di);
1645 }
1646
1647 static int
odictiter_traverse(odictiterobject * di,visitproc visit,void * arg)1648 odictiter_traverse(odictiterobject *di, visitproc visit, void *arg)
1649 {
1650 Py_VISIT(di->di_odict);
1651 Py_VISIT(di->di_current); /* A key could be any type, not just str. */
1652 Py_VISIT(di->di_result);
1653 return 0;
1654 }
1655
1656 /* In order to protect against modifications during iteration, we track
1657 * the current key instead of the current node. */
1658 static PyObject *
odictiter_nextkey(odictiterobject * di)1659 odictiter_nextkey(odictiterobject *di)
1660 {
1661 PyObject *key = NULL;
1662 _ODictNode *node;
1663 int reversed = di->kind & _odict_ITER_REVERSED;
1664
1665 if (di->di_odict == NULL)
1666 return NULL;
1667 if (di->di_current == NULL)
1668 goto done; /* We're already done. */
1669
1670 /* Check for unsupported changes. */
1671 if (di->di_odict->od_state != di->di_state) {
1672 PyErr_SetString(PyExc_RuntimeError,
1673 "OrderedDict mutated during iteration");
1674 goto done;
1675 }
1676 if (di->di_size != PyODict_SIZE(di->di_odict)) {
1677 PyErr_SetString(PyExc_RuntimeError,
1678 "OrderedDict changed size during iteration");
1679 di->di_size = -1; /* Make this state sticky */
1680 return NULL;
1681 }
1682
1683 /* Get the key. */
1684 node = _odict_find_node(di->di_odict, di->di_current);
1685 if (node == NULL) {
1686 if (!PyErr_Occurred())
1687 PyErr_SetObject(PyExc_KeyError, di->di_current);
1688 /* Must have been deleted. */
1689 Py_CLEAR(di->di_current);
1690 return NULL;
1691 }
1692 key = di->di_current;
1693
1694 /* Advance to the next key. */
1695 node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
1696 if (node == NULL) {
1697 /* Reached the end. */
1698 di->di_current = NULL;
1699 }
1700 else {
1701 di->di_current = Py_NewRef(_odictnode_KEY(node));
1702 }
1703
1704 return key;
1705
1706 done:
1707 Py_CLEAR(di->di_odict);
1708 return key;
1709 }
1710
1711 static PyObject *
odictiter_iternext(odictiterobject * di)1712 odictiter_iternext(odictiterobject *di)
1713 {
1714 PyObject *result, *value;
1715 PyObject *key = odictiter_nextkey(di); /* new reference */
1716
1717 if (key == NULL)
1718 return NULL;
1719
1720 /* Handle the keys case. */
1721 if (! (di->kind & _odict_ITER_VALUES)) {
1722 return key;
1723 }
1724
1725 value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */
1726 if (value == NULL) {
1727 if (!PyErr_Occurred())
1728 PyErr_SetObject(PyExc_KeyError, key);
1729 Py_DECREF(key);
1730 goto done;
1731 }
1732 Py_INCREF(value);
1733
1734 /* Handle the values case. */
1735 if (!(di->kind & _odict_ITER_KEYS)) {
1736 Py_DECREF(key);
1737 return value;
1738 }
1739
1740 /* Handle the items case. */
1741 result = di->di_result;
1742
1743 if (Py_REFCNT(result) == 1) {
1744 /* not in use so we can reuse it
1745 * (the common case during iteration) */
1746 Py_INCREF(result);
1747 Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */
1748 Py_DECREF(PyTuple_GET_ITEM(result, 1)); /* borrowed */
1749 // bpo-42536: The GC may have untracked this result tuple. Since we're
1750 // recycling it, make sure it's tracked again:
1751 if (!_PyObject_GC_IS_TRACKED(result)) {
1752 _PyObject_GC_TRACK(result);
1753 }
1754 }
1755 else {
1756 result = PyTuple_New(2);
1757 if (result == NULL) {
1758 Py_DECREF(key);
1759 Py_DECREF(value);
1760 goto done;
1761 }
1762 }
1763
1764 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1765 PyTuple_SET_ITEM(result, 1, value); /* steals reference */
1766 return result;
1767
1768 done:
1769 Py_CLEAR(di->di_current);
1770 Py_CLEAR(di->di_odict);
1771 return NULL;
1772 }
1773
1774 /* No need for tp_clear because odictiterobject is not mutable. */
1775
1776 PyDoc_STRVAR(reduce_doc, "Return state information for pickling");
1777
1778 static PyObject *
odictiter_reduce(odictiterobject * di,PyObject * Py_UNUSED (ignored))1779 odictiter_reduce(odictiterobject *di, PyObject *Py_UNUSED(ignored))
1780 {
1781 /* copy the iterator state */
1782 odictiterobject tmp = *di;
1783 Py_XINCREF(tmp.di_odict);
1784 Py_XINCREF(tmp.di_current);
1785
1786 /* iterate the temporary into a list */
1787 PyObject *list = PySequence_List((PyObject*)&tmp);
1788 Py_XDECREF(tmp.di_odict);
1789 Py_XDECREF(tmp.di_current);
1790 if (list == NULL) {
1791 return NULL;
1792 }
1793 return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list);
1794 }
1795
1796 static PyMethodDef odictiter_methods[] = {
1797 {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc},
1798 {NULL, NULL} /* sentinel */
1799 };
1800
1801 PyTypeObject PyODictIter_Type = {
1802 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1803 "odict_iterator", /* tp_name */
1804 sizeof(odictiterobject), /* tp_basicsize */
1805 0, /* tp_itemsize */
1806 /* methods */
1807 (destructor)odictiter_dealloc, /* tp_dealloc */
1808 0, /* tp_vectorcall_offset */
1809 0, /* tp_getattr */
1810 0, /* tp_setattr */
1811 0, /* tp_as_async */
1812 0, /* tp_repr */
1813 0, /* tp_as_number */
1814 0, /* tp_as_sequence */
1815 0, /* tp_as_mapping */
1816 0, /* tp_hash */
1817 0, /* tp_call */
1818 0, /* tp_str */
1819 PyObject_GenericGetAttr, /* tp_getattro */
1820 0, /* tp_setattro */
1821 0, /* tp_as_buffer */
1822 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1823 0, /* tp_doc */
1824 (traverseproc)odictiter_traverse, /* tp_traverse */
1825 0, /* tp_clear */
1826 0, /* tp_richcompare */
1827 0, /* tp_weaklistoffset */
1828 PyObject_SelfIter, /* tp_iter */
1829 (iternextfunc)odictiter_iternext, /* tp_iternext */
1830 odictiter_methods, /* tp_methods */
1831 0,
1832 };
1833
1834 static PyObject *
odictiter_new(PyODictObject * od,int kind)1835 odictiter_new(PyODictObject *od, int kind)
1836 {
1837 odictiterobject *di;
1838 _ODictNode *node;
1839 int reversed = kind & _odict_ITER_REVERSED;
1840
1841 di = PyObject_GC_New(odictiterobject, &PyODictIter_Type);
1842 if (di == NULL)
1843 return NULL;
1844
1845 if ((kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) {
1846 di->di_result = PyTuple_Pack(2, Py_None, Py_None);
1847 if (di->di_result == NULL) {
1848 Py_DECREF(di);
1849 return NULL;
1850 }
1851 }
1852 else {
1853 di->di_result = NULL;
1854 }
1855
1856 di->kind = kind;
1857 node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
1858 di->di_current = node ? Py_NewRef(_odictnode_KEY(node)) : NULL;
1859 di->di_size = PyODict_SIZE(od);
1860 di->di_state = od->od_state;
1861 di->di_odict = (PyODictObject*)Py_NewRef(od);
1862
1863 _PyObject_GC_TRACK(di);
1864 return (PyObject *)di;
1865 }
1866
1867 /* keys() */
1868
1869 static PyObject *
odictkeys_iter(_PyDictViewObject * dv)1870 odictkeys_iter(_PyDictViewObject *dv)
1871 {
1872 if (dv->dv_dict == NULL) {
1873 Py_RETURN_NONE;
1874 }
1875 return odictiter_new((PyODictObject *)dv->dv_dict,
1876 _odict_ITER_KEYS);
1877 }
1878
1879 static PyObject *
odictkeys_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))1880 odictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1881 {
1882 if (dv->dv_dict == NULL) {
1883 Py_RETURN_NONE;
1884 }
1885 return odictiter_new((PyODictObject *)dv->dv_dict,
1886 _odict_ITER_KEYS|_odict_ITER_REVERSED);
1887 }
1888
1889 static PyMethodDef odictkeys_methods[] = {
1890 {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL},
1891 {NULL, NULL} /* sentinel */
1892 };
1893
1894 PyTypeObject PyODictKeys_Type = {
1895 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1896 "odict_keys", /* tp_name */
1897 0, /* tp_basicsize */
1898 0, /* tp_itemsize */
1899 0, /* tp_dealloc */
1900 0, /* tp_vectorcall_offset */
1901 0, /* tp_getattr */
1902 0, /* tp_setattr */
1903 0, /* tp_as_async */
1904 0, /* tp_repr */
1905 0, /* tp_as_number */
1906 0, /* tp_as_sequence */
1907 0, /* tp_as_mapping */
1908 0, /* tp_hash */
1909 0, /* tp_call */
1910 0, /* tp_str */
1911 0, /* tp_getattro */
1912 0, /* tp_setattro */
1913 0, /* tp_as_buffer */
1914 0, /* tp_flags */
1915 0, /* tp_doc */
1916 0, /* tp_traverse */
1917 0, /* tp_clear */
1918 0, /* tp_richcompare */
1919 0, /* tp_weaklistoffset */
1920 (getiterfunc)odictkeys_iter, /* tp_iter */
1921 0, /* tp_iternext */
1922 odictkeys_methods, /* tp_methods */
1923 0, /* tp_members */
1924 0, /* tp_getset */
1925 &PyDictKeys_Type, /* tp_base */
1926 };
1927
1928 static PyObject *
odictkeys_new(PyObject * od,PyObject * Py_UNUSED (ignored))1929 odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored))
1930 {
1931 return _PyDictView_New(od, &PyODictKeys_Type);
1932 }
1933
1934 /* items() */
1935
1936 static PyObject *
odictitems_iter(_PyDictViewObject * dv)1937 odictitems_iter(_PyDictViewObject *dv)
1938 {
1939 if (dv->dv_dict == NULL) {
1940 Py_RETURN_NONE;
1941 }
1942 return odictiter_new((PyODictObject *)dv->dv_dict,
1943 _odict_ITER_KEYS|_odict_ITER_VALUES);
1944 }
1945
1946 static PyObject *
odictitems_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))1947 odictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
1948 {
1949 if (dv->dv_dict == NULL) {
1950 Py_RETURN_NONE;
1951 }
1952 return odictiter_new((PyODictObject *)dv->dv_dict,
1953 _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED);
1954 }
1955
1956 static PyMethodDef odictitems_methods[] = {
1957 {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL},
1958 {NULL, NULL} /* sentinel */
1959 };
1960
1961 PyTypeObject PyODictItems_Type = {
1962 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1963 "odict_items", /* tp_name */
1964 0, /* tp_basicsize */
1965 0, /* tp_itemsize */
1966 0, /* tp_dealloc */
1967 0, /* tp_vectorcall_offset */
1968 0, /* tp_getattr */
1969 0, /* tp_setattr */
1970 0, /* tp_as_async */
1971 0, /* tp_repr */
1972 0, /* tp_as_number */
1973 0, /* tp_as_sequence */
1974 0, /* tp_as_mapping */
1975 0, /* tp_hash */
1976 0, /* tp_call */
1977 0, /* tp_str */
1978 0, /* tp_getattro */
1979 0, /* tp_setattro */
1980 0, /* tp_as_buffer */
1981 0, /* tp_flags */
1982 0, /* tp_doc */
1983 0, /* tp_traverse */
1984 0, /* tp_clear */
1985 0, /* tp_richcompare */
1986 0, /* tp_weaklistoffset */
1987 (getiterfunc)odictitems_iter, /* tp_iter */
1988 0, /* tp_iternext */
1989 odictitems_methods, /* tp_methods */
1990 0, /* tp_members */
1991 0, /* tp_getset */
1992 &PyDictItems_Type, /* tp_base */
1993 };
1994
1995 static PyObject *
odictitems_new(PyObject * od,PyObject * Py_UNUSED (ignored))1996 odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored))
1997 {
1998 return _PyDictView_New(od, &PyODictItems_Type);
1999 }
2000
2001 /* values() */
2002
2003 static PyObject *
odictvalues_iter(_PyDictViewObject * dv)2004 odictvalues_iter(_PyDictViewObject *dv)
2005 {
2006 if (dv->dv_dict == NULL) {
2007 Py_RETURN_NONE;
2008 }
2009 return odictiter_new((PyODictObject *)dv->dv_dict,
2010 _odict_ITER_VALUES);
2011 }
2012
2013 static PyObject *
odictvalues_reversed(_PyDictViewObject * dv,PyObject * Py_UNUSED (ignored))2014 odictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
2015 {
2016 if (dv->dv_dict == NULL) {
2017 Py_RETURN_NONE;
2018 }
2019 return odictiter_new((PyODictObject *)dv->dv_dict,
2020 _odict_ITER_VALUES|_odict_ITER_REVERSED);
2021 }
2022
2023 static PyMethodDef odictvalues_methods[] = {
2024 {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL},
2025 {NULL, NULL} /* sentinel */
2026 };
2027
2028 PyTypeObject PyODictValues_Type = {
2029 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2030 "odict_values", /* tp_name */
2031 0, /* tp_basicsize */
2032 0, /* tp_itemsize */
2033 0, /* tp_dealloc */
2034 0, /* tp_vectorcall_offset */
2035 0, /* tp_getattr */
2036 0, /* tp_setattr */
2037 0, /* tp_as_async */
2038 0, /* tp_repr */
2039 0, /* tp_as_number */
2040 0, /* tp_as_sequence */
2041 0, /* tp_as_mapping */
2042 0, /* tp_hash */
2043 0, /* tp_call */
2044 0, /* tp_str */
2045 0, /* tp_getattro */
2046 0, /* tp_setattro */
2047 0, /* tp_as_buffer */
2048 0, /* tp_flags */
2049 0, /* tp_doc */
2050 0, /* tp_traverse */
2051 0, /* tp_clear */
2052 0, /* tp_richcompare */
2053 0, /* tp_weaklistoffset */
2054 (getiterfunc)odictvalues_iter, /* tp_iter */
2055 0, /* tp_iternext */
2056 odictvalues_methods, /* tp_methods */
2057 0, /* tp_members */
2058 0, /* tp_getset */
2059 &PyDictValues_Type, /* tp_base */
2060 };
2061
2062 static PyObject *
odictvalues_new(PyObject * od,PyObject * Py_UNUSED (ignored))2063 odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored))
2064 {
2065 return _PyDictView_New(od, &PyODictValues_Type);
2066 }
2067
2068
2069 /* ----------------------------------------------
2070 MutableMapping implementations
2071
2072 Mapping:
2073
2074 ============ ===========
2075 method uses
2076 ============ ===========
2077 __contains__ __getitem__
2078 __eq__ items
2079 __getitem__ +
2080 __iter__ +
2081 __len__ +
2082 __ne__ __eq__
2083 get __getitem__
2084 items ItemsView
2085 keys KeysView
2086 values ValuesView
2087 ============ ===========
2088
2089 ItemsView uses __len__, __iter__, and __getitem__.
2090 KeysView uses __len__, __iter__, and __contains__.
2091 ValuesView uses __len__, __iter__, and __getitem__.
2092
2093 MutableMapping:
2094
2095 ============ ===========
2096 method uses
2097 ============ ===========
2098 __delitem__ +
2099 __setitem__ +
2100 clear popitem
2101 pop __getitem__
2102 __delitem__
2103 popitem __iter__
2104 _getitem__
2105 __delitem__
2106 setdefault __getitem__
2107 __setitem__
2108 update __setitem__
2109 ============ ===========
2110 */
2111
2112 static int
mutablemapping_add_pairs(PyObject * self,PyObject * pairs)2113 mutablemapping_add_pairs(PyObject *self, PyObject *pairs)
2114 {
2115 PyObject *pair, *iterator, *unexpected;
2116 int res = 0;
2117
2118 iterator = PyObject_GetIter(pairs);
2119 if (iterator == NULL)
2120 return -1;
2121 PyErr_Clear();
2122
2123 while ((pair = PyIter_Next(iterator)) != NULL) {
2124 /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */
2125 PyObject *key = NULL, *value = NULL;
2126 PyObject *pair_iterator = PyObject_GetIter(pair);
2127 if (pair_iterator == NULL)
2128 goto Done;
2129
2130 key = PyIter_Next(pair_iterator);
2131 if (key == NULL) {
2132 if (!PyErr_Occurred())
2133 PyErr_SetString(PyExc_ValueError,
2134 "need more than 0 values to unpack");
2135 goto Done;
2136 }
2137
2138 value = PyIter_Next(pair_iterator);
2139 if (value == NULL) {
2140 if (!PyErr_Occurred())
2141 PyErr_SetString(PyExc_ValueError,
2142 "need more than 1 value to unpack");
2143 goto Done;
2144 }
2145
2146 unexpected = PyIter_Next(pair_iterator);
2147 if (unexpected != NULL) {
2148 Py_DECREF(unexpected);
2149 PyErr_SetString(PyExc_ValueError,
2150 "too many values to unpack (expected 2)");
2151 goto Done;
2152 }
2153 else if (PyErr_Occurred())
2154 goto Done;
2155
2156 res = PyObject_SetItem(self, key, value);
2157
2158 Done:
2159 Py_DECREF(pair);
2160 Py_XDECREF(pair_iterator);
2161 Py_XDECREF(key);
2162 Py_XDECREF(value);
2163 if (PyErr_Occurred())
2164 break;
2165 }
2166 Py_DECREF(iterator);
2167
2168 if (res < 0 || PyErr_Occurred() != NULL)
2169 return -1;
2170 else
2171 return 0;
2172 }
2173
2174 static int
mutablemapping_update_arg(PyObject * self,PyObject * arg)2175 mutablemapping_update_arg(PyObject *self, PyObject *arg)
2176 {
2177 int res = 0;
2178 if (PyDict_CheckExact(arg)) {
2179 PyObject *items = PyDict_Items(arg);
2180 if (items == NULL) {
2181 return -1;
2182 }
2183 res = mutablemapping_add_pairs(self, items);
2184 Py_DECREF(items);
2185 return res;
2186 }
2187 PyObject *func;
2188 if (PyObject_GetOptionalAttr(arg, &_Py_ID(keys), &func) < 0) {
2189 return -1;
2190 }
2191 if (func != NULL) {
2192 PyObject *keys = _PyObject_CallNoArgs(func);
2193 Py_DECREF(func);
2194 if (keys == NULL) {
2195 return -1;
2196 }
2197 PyObject *iterator = PyObject_GetIter(keys);
2198 Py_DECREF(keys);
2199 if (iterator == NULL) {
2200 return -1;
2201 }
2202 PyObject *key;
2203 while (res == 0 && (key = PyIter_Next(iterator))) {
2204 PyObject *value = PyObject_GetItem(arg, key);
2205 if (value != NULL) {
2206 res = PyObject_SetItem(self, key, value);
2207 Py_DECREF(value);
2208 }
2209 else {
2210 res = -1;
2211 }
2212 Py_DECREF(key);
2213 }
2214 Py_DECREF(iterator);
2215 if (res != 0 || PyErr_Occurred()) {
2216 return -1;
2217 }
2218 return 0;
2219 }
2220 if (PyObject_GetOptionalAttr(arg, &_Py_ID(items), &func) < 0) {
2221 return -1;
2222 }
2223 if (func != NULL) {
2224 PyObject *items = _PyObject_CallNoArgs(func);
2225 Py_DECREF(func);
2226 if (items == NULL) {
2227 return -1;
2228 }
2229 res = mutablemapping_add_pairs(self, items);
2230 Py_DECREF(items);
2231 return res;
2232 }
2233 res = mutablemapping_add_pairs(self, arg);
2234 return res;
2235 }
2236
2237 static PyObject *
mutablemapping_update(PyObject * self,PyObject * args,PyObject * kwargs)2238 mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs)
2239 {
2240 int res;
2241 /* first handle args, if any */
2242 assert(args == NULL || PyTuple_Check(args));
2243 Py_ssize_t len = (args != NULL) ? PyTuple_GET_SIZE(args) : 0;
2244 if (len > 1) {
2245 const char *msg = "update() takes at most 1 positional argument (%zd given)";
2246 PyErr_Format(PyExc_TypeError, msg, len);
2247 return NULL;
2248 }
2249
2250 if (len) {
2251 PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */
2252 assert(other != NULL);
2253 Py_INCREF(other);
2254 res = mutablemapping_update_arg(self, other);
2255 Py_DECREF(other);
2256 if (res < 0) {
2257 return NULL;
2258 }
2259 }
2260
2261 /* now handle kwargs */
2262 assert(kwargs == NULL || PyDict_Check(kwargs));
2263 if (kwargs != NULL && PyDict_GET_SIZE(kwargs)) {
2264 PyObject *items = PyDict_Items(kwargs);
2265 if (items == NULL)
2266 return NULL;
2267 res = mutablemapping_add_pairs(self, items);
2268 Py_DECREF(items);
2269 if (res == -1)
2270 return NULL;
2271 }
2272
2273 Py_RETURN_NONE;
2274 }
2275