/home/mdboom/Work/builds/cpython/Objects/odictobject.c
Line | Count | Source (jump to first uncovered line) |
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 = 381k _odict_FIRST381k (od); node != NULL; node = 2.81M _odictnode_NEXT2.81M (node)) |
527 | |
528 | /* Return the index into the hash table, regardless of a valid node. */ |
529 | static Py_ssize_t |
530 | _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash) |
531 | { |
532 | PyObject *value = NULL; |
533 | PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys; |
534 | Py_ssize_t ix; |
535 | |
536 | ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value); |
537 | if (ix == DKIX_EMPTY) { Branch (537:9): [True: 211, False: 187k]
|
538 | return keys->dk_nentries; /* index of new entry */ |
539 | } |
540 | if (ix < 0) Branch (540:9): [True: 0, False: 187k]
|
541 | return -1; |
542 | /* We use pointer arithmetic to get the entry's index into the table. */ |
543 | 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 | _odict_resize(PyODictObject *od) |
551 | { |
552 | Py_ssize_t size, i; |
553 | _ODictNode **fast_nodes, *node; |
554 | |
555 | /* Initialize a new "fast nodes" table. */ |
556 | size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_size); |
557 | fast_nodes = PyMem_NEW(_ODictNode *, size); |
558 | if (fast_nodes == NULL) { Branch (558:9): [True: 0, False: 10.6k]
|
559 | PyErr_NoMemory(); |
560 | return -1; |
561 | } |
562 | for (i = 0; 10.6k i < size; i++93.1k ) Branch (562:17): [True: 93.1k, False: 10.6k]
|
563 | fast_nodes[i] = NULL; |
564 | |
565 | /* Copy the current nodes into the table. */ |
566 | _odict_FOREACH(od, node) { |
567 | i = _odict_get_index_raw(od, _odictnode_KEY(node), |
568 | _odictnode_HASH(node)); |
569 | if (i < 0) { Branch (569:13): [True: 0, False: 3.47k]
|
570 | PyMem_Free(fast_nodes); |
571 | return -1; |
572 | } |
573 | fast_nodes[i] = node; |
574 | } |
575 | |
576 | /* Replace the old fast nodes table. */ |
577 | PyMem_Free(od->od_fast_nodes); |
578 | od->od_fast_nodes = fast_nodes; |
579 | od->od_fast_nodes_size = size; |
580 | od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys; |
581 | return 0; |
582 | } |
583 | |
584 | /* Return the index into the hash table, regardless of a valid node. */ |
585 | static Py_ssize_t |
586 | _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash) |
587 | { |
588 | PyDictKeysObject *keys; |
589 | |
590 | assert(key != NULL); |
591 | keys = ((PyDictObject *)od)->ma_keys; |
592 | |
593 | /* Ensure od_fast_nodes and dk_entries are in sync. */ |
594 | if (od->od_resize_sentinel != keys || Branch (594:9): [True: 10.6k, False: 173k]
|
595 | od->od_fast_nodes_size != (173k ONE173k << (keys->dk_log2_size))) { Branch (595:9): [True: 0, False: 173k]
|
596 | int resize_res = _odict_resize(od); |
597 | if (resize_res < 0) Branch (597:13): [True: 0, False: 10.6k]
|
598 | return -1; |
599 | } |
600 | |
601 | return _odict_get_index_raw(od, key, hash); |
602 | } |
603 | |
604 | /* Returns NULL if there was some error or the key was not found. */ |
605 | static _ODictNode * |
606 | _odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash) |
607 | { |
608 | Py_ssize_t index; |
609 | |
610 | if (_odict_EMPTY(od)) |
611 | return NULL; |
612 | index = _odict_get_index(od, key, hash); |
613 | if (index < 0) Branch (613:9): [True: 0, False: 2.39k]
|
614 | return NULL; |
615 | assert(od->od_fast_nodes != NULL); |
616 | return od->od_fast_nodes[index]; |
617 | } |
618 | |
619 | static _ODictNode * |
620 | _odict_find_node(PyODictObject *od, PyObject *key) |
621 | { |
622 | Py_ssize_t index; |
623 | Py_hash_t hash; |
624 | |
625 | if (_odict_EMPTY(od)) |
626 | return NULL; |
627 | hash = PyObject_Hash(key); |
628 | if (hash == -1) Branch (628:9): [True: 0, False: 154k]
|
629 | return NULL; |
630 | index = _odict_get_index(od, key, hash); |
631 | if (index < 0) Branch (631:9): [True: 0, False: 154k]
|
632 | return NULL; |
633 | assert(od->od_fast_nodes != NULL); |
634 | return od->od_fast_nodes[index]; |
635 | } |
636 | |
637 | static void |
638 | _odict_add_head(PyODictObject *od, _ODictNode *node) |
639 | { |
640 | _odictnode_PREV(node) = NULL; |
641 | _odictnode_NEXT(node) = _odict_FIRST(od); |
642 | if (_odict_FIRST(od) == NULL) Branch (642:9): [True: 0, False: 8]
|
643 | _odict_LAST(od) = node; |
644 | else |
645 | _odictnode_PREV(_odict_FIRST(od)) = node; |
646 | _odict_FIRST(od) = node; |
647 | od->od_state++; |
648 | } |
649 | |
650 | static void |
651 | _odict_add_tail(PyODictObject *od, _ODictNode *node) |
652 | { |
653 | _odictnode_PREV(node) = _odict_LAST(od); |
654 | _odictnode_NEXT(node) = NULL; |
655 | if (_odict_LAST(od) == NULL) Branch (655:9): [True: 10.2k, False: 14.9k]
|
656 | _odict_FIRST(od) = node; |
657 | else |
658 | _odictnode_NEXT(_odict_LAST(od)) = node; |
659 | _odict_LAST(od) = node; |
660 | od->od_state++; |
661 | } |
662 | |
663 | /* adds the node to the end of the list */ |
664 | static int |
665 | _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash) |
666 | { |
667 | Py_ssize_t i; |
668 | _ODictNode *node; |
669 | |
670 | Py_INCREF(key); |
671 | i = _odict_get_index(od, key, hash); |
672 | if (i < 0) { Branch (672:9): [True: 0, False: 25.3k]
|
673 | if (!PyErr_Occurred()) Branch (673:13): [True: 0, False: 0]
|
674 | PyErr_SetObject(PyExc_KeyError, key); |
675 | Py_DECREF(key); |
676 | return -1; |
677 | } |
678 | assert(od->od_fast_nodes != NULL); |
679 | if (od->od_fast_nodes[i] != NULL) { Branch (679:9): [True: 254, False: 25.1k]
|
680 | /* We already have a node for the key so there's no need to add one. */ |
681 | Py_DECREF(key); |
682 | return 0; |
683 | } |
684 | |
685 | /* must not be added yet */ |
686 | node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode)); |
687 | if (node == NULL) { Branch (687:9): [True: 0, False: 25.1k]
|
688 | Py_DECREF(key); |
689 | PyErr_NoMemory(); |
690 | return -1; |
691 | } |
692 | |
693 | _odictnode_KEY(node) = key; |
694 | _odictnode_HASH(node) = hash; |
695 | _odict_add_tail(od, node); |
696 | od->od_fast_nodes[i] = node; |
697 | return 0; |
698 | } |
699 | |
700 | /* Putting the decref after the free causes problems. */ |
701 | #define _odictnode_DEALLOC(node) \ |
702 | do { \ |
703 | Py_DECREF(_odictnode_KEY(node)); \ |
704 | PyMem_Free((void *)node); \ |
705 | } while (0) |
706 | |
707 | /* Repeated calls on the same node are no-ops. */ |
708 | static void |
709 | _odict_remove_node(PyODictObject *od, _ODictNode *node) |
710 | { |
711 | if (_odict_FIRST(od) == node) Branch (711:9): [True: 1.77k, False: 497]
|
712 | _odict_FIRST(od) = _odictnode_NEXT(node); |
713 | else if (_odictnode_PREV(node) != NULL) Branch (713:14): [True: 497, False: 0]
|
714 | _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node); |
715 | |
716 | if (_odict_LAST(od) == node) Branch (716:9): [True: 742, False: 1.52k]
|
717 | _odict_LAST(od) = _odictnode_PREV(node); |
718 | else if (_odictnode_NEXT(node) != NULL) Branch (718:14): [True: 1.52k, False: 0]
|
719 | _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node); |
720 | |
721 | _odictnode_PREV(node) = NULL; |
722 | _odictnode_NEXT(node) = NULL; |
723 | od->od_state++; |
724 | } |
725 | |
726 | /* If someone calls PyDict_DelItem() directly on an OrderedDict, we'll |
727 | get all sorts of problems here. In PyODict_DelItem we make sure to |
728 | call _odict_clear_node first. |
729 | |
730 | This matters in the case of colliding keys. Suppose we add 3 keys: |
731 | [A, B, C], where the hash of C collides with A and the next possible |
732 | index in the hash table is occupied by B. If we remove B then for C |
733 | the dict's looknode func will give us the old index of B instead of |
734 | the index we got before deleting B. However, the node for C in |
735 | od_fast_nodes is still at the old dict index of C. Thus to be sure |
736 | things don't get out of sync, we clear the node in od_fast_nodes |
737 | *before* calling PyDict_DelItem. |
738 | |
739 | The same must be done for any other OrderedDict operations where |
740 | we modify od_fast_nodes. |
741 | */ |
742 | static int |
743 | _odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key, |
744 | Py_hash_t hash) |
745 | { |
746 | Py_ssize_t i; |
747 | |
748 | assert(key != NULL); |
749 | if (_odict_EMPTY(od)) { |
750 | /* Let later code decide if this is a KeyError. */ |
751 | return 0; |
752 | } |
753 | |
754 | i = _odict_get_index(od, key, hash); |
755 | if (i < 0) Branch (755:9): [True: 0, False: 2.21k]
|
756 | return PyErr_Occurred() ? -1 : 0; Branch (756:16): [True: 0, False: 0]
|
757 | |
758 | assert(od->od_fast_nodes != NULL); |
759 | if (node == NULL) Branch (759:9): [True: 18, False: 2.20k]
|
760 | node = od->od_fast_nodes[i]; |
761 | assert(node == od->od_fast_nodes[i]); |
762 | if (node == NULL) { Branch (762:9): [True: 2, False: 2.21k]
|
763 | /* Let later code decide if this is a KeyError. */ |
764 | return 0; |
765 | } |
766 | |
767 | // Now clear the node. |
768 | od->od_fast_nodes[i] = NULL; |
769 | _odict_remove_node(od, node); |
770 | _odictnode_DEALLOC(node); |
771 | return 0; |
772 | } |
773 | |
774 | static void |
775 | _odict_clear_nodes(PyODictObject *od) |
776 | { |
777 | _ODictNode *node, *next; |
778 | |
779 | PyMem_Free(od->od_fast_nodes); |
780 | od->od_fast_nodes = NULL; |
781 | od->od_fast_nodes_size = 0; |
782 | od->od_resize_sentinel = NULL; |
783 | |
784 | node = _odict_FIRST(od); |
785 | _odict_FIRST(od) = NULL; |
786 | _odict_LAST(od) = NULL; |
787 | while (node != NULL) { Branch (787:12): [True: 22.9k, False: 10.9k]
|
788 | next = _odictnode_NEXT(node); |
789 | _odictnode_DEALLOC(node); |
790 | node = next; |
791 | } |
792 | } |
793 | |
794 | /* There isn't any memory management of nodes past this point. */ |
795 | #undef _odictnode_DEALLOC |
796 | |
797 | static int |
798 | _odict_keys_equal(PyODictObject *a, PyODictObject *b) |
799 | { |
800 | _ODictNode *node_a, *node_b; |
801 | |
802 | node_a = _odict_FIRST(a); |
803 | node_b = _odict_FIRST(b); |
804 | while (1) { Branch (804:12): [Folded - Ignored]
|
805 | if (node_a == NULL && node_b == NULL83 ) Branch (805:13): [True: 83, False: 380]
Branch (805:31): [True: 83, False: 0]
|
806 | /* success: hit the end of each at the same time */ |
807 | return 1; |
808 | else if (node_a == NULL || node_b == NULL) Branch (808:18): [True: 0, False: 380]
Branch (808:36): [True: 0, False: 380]
|
809 | /* unequal length */ |
810 | return 0; |
811 | else { |
812 | int res = PyObject_RichCompareBool( |
813 | (PyObject *)_odictnode_KEY(node_a), |
814 | (PyObject *)_odictnode_KEY(node_b), |
815 | Py_EQ); |
816 | if (res < 0) Branch (816:17): [True: 0, False: 380]
|
817 | return res; |
818 | else if (res == 0) Branch (818:22): [True: 3, False: 377]
|
819 | return 0; |
820 | |
821 | /* otherwise it must match, so move on to the next one */ |
822 | node_a = _odictnode_NEXT(node_a); |
823 | node_b = _odictnode_NEXT(node_b); |
824 | } |
825 | } |
826 | } |
827 | |
828 | |
829 | /* ---------------------------------------------- |
830 | * OrderedDict mapping methods |
831 | */ |
832 | |
833 | /* mp_ass_subscript: __setitem__() and __delitem__() */ |
834 | |
835 | static int |
836 | odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w) |
837 | { |
838 | if (w == NULL) Branch (838:9): [True: 18, False: 25.3k]
|
839 | return PyODict_DelItem((PyObject *)od, v); |
840 | else |
841 | return PyODict_SetItem((PyObject *)od, v, w); |
842 | } |
843 | |
844 | /* tp_as_mapping */ |
845 | |
846 | static PyMappingMethods odict_as_mapping = { |
847 | 0, /*mp_length*/ |
848 | 0, /*mp_subscript*/ |
849 | (objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/ |
850 | }; |
851 | |
852 | |
853 | /* ---------------------------------------------- |
854 | * OrderedDict number methods |
855 | */ |
856 | |
857 | static int mutablemapping_update_arg(PyObject*, PyObject*); |
858 | |
859 | static PyObject * |
860 | odict_or(PyObject *left, PyObject *right) |
861 | { |
862 | PyTypeObject *type; |
863 | PyObject *other; |
864 | if (PyODict_Check(left)) { |
865 | type = Py_TYPE(left); |
866 | other = right; |
867 | } |
868 | else { |
869 | type = Py_TYPE(right); |
870 | other = left; |
871 | } |
872 | if (!PyDict_Check(other)) { Branch (872:9): [True: 8, False: 14]
|
873 | Py_RETURN_NOTIMPLEMENTED; |
874 | } |
875 | PyObject *new = PyObject_CallOneArg((PyObject*)type, left); |
876 | if (!new) { Branch (876:9): [True: 0, False: 14]
|
877 | return NULL; |
878 | } |
879 | if (mutablemapping_update_arg(new, right) < 0) { Branch (879:9): [True: 0, False: 14]
|
880 | Py_DECREF(new); |
881 | return NULL; |
882 | } |
883 | return new; |
884 | } |
885 | |
886 | static PyObject * |
887 | odict_inplace_or(PyObject *self, PyObject *other) |
888 | { |
889 | if (mutablemapping_update_arg(self, other) < 0) { Branch (889:9): [True: 2, False: 10]
|
890 | return NULL; |
891 | } |
892 | Py_INCREF(self); |
893 | return self; |
894 | } |
895 | |
896 | /* tp_as_number */ |
897 | |
898 | static PyNumberMethods odict_as_number = { |
899 | .nb_or = odict_or, |
900 | .nb_inplace_or = odict_inplace_or, |
901 | }; |
902 | |
903 | |
904 | /* ---------------------------------------------- |
905 | * OrderedDict methods |
906 | */ |
907 | |
908 | /* fromkeys() */ |
909 | |
910 | /*[clinic input] |
911 | @classmethod |
912 | OrderedDict.fromkeys |
913 | |
914 | iterable as seq: object |
915 | value: object = None |
916 | |
917 | Create a new ordered dictionary with keys from iterable and values set to value. |
918 | [clinic start generated code]*/ |
919 | |
920 | static PyObject * |
921 | OrderedDict_fromkeys_impl(PyTypeObject *type, PyObject *seq, PyObject *value) |
922 | /*[clinic end generated code: output=c10390d452d78d6d input=1a0476c229c597b3]*/ |
923 | { |
924 | return _PyDict_FromKeys((PyObject *)type, seq, value); |
925 | } |
926 | |
927 | /* __sizeof__() */ |
928 | |
929 | /* OrderedDict.__sizeof__() does not have a docstring. */ |
930 | PyDoc_STRVAR(odict_sizeof__doc__, ""); |
931 | |
932 | static PyObject * |
933 | odict_sizeof(PyODictObject *od, PyObject *Py_UNUSED(ignored)) |
934 | { |
935 | Py_ssize_t res = _PyDict_SizeOf((PyDictObject *)od); |
936 | res += sizeof(_ODictNode *) * od->od_fast_nodes_size; /* od_fast_nodes */ |
937 | if (!_odict_EMPTY(od)) { Branch (937:9): [True: 8, False: 4]
|
938 | res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */ |
939 | } |
940 | return PyLong_FromSsize_t(res); |
941 | } |
942 | |
943 | /* __reduce__() */ |
944 | |
945 | PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling"); |
946 | |
947 | static PyObject * |
948 | odict_reduce(register PyODictObject *od, PyObject *Py_UNUSED(ignored)) |
949 | { |
950 | PyObject *state, *result = NULL; |
951 | PyObject *items_iter, *items, *args = NULL; |
952 | |
953 | /* capture any instance state */ |
954 | state = _PyObject_GetState((PyObject *)od); |
955 | if (state == NULL) Branch (955:9): [True: 0, False: 44]
|
956 | goto Done; |
957 | |
958 | /* build the result */ |
959 | args = PyTuple_New(0); |
960 | if (args == NULL) Branch (960:9): [True: 0, False: 44]
|
961 | goto Done; |
962 | |
963 | items = PyObject_CallMethodNoArgs((PyObject *)od, &_Py_ID(items)); |
964 | if (items == NULL) Branch (964:9): [True: 0, False: 44]
|
965 | goto Done; |
966 | |
967 | items_iter = PyObject_GetIter(items); |
968 | Py_DECREF(items); |
969 | if (items_iter == NULL) Branch (969:9): [True: 0, False: 44]
|
970 | goto Done; |
971 | |
972 | result = PyTuple_Pack(5, Py_TYPE(od), args, state, Py_None, items_iter); |
973 | Py_DECREF(items_iter); |
974 | |
975 | Done: |
976 | Py_XDECREF(state); |
977 | Py_XDECREF(args); |
978 | |
979 | 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 | OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key, |
998 | PyObject *default_value) |
999 | /*[clinic end generated code: output=97537cb7c28464b6 input=38e098381c1efbc6]*/ |
1000 | { |
1001 | PyObject *result = NULL; |
1002 | |
1003 | if (PyODict_CheckExact(self)) { |
1004 | result = PyODict_GetItemWithError(self, key); /* borrowed */ |
1005 | if (result == NULL) { Branch (1005:13): [True: 3, False: 2]
|
1006 | if (PyErr_Occurred()) Branch (1006:17): [True: 0, False: 3]
|
1007 | return NULL; |
1008 | assert(_odict_find_node(self, key) == NULL); |
1009 | if (PyODict_SetItem((PyObject *)self, key, default_value) >= 0) { Branch (1009:17): [True: 3, False: 0]
|
1010 | result = default_value; |
1011 | Py_INCREF(result); |
1012 | } |
1013 | } |
1014 | else { |
1015 | Py_INCREF(result); |
1016 | } |
1017 | } |
1018 | else { |
1019 | int exists = PySequence_Contains((PyObject *)self, key); |
1020 | if (exists < 0) { Branch (1020:13): [True: 0, False: 7]
|
1021 | return NULL; |
1022 | } |
1023 | else if (exists) { Branch (1023:18): [True: 2, False: 5]
|
1024 | result = PyObject_GetItem((PyObject *)self, key); |
1025 | } |
1026 | else if (PyObject_SetItem((PyObject *)self, key, default_value) >= 0) { Branch (1026:18): [True: 5, False: 0]
|
1027 | result = default_value; |
1028 | Py_INCREF(result); |
1029 | } |
1030 | } |
1031 | |
1032 | return result; |
1033 | } |
1034 | |
1035 | /* pop() */ |
1036 | |
1037 | static PyObject * |
1038 | _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj, |
1039 | Py_hash_t hash) |
1040 | { |
1041 | PyObject *value = NULL; |
1042 | |
1043 | _ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash); |
1044 | if (node != NULL) { Branch (1044:9): [True: 2.20k, False: 268]
|
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 | int res = _odict_clear_node((PyODictObject *)od, node, key, hash); |
1049 | if (res < 0) { Branch (1049:13): [True: 0, False: 2.20k]
|
1050 | return NULL; |
1051 | } |
1052 | /* Now delete the value from the dict. */ |
1053 | value = _PyDict_Pop_KnownHash(od, key, hash, failobj); |
1054 | } |
1055 | else if (value == NULL && !PyErr_Occurred()) { Branch (1055:14): [True: 268, False: 0]
Branch (1055:31): [True: 268, False: 0]
|
1056 | /* Apply the fallback value, if necessary. */ |
1057 | if (failobj) { Branch (1057:13): [True: 257, False: 11]
|
1058 | value = failobj; |
1059 | Py_INCREF(failobj); |
1060 | } |
1061 | else { |
1062 | PyErr_SetObject(PyExc_KeyError, key); |
1063 | } |
1064 | } |
1065 | |
1066 | 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 | OrderedDict_pop_impl(PyODictObject *self, PyObject *key, |
1084 | PyObject *default_value) |
1085 | /*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/ |
1086 | { |
1087 | Py_hash_t hash = PyObject_Hash(key); |
1088 | if (hash == -1) Branch (1088:9): [True: 0, False: 1.88k]
|
1089 | return NULL; |
1090 | 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 | OrderedDict_popitem_impl(PyODictObject *self, int last) |
1108 | /*[clinic end generated code: output=98e7d986690d49eb input=d992ac5ee8305e1a]*/ |
1109 | { |
1110 | PyObject *key, *value, *item = NULL; |
1111 | _ODictNode *node; |
1112 | |
1113 | /* pull the item */ |
1114 | |
1115 | if (_odict_EMPTY(self)) { |
1116 | PyErr_SetString(PyExc_KeyError, "dictionary is empty"); |
1117 | return NULL; |
1118 | } |
1119 | |
1120 | node = last ? _odict_LAST37 (self) : _odict_FIRST546 (self); Branch (1120:12): [True: 37, False: 546]
|
1121 | key = _odictnode_KEY(node); |
1122 | Py_INCREF(key); |
1123 | value = _odict_popkey_hash((PyObject *)self, key, NULL, _odictnode_HASH(node)); |
1124 | if (value == NULL) Branch (1124:9): [True: 0, False: 583]
|
1125 | return NULL; |
1126 | item = PyTuple_Pack(2, key, value); |
1127 | Py_DECREF(key); |
1128 | Py_DECREF(value); |
1129 | 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 | odict_clear(register PyODictObject *od, PyObject *Py_UNUSED(ignored)) |
1170 | { |
1171 | PyDict_Clear((PyObject *)od); |
1172 | _odict_clear_nodes(od); |
1173 | 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 | odict_copy(register PyODictObject *od, PyObject *Py_UNUSED(ignored)) |
1186 | { |
1187 | _ODictNode *node; |
1188 | PyObject *od_copy; |
1189 | |
1190 | if (PyODict_CheckExact(od)) |
1191 | od_copy = PyODict_New(); |
1192 | else |
1193 | od_copy = _PyObject_CallNoArgs((PyObject *)Py_TYPE(od)); |
1194 | if (od_copy == NULL) Branch (1194:9): [True: 0, False: 21]
|
1195 | return NULL; |
1196 | |
1197 | if (PyODict_CheckExact(od)) { |
1198 | _odict_FOREACH14 (od, node) { |
1199 | PyObject *key = _odictnode_KEY(node); |
1200 | PyObject *value = _odictnode_VALUE(node, od); |
1201 | if (value == NULL) { Branch (1201:17): [True: 1, False: 67]
|
1202 | if (!PyErr_Occurred()) Branch (1202:21): [True: 1, False: 0]
|
1203 | PyErr_SetObject(PyExc_KeyError, key); |
1204 | goto fail; |
1205 | } |
1206 | if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value, Branch (1206:17): [True: 0, False: 67]
|
1207 | _odictnode_HASH(node)) != 0) |
1208 | goto fail; |
1209 | } |
1210 | } |
1211 | else { |
1212 | _odict_FOREACH7 (od, node) { |
1213 | int res; |
1214 | PyObject *value = PyObject_GetItem((PyObject *)od, |
1215 | _odictnode_KEY(node)); |
1216 | if (value == NULL) Branch (1216:17): [True: 1, False: 24]
|
1217 | goto fail; |
1218 | res = PyObject_SetItem((PyObject *)od_copy, |
1219 | _odictnode_KEY(node), value); |
1220 | Py_DECREF(value); |
1221 | if (res != 0) Branch (1221:17): [True: 0, False: 24]
|
1222 | goto fail; |
1223 | } |
1224 | } |
1225 | return od_copy; |
1226 | |
1227 | fail: |
1228 | Py_DECREF(od_copy); |
1229 | 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 | odict_reversed(PyODictObject *od, PyObject *Py_UNUSED(ignored)) |
1246 | { |
1247 | 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 | 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 | if (_odict_EMPTY(self)) { |
1271 | PyErr_SetObject(PyExc_KeyError, key); |
1272 | return NULL; |
1273 | } |
1274 | node = last ? _odict_LAST66 (self) : _odict_FIRST12 (self); Branch (1274:12): [True: 66, False: 12]
|
1275 | if (key != _odictnode_KEY(node)) { Branch (1275:9): [True: 61, False: 17]
|
1276 | node = _odict_find_node(self, key); |
1277 | if (node == NULL) { Branch (1277:13): [True: 4, False: 57]
|
1278 | if (!PyErr_Occurred()) Branch (1278:17): [True: 4, False: 0]
|
1279 | PyErr_SetObject(PyExc_KeyError, key); |
1280 | return NULL; |
1281 | } |
1282 | if (last) { Branch (1282:13): [True: 47, False: 10]
|
1283 | /* Only move if not already the last one. */ |
1284 | if (node != _odict_LAST(self)) { Branch (1284:17): [True: 45, False: 2]
|
1285 | _odict_remove_node(self, node); |
1286 | _odict_add_tail(self, node); |
1287 | } |
1288 | } |
1289 | else { |
1290 | /* Only move if not already the first one. */ |
1291 | if (node != _odict_FIRST(self)) { Branch (1291:17): [True: 8, False: 2]
|
1292 | _odict_remove_node(self, node); |
1293 | _odict_add_head(self, node); |
1294 | } |
1295 | } |
1296 | } |
1297 | Py_RETURN_NONE74 ; |
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 | odict_dealloc(PyODictObject *self) |
1355 | { |
1356 | PyObject_GC_UnTrack(self); |
1357 | Py_TRASHCAN_BEGIN(self, odict_dealloc) |
1358 | |
1359 | Py_XDECREF(self->od_inst_dict); |
1360 | if (self->od_weakreflist != NULL) Branch (1360:9): [True: 0, False: 10.8k]
|
1361 | PyObject_ClearWeakRefs((PyObject *)self); |
1362 | |
1363 | _odict_clear_nodes(self); |
1364 | PyDict_Type.tp_dealloc((PyObject *)self); |
1365 | |
1366 | Py_TRASHCAN_END |
1367 | } |
1368 | |
1369 | /* tp_repr */ |
1370 | |
1371 | static PyObject * |
1372 | odict_repr(PyODictObject *self) |
1373 | { |
1374 | int i; |
1375 | PyObject *pieces = NULL, *result = NULL; |
1376 | |
1377 | if (PyODict_SIZE(self) == 0) Branch (1377:9): [True: 17, False: 116]
|
1378 | return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self))); |
1379 | |
1380 | i = Py_ReprEnter((PyObject *)self); |
1381 | if (i != 0) { Branch (1381:9): [True: 2, False: 114]
|
1382 | return i > 0 ? PyUnicode_FromString("...") : NULL; Branch (1382:16): [True: 2, False: 0]
|
1383 | } |
1384 | |
1385 | if (PyODict_CheckExact(self)) { |
1386 | Py_ssize_t count = 0; |
1387 | _ODictNode *node; |
1388 | pieces = PyList_New(PyODict_SIZE(self)); |
1389 | if (pieces == NULL) Branch (1389:13): [True: 0, False: 52]
|
1390 | goto Done; |
1391 | |
1392 | _odict_FOREACH52 (self, node)52 { |
1393 | PyObject *pair; |
1394 | PyObject *key = _odictnode_KEY(node); |
1395 | PyObject *value = _odictnode_VALUE(node, self); |
1396 | if (value == NULL) { Branch (1396:17): [True: 4, False: 304]
|
1397 | if (!PyErr_Occurred()) Branch (1397:21): [True: 4, False: 0]
|
1398 | PyErr_SetObject(PyExc_KeyError, key); |
1399 | goto Done; |
1400 | } |
1401 | pair = PyTuple_Pack(2, key, value); |
1402 | if (pair == NULL) Branch (1402:17): [True: 0, False: 304]
|
1403 | goto Done; |
1404 | |
1405 | if (count < PyList_GET_SIZE(pieces)) Branch (1405:17): [True: 304, False: 0]
|
1406 | PyList_SET_ITEM(pieces, count, pair); /* steals reference */ |
1407 | else { |
1408 | if (PyList_Append(pieces, pair) < 0) { Branch (1408:21): [True: 0, False: 0]
|
1409 | Py_DECREF(pair); |
1410 | goto Done; |
1411 | } |
1412 | Py_DECREF(pair); |
1413 | } |
1414 | count++; |
1415 | } |
1416 | if (count < PyList_GET_SIZE(pieces)) { Branch (1416:13): [True: 3, False: 45]
|
1417 | Py_SET_SIZE(pieces, count); |
1418 | } |
1419 | } |
1420 | else { |
1421 | PyObject *items = PyObject_CallMethodNoArgs( |
1422 | (PyObject *)self, &_Py_ID(items)); |
1423 | if (items == NULL) Branch (1423:13): [True: 0, False: 62]
|
1424 | goto Done; |
1425 | pieces = PySequence_List(items); |
1426 | Py_DECREF(items); |
1427 | if (pieces == NULL) Branch (1427:13): [True: 4, False: 58]
|
1428 | goto Done; |
1429 | } |
1430 | |
1431 | result = PyUnicode_FromFormat("%s(%R)", |
1432 | _PyType_Name(Py_TYPE(self)), pieces); |
1433 | |
1434 | Done: |
1435 | Py_XDECREF(pieces); |
1436 | Py_ReprLeave((PyObject *)self); |
1437 | 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 | odict_traverse(PyODictObject *od, visitproc visit, void *arg) |
1449 | { |
1450 | _ODictNode *node; |
1451 | |
1452 | Py_VISIT(od->od_inst_dict); |
1453 | _odict_FOREACH370k (od, node)370k { |
1454 | Py_VISIT(_odictnode_KEY(node)); |
1455 | } |
1456 | return PyDict_Type.tp_traverse((PyObject *)od, visit, arg); |
1457 | } |
1458 | |
1459 | /* tp_clear */ |
1460 | |
1461 | static int |
1462 | odict_tp_clear(PyODictObject *od) |
1463 | { |
1464 | Py_CLEAR(od->od_inst_dict); |
1465 | PyDict_Clear((PyObject *)od); |
1466 | _odict_clear_nodes(od); |
1467 | return 0; |
1468 | } |
1469 | |
1470 | /* tp_richcompare */ |
1471 | |
1472 | static PyObject * |
1473 | odict_richcompare(PyObject *v, PyObject *w, int op) |
1474 | { |
1475 | if (!PyODict_Check(v) || !PyDict_Check(w)) { Branch (1475:9): [True: 0, False: 114]
Branch (1475:30): [True: 1, False: 113]
|
1476 | Py_RETURN_NOTIMPLEMENTED; |
1477 | } |
1478 | |
1479 | if (op == Py_EQ || op == 9 Py_NE9 ) { Branch (1479:9): [True: 104, False: 9]
Branch (1479:24): [True: 9, False: 0]
|
1480 | PyObject *res, *cmp; |
1481 | int eq; |
1482 | |
1483 | cmp = PyDict_Type.tp_richcompare(v, w, op); |
1484 | if (cmp == NULL) Branch (1484:13): [True: 0, False: 113]
|
1485 | return NULL; |
1486 | if (!PyODict_Check(w)) Branch (1486:13): [True: 21, False: 92]
|
1487 | return cmp; |
1488 | if (op == Py_EQ && cmp == 83 Py_False83 ) Branch (1488:13): [True: 83, False: 9]
Branch (1488:28): [True: 0, False: 83]
|
1489 | return cmp; |
1490 | if (op == Py_NE && cmp == 9 Py_True9 ) Branch (1490:13): [True: 9, False: 83]
Branch (1490:28): [True: 6, False: 3]
|
1491 | return cmp; |
1492 | Py_DECREF(cmp); |
1493 | |
1494 | /* Try comparing odict keys. */ |
1495 | eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w); |
1496 | if (eq < 0) Branch (1496:13): [True: 0, False: 86]
|
1497 | return NULL; |
1498 | |
1499 | res = (eq == (op == Py_EQ)) ? Py_True : Py_False; Branch (1499:15): [True: 86, False: 0]
|
1500 | Py_INCREF(res); |
1501 | return res; |
1502 | } else { |
1503 | Py_RETURN_NOTIMPLEMENTED; |
1504 | } |
1505 | } |
1506 | |
1507 | /* tp_iter */ |
1508 | |
1509 | static PyObject * |
1510 | odict_iter(PyODictObject *od) |
1511 | { |
1512 | return odictiter_new(od, _odict_ITER_KEYS); |
1513 | } |
1514 | |
1515 | /* tp_init */ |
1516 | |
1517 | static int |
1518 | odict_init(PyObject *self, PyObject *args, PyObject *kwds) |
1519 | { |
1520 | PyObject *res; |
1521 | Py_ssize_t len = PyObject_Length(args); |
1522 | |
1523 | if (len == -1) Branch (1523:9): [True: 0, False: 10.8k]
|
1524 | return -1; |
1525 | if (len > 1) { Branch (1525:9): [True: 6, False: 10.8k]
|
1526 | const char *msg = "expected at most 1 arguments, got %zd"; |
1527 | PyErr_Format(PyExc_TypeError, msg, len); |
1528 | return -1; |
1529 | } |
1530 | |
1531 | /* __init__() triggering update() is just the way things are! */ |
1532 | res = odict_update(self, args, kwds); |
1533 | if (res == NULL) { Branch (1533:9): [True: 2, False: 10.8k]
|
1534 | return -1; |
1535 | } else { |
1536 | Py_DECREF(res); |
1537 | 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 | PyODict_New(void) |
1592 | { |
1593 | return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL); |
1594 | } |
1595 | |
1596 | static int |
1597 | _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value, |
1598 | Py_hash_t hash) |
1599 | { |
1600 | int res = _PyDict_SetItem_KnownHash(od, key, value, hash); |
1601 | if (res == 0) { Branch (1601:9): [True: 25.3k, False: 0]
|
1602 | res = _odict_add_new_node((PyODictObject *)od, key, hash); |
1603 | if (res < 0) { Branch (1603:13): [True: 0, False: 25.3k]
|
1604 | /* Revert setting the value on the dict */ |
1605 | PyObject *exc, *val, *tb; |
1606 | PyErr_Fetch(&exc, &val, &tb); |
1607 | (void) _PyDict_DelItem_KnownHash(od, key, hash); |
1608 | _PyErr_ChainExceptions(exc, val, tb); |
1609 | } |
1610 | } |
1611 | return res; |
1612 | } |
1613 | |
1614 | int |
1615 | PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) |
1616 | { |
1617 | Py_hash_t hash = PyObject_Hash(key); |
1618 | if (hash == -1) Branch (1618:9): [True: 0, False: 25.3k]
|
1619 | return -1; |
1620 | return _PyODict_SetItem_KnownHash(od, key, value, hash); |
1621 | } |
1622 | |
1623 | int |
1624 | PyODict_DelItem(PyObject *od, PyObject *key) |
1625 | { |
1626 | int res; |
1627 | Py_hash_t hash = PyObject_Hash(key); |
1628 | if (hash == -1) Branch (1628:9): [True: 0, False: 18]
|
1629 | return -1; |
1630 | res = _odict_clear_node((PyODictObject *)od, NULL, key, hash); |
1631 | if (res < 0) Branch (1631:9): [True: 0, False: 18]
|
1632 | return -1; |
1633 | 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 | odictiter_dealloc(odictiterobject *di) |
1653 | { |
1654 | _PyObject_GC_UNTRACK(di); |
1655 | Py_XDECREF(di->di_odict); |
1656 | Py_XDECREF(di->di_current); |
1657 | if ((di->kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) { Branch (1657:9): [True: 4.64k, False: 17.5k]
|
1658 | Py_DECREF(di->di_result); |
1659 | } |
1660 | PyObject_GC_Del(di); |
1661 | } |
1662 | |
1663 | static int |
1664 | odictiter_traverse(odictiterobject *di, visitproc visit, void *arg) |
1665 | { |
1666 | Py_VISIT(di->di_odict); |
1667 | Py_VISIT(di->di_current); /* A key could be any type, not just str. */ |
1668 | Py_VISIT(di->di_result); |
1669 | 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 | odictiter_nextkey(odictiterobject *di) |
1676 | { |
1677 | PyObject *key = NULL; |
1678 | _ODictNode *node; |
1679 | int reversed = di->kind & _odict_ITER_REVERSED; |
1680 | |
1681 | if (di->di_odict == NULL) Branch (1681:9): [True: 618, False: 176k]
|
1682 | return NULL; |
1683 | if (di->di_current == NULL) Branch (1683:9): [True: 21.9k, False: 154k]
|
1684 | goto done; /* We're already done. */ |
1685 | |
1686 | /* Check for unsupported changes. */ |
1687 | if (di->di_odict->od_state != di->di_state) { Branch (1687:9): [True: 8, False: 154k]
|
1688 | PyErr_SetString(PyExc_RuntimeError, |
1689 | "OrderedDict mutated during iteration"); |
1690 | goto done; |
1691 | } |
1692 | if (di->di_size != PyODict_SIZE(di->di_odict)) { Branch (1692:9): [True: 0, False: 154k]
|
1693 | PyErr_SetString(PyExc_RuntimeError, |
1694 | "OrderedDict changed size during iteration"); |
1695 | di->di_size = -1; /* Make this state sticky */ |
1696 | return NULL; |
1697 | } |
1698 | |
1699 | /* Get the key. */ |
1700 | node = _odict_find_node(di->di_odict, di->di_current); |
1701 | if (node == NULL) { Branch (1701:9): [True: 7, False: 154k]
|
1702 | if (!PyErr_Occurred()) Branch (1702:13): [True: 7, False: 0]
|
1703 | PyErr_SetObject(PyExc_KeyError, di->di_current); |
1704 | /* Must have been deleted. */ |
1705 | Py_CLEAR(di->di_current); |
1706 | return NULL; |
1707 | } |
1708 | key = di->di_current; |
1709 | |
1710 | /* Advance to the next key. */ |
1711 | node = reversed ? _odictnode_PREV58 (node) : _odictnode_NEXT154k (node); Branch (1711:12): [True: 58, False: 154k]
|
1712 | if (node == NULL) { Branch (1712:9): [True: 21.2k, False: 133k]
|
1713 | /* Reached the end. */ |
1714 | di->di_current = NULL; |
1715 | } |
1716 | else { |
1717 | di->di_current = _odictnode_KEY(node); |
1718 | Py_INCREF(di->di_current); |
1719 | } |
1720 | |
1721 | return key; |
1722 | |
1723 | done: |
1724 | Py_CLEAR(di->di_odict); |
1725 | return key; |
1726 | } |
1727 | |
1728 | static PyObject * |
1729 | odictiter_iternext(odictiterobject *di) |
1730 | { |
1731 | PyObject *result, *value; |
1732 | PyObject *key = odictiter_nextkey(di); /* new reference */ |
1733 | |
1734 | if (key == NULL) Branch (1734:9): [True: 22.5k, False: 154k]
|
1735 | return NULL; |
1736 | |
1737 | /* Handle the keys case. */ |
1738 | if (! (di->kind & _odict_ITER_VALUES)) { Branch (1738:9): [True: 2.70k, False: 151k]
|
1739 | return key; |
1740 | } |
1741 | |
1742 | value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */ |
1743 | if (value == NULL) { Branch (1743:9): [True: 1, False: 151k]
|
1744 | if (!PyErr_Occurred()) Branch (1744:13): [True: 1, False: 0]
|
1745 | PyErr_SetObject(PyExc_KeyError, key); |
1746 | Py_DECREF(key); |
1747 | goto done; |
1748 | } |
1749 | Py_INCREF(value); |
1750 | |
1751 | /* Handle the values case. */ |
1752 | if (!(di->kind & _odict_ITER_KEYS)) { Branch (1752:9): [True: 138k, False: 12.8k]
|
1753 | Py_DECREF(key); |
1754 | return value; |
1755 | } |
1756 | |
1757 | /* Handle the items case. */ |
1758 | result = di->di_result; |
1759 | |
1760 | if (Py_REFCNT(result) == 1) { Branch (1760:9): [True: 11.7k, False: 1.11k]
|
1761 | /* not in use so we can reuse it |
1762 | * (the common case during iteration) */ |
1763 | Py_INCREF(result); |
1764 | Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */ |
1765 | 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 | if (!_PyObject_GC_IS_TRACKED(result)) { Branch (1768:13): [True: 2, False: 11.7k]
|
1769 | _PyObject_GC_TRACK(result); |
1770 | } |
1771 | } |
1772 | else { |
1773 | result = PyTuple_New(2); |
1774 | if (result == NULL) { Branch (1774:13): [True: 0, False: 1.11k]
|
1775 | Py_DECREF(key); |
1776 | Py_DECREF(value); |
1777 | goto done; |
1778 | } |
1779 | } |
1780 | |
1781 | PyTuple_SET_ITEM(result, 0, key); /* steals reference */ |
1782 | PyTuple_SET_ITEM(result, 1, value); /* steals reference */ |
1783 | return result; |
1784 | |
1785 | done: |
1786 | Py_CLEAR(di->di_current); |
1787 | Py_CLEAR(di->di_odict); |
1788 | 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 | odictiter_reduce(odictiterobject *di, PyObject *Py_UNUSED(ignored)) |
1797 | { |
1798 | /* copy the iterator state */ |
1799 | odictiterobject tmp = *di; |
1800 | Py_XINCREF(tmp.di_odict); |
1801 | Py_XINCREF(tmp.di_current); |
1802 | |
1803 | /* iterate the temporary into a list */ |
1804 | PyObject *list = PySequence_List((PyObject*)&tmp); |
1805 | Py_XDECREF(tmp.di_odict); |
1806 | Py_XDECREF(tmp.di_current); |
1807 | if (list == NULL) { Branch (1807:9): [True: 0, False: 36]
|
1808 | return NULL; |
1809 | } |
1810 | 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 | odictiter_new(PyODictObject *od, int kind) |
1853 | { |
1854 | odictiterobject *di; |
1855 | _ODictNode *node; |
1856 | int reversed = kind & _odict_ITER_REVERSED; |
1857 | |
1858 | di = PyObject_GC_New(odictiterobject, &PyODictIter_Type); |
1859 | if (di == NULL) Branch (1859:9): [True: 0, False: 22.2k]
|
1860 | return NULL; |
1861 | |
1862 | if ((kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) { Branch (1862:9): [True: 4.64k, False: 17.5k]
|
1863 | di->di_result = PyTuple_Pack(2, Py_None, Py_None); |
1864 | if (di->di_result == NULL) { Branch (1864:13): [True: 0, False: 4.64k]
|
1865 | Py_DECREF(di); |
1866 | return NULL; |
1867 | } |
1868 | } |
1869 | else { |
1870 | di->di_result = NULL; |
1871 | } |
1872 | |
1873 | di->kind = kind; |
1874 | node = reversed ? _odict_LAST18 (od) : _odict_FIRST22.2k (od); Branch (1874:12): [True: 18, False: 22.2k]
|
1875 | di->di_current = node ? _odictnode_KEY21.4k (node) : NULL; Branch (1875:22): [True: 21.4k, False: 827]
|
1876 | Py_XINCREF(di->di_current); |
1877 | di->di_size = PyODict_SIZE(od); |
1878 | di->di_state = od->od_state; |
1879 | di->di_odict = od; |
1880 | Py_INCREF(od); |
1881 | |
1882 | _PyObject_GC_TRACK(di); |
1883 | return (PyObject *)di; |
1884 | } |
1885 | |
1886 | /* keys() */ |
1887 | |
1888 | static PyObject * |
1889 | odictkeys_iter(_PyDictViewObject *dv) |
1890 | { |
1891 | if (dv->dv_dict == NULL) { Branch (1891:9): [True: 0, False: 390]
|
1892 | Py_RETURN_NONE; |
1893 | } |
1894 | return odictiter_new((PyODictObject *)dv->dv_dict, |
1895 | _odict_ITER_KEYS); |
1896 | } |
1897 | |
1898 | static PyObject * |
1899 | odictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
1900 | { |
1901 | if (dv->dv_dict == NULL) { Branch (1901:9): [True: 0, False: 4]
|
1902 | Py_RETURN_NONE; |
1903 | } |
1904 | 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 | odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored)) |
1949 | { |
1950 | return _PyDictView_New(od, &PyODictKeys_Type); |
1951 | } |
1952 | |
1953 | /* items() */ |
1954 | |
1955 | static PyObject * |
1956 | odictitems_iter(_PyDictViewObject *dv) |
1957 | { |
1958 | if (dv->dv_dict == NULL) { Branch (1958:9): [True: 0, False: 4.64k]
|
1959 | Py_RETURN_NONE; |
1960 | } |
1961 | return odictiter_new((PyODictObject *)dv->dv_dict, |
1962 | _odict_ITER_KEYS|_odict_ITER_VALUES); |
1963 | } |
1964 | |
1965 | static PyObject * |
1966 | odictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
1967 | { |
1968 | if (dv->dv_dict == NULL) { Branch (1968:9): [True: 0, False: 4]
|
1969 | Py_RETURN_NONE; |
1970 | } |
1971 | 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 | odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored)) |
2016 | { |
2017 | return _PyDictView_New(od, &PyODictItems_Type); |
2018 | } |
2019 | |
2020 | /* values() */ |
2021 | |
2022 | static PyObject * |
2023 | odictvalues_iter(_PyDictViewObject *dv) |
2024 | { |
2025 | if (dv->dv_dict == NULL) { Branch (2025:9): [True: 0, False: 16.7k]
|
2026 | Py_RETURN_NONE; |
2027 | } |
2028 | return odictiter_new((PyODictObject *)dv->dv_dict, |
2029 | _odict_ITER_VALUES); |
2030 | } |
2031 | |
2032 | static PyObject * |
2033 | odictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
2034 | { |
2035 | if (dv->dv_dict == NULL) { Branch (2035:9): [True: 0, False: 4]
|
2036 | Py_RETURN_NONE; |
2037 | } |
2038 | 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 | odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored)) |
2083 | { |
2084 | 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 | mutablemapping_add_pairs(PyObject *self, PyObject *pairs) |
2133 | { |
2134 | PyObject *pair, *iterator, *unexpected; |
2135 | int res = 0; |
2136 | |
2137 | iterator = PyObject_GetIter(pairs); |
2138 | if (iterator == NULL) Branch (2138:9): [True: 8, False: 6.67k]
|
2139 | return -1; |
2140 | PyErr_Clear(); |
2141 | |
2142 | while ((pair = PyIter_Next(iterator)) != NULL) { Branch (2142:12): [True: 15.0k, False: 6.66k]
|
2143 | /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */ |
2144 | PyObject *key = NULL, *value = NULL; |
2145 | PyObject *pair_iterator = PyObject_GetIter(pair); |
2146 | if (pair_iterator == NULL) Branch (2146:13): [True: 0, False: 15.0k]
|
2147 | goto Done; |
2148 | |
2149 | key = PyIter_Next(pair_iterator); |
2150 | if (key == NULL) { Branch (2150:13): [True: 0, False: 15.0k]
|
2151 | if (!PyErr_Occurred()) Branch (2151:17): [True: 0, False: 0]
|
2152 | PyErr_SetString(PyExc_ValueError, |
2153 | "need more than 0 values to unpack"); |
2154 | goto Done; |
2155 | } |
2156 | |
2157 | value = PyIter_Next(pair_iterator); |
2158 | if (value == NULL) { Branch (2158:13): [True: 2, False: 15.0k]
|
2159 | if (!PyErr_Occurred()) Branch (2159:17): [True: 2, False: 0]
|
2160 | PyErr_SetString(PyExc_ValueError, |
2161 | "need more than 1 value to unpack"); |
2162 | goto Done; |
2163 | } |
2164 | |
2165 | unexpected = PyIter_Next(pair_iterator); |
2166 | if (unexpected != NULL) { Branch (2166:13): [True: 2, False: 15.0k]
|
2167 | Py_DECREF(unexpected); |
2168 | PyErr_SetString(PyExc_ValueError, |
2169 | "too many values to unpack (expected 2)"); |
2170 | goto Done; |
2171 | } |
2172 | else if (PyErr_Occurred()) Branch (2172:18): [True: 0, False: 15.0k]
|
2173 | goto Done; |
2174 | |
2175 | res = PyObject_SetItem(self, key, value); |
2176 | |
2177 | Done: |
2178 | Py_DECREF(pair); |
2179 | Py_XDECREF(pair_iterator); |
2180 | Py_XDECREF(key); |
2181 | Py_XDECREF(value); |
2182 | if (PyErr_Occurred()) Branch (2182:13): [True: 4, False: 15.0k]
|
2183 | break; |
2184 | } |
2185 | Py_DECREF(iterator); |
2186 | |
2187 | if (res < 0 || PyErr_Occurred() != NULL) Branch (2187:9): [True: 0, False: 6.67k]
Branch (2187:20): [True: 6, False: 6.66k]
|
2188 | return -1; |
2189 | else |
2190 | return 0; |
2191 | } |
2192 | |
2193 | static int |
2194 | mutablemapping_update_arg(PyObject *self, PyObject *arg) |
2195 | { |
2196 | int res = 0; |
2197 | if (PyDict_CheckExact(arg)) { |
2198 | PyObject *items = PyDict_Items(arg); |
2199 | if (items == NULL) { Branch (2199:13): [True: 0, False: 29]
|
2200 | return -1; |
2201 | } |
2202 | res = mutablemapping_add_pairs(self, items); |
2203 | Py_DECREF(items); |
2204 | return res; |
2205 | } |
2206 | PyObject *func; |
2207 | if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) { Branch (2207:9): [True: 0, False: 6.66k]
|
2208 | return -1; |
2209 | } |
2210 | if (func != NULL) { Branch (2210:9): [True: 46, False: 6.61k]
|
2211 | PyObject *keys = _PyObject_CallNoArgs(func); |
2212 | Py_DECREF(func); |
2213 | if (keys == NULL) { Branch (2213:13): [True: 2, False: 44]
|
2214 | return -1; |
2215 | } |
2216 | PyObject *iterator = PyObject_GetIter(keys); |
2217 | Py_DECREF(keys); |
2218 | if (iterator == NULL) { Branch (2218:13): [True: 0, False: 44]
|
2219 | return -1; |
2220 | } |
2221 | PyObject *key; |
2222 | while (res == 0 && (key = PyIter_Next(iterator))196 ) { Branch (2222:16): [True: 196, False: 2]
Branch (2222:28): [True: 154, False: 42]
|
2223 | PyObject *value = PyObject_GetItem(arg, key); |
2224 | if (value != NULL) { Branch (2224:17): [True: 152, False: 2]
|
2225 | res = PyObject_SetItem(self, key, value); |
2226 | Py_DECREF(value); |
2227 | } |
2228 | else { |
2229 | res = -1; |
2230 | } |
2231 | Py_DECREF(key); |
2232 | } |
2233 | Py_DECREF(iterator); |
2234 | if (res != 0 || PyErr_Occurred()42 ) { Branch (2234:13): [True: 2, False: 42]
Branch (2234:25): [True: 2, False: 40]
|
2235 | return -1; |
2236 | } |
2237 | return 0; |
2238 | } |
2239 | if (_PyObject_LookupAttr(arg, &_Py_ID(items), &func) < 0) { Branch (2239:9): [True: 0, False: 6.61k]
|
2240 | return -1; |
2241 | } |
2242 | if (func != NULL) { Branch (2242:9): [True: 0, False: 6.61k]
|
2243 | PyObject *items = _PyObject_CallNoArgs(func); |
2244 | Py_DECREF(func); |
2245 | if (items == NULL) { Branch (2245:13): [True: 0, False: 0]
|
2246 | return -1; |
2247 | } |
2248 | res = mutablemapping_add_pairs(self, items); |
2249 | Py_DECREF(items); |
2250 | return res; |
2251 | } |
2252 | res = mutablemapping_add_pairs(self, arg); |
2253 | return res; |
2254 | } |
2255 | |
2256 | static PyObject * |
2257 | 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 | Py_ssize_t len = (args != NULL) ? PyTuple_GET_SIZE(args) : 00 ; Branch (2262:22): [True: 10.9k, False: 0]
|
2263 | if (len > 1) { Branch (2263:9): [True: 6, False: 10.9k]
|
2264 | const char *msg = "update() takes at most 1 positional argument (%zd given)"; |
2265 | PyErr_Format(PyExc_TypeError, msg, len); |
2266 | return NULL; |
2267 | } |
2268 | |
2269 | if (len) { Branch (2269:9): [True: 6.66k, False: 4.24k]
|
2270 | PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */ |
2271 | assert(other != NULL); |
2272 | Py_INCREF(other); |
2273 | res = mutablemapping_update_arg(self, other); |
2274 | Py_DECREF(other); |
2275 | if (res < 0) { Branch (2275:13): [True: 18, False: 6.64k]
|
2276 | return NULL; |
2277 | } |
2278 | } |
2279 | |
2280 | /* now handle kwargs */ |
2281 | assert(kwargs == NULL || PyDict_Check(kwargs)); |
2282 | if (kwargs != NULL && PyDict_GET_SIZE40 (kwargs)) { Branch (2282:9): [True: 40, False: 10.8k]
|
2283 | PyObject *items = PyDict_Items(kwargs); |
2284 | if (items == NULL) Branch (2284:13): [True: 0, False: 37]
|
2285 | return NULL; |
2286 | res = mutablemapping_add_pairs(self, items); |
2287 | Py_DECREF(items); |
2288 | if (res == -1) Branch (2288:13): [True: 0, False: 37]
|
2289 | return NULL; |
2290 | } |
2291 | |
2292 | Py_RETURN_NONE0 ; |
2293 | } |