1/* Ordered Dictionary object implementation. 2 3This implementation is necessarily explicitly equivalent to the pure Python 4OrderedDict class in Lib/collections/__init__.py. The strategy there 5involves using a doubly-linked-list to capture the order. We keep to that 6strategy, using a lower-level linked-list. 7 8About the Linked-List 9===================== 10 11For the linked list we use a basic doubly-linked-list. Using a circularly- 12linked-list does have some benefits, but they don't apply so much here 13since OrderedDict is focused on the ends of the list (for the most part). 14Furthermore, there are some features of generic linked-lists that we simply 15don't need for OrderedDict. Thus a simple custom implementation meets our 16needs. Alternatives to our simple approach include the QCIRCLE_* 17macros from BSD's queue.h, and the linux's list.h. 18 19Getting O(1) Node Lookup 20------------------------ 21 22One invariant of Python's OrderedDict is that it preserves time complexity 23of dict's methods, particularly the O(1) operations. Simply adding a 24linked-list on top of dict is not sufficient here; operations for nodes in 25the middle of the linked-list implicitly require finding the node first. 26With a simple linked-list like we're using, that is an O(n) operation. 27Consequently, methods like __delitem__() would change from O(1) to O(n), 28which is unacceptable. 29 30In order to preserve O(1) performance for node removal (finding nodes), we 31must do better than just looping through the linked-list. Here are options 32we've considered: 33 341. use a second dict to map keys to nodes (a la the pure Python version). 352. keep a simple hash table mirroring the order of dict's, mapping each key 36 to the corresponding node in the linked-list. 373. use a version of shared keys (split dict) that allows non-unicode keys. 384. have the value stored for each key be a (value, node) pair, and adjust 39 __getitem__(), get(), etc. accordingly. 40 41The approach with the least performance impact (time and space) is #2, 42mirroring the key order of dict's dk_entries with an array of node pointers. 43While _Py_dict_lookup() does not give us the index into the array, 44we make use of pointer arithmetic to get that index. An alternative would 45be to refactor _Py_dict_lookup() to provide the index, explicitly exposing 46the implementation detail. We could even just use a custom lookup function 47for OrderedDict that facilitates our need. However, both approaches are 48significantly more complicated than just using pointer arithmetic. 49 50The catch with mirroring the hash table ordering is that we have to keep 51the ordering in sync through any dict resizes. However, that order only 52matters during node lookup. We can simply defer any potential resizing 53until we need to do a lookup. 54 55Linked-List Nodes 56----------------- 57 58The current implementation stores a pointer to the associated key only. 59One alternative would be to store a pointer to the PyDictKeyEntry instead. 60This would save one pointer de-reference per item, which is nice during 61calls to values() and items(). However, it adds unnecessary overhead 62otherwise, so we stick with just the key. 63 64Linked-List API 65--------------- 66 67As noted, the linked-list implemented here does not have all the bells and 68whistles. However, we recognize that the implementation may need to 69change to accommodate performance improvements or extra functionality. To 70that end, we use a simple API to interact with the linked-list. Here's a 71summary of the methods/macros: 72 73Node info: 74 75* _odictnode_KEY(node) 76* _odictnode_VALUE(od, node) 77* _odictnode_PREV(node) 78* _odictnode_NEXT(node) 79 80Linked-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 87For adding nodes: 88 89* _odict_add_head(od, node) 90* _odict_add_tail(od, node) 91* _odict_add_new_node(od, key, hash) 92 93For removing nodes: 94 95* _odict_clear_node(od, node, key, hash) 96* _odict_clear_nodes(od, clear_each) 97 98Others: 99 100* _odict_find_node_hash(od, key, hash) 101* _odict_find_node(od, key) 102* _odict_keys_equal(od1, od2) 103 104And here's a look at how the linked-list relates to the OrderedDict API: 105 106============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === 107method 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 119clear ~ ~ X 120copy X X X 121items X X X 122keys X X 123move_to_end X X X ~ h/t key 124pop free key 125popitem X X free X X node 126setdefault ~ ? ~ 127values X X 128============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === 129 130__delitem__ is the only method that directly relies on finding an arbitrary 131node in the linked-list. Everything else is iteration or relates to the 132ends of the linked-list. 133 134Situation that Endangers Consistency 135------------------------------------ 136Using a raw linked-list for OrderedDict exposes a key situation that can 137cause problems. If a node is stored in a variable, there is a chance that 138the node may have been deallocated before the variable gets used, thus 139potentially leading to a segmentation fault. A key place where this shows 140up is during iteration through the linked list (via _odict_FOREACH or 141otherwise). 142 143A 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 155Another related problem, preserving consistent ordering during iteration, 156is described below. That one is not exclusive to using linked-lists. 157 158 159Challenges from Subclassing dict 160================================ 161 162OrderedDict subclasses dict, which is an unusual relationship between two 163builtin types (other than the base object type). Doing so results in 164some complication and deserves further explanation. There are two things 165to consider here. First, in what circumstances or with what adjustments 166can OrderedDict be used as a drop-in replacement for dict (at the C level)? 167Second, how can the OrderedDict implementation leverage the dict 168implementation effectively without introducing unnecessary coupling or 169inefficiencies? 170 171This second point is reflected here and in the implementation, so the 172further focus is on the first point. It is worth noting that for 173overridden methods, the dict implementation is deferred to as much as 174possible. Furthermore, coupling is limited to as little as is reasonable. 175 176Concrete API Compatibility 177-------------------------- 178 179Use of the concrete C-API for dict (PyDict_*) with OrderedDict is 180problematic. (See http://bugs.python.org/issue10977.) The concrete API 181has a number of hard-coded assumptions tied to the dict implementation. 182This is, in part, due to performance reasons, which is understandable 183given the part dict plays in Python. 184 185Any attempt to replace dict with OrderedDict for any role in the 186interpreter (e.g. **kwds) faces a challenge. Such any effort must 187recognize that the instances in affected locations currently interact with 188the concrete API. 189 190Here are some ways to address this challenge: 191 1921. Change the relevant usage of the concrete API in CPython and add 193 PyDict_CheckExact() calls to each of the concrete API functions. 1942. Adjust the relevant concrete API functions to explicitly accommodate 195 OrderedDict. 1963. 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 200Adding the checks to the concrete API would help make any interpreter 201switch to OrderedDict less painful for extension modules. However, this 202won't work. The equivalent C API call to `dict.__setitem__(obj, k, v)` 203is 'PyDict_SetItem(obj, k, v)`. This illustrates how subclasses in C call 204the base class's methods, since there is no equivalent of super() in the 205C API. Calling into Python for parent class API would work, but some 206extension modules already rely on this feature of the concrete API. 207 208For reference, here is a breakdown of some of the dict concrete API: 209 210========================== ============= ======================= 211concrete API uses abstract API 212========================== ============= ======================= 213PyDict_Check PyMapping_Check 214(PyDict_CheckExact) - 215(PyDict_New) - 216(PyDictProxy_New) - 217PyDict_Clear - 218PyDict_Contains PySequence_Contains 219PyDict_Copy - 220PyDict_SetItem PyObject_SetItem 221PyDict_SetItemString PyMapping_SetItemString 222PyDict_DelItem PyMapping_DelItem 223PyDict_DelItemString PyMapping_DelItemString 224PyDict_GetItem - 225PyDict_GetItemWithError PyObject_GetItem 226_PyDict_GetItemIdWithError - 227PyDict_GetItemString PyMapping_GetItemString 228PyDict_Items PyMapping_Items 229PyDict_Keys PyMapping_Keys 230PyDict_Values PyMapping_Values 231PyDict_Size PyMapping_Size 232 PyMapping_Length 233PyDict_Next PyIter_Next 234_PyDict_Next - 235PyDict_Merge - 236PyDict_Update - 237PyDict_MergeFromSeq2 - 238PyDict_ClearFreeList - 239- PyMapping_HasKeyString 240- PyMapping_HasKey 241========================== ============= ======================= 242 243 244The dict Interface Relative to OrderedDict 245========================================== 246 247Since OrderedDict subclasses dict, understanding the various methods and 248attributes of dict is important for implementing OrderedDict. 249 250Relevant Type Slots 251------------------- 252 253================= ================ =================== ================ 254slot attribute object dict 255================= ================ =================== ================ 256tp_dealloc - object_dealloc dict_dealloc 257tp_repr __repr__ object_repr dict_repr 258sq_contains __contains__ - dict_contains 259mp_length __len__ - dict_length 260mp_subscript __getitem__ - dict_subscript 261mp_ass_subscript __setitem__ - dict_ass_sub 262 __delitem__ 263tp_hash __hash__ _Py_HashPointer ..._HashNotImpl 264tp_str __str__ object_str - 265tp_getattro __getattribute__ ..._GenericGetAttr (repeated) 266 __getattr__ 267tp_setattro __setattr__ ..._GenericSetAttr (disabled) 268tp_doc __doc__ (literal) dictionary_doc 269tp_traverse - - dict_traverse 270tp_clear - - dict_tp_clear 271tp_richcompare __eq__ object_richcompare dict_richcompare 272 __ne__ 273tp_weaklistoffset (__weakref__) - - 274tp_iter __iter__ - dict_iter 275tp_dictoffset (__dict__) - - 276tp_init __init__ object_init dict_init 277tp_alloc - PyType_GenericAlloc (repeated) 278tp_new __new__ object_new dict_new 279tp_free - PyObject_Del PyObject_GC_Del 280================= ================ =================== ================ 281 282Relevant Methods 283---------------- 284 285================ =================== =============== 286method object dict 287================ =================== =============== 288__reduce__ object_reduce - 289__sizeof__ object_sizeof dict_sizeof 290clear - dict_clear 291copy - dict_copy 292fromkeys - dict_fromkeys 293get - dict_get 294items - dictitems_new 295keys - dictkeys_new 296pop - dict_pop 297popitem - dict_popitem 298setdefault - dict_setdefault 299update - dict_update 300values - dictvalues_new 301================ =================== =============== 302 303 304Pure Python OrderedDict 305======================= 306 307As already noted, compatibility with the pure Python OrderedDict 308implementation is a key goal of this C implementation. To further that 309goal, here's a summary of how OrderedDict-specific methods are implemented 310in collections/__init__.py. Also provided is an indication of which 311methods directly mutate or iterate the object, as well as any relationship 312with the underlying linked-list. 313 314============= ============== == ================ === === ==== 315method 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__ 337clear OrderedDict Y dict.clear X 338copy OrderedDict N __class__ 339 __init__ 340fromkeys OrderedDict N __setitem__ 341get dict - - ~ 342items MutableMapping - ItemsView X 343keys MutableMapping - KeysView X 344move_to_end OrderedDict Y - X 345pop OrderedDict N __contains__ X 346 __getitem__ 347 __delitem__ 348popitem OrderedDict Y dict.pop X 349setdefault OrderedDict N __contains__ ~ 350 __getitem__ 351 __setitem__ 352update MutableMapping - __setitem__ ~ 353values MutableMapping - ValuesView X 354============= ============== == ================ === === ==== 355 356__reversed__ and move_to_end are both exclusive to OrderedDict. 357 358 359C OrderedDict Implementation 360============================ 361 362================= ================ 363slot impl 364================= ================ 365tp_dealloc odict_dealloc 366tp_repr odict_repr 367mp_ass_subscript odict_ass_sub 368tp_doc odict_doc 369tp_traverse odict_traverse 370tp_clear odict_tp_clear 371tp_richcompare odict_richcompare 372tp_weaklistoffset (offset) 373tp_iter odict_iter 374tp_dictoffset (offset) 375tp_init odict_init 376tp_alloc (repeated) 377================= ================ 378 379================= ================ 380method impl 381================= ================ 382__reduce__ odict_reduce 383__sizeof__ odict_sizeof 384clear odict_clear 385copy odict_copy 386fromkeys odict_fromkeys 387items odictitems_new 388keys odictkeys_new 389pop odict_pop 390popitem odict_popitem 391setdefault odict_setdefault 392update odict_update 393values odictvalues_new 394================= ================ 395 396Inherited unchanged from object/dict: 397 398================ ========================== 399method 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 410get - 411================ ========================== 412 413 414Other Challenges 415================ 416 417Preserving Ordering During Iteration 418------------------------------------ 419During iteration through an OrderedDict, it is possible that items could 420get added, removed, or reordered. For a linked-list implementation, as 421with some other implementations, that situation may lead to undefined 422behavior. The documentation for dict mentions this in the `iter()` section 423of http://docs.python.org/3.4/library/stdtypes.html#dictionary-view-objects. 424In this implementation we follow dict's lead (as does the pure Python 425implementation) for __iter__(), keys(), values(), and items(). 426 427For internal iteration (using _odict_FOREACH or not), there is still the 428risk that not all nodes that we expect to be seen in the loop actually get 429seen. Thus, we are careful in each of those places to ensure that they 430are. This comes, of course, at a small price at each location. The 431solutions are much the same as those detailed in the `Situation that 432Endangers Consistency` section above. 433 434 435Potential 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 451sooner: 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 457later: 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] 476class OrderedDict "PyODictObject *" "&PyODict_Type" 477[clinic start generated code]*/ 478/*[clinic end generated code: output=da39a3ee5e6b4b0d input=ca0641cf6143d4af]*/ 479 480 481typedef struct _odictnode _ODictNode; 482 483/* PyODictObject */ 484struct _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 505struct _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. */ 529static 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) { 538 return keys->dk_nentries; /* index of new entry */ 539 } 540 if (ix < 0) 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. */ 549static 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) { 559 PyErr_NoMemory(); 560 return -1; 561 } 562 for (i = 0; i < size; i++) 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) { 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. */ 585static 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 || 595 od->od_fast_nodes_size != (ONE << (keys->dk_log2_size))) { 596 int resize_res = _odict_resize(od); 597 if (resize_res < 0) 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. */ 605static _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) 614 return NULL; 615 assert(od->od_fast_nodes != NULL); 616 return od->od_fast_nodes[index]; 617} 618 619static _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) 629 return NULL; 630 index = _odict_get_index(od, key, hash); 631 if (index < 0) 632 return NULL; 633 assert(od->od_fast_nodes != NULL); 634 return od->od_fast_nodes[index]; 635} 636 637static 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) 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 650static 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) 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 */ 664static 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) { 673 if (!PyErr_Occurred()) 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) { 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) { 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. */ 708static void 709_odict_remove_node(PyODictObject *od, _ODictNode *node) 710{ 711 if (_odict_FIRST(od) == node) 712 _odict_FIRST(od) = _odictnode_NEXT(node); 713 else if (_odictnode_PREV(node) != NULL) 714 _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node); 715 716 if (_odict_LAST(od) == node) 717 _odict_LAST(od) = _odictnode_PREV(node); 718 else if (_odictnode_NEXT(node) != NULL) 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*/ 742static 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) 756 return PyErr_Occurred() ? -1 : 0; 757 758 assert(od->od_fast_nodes != NULL); 759 if (node == NULL) 760 node = od->od_fast_nodes[i]; 761 assert(node == od->od_fast_nodes[i]); 762 if (node == NULL) { 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 774static 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) { 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 797static 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) { 805 if (node_a == NULL && node_b == NULL) 806 /* success: hit the end of each at the same time */ 807 return 1; 808 else if (node_a == NULL || node_b == NULL) 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) 817 return res; 818 else if (res == 0) 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 835static int 836odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w) 837{ 838 if (w == NULL) 839 return PyODict_DelItem((PyObject *)od, v); 840 else 841 return PyODict_SetItem((PyObject *)od, v, w); 842} 843 844/* tp_as_mapping */ 845 846static 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 857static int mutablemapping_update_arg(PyObject*, PyObject*); 858 859static PyObject * 860odict_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)) { 873 Py_RETURN_NOTIMPLEMENTED; 874 } 875 PyObject *new = PyObject_CallOneArg((PyObject*)type, left); 876 if (!new) { 877 return NULL; 878 } 879 if (mutablemapping_update_arg(new, right) < 0) { 880 Py_DECREF(new); 881 return NULL; 882 } 883 return new; 884} 885 886static PyObject * 887odict_inplace_or(PyObject *self, PyObject *other) 888{ 889 if (mutablemapping_update_arg(self, other) < 0) { 890 return NULL; 891 } 892 Py_INCREF(self); 893 return self; 894} 895 896/* tp_as_number */ 897 898static 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 912OrderedDict.fromkeys 913 914 iterable as seq: object 915 value: object = None 916 917Create a new ordered dictionary with keys from iterable and values set to value. 918[clinic start generated code]*/ 919 920static PyObject * 921OrderedDict_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. */ 930PyDoc_STRVAR(odict_sizeof__doc__, ""); 931 932static PyObject * 933odict_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)) { 938 res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */ 939 } 940 return PyLong_FromSsize_t(res); 941} 942 943/* __reduce__() */ 944 945PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling"); 946 947static PyObject * 948odict_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) 956 goto Done; 957 958 /* build the result */ 959 args = PyTuple_New(0); 960 if (args == NULL) 961 goto Done; 962 963 items = PyObject_CallMethodNoArgs((PyObject *)od, &_Py_ID(items)); 964 if (items == NULL) 965 goto Done; 966 967 items_iter = PyObject_GetIter(items); 968 Py_DECREF(items); 969 if (items_iter == NULL) 970 goto Done; 971 972 result = PyTuple_Pack(5, Py_TYPE(od), args, state, Py_None, items_iter); 973 Py_DECREF(items_iter); 974 975Done: 976 Py_XDECREF(state); 977 Py_XDECREF(args); 978 979 return result; 980} 981 982/* setdefault(): Skips __missing__() calls. */ 983 984 985/*[clinic input] 986OrderedDict.setdefault 987 988 key: object 989 default: object = None 990 991Insert key with a value of default if key is not in the dictionary. 992 993Return the value for key if key is in the dictionary, else default. 994[clinic start generated code]*/ 995 996static PyObject * 997OrderedDict_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) { 1006 if (PyErr_Occurred()) 1007 return NULL; 1008 assert(_odict_find_node(self, key) == NULL); 1009 if (PyODict_SetItem((PyObject *)self, key, default_value) >= 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) { 1021 return NULL; 1022 } 1023 else if (exists) { 1024 result = PyObject_GetItem((PyObject *)self, key); 1025 } 1026 else if (PyObject_SetItem((PyObject *)self, key, default_value) >= 0) { 1027 result = default_value; 1028 Py_INCREF(result); 1029 } 1030 } 1031 1032 return result; 1033} 1034 1035/* pop() */ 1036 1037static 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) { 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) { 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()) { 1056 /* Apply the fallback value, if necessary. */ 1057 if (failobj) { 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] 1071OrderedDict.pop 1072 1073 key: object 1074 default: object = NULL 1075 1076od.pop(key[,default]) -> v, remove specified key and return the corresponding value. 1077 1078If the key is not found, return the default if given; otherwise, 1079raise a KeyError. 1080[clinic start generated code]*/ 1081 1082static PyObject * 1083OrderedDict_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) 1089 return NULL; 1090 return _odict_popkey_hash((PyObject *)self, key, default_value, hash); 1091} 1092 1093 1094/* popitem() */ 1095 1096/*[clinic input] 1097OrderedDict.popitem 1098 1099 last: bool = True 1100 1101Remove and return a (key, value) pair from the dictionary. 1102 1103Pairs are returned in LIFO order if last is true or FIFO order if false. 1104[clinic start generated code]*/ 1105 1106static PyObject * 1107OrderedDict_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_LAST(self) : _odict_FIRST(self); 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) 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. */ 1135PyDoc_STRVAR(odict_keys__doc__, ""); 1136 1137static PyObject * odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */ 1138 1139/* values() */ 1140 1141/* MutableMapping.values() does not have a docstring. */ 1142PyDoc_STRVAR(odict_values__doc__, ""); 1143 1144static PyObject * odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */ 1145 1146/* items() */ 1147 1148/* MutableMapping.items() does not have a docstring. */ 1149PyDoc_STRVAR(odict_items__doc__, ""); 1150 1151static PyObject * odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored)); /* forward */ 1152 1153/* update() */ 1154 1155/* MutableMapping.update() does not have a docstring. */ 1156PyDoc_STRVAR(odict_update__doc__, ""); 1157 1158/* forward */ 1159static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *); 1160 1161#define odict_update mutablemapping_update 1162 1163/* clear() */ 1164 1165PyDoc_STRVAR(odict_clear__doc__, 1166 "od.clear() -> None. Remove all items from od."); 1167 1168static PyObject * 1169odict_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 */ 1179static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *, 1180 Py_hash_t); 1181 1182PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od"); 1183 1184static PyObject * 1185odict_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) 1195 return NULL; 1196 1197 if (PyODict_CheckExact(od)) { 1198 _odict_FOREACH(od, node) { 1199 PyObject *key = _odictnode_KEY(node); 1200 PyObject *value = _odictnode_VALUE(node, od); 1201 if (value == NULL) { 1202 if (!PyErr_Occurred()) 1203 PyErr_SetObject(PyExc_KeyError, key); 1204 goto fail; 1205 } 1206 if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value, 1207 _odictnode_HASH(node)) != 0) 1208 goto fail; 1209 } 1210 } 1211 else { 1212 _odict_FOREACH(od, node) { 1213 int res; 1214 PyObject *value = PyObject_GetItem((PyObject *)od, 1215 _odictnode_KEY(node)); 1216 if (value == NULL) 1217 goto fail; 1218 res = PyObject_SetItem((PyObject *)od_copy, 1219 _odictnode_KEY(node), value); 1220 Py_DECREF(value); 1221 if (res != 0) 1222 goto fail; 1223 } 1224 } 1225 return od_copy; 1226 1227fail: 1228 Py_DECREF(od_copy); 1229 return NULL; 1230} 1231 1232/* __reversed__() */ 1233 1234PyDoc_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 */ 1242static PyObject * odictiter_new(PyODictObject *, int); 1243 1244static PyObject * 1245odict_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] 1254OrderedDict.move_to_end 1255 1256 key: object 1257 last: bool = True 1258 1259Move an existing element to the end (or beginning if last is false). 1260 1261Raise KeyError if the element does not exist. 1262[clinic start generated code]*/ 1263 1264static PyObject * 1265OrderedDict_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_LAST(self) : _odict_FIRST(self); 1275 if (key != _odictnode_KEY(node)) { 1276 node = _odict_find_node(self, key); 1277 if (node == NULL) { 1278 if (!PyErr_Occurred()) 1279 PyErr_SetObject(PyExc_KeyError, key); 1280 return NULL; 1281 } 1282 if (last) { 1283 /* Only move if not already the last one. */ 1284 if (node != _odict_LAST(self)) { 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)) { 1292 _odict_remove_node(self, node); 1293 _odict_add_head(self, node); 1294 } 1295 } 1296 } 1297 Py_RETURN_NONE; 1298} 1299 1300 1301/* tp_methods */ 1302 1303static 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 1342static 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 1353static void 1354odict_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) 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 1371static PyObject * 1372odict_repr(PyODictObject *self) 1373{ 1374 int i; 1375 PyObject *pieces = NULL, *result = NULL; 1376 1377 if (PyODict_SIZE(self) == 0) 1378 return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self))); 1379 1380 i = Py_ReprEnter((PyObject *)self); 1381 if (i != 0) { 1382 return i > 0 ? PyUnicode_FromString("...") : NULL; 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) 1390 goto Done; 1391 1392 _odict_FOREACH(self, node) { 1393 PyObject *pair; 1394 PyObject *key = _odictnode_KEY(node); 1395 PyObject *value = _odictnode_VALUE(node, self); 1396 if (value == NULL) { 1397 if (!PyErr_Occurred()) 1398 PyErr_SetObject(PyExc_KeyError, key); 1399 goto Done; 1400 } 1401 pair = PyTuple_Pack(2, key, value); 1402 if (pair == NULL) 1403 goto Done; 1404 1405 if (count < PyList_GET_SIZE(pieces)) 1406 PyList_SET_ITEM(pieces, count, pair); /* steals reference */ 1407 else { 1408 if (PyList_Append(pieces, pair) < 0) { 1409 Py_DECREF(pair); 1410 goto Done; 1411 } 1412 Py_DECREF(pair); 1413 } 1414 count++; 1415 } 1416 if (count < PyList_GET_SIZE(pieces)) { 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) 1424 goto Done; 1425 pieces = PySequence_List(items); 1426 Py_DECREF(items); 1427 if (pieces == NULL) 1428 goto Done; 1429 } 1430 1431 result = PyUnicode_FromFormat("%s(%R)", 1432 _PyType_Name(Py_TYPE(self)), pieces); 1433 1434Done: 1435 Py_XDECREF(pieces); 1436 Py_ReprLeave((PyObject *)self); 1437 return result; 1438} 1439 1440/* tp_doc */ 1441 1442PyDoc_STRVAR(odict_doc, 1443 "Dictionary that remembers insertion order"); 1444 1445/* tp_traverse */ 1446 1447static int 1448odict_traverse(PyODictObject *od, visitproc visit, void *arg) 1449{ 1450 _ODictNode *node; 1451 1452 Py_VISIT(od->od_inst_dict); 1453 _odict_FOREACH(od, node) { 1454 Py_VISIT(_odictnode_KEY(node)); 1455 } 1456 return PyDict_Type.tp_traverse((PyObject *)od, visit, arg); 1457} 1458 1459/* tp_clear */ 1460 1461static int 1462odict_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 1472static PyObject * 1473odict_richcompare(PyObject *v, PyObject *w, int op) 1474{ 1475 if (!PyODict_Check(v) || !PyDict_Check(w)) { 1476 Py_RETURN_NOTIMPLEMENTED; 1477 } 1478 1479 if (op == Py_EQ || op == Py_NE) { 1480 PyObject *res, *cmp; 1481 int eq; 1482 1483 cmp = PyDict_Type.tp_richcompare(v, w, op); 1484 if (cmp == NULL) 1485 return NULL; 1486 if (!PyODict_Check(w)) 1487 return cmp; 1488 if (op == Py_EQ && cmp == Py_False) 1489 return cmp; 1490 if (op == Py_NE && cmp == Py_True) 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) 1497 return NULL; 1498 1499 res = (eq == (op == Py_EQ)) ? Py_True : Py_False; 1500 Py_INCREF(res); 1501 return res; 1502 } else { 1503 Py_RETURN_NOTIMPLEMENTED; 1504 } 1505} 1506 1507/* tp_iter */ 1508 1509static PyObject * 1510odict_iter(PyODictObject *od) 1511{ 1512 return odictiter_new(od, _odict_ITER_KEYS); 1513} 1514 1515/* tp_init */ 1516 1517static int 1518odict_init(PyObject *self, PyObject *args, PyObject *kwds) 1519{ 1520 PyObject *res; 1521 Py_ssize_t len = PyObject_Length(args); 1522 1523 if (len == -1) 1524 return -1; 1525 if (len > 1) { 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) { 1534 return -1; 1535 } else { 1536 Py_DECREF(res); 1537 return 0; 1538 } 1539} 1540 1541/* PyODict_Type */ 1542 1543PyTypeObject 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 1590PyObject * 1591PyODict_New(void) 1592{ 1593 return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL); 1594} 1595 1596static 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) { 1602 res = _odict_add_new_node((PyODictObject *)od, key, hash); 1603 if (res < 0) { 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 1614int 1615PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) 1616{ 1617 Py_hash_t hash = PyObject_Hash(key); 1618 if (hash == -1) 1619 return -1; 1620 return _PyODict_SetItem_KnownHash(od, key, value, hash); 1621} 1622 1623int 1624PyODict_DelItem(PyObject *od, PyObject *key) 1625{ 1626 int res; 1627 Py_hash_t hash = PyObject_Hash(key); 1628 if (hash == -1) 1629 return -1; 1630 res = _odict_clear_node((PyODictObject *)od, NULL, key, hash); 1631 if (res < 0) 1632 return -1; 1633 return _PyDict_DelItem_KnownHash(od, key, hash); 1634} 1635 1636 1637/* ------------------------------------------- 1638 * The OrderedDict views (keys/values/items) 1639 */ 1640 1641typedef 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 1651static void 1652odictiter_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) { 1658 Py_DECREF(di->di_result); 1659 } 1660 PyObject_GC_Del(di); 1661} 1662 1663static int 1664odictiter_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. */ 1674static PyObject * 1675odictiter_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) 1682 return NULL; 1683 if (di->di_current == NULL) 1684 goto done; /* We're already done. */ 1685 1686 /* Check for unsupported changes. */ 1687 if (di->di_odict->od_state != di->di_state) { 1688 PyErr_SetString(PyExc_RuntimeError, 1689 "OrderedDict mutated during iteration"); 1690 goto done; 1691 } 1692 if (di->di_size != PyODict_SIZE(di->di_odict)) { 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) { 1702 if (!PyErr_Occurred()) 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_PREV(node) : _odictnode_NEXT(node); 1712 if (node == NULL) { 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 1723done: 1724 Py_CLEAR(di->di_odict); 1725 return key; 1726} 1727 1728static PyObject * 1729odictiter_iternext(odictiterobject *di) 1730{ 1731 PyObject *result, *value; 1732 PyObject *key = odictiter_nextkey(di); /* new reference */ 1733 1734 if (key == NULL) 1735 return NULL; 1736 1737 /* Handle the keys case. */ 1738 if (! (di->kind & _odict_ITER_VALUES)) { 1739 return key; 1740 } 1741 1742 value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */ 1743 if (value == NULL) { 1744 if (!PyErr_Occurred()) 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)) { 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) { 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)) { 1769 _PyObject_GC_TRACK(result); 1770 } 1771 } 1772 else { 1773 result = PyTuple_New(2); 1774 if (result == NULL) { 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 1785done: 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 1793PyDoc_STRVAR(reduce_doc, "Return state information for pickling"); 1794 1795static PyObject * 1796odictiter_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) { 1808 return NULL; 1809 } 1810 return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list); 1811} 1812 1813static PyMethodDef odictiter_methods[] = { 1814 {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc}, 1815 {NULL, NULL} /* sentinel */ 1816}; 1817 1818PyTypeObject 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 1851static PyObject * 1852odictiter_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) 1860 return NULL; 1861 1862 if ((kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) { 1863 di->di_result = PyTuple_Pack(2, Py_None, Py_None); 1864 if (di->di_result == NULL) { 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_LAST(od) : _odict_FIRST(od); 1875 di->di_current = node ? _odictnode_KEY(node) : NULL; 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 1888static PyObject * 1889odictkeys_iter(_PyDictViewObject *dv) 1890{ 1891 if (dv->dv_dict == NULL) { 1892 Py_RETURN_NONE; 1893 } 1894 return odictiter_new((PyODictObject *)dv->dv_dict, 1895 _odict_ITER_KEYS); 1896} 1897 1898static PyObject * 1899odictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) 1900{ 1901 if (dv->dv_dict == NULL) { 1902 Py_RETURN_NONE; 1903 } 1904 return odictiter_new((PyODictObject *)dv->dv_dict, 1905 _odict_ITER_KEYS|_odict_ITER_REVERSED); 1906} 1907 1908static PyMethodDef odictkeys_methods[] = { 1909 {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL}, 1910 {NULL, NULL} /* sentinel */ 1911}; 1912 1913PyTypeObject 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 1947static PyObject * 1948odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored)) 1949{ 1950 return _PyDictView_New(od, &PyODictKeys_Type); 1951} 1952 1953/* items() */ 1954 1955static PyObject * 1956odictitems_iter(_PyDictViewObject *dv) 1957{ 1958 if (dv->dv_dict == NULL) { 1959 Py_RETURN_NONE; 1960 } 1961 return odictiter_new((PyODictObject *)dv->dv_dict, 1962 _odict_ITER_KEYS|_odict_ITER_VALUES); 1963} 1964 1965static PyObject * 1966odictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) 1967{ 1968 if (dv->dv_dict == NULL) { 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 1975static PyMethodDef odictitems_methods[] = { 1976 {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL}, 1977 {NULL, NULL} /* sentinel */ 1978}; 1979 1980PyTypeObject 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 2014static PyObject * 2015odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored)) 2016{ 2017 return _PyDictView_New(od, &PyODictItems_Type); 2018} 2019 2020/* values() */ 2021 2022static PyObject * 2023odictvalues_iter(_PyDictViewObject *dv) 2024{ 2025 if (dv->dv_dict == NULL) { 2026 Py_RETURN_NONE; 2027 } 2028 return odictiter_new((PyODictObject *)dv->dv_dict, 2029 _odict_ITER_VALUES); 2030} 2031 2032static PyObject * 2033odictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) 2034{ 2035 if (dv->dv_dict == NULL) { 2036 Py_RETURN_NONE; 2037 } 2038 return odictiter_new((PyODictObject *)dv->dv_dict, 2039 _odict_ITER_VALUES|_odict_ITER_REVERSED); 2040} 2041 2042static PyMethodDef odictvalues_methods[] = { 2043 {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL}, 2044 {NULL, NULL} /* sentinel */ 2045}; 2046 2047PyTypeObject 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 2081static PyObject * 2082odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored)) 2083{ 2084 return _PyDictView_New(od, &PyODictValues_Type); 2085} 2086 2087 2088/* ---------------------------------------------- 2089 MutableMapping implementations 2090 2091Mapping: 2092 2093============ =========== 2094method uses 2095============ =========== 2096__contains__ __getitem__ 2097__eq__ items 2098__getitem__ + 2099__iter__ + 2100__len__ + 2101__ne__ __eq__ 2102get __getitem__ 2103items ItemsView 2104keys KeysView 2105values ValuesView 2106============ =========== 2107 2108ItemsView uses __len__, __iter__, and __getitem__. 2109KeysView uses __len__, __iter__, and __contains__. 2110ValuesView uses __len__, __iter__, and __getitem__. 2111 2112MutableMapping: 2113 2114============ =========== 2115method uses 2116============ =========== 2117__delitem__ + 2118__setitem__ + 2119clear popitem 2120pop __getitem__ 2121 __delitem__ 2122popitem __iter__ 2123 _getitem__ 2124 __delitem__ 2125setdefault __getitem__ 2126 __setitem__ 2127update __setitem__ 2128============ =========== 2129*/ 2130 2131static int 2132mutablemapping_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) 2139 return -1; 2140 PyErr_Clear(); 2141 2142 while ((pair = PyIter_Next(iterator)) != NULL) { 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) 2147 goto Done; 2148 2149 key = PyIter_Next(pair_iterator); 2150 if (key == NULL) { 2151 if (!PyErr_Occurred()) 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) { 2159 if (!PyErr_Occurred()) 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) { 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()) 2173 goto Done; 2174 2175 res = PyObject_SetItem(self, key, value); 2176 2177Done: 2178 Py_DECREF(pair); 2179 Py_XDECREF(pair_iterator); 2180 Py_XDECREF(key); 2181 Py_XDECREF(value); 2182 if (PyErr_Occurred()) 2183 break; 2184 } 2185 Py_DECREF(iterator); 2186 2187 if (res < 0 || PyErr_Occurred() != NULL) 2188 return -1; 2189 else 2190 return 0; 2191} 2192 2193static int 2194mutablemapping_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) { 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) { 2208 return -1; 2209 } 2210 if (func != NULL) { 2211 PyObject *keys = _PyObject_CallNoArgs(func); 2212 Py_DECREF(func); 2213 if (keys == NULL) { 2214 return -1; 2215 } 2216 PyObject *iterator = PyObject_GetIter(keys); 2217 Py_DECREF(keys); 2218 if (iterator == NULL) { 2219 return -1; 2220 } 2221 PyObject *key; 2222 while (res == 0 && (key = PyIter_Next(iterator))) { 2223 PyObject *value = PyObject_GetItem(arg, key); 2224 if (value != NULL) { 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()) { 2235 return -1; 2236 } 2237 return 0; 2238 } 2239 if (_PyObject_LookupAttr(arg, &_Py_ID(items), &func) < 0) { 2240 return -1; 2241 } 2242 if (func != NULL) { 2243 PyObject *items = _PyObject_CallNoArgs(func); 2244 Py_DECREF(func); 2245 if (items == NULL) { 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 2256static PyObject * 2257mutablemapping_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) : 0; 2263 if (len > 1) { 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) { 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) { 2276 return NULL; 2277 } 2278 } 2279 2280 /* now handle kwargs */ 2281 assert(kwargs == NULL || PyDict_Check(kwargs)); 2282 if (kwargs != NULL && PyDict_GET_SIZE(kwargs)) { 2283 PyObject *items = PyDict_Items(kwargs); 2284 if (items == NULL) 2285 return NULL; 2286 res = mutablemapping_add_pairs(self, items); 2287 Py_DECREF(items); 2288 if (res == -1) 2289 return NULL; 2290 } 2291 2292 Py_RETURN_NONE; 2293} 2294