Branch data 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 : 199414 : _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
531 : : {
532 : 199414 : PyObject *value = NULL;
533 : 199414 : PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
534 : : Py_ssize_t ix;
535 : :
536 : 199414 : ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);
537 [ + + ]: 199414 : if (ix == DKIX_EMPTY) {
538 : 219 : return keys->dk_nentries; /* index of new entry */
539 : : }
540 [ - + ]: 199195 : if (ix < 0)
541 : 0 : return -1;
542 : : /* We use pointer arithmetic to get the entry's index into the table. */
543 : 199195 : 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 : 11997 : _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 : 11997 : size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_size);
557 [ + - ]: 11997 : fast_nodes = PyMem_NEW(_ODictNode *, size);
558 [ - + ]: 11997 : if (fast_nodes == NULL) {
559 : : PyErr_NoMemory();
560 : 0 : return -1;
561 : : }
562 [ + + ]: 127573 : for (i = 0; i < size; i++)
563 : 115576 : fast_nodes[i] = NULL;
564 : :
565 : : /* Copy the current nodes into the table. */
566 [ + + ]: 21175 : _odict_FOREACH(od, node) {
567 : 9178 : i = _odict_get_index_raw(od, _odictnode_KEY(node),
568 : : _odictnode_HASH(node));
569 [ - + ]: 9178 : if (i < 0) {
570 : 0 : PyMem_Free(fast_nodes);
571 : 0 : return -1;
572 : : }
573 : 9178 : fast_nodes[i] = node;
574 : : }
575 : :
576 : : /* Replace the old fast nodes table. */
577 : 11997 : PyMem_Free(od->od_fast_nodes);
578 : 11997 : od->od_fast_nodes = fast_nodes;
579 : 11997 : od->od_fast_nodes_size = size;
580 : 11997 : od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;
581 : 11997 : return 0;
582 : : }
583 : :
584 : : /* Return the index into the hash table, regardless of a valid node. */
585 : : static Py_ssize_t
586 : 190236 : _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)
587 : : {
588 : : PyDictKeysObject *keys;
589 : :
590 : : assert(key != NULL);
591 : 190236 : keys = ((PyDictObject *)od)->ma_keys;
592 : :
593 : : /* Ensure od_fast_nodes and dk_entries are in sync. */
594 [ + + ]: 190236 : if (od->od_resize_sentinel != keys ||
595 [ - + ]: 178239 : od->od_fast_nodes_size != (ONE << (keys->dk_log2_size))) {
596 : 11997 : int resize_res = _odict_resize(od);
597 [ - + ]: 11997 : if (resize_res < 0)
598 : 0 : return -1;
599 : : }
600 : :
601 : 190236 : 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 : : assert(od->od_fast_nodes != NULL);
616 : 2412 : return od->od_fast_nodes[index];
617 : : }
618 : :
619 : : static _ODictNode *
620 : 154800 : _odict_find_node(PyODictObject *od, PyObject *key)
621 : : {
622 : : Py_ssize_t index;
623 : : Py_hash_t hash;
624 : :
625 [ - + ]: 154800 : if (_odict_EMPTY(od))
626 : 0 : return NULL;
627 : 154800 : hash = PyObject_Hash(key);
628 [ - + ]: 154800 : if (hash == -1)
629 : 0 : return NULL;
630 : 154800 : index = _odict_get_index(od, key, hash);
631 [ - + ]: 154800 : if (index < 0)
632 : 0 : return NULL;
633 : : assert(od->od_fast_nodes != NULL);
634 : 154800 : 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 : 30572 : _odict_add_tail(PyODictObject *od, _ODictNode *node)
652 : : {
653 : 30572 : _odictnode_PREV(node) = _odict_LAST(od);
654 : 30572 : _odictnode_NEXT(node) = NULL;
655 [ + + ]: 30572 : if (_odict_LAST(od) == NULL)
656 : 10740 : _odict_FIRST(od) = node;
657 : : else
658 : 19832 : _odictnode_NEXT(_odict_LAST(od)) = node;
659 : 30572 : _odict_LAST(od) = node;
660 : 30572 : od->od_state++;
661 : 30572 : }
662 : :
663 : : /* adds the node to the end of the list */
664 : : static int
665 : 30799 : _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
666 : : {
667 : : Py_ssize_t i;
668 : : _ODictNode *node;
669 : :
670 : 30799 : Py_INCREF(key);
671 : 30799 : i = _odict_get_index(od, key, hash);
672 [ - + ]: 30799 : 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 : : assert(od->od_fast_nodes != NULL);
679 [ + + ]: 30799 : 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 : 30527 : node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode));
687 [ - + ]: 30527 : if (node == NULL) {
688 : 0 : Py_DECREF(key);
689 : : PyErr_NoMemory();
690 : 0 : return -1;
691 : : }
692 : :
693 : 30527 : _odictnode_KEY(node) = key;
694 : 30527 : _odictnode_HASH(node) = hash;
695 : 30527 : _odict_add_tail(od, node);
696 : 30527 : od->od_fast_nodes[i] = node;
697 : 30527 : 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 : 1776 : _odict_FIRST(od) = _odictnode_NEXT(node);
713 [ + - ]: 500 : else if (_odictnode_PREV(node) != NULL)
714 : 500 : _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);
715 : :
716 [ + + ]: 2276 : if (_odict_LAST(od) == node)
717 : 747 : _odict_LAST(od) = _odictnode_PREV(node);
718 [ + - ]: 1529 : else if (_odictnode_NEXT(node) != NULL)
719 : 1529 : _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 : : 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 : : assert(od->od_fast_nodes != NULL);
759 [ + + ]: 2225 : if (node == NULL)
760 : 18 : node = od->od_fast_nodes[i];
761 : : 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 : 11564 : _odict_clear_nodes(PyODictObject *od)
776 : : {
777 : : _ODictNode *node, *next;
778 : :
779 : 11564 : PyMem_Free(od->od_fast_nodes);
780 : 11564 : od->od_fast_nodes = NULL;
781 : 11564 : od->od_fast_nodes_size = 0;
782 : 11564 : od->od_resize_sentinel = NULL;
783 : :
784 : 11564 : node = _odict_FIRST(od);
785 : 11564 : _odict_FIRST(od) = NULL;
786 : 11564 : _odict_LAST(od) = NULL;
787 [ + + ]: 39868 : while (node != NULL) {
788 : 28304 : next = _odictnode_NEXT(node);
789 : 28304 : _odictnode_DEALLOC(node);
790 : 28304 : node = next;
791 : : }
792 : 11564 : }
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 : 30724 : odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w)
837 : : {
838 [ + + ]: 30724 : if (w == NULL)
839 : 18 : return PyODict_DelItem((PyObject *)od, v);
840 : : else
841 : 30706 : 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 : : 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 : 11465 : odict_dealloc(PyODictObject *self)
1355 : : {
1356 : 11465 : PyObject_GC_UnTrack(self);
1357 [ + + + + ]: 11465 : Py_TRASHCAN_BEGIN(self, odict_dealloc)
1358 : :
1359 : 11445 : Py_XDECREF(self->od_inst_dict);
1360 [ - + ]: 11445 : if (self->od_weakreflist != NULL)
1361 : 0 : PyObject_ClearWeakRefs((PyObject *)self);
1362 : :
1363 : 11445 : _odict_clear_nodes(self);
1364 : 11445 : PyDict_Type.tp_dealloc((PyObject *)self);
1365 : :
1366 [ + + ]: 11445 : Py_TRASHCAN_END
1367 : 11465 : }
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 [ + + ]: 357 : _odict_FOREACH(self, node) {
1393 : : PyObject *pair;
1394 : 309 : PyObject *key = _odictnode_KEY(node);
1395 : 309 : PyObject *value = _odictnode_VALUE(node, self);
1396 [ + + ]: 309 : if (value == NULL) {
1397 [ + - ]: 4 : if (!PyErr_Occurred())
1398 : 4 : PyErr_SetObject(PyExc_KeyError, key);
1399 : 4 : goto Done;
1400 : : }
1401 : 305 : pair = PyTuple_Pack(2, key, value);
1402 [ - + ]: 305 : if (pair == NULL)
1403 : 0 : goto Done;
1404 : :
1405 [ + - ]: 305 : if (count < PyList_GET_SIZE(pieces))
1406 : 305 : 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 : 305 : 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 : 21670 : odict_traverse(PyODictObject *od, visitproc visit, void *arg)
1449 : : {
1450 : : _ODictNode *node;
1451 : :
1452 [ + + - + ]: 21670 : Py_VISIT(od->od_inst_dict);
1453 [ + + ]: 186850 : _odict_FOREACH(od, node) {
1454 [ + - - + ]: 165180 : Py_VISIT(_odictnode_KEY(node));
1455 : : }
1456 : 21670 : 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 : 11417 : odict_init(PyObject *self, PyObject *args, PyObject *kwds)
1519 : : {
1520 : : PyObject *res;
1521 : 11417 : Py_ssize_t len = PyObject_Length(args);
1522 : :
1523 [ - + ]: 11417 : if (len == -1)
1524 : 0 : return -1;
1525 [ + + ]: 11417 : 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 : 11411 : res = odict_update(self, args, kwds);
1533 [ + + ]: 11411 : if (res == NULL) {
1534 : 2 : return -1;
1535 : : } else {
1536 : 11409 : Py_DECREF(res);
1537 : 11409 : 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 : 30799 : _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,
1598 : : Py_hash_t hash)
1599 : : {
1600 : 30799 : int res = _PyDict_SetItem_KnownHash(od, key, value, hash);
1601 [ + - ]: 30799 : if (res == 0) {
1602 : 30799 : res = _odict_add_new_node((PyODictObject *)od, key, hash);
1603 [ - + ]: 30799 : 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 : 30799 : return res;
1612 : : }
1613 : :
1614 : : int
1615 : 30709 : PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value)
1616 : : {
1617 : 30709 : Py_hash_t hash = PyObject_Hash(key);
1618 [ - + ]: 30709 : if (hash == -1)
1619 : 0 : return -1;
1620 : 30709 : 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 : 22425 : odictiter_dealloc(odictiterobject *di)
1653 : : {
1654 : 22425 : _PyObject_GC_UNTRACK(di);
1655 : 22425 : Py_XDECREF(di->di_odict);
1656 : 22425 : Py_XDECREF(di->di_current);
1657 [ + + ]: 22425 : if ((di->kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) {
1658 : 4663 : Py_DECREF(di->di_result);
1659 : : }
1660 : 22425 : PyObject_GC_Del(di);
1661 : 22425 : }
1662 : :
1663 : : static int
1664 : 220 : odictiter_traverse(odictiterobject *di, visitproc visit, void *arg)
1665 : : {
1666 [ + + - + ]: 220 : Py_VISIT(di->di_odict);
1667 [ + + - + ]: 220 : Py_VISIT(di->di_current); /* A key could be any type, not just str. */
1668 [ + + - + ]: 220 : Py_VISIT(di->di_result);
1669 : 220 : 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 : 177460 : odictiter_nextkey(odictiterobject *di)
1676 : : {
1677 : 177460 : PyObject *key = NULL;
1678 : : _ODictNode *node;
1679 : 177460 : int reversed = di->kind & _odict_ITER_REVERSED;
1680 : :
1681 [ + + ]: 177460 : if (di->di_odict == NULL)
1682 : 618 : return NULL;
1683 [ + + ]: 176842 : if (di->di_current == NULL)
1684 : 22095 : goto done; /* We're already done. */
1685 : :
1686 : : /* Check for unsupported changes. */
1687 [ + + ]: 154747 : 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 [ - + ]: 154739 : 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 : 154739 : node = _odict_find_node(di->di_odict, di->di_current);
1701 [ + + ]: 154739 : 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 : 154732 : key = di->di_current;
1709 : :
1710 : : /* Advance to the next key. */
1711 [ + + ]: 154732 : node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
1712 [ + + ]: 154732 : if (node == NULL) {
1713 : : /* Reached the end. */
1714 : 21463 : di->di_current = NULL;
1715 : : }
1716 : : else {
1717 : 133269 : di->di_current = _odictnode_KEY(node);
1718 : 133269 : Py_INCREF(di->di_current);
1719 : : }
1720 : :
1721 : 154732 : return key;
1722 : :
1723 : 22103 : done:
1724 [ + - ]: 22103 : Py_CLEAR(di->di_odict);
1725 : 22103 : return key;
1726 : : }
1727 : :
1728 : : static PyObject *
1729 : 177460 : odictiter_iternext(odictiterobject *di)
1730 : : {
1731 : : PyObject *result, *value;
1732 : 177460 : PyObject *key = odictiter_nextkey(di); /* new reference */
1733 : :
1734 [ + + ]: 177460 : if (key == NULL)
1735 : 22728 : return NULL;
1736 : :
1737 : : /* Handle the keys case. */
1738 [ + + ]: 154732 : if (! (di->kind & _odict_ITER_VALUES)) {
1739 : 2781 : return key;
1740 : : }
1741 : :
1742 : 151951 : value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */
1743 [ + + ]: 151951 : 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 : 151950 : Py_INCREF(value);
1750 : :
1751 : : /* Handle the values case. */
1752 [ + + ]: 151950 : if (!(di->kind & _odict_ITER_KEYS)) {
1753 : 139026 : Py_DECREF(key);
1754 : 139026 : 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 : 22425 : odictiter_new(PyODictObject *od, int kind)
1853 : : {
1854 : : odictiterobject *di;
1855 : : _ODictNode *node;
1856 : 22425 : int reversed = kind & _odict_ITER_REVERSED;
1857 : :
1858 : 22425 : di = PyObject_GC_New(odictiterobject, &PyODictIter_Type);
1859 [ - + ]: 22425 : if (di == NULL)
1860 : 0 : return NULL;
1861 : :
1862 [ + + ]: 22425 : 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 : 17762 : di->di_result = NULL;
1871 : : }
1872 : :
1873 : 22425 : di->kind = kind;
1874 [ + + ]: 22425 : node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
1875 [ + + ]: 22425 : di->di_current = node ? _odictnode_KEY(node) : NULL;
1876 : 22425 : Py_XINCREF(di->di_current);
1877 : 22425 : di->di_size = PyODict_SIZE(od);
1878 : 22425 : di->di_state = od->od_state;
1879 : 22425 : di->di_odict = od;
1880 : 22425 : Py_INCREF(od);
1881 : :
1882 : 22425 : _PyObject_GC_TRACK(di);
1883 : 22425 : 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 : 16922 : odictvalues_iter(_PyDictViewObject *dv)
2024 : : {
2025 [ - + ]: 16922 : if (dv->dv_dict == NULL) {
2026 : 0 : Py_RETURN_NONE;
2027 : : }
2028 : 16922 : 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 : 16929 : odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored))
2083 : : {
2084 : 16929 : 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 : 7124 : mutablemapping_add_pairs(PyObject *self, PyObject *pairs)
2133 : : {
2134 : : PyObject *pair, *iterator, *unexpected;
2135 : 7124 : int res = 0;
2136 : :
2137 : 7124 : iterator = PyObject_GetIter(pairs);
2138 [ + + ]: 7124 : if (iterator == NULL)
2139 : 8 : return -1;
2140 : 7116 : PyErr_Clear();
2141 : :
2142 [ + + ]: 27212 : while ((pair = PyIter_Next(iterator)) != NULL) {
2143 : : /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */
2144 : 20100 : PyObject *key = NULL, *value = NULL;
2145 : 20100 : PyObject *pair_iterator = PyObject_GetIter(pair);
2146 [ - + ]: 20100 : if (pair_iterator == NULL)
2147 : 0 : goto Done;
2148 : :
2149 : 20100 : key = PyIter_Next(pair_iterator);
2150 [ - + ]: 20100 : 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 : 20100 : value = PyIter_Next(pair_iterator);
2158 [ + + ]: 20100 : 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 : 20098 : unexpected = PyIter_Next(pair_iterator);
2166 [ + + ]: 20098 : 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 [ - + ]: 20096 : else if (PyErr_Occurred())
2173 : 0 : goto Done;
2174 : :
2175 : 20096 : res = PyObject_SetItem(self, key, value);
2176 : :
2177 : 20100 : Done:
2178 : 20100 : Py_DECREF(pair);
2179 : 20100 : Py_XDECREF(pair_iterator);
2180 : 20100 : Py_XDECREF(key);
2181 : 20100 : Py_XDECREF(value);
2182 [ + + ]: 20100 : if (PyErr_Occurred())
2183 : 4 : break;
2184 : : }
2185 : 7116 : Py_DECREF(iterator);
2186 : :
2187 [ + - + + ]: 7116 : if (res < 0 || PyErr_Occurred() != NULL)
2188 : 6 : return -1;
2189 : : else
2190 : 7110 : return 0;
2191 : : }
2192 : :
2193 : : static int
2194 : 7133 : mutablemapping_update_arg(PyObject *self, PyObject *arg)
2195 : : {
2196 : 7133 : int res = 0;
2197 [ + + ]: 7133 : 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 [ - + ]: 7104 : if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) {
2208 : 0 : return -1;
2209 : : }
2210 [ + + ]: 7104 : 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 [ - + ]: 7058 : if (_PyObject_LookupAttr(arg, &_Py_ID(items), &func) < 0) {
2240 : 0 : return -1;
2241 : : }
2242 [ - + ]: 7058 : 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 : 7058 : res = mutablemapping_add_pairs(self, arg);
2253 : 7058 : return res;
2254 : : }
2255 : :
2256 : : static PyObject *
2257 : 11477 : mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs)
2258 : : {
2259 : : int res;
2260 : : /* first handle args, if any */
2261 : : assert(args == NULL || PyTuple_Check(args));
2262 [ + - ]: 11477 : Py_ssize_t len = (args != NULL) ? PyTuple_GET_SIZE(args) : 0;
2263 [ + + ]: 11477 : 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 [ + + ]: 11471 : if (len) {
2270 : 7107 : PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */
2271 : : assert(other != NULL);
2272 : 7107 : Py_INCREF(other);
2273 : 7107 : res = mutablemapping_update_arg(self, other);
2274 : 7107 : Py_DECREF(other);
2275 [ + + ]: 7107 : if (res < 0) {
2276 : 18 : return NULL;
2277 : : }
2278 : : }
2279 : :
2280 : : /* now handle kwargs */
2281 : : assert(kwargs == NULL || PyDict_Check(kwargs));
2282 [ + + + + ]: 11453 : 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 : 11453 : Py_RETURN_NONE;
2293 : : }
|
