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