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