LCOV - code coverage report
Current view: | top level - Objects - odictobject.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 0 | 637 | 0.0 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 0 | 55 | 0.0 %
|  |  | Branches: | 0 | 378 | 0.0 %

               Branch data     Line data    Source code
           1                 :            : /* Ordered Dictionary object implementation.
           2                 :            :
           3                 :            : This implementation is necessarily explicitly equivalent to the pure Python
           4                 :            : OrderedDict class in Lib/collections/__init__.py.  The strategy there
           5                 :            : involves using a doubly-linked-list to capture the order.  We keep to that
           6                 :            : strategy, using a lower-level linked-list.
           7                 :            :
           8                 :            : About the Linked-List
           9                 :            : =====================
          10                 :            :
          11                 :            : For the linked list we use a basic doubly-linked-list.  Using a circularly-
          12                 :            : linked-list does have some benefits, but they don't apply so much here
          13                 :            : since OrderedDict is focused on the ends of the list (for the most part).
          14                 :            : Furthermore, there are some features of generic linked-lists that we simply
          15                 :            : don't need for OrderedDict.  Thus a simple custom implementation meets our
          16                 :            : needs.  Alternatives to our simple approach include the QCIRCLE_*
          17                 :            : macros from BSD's queue.h, and the linux's list.h.
          18                 :            :
          19                 :            : Getting O(1) Node Lookup
          20                 :            : ------------------------
          21                 :            :
          22                 :            : One invariant of Python's OrderedDict is that it preserves time complexity
          23                 :            : of dict's methods, particularly the O(1) operations.  Simply adding a
          24                 :            : linked-list on top of dict is not sufficient here; operations for nodes in
          25                 :            : the middle of the linked-list implicitly require finding the node first.
          26                 :            : With a simple linked-list like we're using, that is an O(n) operation.
          27                 :            : Consequently, methods like __delitem__() would change from O(1) to O(n),
          28                 :            : which is unacceptable.
          29                 :            :
          30                 :            : In order to preserve O(1) performance for node removal (finding nodes), we
          31                 :            : must do better than just looping through the linked-list.  Here are options
          32                 :            : we've considered:
          33                 :            :
          34                 :            : 1. use a second dict to map keys to nodes (a la the pure Python version).
          35                 :            : 2. keep a simple hash table mirroring the order of dict's, mapping each key
          36                 :            :    to the corresponding node in the linked-list.
          37                 :            : 3. use a version of shared keys (split dict) that allows non-unicode keys.
          38                 :            : 4. have the value stored for each key be a (value, node) pair, and adjust
          39                 :            :    __getitem__(), get(), etc. accordingly.
          40                 :            :
          41                 :            : The approach with the least performance impact (time and space) is #2,
          42                 :            : mirroring the key order of dict's dk_entries with an array of node pointers.
          43                 :            : While _Py_dict_lookup() does not give us the index into the array,
          44                 :            : we make use of pointer arithmetic to get that index.  An alternative would
          45                 :            : be to refactor _Py_dict_lookup() to provide the index, explicitly exposing
          46                 :            : the implementation detail.  We could even just use a custom lookup function
          47                 :            : for OrderedDict that facilitates our need.  However, both approaches are
          48                 :            : significantly more complicated than just using pointer arithmetic.
          49                 :            :
          50                 :            : The catch with mirroring the hash table ordering is that we have to keep
          51                 :            : the ordering in sync through any dict resizes.  However, that order only
          52                 :            : matters during node lookup.  We can simply defer any potential resizing
          53                 :            : until we need to do a lookup.
          54                 :            :
          55                 :            : Linked-List Nodes
          56                 :            : -----------------
          57                 :            :
          58                 :            : The current implementation stores a pointer to the associated key only.
          59                 :            : One alternative would be to store a pointer to the PyDictKeyEntry instead.
          60                 :            : This would save one pointer de-reference per item, which is nice during
          61                 :            : calls to values() and items().  However, it adds unnecessary overhead
          62                 :            : otherwise, so we stick with just the key.
          63                 :            :
          64                 :            : Linked-List API
          65                 :            : ---------------
          66                 :            :
          67                 :            : As noted, the linked-list implemented here does not have all the bells and
          68                 :            : whistles.  However, we recognize that the implementation may need to
          69                 :            : change to accommodate performance improvements or extra functionality.  To
          70                 :            : that end, we use a simple API to interact with the linked-list.  Here's a
          71                 :            : summary of the methods/macros:
          72                 :            :
          73                 :            : Node info:
          74                 :            :
          75                 :            : * _odictnode_KEY(node)
          76                 :            : * _odictnode_VALUE(od, node)
          77                 :            : * _odictnode_PREV(node)
          78                 :            : * _odictnode_NEXT(node)
          79                 :            :
          80                 :            : Linked-List info:
          81                 :            :
          82                 :            : * _odict_FIRST(od)
          83                 :            : * _odict_LAST(od)
          84                 :            : * _odict_EMPTY(od)
          85                 :            : * _odict_FOREACH(od, node) - used in place of `for (node=...)`
          86                 :            :
          87                 :            : For adding nodes:
          88                 :            :
          89                 :            : * _odict_add_head(od, node)
          90                 :            : * _odict_add_tail(od, node)
          91                 :            : * _odict_add_new_node(od, key, hash)
          92                 :            :
          93                 :            : For removing nodes:
          94                 :            :
          95                 :            : * _odict_clear_node(od, node, key, hash)
          96                 :            : * _odict_clear_nodes(od, clear_each)
          97                 :            :
          98                 :            : Others:
          99                 :            :
         100                 :            : * _odict_find_node_hash(od, key, hash)
         101                 :            : * _odict_find_node(od, key)
         102                 :            : * _odict_keys_equal(od1, od2)
         103                 :            :
         104                 :            : And here's a look at how the linked-list relates to the OrderedDict API:
         105                 :            :
         106                 :            : ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
         107                 :            : method       key val prev next mem  1st last empty iter find add rmv  clr keq
         108                 :            : ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
         109                 :            : __del__                                      ~                        X
         110                 :            : __delitem__                    free                     ~        node
         111                 :            : __eq__       ~                                                            X
         112                 :            : __iter__     X            X
         113                 :            : __new__                             X   X
         114                 :            : __reduce__   X   ~                                 X
         115                 :            : __repr__     X   X                                 X
         116                 :            : __reversed__ X       X
         117                 :            : __setitem__                                                  key
         118                 :            : __sizeof__                     size          X
         119                 :            : clear                          ~             ~                        X
         120                 :            : copy         X   X                                 X
         121                 :            : items        X   X        X
         122                 :            : keys         X            X
         123                 :            : move_to_end  X                      X   X               ~    h/t key
         124                 :            : pop                            free                              key
         125                 :            : popitem      X   X             free X   X                        node
         126                 :            : setdefault       ~                                      ?    ~
         127                 :            : values           X        X
         128                 :            : ============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === ===
         129                 :            :
         130                 :            : __delitem__ is the only method that directly relies on finding an arbitrary
         131                 :            : node in the linked-list.  Everything else is iteration or relates to the
         132                 :            : ends of the linked-list.
         133                 :            :
         134                 :            : Situation that Endangers Consistency
         135                 :            : ------------------------------------
         136                 :            : Using a raw linked-list for OrderedDict exposes a key situation that can
         137                 :            : cause problems.  If a node is stored in a variable, there is a chance that
         138                 :            : the node may have been deallocated before the variable gets used, thus
         139                 :            : potentially leading to a segmentation fault.  A key place where this shows
         140                 :            : up is during iteration through the linked list (via _odict_FOREACH or
         141                 :            : otherwise).
         142                 :            :
         143                 :            : A number of solutions are available to resolve this situation:
         144                 :            :
         145                 :            : * defer looking up the node until as late as possible and certainly after
         146                 :            :   any code that could possibly result in a deletion;
         147                 :            : * if the node is needed both before and after a point where the node might
         148                 :            :   be removed, do a check before using the node at the "after" location to
         149                 :            :   see if the node is still valid;
         150                 :            : * like the last one, but simply pull the node again to ensure it's right;
         151                 :            : * keep the key in the variable instead of the node and then look up the
         152                 :            :   node using the key at the point where the node is needed (this is what
         153                 :            :   we do for the iterators).
         154                 :            :
         155                 :            : Another related problem, preserving consistent ordering during iteration,
         156                 :            : is described below.  That one is not exclusive to using linked-lists.
         157                 :            :
         158                 :            :
         159                 :            : Challenges from Subclassing dict
         160                 :            : ================================
         161                 :            :
         162                 :            : OrderedDict subclasses dict, which is an unusual relationship between two
         163                 :            : builtin types (other than the base object type).  Doing so results in
         164                 :            : some complication and deserves further explanation.  There are two things
         165                 :            : to consider here.  First, in what circumstances or with what adjustments
         166                 :            : can OrderedDict be used as a drop-in replacement for dict (at the C level)?
         167                 :            : Second, how can the OrderedDict implementation leverage the dict
         168                 :            : implementation effectively without introducing unnecessary coupling or
         169                 :            : inefficiencies?
         170                 :            :
         171                 :            : This second point is reflected here and in the implementation, so the
         172                 :            : further focus is on the first point.  It is worth noting that for
         173                 :            : overridden methods, the dict implementation is deferred to as much as
         174                 :            : possible.  Furthermore, coupling is limited to as little as is reasonable.
         175                 :            :
         176                 :            : Concrete API Compatibility
         177                 :            : --------------------------
         178                 :            :
         179                 :            : Use of the concrete C-API for dict (PyDict_*) with OrderedDict is
         180                 :            : problematic.  (See http://bugs.python.org/issue10977.)  The concrete API
         181                 :            : has a number of hard-coded assumptions tied to the dict implementation.
         182                 :            : This is, in part, due to performance reasons, which is understandable
         183                 :            : given the part dict plays in Python.
         184                 :            :
         185                 :            : Any attempt to replace dict with OrderedDict for any role in the
         186                 :            : interpreter (e.g. **kwds) faces a challenge.  Such any effort must
         187                 :            : recognize that the instances in affected locations currently interact with
         188                 :            : the concrete API.
         189                 :            :
         190                 :            : Here are some ways to address this challenge:
         191                 :            :
         192                 :            : 1. Change the relevant usage of the concrete API in CPython and add
         193                 :            :    PyDict_CheckExact() calls to each of the concrete API functions.
         194                 :            : 2. Adjust the relevant concrete API functions to explicitly accommodate
         195                 :            :    OrderedDict.
         196                 :            : 3. As with #1, add the checks, but improve the abstract API with smart fast
         197                 :            :    paths for dict and OrderedDict, and refactor CPython to use the abstract
         198                 :            :    API.  Improvements to the abstract API would be valuable regardless.
         199                 :            :
         200                 :            : Adding the checks to the concrete API would help make any interpreter
         201                 :            : switch to OrderedDict less painful for extension modules.  However, this
         202                 :            : won't work.  The equivalent C API call to `dict.__setitem__(obj, k, v)`
         203                 :            : is 'PyDict_SetItem(obj, k, v)`.  This illustrates how subclasses in C call
         204                 :            : the base class's methods, since there is no equivalent of super() in the
         205                 :            : C API.  Calling into Python for parent class API would work, but some
         206                 :            : extension modules already rely on this feature of the concrete API.
         207                 :            :
         208                 :            : For reference, here is a breakdown of some of the dict concrete API:
         209                 :            :
         210                 :            : ========================== ============= =======================
         211                 :            : concrete API               uses          abstract API
         212                 :            : ========================== ============= =======================
         213                 :            : PyDict_Check                             PyMapping_Check
         214                 :            : (PyDict_CheckExact)                      -
         215                 :            : (PyDict_New)                             -
         216                 :            : (PyDictProxy_New)                        -
         217                 :            : PyDict_Clear                             -
         218                 :            : PyDict_Contains                          PySequence_Contains
         219                 :            : PyDict_Copy                              -
         220                 :            : PyDict_SetItem                           PyObject_SetItem
         221                 :            : PyDict_SetItemString                     PyMapping_SetItemString
         222                 :            : PyDict_DelItem                           PyMapping_DelItem
         223                 :            : PyDict_DelItemString                     PyMapping_DelItemString
         224                 :            : PyDict_GetItem                           -
         225                 :            : PyDict_GetItemWithError                  PyObject_GetItem
         226                 :            : _PyDict_GetItemIdWithError               -
         227                 :            : PyDict_GetItemString                     PyMapping_GetItemString
         228                 :            : PyDict_Items                             PyMapping_Items
         229                 :            : PyDict_Keys                              PyMapping_Keys
         230                 :            : PyDict_Values                            PyMapping_Values
         231                 :            : PyDict_Size                              PyMapping_Size
         232                 :            :                                          PyMapping_Length
         233                 :            : PyDict_Next                              PyIter_Next
         234                 :            : _PyDict_Next                             -
         235                 :            : PyDict_Merge                             -
         236                 :            : PyDict_Update                            -
         237                 :            : PyDict_MergeFromSeq2                     -
         238                 :            : PyDict_ClearFreeList                     -
         239                 :            : -                                        PyMapping_HasKeyString
         240                 :            : -                                        PyMapping_HasKey
         241                 :            : ========================== ============= =======================
         242                 :            :
         243                 :            :
         244                 :            : The dict Interface Relative to OrderedDict
         245                 :            : ==========================================
         246                 :            :
         247                 :            : Since OrderedDict subclasses dict, understanding the various methods and
         248                 :            : attributes of dict is important for implementing OrderedDict.
         249                 :            :
         250                 :            : Relevant Type Slots
         251                 :            : -------------------
         252                 :            :
         253                 :            : ================= ================ =================== ================
         254                 :            : slot              attribute        object              dict
         255                 :            : ================= ================ =================== ================
         256                 :            : tp_dealloc        -                object_dealloc      dict_dealloc
         257                 :            : tp_repr           __repr__         object_repr         dict_repr
         258                 :            : sq_contains       __contains__     -                   dict_contains
         259                 :            : mp_length         __len__          -                   dict_length
         260                 :            : mp_subscript      __getitem__      -                   dict_subscript
         261                 :            : mp_ass_subscript  __setitem__      -                   dict_ass_sub
         262                 :            :                   __delitem__
         263                 :            : tp_hash           __hash__         _Py_HashPointer     ..._HashNotImpl
         264                 :            : tp_str            __str__          object_str          -
         265                 :            : tp_getattro       __getattribute__ ..._GenericGetAttr  (repeated)
         266                 :            :                   __getattr__
         267                 :            : tp_setattro       __setattr__      ..._GenericSetAttr  (disabled)
         268                 :            : tp_doc            __doc__          (literal)           dictionary_doc
         269                 :            : tp_traverse       -                -                   dict_traverse
         270                 :            : tp_clear          -                -                   dict_tp_clear
         271                 :            : tp_richcompare    __eq__           object_richcompare  dict_richcompare
         272                 :            :                   __ne__
         273                 :            : tp_weaklistoffset (__weakref__)    -                   -
         274                 :            : tp_iter           __iter__         -                   dict_iter
         275                 :            : tp_dictoffset     (__dict__)       -                   -
         276                 :            : tp_init           __init__         object_init         dict_init
         277                 :            : tp_alloc          -                PyType_GenericAlloc (repeated)
         278                 :            : tp_new            __new__          object_new          dict_new
         279                 :            : tp_free           -                PyObject_Del        PyObject_GC_Del
         280                 :            : ================= ================ =================== ================
         281                 :            :
         282                 :            : Relevant Methods
         283                 :            : ----------------
         284                 :            :
         285                 :            : ================ =================== ===============
         286                 :            : method           object              dict
         287                 :            : ================ =================== ===============
         288                 :            : __reduce__       object_reduce       -
         289                 :            : __sizeof__       object_sizeof       dict_sizeof
         290                 :            : clear            -                   dict_clear
         291                 :            : copy             -                   dict_copy
         292                 :            : fromkeys         -                   dict_fromkeys
         293                 :            : get              -                   dict_get
         294                 :            : items            -                   dictitems_new
         295                 :            : keys             -                   dictkeys_new
         296                 :            : pop              -                   dict_pop
         297                 :            : popitem          -                   dict_popitem
         298                 :            : setdefault       -                   dict_setdefault
         299                 :            : update           -                   dict_update
         300                 :            : values           -                   dictvalues_new
         301                 :            : ================ =================== ===============
         302                 :            :
         303                 :            :
         304                 :            : Pure Python OrderedDict
         305                 :            : =======================
         306                 :            :
         307                 :            : As already noted, compatibility with the pure Python OrderedDict
         308                 :            : implementation is a key goal of this C implementation.  To further that
         309                 :            : goal, here's a summary of how OrderedDict-specific methods are implemented
         310                 :            : in collections/__init__.py.  Also provided is an indication of which
         311                 :            : methods directly mutate or iterate the object, as well as any relationship
         312                 :            : with the underlying linked-list.
         313                 :            :
         314                 :            : ============= ============== == ================ === === ====
         315                 :            : method        impl used      ll uses             inq mut iter
         316                 :            : ============= ============== == ================ === === ====
         317                 :            : __contains__  dict           -  -                X
         318                 :            : __delitem__   OrderedDict    Y  dict.__delitem__     X
         319                 :            : __eq__        OrderedDict    N  OrderedDict      ~
         320                 :            :                                 dict.__eq__
         321                 :            :                                 __iter__
         322                 :            : __getitem__   dict           -  -                X
         323                 :            : __iter__      OrderedDict    Y  -                        X
         324                 :            : __init__      OrderedDict    N  update
         325                 :            : __len__       dict           -  -                X
         326                 :            : __ne__        MutableMapping -  __eq__           ~
         327                 :            : __reduce__    OrderedDict    N  OrderedDict      ~
         328                 :            :                                 __iter__
         329                 :            :                                 __getitem__
         330                 :            : __repr__      OrderedDict    N  __class__        ~
         331                 :            :                                 items
         332                 :            : __reversed__  OrderedDict    Y  -                        X
         333                 :            : __setitem__   OrderedDict    Y  __contains__         X
         334                 :            :                                 dict.__setitem__
         335                 :            : __sizeof__    OrderedDict    Y  __len__          ~
         336                 :            :                                 __dict__
         337                 :            : clear         OrderedDict    Y  dict.clear           X
         338                 :            : copy          OrderedDict    N  __class__
         339                 :            :                                 __init__
         340                 :            : fromkeys      OrderedDict    N  __setitem__
         341                 :            : get           dict           -  -                ~
         342                 :            : items         MutableMapping -  ItemsView                X
         343                 :            : keys          MutableMapping -  KeysView                 X
         344                 :            : move_to_end   OrderedDict    Y  -                    X
         345                 :            : pop           OrderedDict    N  __contains__         X
         346                 :            :                                 __getitem__
         347                 :            :                                 __delitem__
         348                 :            : popitem       OrderedDict    Y  dict.pop             X
         349                 :            : setdefault    OrderedDict    N  __contains__         ~
         350                 :            :                                 __getitem__
         351                 :            :                                 __setitem__
         352                 :            : update        MutableMapping -  __setitem__          ~
         353                 :            : values        MutableMapping -  ValuesView               X
         354                 :            : ============= ============== == ================ === === ====
         355                 :            :
         356                 :            : __reversed__ and move_to_end are both exclusive to OrderedDict.
         357                 :            :
         358                 :            :
         359                 :            : C OrderedDict Implementation
         360                 :            : ============================
         361                 :            :
         362                 :            : ================= ================
         363                 :            : slot              impl
         364                 :            : ================= ================
         365                 :            : tp_dealloc        odict_dealloc
         366                 :            : tp_repr           odict_repr
         367                 :            : mp_ass_subscript  odict_ass_sub
         368                 :            : tp_doc            odict_doc
         369                 :            : tp_traverse       odict_traverse
         370                 :            : tp_clear          odict_tp_clear
         371                 :            : tp_richcompare    odict_richcompare
         372                 :            : tp_weaklistoffset (offset)
         373                 :            : tp_iter           odict_iter
         374                 :            : tp_dictoffset     (offset)
         375                 :            : tp_init           odict_init
         376                 :            : tp_alloc          (repeated)
         377                 :            : ================= ================
         378                 :            :
         379                 :            : ================= ================
         380                 :            : method            impl
         381                 :            : ================= ================
         382                 :            : __reduce__        odict_reduce
         383                 :            : __sizeof__        odict_sizeof
         384                 :            : clear             odict_clear
         385                 :            : copy              odict_copy
         386                 :            : fromkeys          odict_fromkeys
         387                 :            : items             odictitems_new
         388                 :            : keys              odictkeys_new
         389                 :            : pop               odict_pop
         390                 :            : popitem           odict_popitem
         391                 :            : setdefault        odict_setdefault
         392                 :            : update            odict_update
         393                 :            : values            odictvalues_new
         394                 :            : ================= ================
         395                 :            :
         396                 :            : Inherited unchanged from object/dict:
         397                 :            :
         398                 :            : ================ ==========================
         399                 :            : method           type field
         400                 :            : ================ ==========================
         401                 :            : -                tp_free
         402                 :            : __contains__     tp_as_sequence.sq_contains
         403                 :            : __getattr__      tp_getattro
         404                 :            : __getattribute__ tp_getattro
         405                 :            : __getitem__      tp_as_mapping.mp_subscript
         406                 :            : __hash__         tp_hash
         407                 :            : __len__          tp_as_mapping.mp_length
         408                 :            : __setattr__      tp_setattro
         409                 :            : __str__          tp_str
         410                 :            : get              -
         411                 :            : ================ ==========================
         412                 :            :
         413                 :            :
         414                 :            : Other Challenges
         415                 :            : ================
         416                 :            :
         417                 :            : Preserving Ordering During Iteration
         418                 :            : ------------------------------------
         419                 :            : During iteration through an OrderedDict, it is possible that items could
         420                 :            : get added, removed, or reordered.  For a linked-list implementation, as
         421                 :            : with some other implementations, that situation may lead to undefined
         422                 :            : behavior.  The documentation for dict mentions this in the `iter()` section
         423                 :            : of http://docs.python.org/3.4/library/stdtypes.html#dictionary-view-objects.
         424                 :            : In this implementation we follow dict's lead (as does the pure Python
         425                 :            : implementation) for __iter__(), keys(), values(), and items().
         426                 :            :
         427                 :            : For internal iteration (using _odict_FOREACH or not), there is still the
         428                 :            : risk that not all nodes that we expect to be seen in the loop actually get
         429                 :            : seen.  Thus, we are careful in each of those places to ensure that they
         430                 :            : are.  This comes, of course, at a small price at each location.  The
         431                 :            : solutions are much the same as those detailed in the `Situation that
         432                 :            : Endangers Consistency` section above.
         433                 :            :
         434                 :            :
         435                 :            : Potential Optimizations
         436                 :            : =======================
         437                 :            :
         438                 :            : * Allocate the nodes as a block via od_fast_nodes instead of individually.
         439                 :            :   - Set node->key to NULL to indicate the node is not-in-use.
         440                 :            :   - Add _odict_EXISTS()?
         441                 :            :   - How to maintain consistency across resizes?  Existing node pointers
         442                 :            :     would be invalidated after a resize, which is particularly problematic
         443                 :            :     for the iterators.
         444                 :            : * Use a more stream-lined implementation of update() and, likely indirectly,
         445                 :            :   __init__().
         446                 :            :
         447                 :            : */
         448                 :            :
         449                 :            : /* TODO
         450                 :            :
         451                 :            : sooner:
         452                 :            : - reentrancy (make sure everything is at a thread-safe state when calling
         453                 :            :   into Python).  I've already checked this multiple times, but want to
         454                 :            :   make one more pass.
         455                 :            : - add unit tests for reentrancy?
         456                 :            :
         457                 :            : later:
         458                 :            : - make the dict views support the full set API (the pure Python impl does)
         459                 :            : - implement a fuller MutableMapping API in C?
         460                 :            : - move the MutableMapping implementation to abstract.c?
         461                 :            : - optimize mutablemapping_update
         462                 :            : - use PyObject_Malloc (small object allocator) for odict nodes?
         463                 :            : - support subclasses better (e.g. in odict_richcompare)
         464                 :            :
         465                 :            : */
         466                 :            :
         467                 :            : #include "Python.h"
         468                 :            : #include "pycore_call.h"          // _PyObject_CallNoArgs()
         469                 :            : #include "pycore_object.h"        // _PyObject_GC_UNTRACK()
         470                 :            : #include "pycore_dict.h"          // _Py_dict_lookup()
         471                 :            : #include <stddef.h>               // offsetof()
         472                 :            :
         473                 :            : #include "clinic/odictobject.c.h"
         474                 :            :
         475                 :            : /*[clinic input]
         476                 :            : class OrderedDict "PyODictObject *" "&PyODict_Type"
         477                 :            : [clinic start generated code]*/
         478                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ca0641cf6143d4af]*/
         479                 :            :
         480                 :            :
         481                 :            : typedef struct _odictnode _ODictNode;
         482                 :            :
         483                 :            : /* PyODictObject */
         484                 :            : struct _odictobject {
         485                 :            :     PyDictObject od_dict;        /* the underlying dict */
         486                 :            :     _ODictNode *od_first;        /* first node in the linked list, if any */
         487                 :            :     _ODictNode *od_last;         /* last node in the linked list, if any */
         488                 :            :     /* od_fast_nodes, od_fast_nodes_size and od_resize_sentinel are managed
         489                 :            :      * by _odict_resize().
         490                 :            :      * Note that we rely on implementation details of dict for both. */
         491                 :            :     _ODictNode **od_fast_nodes;  /* hash table that mirrors the dict table */
         492                 :            :     Py_ssize_t od_fast_nodes_size;
         493                 :            :     void *od_resize_sentinel;    /* changes if odict should be resized */
         494                 :            :
         495                 :            :     size_t od_state;             /* incremented whenever the LL changes */
         496                 :            :     PyObject *od_inst_dict;      /* OrderedDict().__dict__ */
         497                 :            :     PyObject *od_weakreflist;    /* holds weakrefs to the odict */
         498                 :            : };
         499                 :            :
         500                 :            :
         501                 :            : /* ----------------------------------------------
         502                 :            :  * odict keys (a simple doubly-linked list)
         503                 :            :  */
         504                 :            :
         505                 :            : struct _odictnode {
         506                 :            :     PyObject *key;
         507                 :            :     Py_hash_t hash;
         508                 :            :     _ODictNode *next;
         509                 :            :     _ODictNode *prev;
         510                 :            : };
         511                 :            :
         512                 :            : #define _odictnode_KEY(node) \
         513                 :            :     (node->key)
         514                 :            : #define _odictnode_HASH(node) \
         515                 :            :     (node->hash)
         516                 :            : /* borrowed reference */
         517                 :            : #define _odictnode_VALUE(node, od) \
         518                 :            :     PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))
         519                 :            : #define _odictnode_PREV(node) (node->prev)
         520                 :            : #define _odictnode_NEXT(node) (node->next)
         521                 :            :
         522                 :            : #define _odict_FIRST(od) (((PyODictObject *)od)->od_first)
         523                 :            : #define _odict_LAST(od) (((PyODictObject *)od)->od_last)
         524                 :            : #define _odict_EMPTY(od) (_odict_FIRST(od) == NULL)
         525                 :            : #define _odict_FOREACH(od, node) \
         526                 :            :     for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))
         527                 :            :
         528                 :            : /* Return the index into the hash table, regardless of a valid node. */
         529                 :            : static Py_ssize_t
         530                 :          0 : _odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
         531                 :            : {
         532                 :          0 :     PyObject *value = NULL;
         533                 :          0 :     PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
         534                 :            :     Py_ssize_t ix;
         535                 :            :
         536                 :          0 :     ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);
         537         [ #  # ]:          0 :     if (ix == DKIX_EMPTY) {
         538                 :          0 :         return keys->dk_nentries;  /* index of new entry */
         539                 :            :     }
         540         [ #  # ]:          0 :     if (ix < 0)
         541                 :          0 :         return -1;
         542                 :            :     /* We use pointer arithmetic to get the entry's index into the table. */
         543                 :          0 :     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                 :          0 : _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                 :          0 :     size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_size);
         557         [ #  # ]:          0 :     fast_nodes = PyMem_NEW(_ODictNode *, size);
         558         [ #  # ]:          0 :     if (fast_nodes == NULL) {
         559                 :          0 :         PyErr_NoMemory();
         560                 :          0 :         return -1;
         561                 :            :     }
         562         [ #  # ]:          0 :     for (i = 0; i < size; i++)
         563                 :          0 :         fast_nodes[i] = NULL;
         564                 :            :
         565                 :            :     /* Copy the current nodes into the table. */
         566         [ #  # ]:          0 :     _odict_FOREACH(od, node) {
         567                 :          0 :         i = _odict_get_index_raw(od, _odictnode_KEY(node),
         568                 :            :                                  _odictnode_HASH(node));
         569         [ #  # ]:          0 :         if (i < 0) {
         570                 :          0 :             PyMem_Free(fast_nodes);
         571                 :          0 :             return -1;
         572                 :            :         }
         573                 :          0 :         fast_nodes[i] = node;
         574                 :            :     }
         575                 :            :
         576                 :            :     /* Replace the old fast nodes table. */
         577                 :          0 :     PyMem_Free(od->od_fast_nodes);
         578                 :          0 :     od->od_fast_nodes = fast_nodes;
         579                 :          0 :     od->od_fast_nodes_size = size;
         580                 :          0 :     od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;
         581                 :          0 :     return 0;
         582                 :            : }
         583                 :            :
         584                 :            : /* Return the index into the hash table, regardless of a valid node. */
         585                 :            : static Py_ssize_t
         586                 :          0 : _odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)
         587                 :            : {
         588                 :            :     PyDictKeysObject *keys;
         589                 :            :
         590                 :            :     assert(key != NULL);
         591                 :          0 :     keys = ((PyDictObject *)od)->ma_keys;
         592                 :            :
         593                 :            :     /* Ensure od_fast_nodes and dk_entries are in sync. */
         594         [ #  # ]:          0 :     if (od->od_resize_sentinel != keys ||
         595         [ #  # ]:          0 :         od->od_fast_nodes_size != (ONE << (keys->dk_log2_size))) {
         596                 :          0 :         int resize_res = _odict_resize(od);
         597         [ #  # ]:          0 :         if (resize_res < 0)
         598                 :          0 :             return -1;
         599                 :            :     }
         600                 :            :
         601                 :          0 :     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                 :          0 : _odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash)
         607                 :            : {
         608                 :            :     Py_ssize_t index;
         609                 :            :
         610         [ #  # ]:          0 :     if (_odict_EMPTY(od))
         611                 :          0 :         return NULL;
         612                 :          0 :     index = _odict_get_index(od, key, hash);
         613         [ #  # ]:          0 :     if (index < 0)
         614                 :          0 :         return NULL;
         615                 :            :     assert(od->od_fast_nodes != NULL);
         616                 :          0 :     return od->od_fast_nodes[index];
         617                 :            : }
         618                 :            :
         619                 :            : static _ODictNode *
         620                 :          0 : _odict_find_node(PyODictObject *od, PyObject *key)
         621                 :            : {
         622                 :            :     Py_ssize_t index;
         623                 :            :     Py_hash_t hash;
         624                 :            :
         625         [ #  # ]:          0 :     if (_odict_EMPTY(od))
         626                 :          0 :         return NULL;
         627                 :          0 :     hash = PyObject_Hash(key);
         628         [ #  # ]:          0 :     if (hash == -1)
         629                 :          0 :         return NULL;
         630                 :          0 :     index = _odict_get_index(od, key, hash);
         631         [ #  # ]:          0 :     if (index < 0)
         632                 :          0 :         return NULL;
         633                 :            :     assert(od->od_fast_nodes != NULL);
         634                 :          0 :     return od->od_fast_nodes[index];
         635                 :            : }
         636                 :            :
         637                 :            : static void
         638                 :          0 : _odict_add_head(PyODictObject *od, _ODictNode *node)
         639                 :            : {
         640                 :          0 :     _odictnode_PREV(node) = NULL;
         641                 :          0 :     _odictnode_NEXT(node) = _odict_FIRST(od);
         642         [ #  # ]:          0 :     if (_odict_FIRST(od) == NULL)
         643                 :          0 :         _odict_LAST(od) = node;
         644                 :            :     else
         645                 :          0 :         _odictnode_PREV(_odict_FIRST(od)) = node;
         646                 :          0 :     _odict_FIRST(od) = node;
         647                 :          0 :     od->od_state++;
         648                 :          0 : }
         649                 :            :
         650                 :            : static void
         651                 :          0 : _odict_add_tail(PyODictObject *od, _ODictNode *node)
         652                 :            : {
         653                 :          0 :     _odictnode_PREV(node) = _odict_LAST(od);
         654                 :          0 :     _odictnode_NEXT(node) = NULL;
         655         [ #  # ]:          0 :     if (_odict_LAST(od) == NULL)
         656                 :          0 :         _odict_FIRST(od) = node;
         657                 :            :     else
         658                 :          0 :         _odictnode_NEXT(_odict_LAST(od)) = node;
         659                 :          0 :     _odict_LAST(od) = node;
         660                 :          0 :     od->od_state++;
         661                 :          0 : }
         662                 :            :
         663                 :            : /* adds the node to the end of the list */
         664                 :            : static int
         665                 :          0 : _odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
         666                 :            : {
         667                 :            :     Py_ssize_t i;
         668                 :            :     _ODictNode *node;
         669                 :            :
         670                 :          0 :     Py_INCREF(key);
         671                 :          0 :     i = _odict_get_index(od, key, hash);
         672         [ #  # ]:          0 :     if (i < 0) {
         673         [ #  # ]:          0 :         if (!PyErr_Occurred())
         674                 :          0 :             PyErr_SetObject(PyExc_KeyError, key);
         675                 :          0 :         Py_DECREF(key);
         676                 :          0 :         return -1;
         677                 :            :     }
         678                 :            :     assert(od->od_fast_nodes != NULL);
         679         [ #  # ]:          0 :     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                 :          0 :         Py_DECREF(key);
         682                 :          0 :         return 0;
         683                 :            :     }
         684                 :            :
         685                 :            :     /* must not be added yet */
         686                 :          0 :     node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode));
         687         [ #  # ]:          0 :     if (node == NULL) {
         688                 :          0 :         Py_DECREF(key);
         689                 :          0 :         PyErr_NoMemory();
         690                 :          0 :         return -1;
         691                 :            :     }
         692                 :            :
         693                 :          0 :     _odictnode_KEY(node) = key;
         694                 :          0 :     _odictnode_HASH(node) = hash;
         695                 :          0 :     _odict_add_tail(od, node);
         696                 :          0 :     od->od_fast_nodes[i] = node;
         697                 :          0 :     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                 :          0 : _odict_remove_node(PyODictObject *od, _ODictNode *node)
         710                 :            : {
         711         [ #  # ]:          0 :     if (_odict_FIRST(od) == node)
         712                 :          0 :         _odict_FIRST(od) = _odictnode_NEXT(node);
         713         [ #  # ]:          0 :     else if (_odictnode_PREV(node) != NULL)
         714                 :          0 :         _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);
         715                 :            :
         716         [ #  # ]:          0 :     if (_odict_LAST(od) == node)
         717                 :          0 :         _odict_LAST(od) = _odictnode_PREV(node);
         718         [ #  # ]:          0 :     else if (_odictnode_NEXT(node) != NULL)
         719                 :          0 :         _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node);
         720                 :            :
         721                 :          0 :     _odictnode_PREV(node) = NULL;
         722                 :          0 :     _odictnode_NEXT(node) = NULL;
         723                 :          0 :     od->od_state++;
         724                 :          0 : }
         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                 :          0 : _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         [ #  # ]:          0 :     if (_odict_EMPTY(od)) {
         750                 :            :         /* Let later code decide if this is a KeyError. */
         751                 :          0 :         return 0;
         752                 :            :     }
         753                 :            :
         754                 :          0 :     i = _odict_get_index(od, key, hash);
         755         [ #  # ]:          0 :     if (i < 0)
         756         [ #  # ]:          0 :         return PyErr_Occurred() ? -1 : 0;
         757                 :            :
         758                 :            :     assert(od->od_fast_nodes != NULL);
         759         [ #  # ]:          0 :     if (node == NULL)
         760                 :          0 :         node = od->od_fast_nodes[i];
         761                 :            :     assert(node == od->od_fast_nodes[i]);
         762         [ #  # ]:          0 :     if (node == NULL) {
         763                 :            :         /* Let later code decide if this is a KeyError. */
         764                 :          0 :         return 0;
         765                 :            :     }
         766                 :            :
         767                 :            :     // Now clear the node.
         768                 :          0 :     od->od_fast_nodes[i] = NULL;
         769                 :          0 :     _odict_remove_node(od, node);
         770                 :          0 :     _odictnode_DEALLOC(node);
         771                 :          0 :     return 0;
         772                 :            : }
         773                 :            :
         774                 :            : static void
         775                 :          0 : _odict_clear_nodes(PyODictObject *od)
         776                 :            : {
         777                 :            :     _ODictNode *node, *next;
         778                 :            :
         779                 :          0 :     PyMem_Free(od->od_fast_nodes);
         780                 :          0 :     od->od_fast_nodes = NULL;
         781                 :          0 :     od->od_fast_nodes_size = 0;
         782                 :          0 :     od->od_resize_sentinel = NULL;
         783                 :            :
         784                 :          0 :     node = _odict_FIRST(od);
         785                 :          0 :     _odict_FIRST(od) = NULL;
         786                 :          0 :     _odict_LAST(od) = NULL;
         787         [ #  # ]:          0 :     while (node != NULL) {
         788                 :          0 :         next = _odictnode_NEXT(node);
         789                 :          0 :         _odictnode_DEALLOC(node);
         790                 :          0 :         node = next;
         791                 :            :     }
         792                 :          0 : }
         793                 :            :
         794                 :            : /* There isn't any memory management of nodes past this point. */
         795                 :            : #undef _odictnode_DEALLOC
         796                 :            :
         797                 :            : static int
         798                 :          0 : _odict_keys_equal(PyODictObject *a, PyODictObject *b)
         799                 :            : {
         800                 :            :     _ODictNode *node_a, *node_b;
         801                 :            :
         802                 :          0 :     node_a = _odict_FIRST(a);
         803                 :          0 :     node_b = _odict_FIRST(b);
         804                 :            :     while (1) {
         805   [ #  #  #  # ]:          0 :         if (node_a == NULL && node_b == NULL)
         806                 :            :             /* success: hit the end of each at the same time */
         807                 :          0 :             return 1;
         808   [ #  #  #  # ]:          0 :         else if (node_a == NULL || node_b == NULL)
         809                 :            :             /* unequal length */
         810                 :          0 :             return 0;
         811                 :            :         else {
         812                 :          0 :             int res = PyObject_RichCompareBool(
         813                 :            :                                             (PyObject *)_odictnode_KEY(node_a),
         814                 :            :                                             (PyObject *)_odictnode_KEY(node_b),
         815                 :            :                                             Py_EQ);
         816         [ #  # ]:          0 :             if (res < 0)
         817                 :          0 :                 return res;
         818         [ #  # ]:          0 :             else if (res == 0)
         819                 :          0 :                 return 0;
         820                 :            :
         821                 :            :             /* otherwise it must match, so move on to the next one */
         822                 :          0 :             node_a = _odictnode_NEXT(node_a);
         823                 :          0 :             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                 :          0 : odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w)
         837                 :            : {
         838         [ #  # ]:          0 :     if (w == NULL)
         839                 :          0 :         return PyODict_DelItem((PyObject *)od, v);
         840                 :            :     else
         841                 :          0 :         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                 :          0 : odict_or(PyObject *left, PyObject *right)
         861                 :            : {
         862                 :            :     PyTypeObject *type;
         863                 :            :     PyObject *other;
         864         [ #  # ]:          0 :     if (PyODict_Check(left)) {
         865                 :          0 :         type = Py_TYPE(left);
         866                 :          0 :         other = right;
         867                 :            :     }
         868                 :            :     else {
         869                 :          0 :         type = Py_TYPE(right);
         870                 :          0 :         other = left;
         871                 :            :     }
         872         [ #  # ]:          0 :     if (!PyDict_Check(other)) {
         873                 :          0 :         Py_RETURN_NOTIMPLEMENTED;
         874                 :            :     }
         875                 :          0 :     PyObject *new = PyObject_CallOneArg((PyObject*)type, left);
         876         [ #  # ]:          0 :     if (!new) {
         877                 :          0 :         return NULL;
         878                 :            :     }
         879         [ #  # ]:          0 :     if (mutablemapping_update_arg(new, right) < 0) {
         880                 :          0 :         Py_DECREF(new);
         881                 :          0 :         return NULL;
         882                 :            :     }
         883                 :          0 :     return new;
         884                 :            : }
         885                 :            :
         886                 :            : static PyObject *
         887                 :          0 : odict_inplace_or(PyObject *self, PyObject *other)
         888                 :            : {
         889         [ #  # ]:          0 :     if (mutablemapping_update_arg(self, other) < 0) {
         890                 :          0 :         return NULL;
         891                 :            :     }
         892                 :          0 :     return Py_NewRef(self);
         893                 :            : }
         894                 :            :
         895                 :            : /* tp_as_number */
         896                 :            :
         897                 :            : static PyNumberMethods odict_as_number = {
         898                 :            :     .nb_or = odict_or,
         899                 :            :     .nb_inplace_or = odict_inplace_or,
         900                 :            : };
         901                 :            :
         902                 :            :
         903                 :            : /* ----------------------------------------------
         904                 :            :  * OrderedDict methods
         905                 :            :  */
         906                 :            :
         907                 :            : /* fromkeys() */
         908                 :            :
         909                 :            : /*[clinic input]
         910                 :            : @classmethod
         911                 :            : OrderedDict.fromkeys
         912                 :            :
         913                 :            :     iterable as seq: object
         914                 :            :     value: object = None
         915                 :            :
         916                 :            : Create a new ordered dictionary with keys from iterable and values set to value.
         917                 :            : [clinic start generated code]*/
         918                 :            :
         919                 :            : static PyObject *
         920                 :          0 : OrderedDict_fromkeys_impl(PyTypeObject *type, PyObject *seq, PyObject *value)
         921                 :            : /*[clinic end generated code: output=c10390d452d78d6d input=1a0476c229c597b3]*/
         922                 :            : {
         923                 :          0 :     return _PyDict_FromKeys((PyObject *)type, seq, value);
         924                 :            : }
         925                 :            :
         926                 :            : /* __sizeof__() */
         927                 :            :
         928                 :            : /* OrderedDict.__sizeof__() does not have a docstring. */
         929                 :            : PyDoc_STRVAR(odict_sizeof__doc__, "");
         930                 :            :
         931                 :            : static PyObject *
         932                 :          0 : odict_sizeof(PyODictObject *od, PyObject *Py_UNUSED(ignored))
         933                 :            : {
         934                 :          0 :     Py_ssize_t res = _PyDict_SizeOf((PyDictObject *)od);
         935                 :          0 :     res += sizeof(_ODictNode *) * od->od_fast_nodes_size;  /* od_fast_nodes */
         936         [ #  # ]:          0 :     if (!_odict_EMPTY(od)) {
         937                 :          0 :         res += sizeof(_ODictNode) * PyODict_SIZE(od);  /* linked-list */
         938                 :            :     }
         939                 :          0 :     return PyLong_FromSsize_t(res);
         940                 :            : }
         941                 :            :
         942                 :            : /* __reduce__() */
         943                 :            :
         944                 :            : PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling");
         945                 :            :
         946                 :            : static PyObject *
         947                 :          0 : odict_reduce(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
         948                 :            : {
         949                 :          0 :     PyObject *state, *result = NULL;
         950                 :          0 :     PyObject *items_iter, *items, *args = NULL;
         951                 :            :
         952                 :            :     /* capture any instance state */
         953                 :          0 :     state = _PyObject_GetState((PyObject *)od);
         954         [ #  # ]:          0 :     if (state == NULL)
         955                 :          0 :         goto Done;
         956                 :            :
         957                 :            :     /* build the result */
         958                 :          0 :     args = PyTuple_New(0);
         959         [ #  # ]:          0 :     if (args == NULL)
         960                 :          0 :         goto Done;
         961                 :            :
         962                 :          0 :     items = PyObject_CallMethodNoArgs((PyObject *)od, &_Py_ID(items));
         963         [ #  # ]:          0 :     if (items == NULL)
         964                 :          0 :         goto Done;
         965                 :            :
         966                 :          0 :     items_iter = PyObject_GetIter(items);
         967                 :          0 :     Py_DECREF(items);
         968         [ #  # ]:          0 :     if (items_iter == NULL)
         969                 :          0 :         goto Done;
         970                 :            :
         971                 :          0 :     result = PyTuple_Pack(5, Py_TYPE(od), args, state, Py_None, items_iter);
         972                 :          0 :     Py_DECREF(items_iter);
         973                 :            :
         974                 :          0 : Done:
         975                 :          0 :     Py_XDECREF(state);
         976                 :          0 :     Py_XDECREF(args);
         977                 :            :
         978                 :          0 :     return result;
         979                 :            : }
         980                 :            :
         981                 :            : /* setdefault(): Skips __missing__() calls. */
         982                 :            :
         983                 :            :
         984                 :            : /*[clinic input]
         985                 :            : OrderedDict.setdefault
         986                 :            :
         987                 :            :     key: object
         988                 :            :     default: object = None
         989                 :            :
         990                 :            : Insert key with a value of default if key is not in the dictionary.
         991                 :            :
         992                 :            : Return the value for key if key is in the dictionary, else default.
         993                 :            : [clinic start generated code]*/
         994                 :            :
         995                 :            : static PyObject *
         996                 :          0 : OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,
         997                 :            :                             PyObject *default_value)
         998                 :            : /*[clinic end generated code: output=97537cb7c28464b6 input=38e098381c1efbc6]*/
         999                 :            : {
        1000                 :          0 :     PyObject *result = NULL;
        1001                 :            :
        1002         [ #  # ]:          0 :     if (PyODict_CheckExact(self)) {
        1003                 :          0 :         result = PyODict_GetItemWithError(self, key);  /* borrowed */
        1004         [ #  # ]:          0 :         if (result == NULL) {
        1005         [ #  # ]:          0 :             if (PyErr_Occurred())
        1006                 :          0 :                 return NULL;
        1007                 :            :             assert(_odict_find_node(self, key) == NULL);
        1008         [ #  # ]:          0 :             if (PyODict_SetItem((PyObject *)self, key, default_value) >= 0) {
        1009                 :          0 :                 result = Py_NewRef(default_value);
        1010                 :            :             }
        1011                 :            :         }
        1012                 :            :         else {
        1013                 :          0 :             Py_INCREF(result);
        1014                 :            :         }
        1015                 :            :     }
        1016                 :            :     else {
        1017                 :          0 :         int exists = PySequence_Contains((PyObject *)self, key);
        1018         [ #  # ]:          0 :         if (exists < 0) {
        1019                 :          0 :             return NULL;
        1020                 :            :         }
        1021         [ #  # ]:          0 :         else if (exists) {
        1022                 :          0 :             result = PyObject_GetItem((PyObject *)self, key);
        1023                 :            :         }
        1024         [ #  # ]:          0 :         else if (PyObject_SetItem((PyObject *)self, key, default_value) >= 0) {
        1025                 :          0 :             result = Py_NewRef(default_value);
        1026                 :            :         }
        1027                 :            :     }
        1028                 :            :
        1029                 :          0 :     return result;
        1030                 :            : }
        1031                 :            :
        1032                 :            : /* pop() */
        1033                 :            :
        1034                 :            : static PyObject *
        1035                 :          0 : _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
        1036                 :            :                    Py_hash_t hash)
        1037                 :            : {
        1038                 :          0 :     PyObject *value = NULL;
        1039                 :            :
        1040                 :          0 :     _ODictNode *node = _odict_find_node_hash((PyODictObject *)od, key, hash);
        1041         [ #  # ]:          0 :     if (node != NULL) {
        1042                 :            :         /* Pop the node first to avoid a possible dict resize (due to
        1043                 :            :            eval loop reentrancy) and complications due to hash collision
        1044                 :            :            resolution. */
        1045                 :          0 :         int res = _odict_clear_node((PyODictObject *)od, node, key, hash);
        1046         [ #  # ]:          0 :         if (res < 0) {
        1047                 :          0 :             return NULL;
        1048                 :            :         }
        1049                 :            :         /* Now delete the value from the dict. */
        1050                 :          0 :         value = _PyDict_Pop_KnownHash(od, key, hash, failobj);
        1051                 :            :     }
        1052   [ #  #  #  # ]:          0 :     else if (value == NULL && !PyErr_Occurred()) {
        1053                 :            :         /* Apply the fallback value, if necessary. */
        1054         [ #  # ]:          0 :         if (failobj) {
        1055                 :          0 :             value = Py_NewRef(failobj);
        1056                 :            :         }
        1057                 :            :         else {
        1058                 :          0 :             PyErr_SetObject(PyExc_KeyError, key);
        1059                 :            :         }
        1060                 :            :     }
        1061                 :            :
        1062                 :          0 :     return value;
        1063                 :            : }
        1064                 :            :
        1065                 :            : /* Skips __missing__() calls. */
        1066                 :            : /*[clinic input]
        1067                 :            : OrderedDict.pop
        1068                 :            :
        1069                 :            :     key: object
        1070                 :            :     default: object = NULL
        1071                 :            :
        1072                 :            : od.pop(key[,default]) -> v, remove specified key and return the corresponding value.
        1073                 :            :
        1074                 :            : If the key is not found, return the default if given; otherwise,
        1075                 :            : raise a KeyError.
        1076                 :            : [clinic start generated code]*/
        1077                 :            :
        1078                 :            : static PyObject *
        1079                 :          0 : OrderedDict_pop_impl(PyODictObject *self, PyObject *key,
        1080                 :            :                      PyObject *default_value)
        1081                 :            : /*[clinic end generated code: output=7a6447d104e7494b input=7efe36601007dff7]*/
        1082                 :            : {
        1083                 :          0 :     Py_hash_t hash = PyObject_Hash(key);
        1084         [ #  # ]:          0 :     if (hash == -1)
        1085                 :          0 :         return NULL;
        1086                 :          0 :     return _odict_popkey_hash((PyObject *)self, key, default_value, hash);
        1087                 :            : }
        1088                 :            :
        1089                 :            :
        1090                 :            : /* popitem() */
        1091                 :            :
        1092                 :            : /*[clinic input]
        1093                 :            : OrderedDict.popitem
        1094                 :            :
        1095                 :            :     last: bool = True
        1096                 :            :
        1097                 :            : Remove and return a (key, value) pair from the dictionary.
        1098                 :            :
        1099                 :            : Pairs are returned in LIFO order if last is true or FIFO order if false.
        1100                 :            : [clinic start generated code]*/
        1101                 :            :
        1102                 :            : static PyObject *
        1103                 :          0 : OrderedDict_popitem_impl(PyODictObject *self, int last)
        1104                 :            : /*[clinic end generated code: output=98e7d986690d49eb input=d992ac5ee8305e1a]*/
        1105                 :            : {
        1106                 :          0 :     PyObject *key, *value, *item = NULL;
        1107                 :            :     _ODictNode *node;
        1108                 :            :
        1109                 :            :     /* pull the item */
        1110                 :            :
        1111         [ #  # ]:          0 :     if (_odict_EMPTY(self)) {
        1112                 :          0 :         PyErr_SetString(PyExc_KeyError, "dictionary is empty");
        1113                 :          0 :         return NULL;
        1114                 :            :     }
        1115                 :            :
        1116         [ #  # ]:          0 :     node = last ? _odict_LAST(self) : _odict_FIRST(self);
        1117                 :          0 :     key = Py_NewRef(_odictnode_KEY(node));
        1118                 :          0 :     value = _odict_popkey_hash((PyObject *)self, key, NULL, _odictnode_HASH(node));
        1119         [ #  # ]:          0 :     if (value == NULL)
        1120                 :          0 :         return NULL;
        1121                 :          0 :     item = PyTuple_Pack(2, key, value);
        1122                 :          0 :     Py_DECREF(key);
        1123                 :          0 :     Py_DECREF(value);
        1124                 :          0 :     return item;
        1125                 :            : }
        1126                 :            :
        1127                 :            : /* keys() */
        1128                 :            :
        1129                 :            : /* MutableMapping.keys() does not have a docstring. */
        1130                 :            : PyDoc_STRVAR(odict_keys__doc__, "");
        1131                 :            :
        1132                 :            : static PyObject * odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored));  /* forward */
        1133                 :            :
        1134                 :            : /* values() */
        1135                 :            :
        1136                 :            : /* MutableMapping.values() does not have a docstring. */
        1137                 :            : PyDoc_STRVAR(odict_values__doc__, "");
        1138                 :            :
        1139                 :            : static PyObject * odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored));  /* forward */
        1140                 :            :
        1141                 :            : /* items() */
        1142                 :            :
        1143                 :            : /* MutableMapping.items() does not have a docstring. */
        1144                 :            : PyDoc_STRVAR(odict_items__doc__, "");
        1145                 :            :
        1146                 :            : static PyObject * odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored));  /* forward */
        1147                 :            :
        1148                 :            : /* update() */
        1149                 :            :
        1150                 :            : /* MutableMapping.update() does not have a docstring. */
        1151                 :            : PyDoc_STRVAR(odict_update__doc__, "");
        1152                 :            :
        1153                 :            : /* forward */
        1154                 :            : static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *);
        1155                 :            :
        1156                 :            : #define odict_update mutablemapping_update
        1157                 :            :
        1158                 :            : /* clear() */
        1159                 :            :
        1160                 :            : PyDoc_STRVAR(odict_clear__doc__,
        1161                 :            :              "od.clear() -> None.  Remove all items from od.");
        1162                 :            :
        1163                 :            : static PyObject *
        1164                 :          0 : odict_clear(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
        1165                 :            : {
        1166                 :          0 :     PyDict_Clear((PyObject *)od);
        1167                 :          0 :     _odict_clear_nodes(od);
        1168                 :          0 :     Py_RETURN_NONE;
        1169                 :            : }
        1170                 :            :
        1171                 :            : /* copy() */
        1172                 :            :
        1173                 :            : /* forward */
        1174                 :            : static int _PyODict_SetItem_KnownHash(PyObject *, PyObject *, PyObject *,
        1175                 :            :                                       Py_hash_t);
        1176                 :            :
        1177                 :            : PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od");
        1178                 :            :
        1179                 :            : static PyObject *
        1180                 :          0 : odict_copy(register PyODictObject *od, PyObject *Py_UNUSED(ignored))
        1181                 :            : {
        1182                 :            :     _ODictNode *node;
        1183                 :            :     PyObject *od_copy;
        1184                 :            :
        1185         [ #  # ]:          0 :     if (PyODict_CheckExact(od))
        1186                 :          0 :         od_copy = PyODict_New();
        1187                 :            :     else
        1188                 :          0 :         od_copy = _PyObject_CallNoArgs((PyObject *)Py_TYPE(od));
        1189         [ #  # ]:          0 :     if (od_copy == NULL)
        1190                 :          0 :         return NULL;
        1191                 :            :
        1192         [ #  # ]:          0 :     if (PyODict_CheckExact(od)) {
        1193         [ #  # ]:          0 :         _odict_FOREACH(od, node) {
        1194                 :          0 :             PyObject *key = _odictnode_KEY(node);
        1195                 :          0 :             PyObject *value = _odictnode_VALUE(node, od);
        1196         [ #  # ]:          0 :             if (value == NULL) {
        1197         [ #  # ]:          0 :                 if (!PyErr_Occurred())
        1198                 :          0 :                     PyErr_SetObject(PyExc_KeyError, key);
        1199                 :          0 :                 goto fail;
        1200                 :            :             }
        1201         [ #  # ]:          0 :             if (_PyODict_SetItem_KnownHash((PyObject *)od_copy, key, value,
        1202                 :            :                                            _odictnode_HASH(node)) != 0)
        1203                 :          0 :                 goto fail;
        1204                 :            :         }
        1205                 :            :     }
        1206                 :            :     else {
        1207         [ #  # ]:          0 :         _odict_FOREACH(od, node) {
        1208                 :            :             int res;
        1209                 :          0 :             PyObject *value = PyObject_GetItem((PyObject *)od,
        1210                 :            :                                                _odictnode_KEY(node));
        1211         [ #  # ]:          0 :             if (value == NULL)
        1212                 :          0 :                 goto fail;
        1213                 :          0 :             res = PyObject_SetItem((PyObject *)od_copy,
        1214                 :            :                                    _odictnode_KEY(node), value);
        1215                 :          0 :             Py_DECREF(value);
        1216         [ #  # ]:          0 :             if (res != 0)
        1217                 :          0 :                 goto fail;
        1218                 :            :         }
        1219                 :            :     }
        1220                 :          0 :     return od_copy;
        1221                 :            :
        1222                 :          0 : fail:
        1223                 :          0 :     Py_DECREF(od_copy);
        1224                 :          0 :     return NULL;
        1225                 :            : }
        1226                 :            :
        1227                 :            : /* __reversed__() */
        1228                 :            :
        1229                 :            : PyDoc_STRVAR(odict_reversed__doc__, "od.__reversed__() <==> reversed(od)");
        1230                 :            :
        1231                 :            : #define _odict_ITER_REVERSED 1
        1232                 :            : #define _odict_ITER_KEYS 2
        1233                 :            : #define _odict_ITER_VALUES 4
        1234                 :            : #define _odict_ITER_ITEMS (_odict_ITER_KEYS|_odict_ITER_VALUES)
        1235                 :            :
        1236                 :            : /* forward */
        1237                 :            : static PyObject * odictiter_new(PyODictObject *, int);
        1238                 :            :
        1239                 :            : static PyObject *
        1240                 :          0 : odict_reversed(PyODictObject *od, PyObject *Py_UNUSED(ignored))
        1241                 :            : {
        1242                 :          0 :     return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED);
        1243                 :            : }
        1244                 :            :
        1245                 :            :
        1246                 :            : /* move_to_end() */
        1247                 :            :
        1248                 :            : /*[clinic input]
        1249                 :            : OrderedDict.move_to_end
        1250                 :            :
        1251                 :            :     key: object
        1252                 :            :     last: bool = True
        1253                 :            :
        1254                 :            : Move an existing element to the end (or beginning if last is false).
        1255                 :            :
        1256                 :            : Raise KeyError if the element does not exist.
        1257                 :            : [clinic start generated code]*/
        1258                 :            :
        1259                 :            : static PyObject *
        1260                 :          0 : OrderedDict_move_to_end_impl(PyODictObject *self, PyObject *key, int last)
        1261                 :            : /*[clinic end generated code: output=fafa4c5cc9b92f20 input=d6ceff7132a2fcd7]*/
        1262                 :            : {
        1263                 :            :     _ODictNode *node;
        1264                 :            :
        1265         [ #  # ]:          0 :     if (_odict_EMPTY(self)) {
        1266                 :          0 :         PyErr_SetObject(PyExc_KeyError, key);
        1267                 :          0 :         return NULL;
        1268                 :            :     }
        1269         [ #  # ]:          0 :     node = last ? _odict_LAST(self) : _odict_FIRST(self);
        1270         [ #  # ]:          0 :     if (key != _odictnode_KEY(node)) {
        1271                 :          0 :         node = _odict_find_node(self, key);
        1272         [ #  # ]:          0 :         if (node == NULL) {
        1273         [ #  # ]:          0 :             if (!PyErr_Occurred())
        1274                 :          0 :                 PyErr_SetObject(PyExc_KeyError, key);
        1275                 :          0 :             return NULL;
        1276                 :            :         }
        1277         [ #  # ]:          0 :         if (last) {
        1278                 :            :             /* Only move if not already the last one. */
        1279         [ #  # ]:          0 :             if (node != _odict_LAST(self)) {
        1280                 :          0 :                 _odict_remove_node(self, node);
        1281                 :          0 :                 _odict_add_tail(self, node);
        1282                 :            :             }
        1283                 :            :         }
        1284                 :            :         else {
        1285                 :            :             /* Only move if not already the first one. */
        1286         [ #  # ]:          0 :             if (node != _odict_FIRST(self)) {
        1287                 :          0 :                 _odict_remove_node(self, node);
        1288                 :          0 :                 _odict_add_head(self, node);
        1289                 :            :             }
        1290                 :            :         }
        1291                 :            :     }
        1292                 :          0 :     Py_RETURN_NONE;
        1293                 :            : }
        1294                 :            :
        1295                 :            :
        1296                 :            : /* tp_methods */
        1297                 :            :
        1298                 :            : static PyMethodDef odict_methods[] = {
        1299                 :            :
        1300                 :            :     /* overridden dict methods */
        1301                 :            :     ORDEREDDICT_FROMKEYS_METHODDEF
        1302                 :            :     {"__sizeof__",      (PyCFunction)odict_sizeof,      METH_NOARGS,
        1303                 :            :      odict_sizeof__doc__},
        1304                 :            :     {"__reduce__",      (PyCFunction)odict_reduce,      METH_NOARGS,
        1305                 :            :      odict_reduce__doc__},
        1306                 :            :     ORDEREDDICT_SETDEFAULT_METHODDEF
        1307                 :            :     ORDEREDDICT_POP_METHODDEF
        1308                 :            :     ORDEREDDICT_POPITEM_METHODDEF
        1309                 :            :     {"keys",            odictkeys_new,                  METH_NOARGS,
        1310                 :            :      odict_keys__doc__},
        1311                 :            :     {"values",          odictvalues_new,                METH_NOARGS,
        1312                 :            :      odict_values__doc__},
        1313                 :            :     {"items",           odictitems_new,                 METH_NOARGS,
        1314                 :            :      odict_items__doc__},
        1315                 :            :     {"update",          _PyCFunction_CAST(odict_update), METH_VARARGS | METH_KEYWORDS,
        1316                 :            :      odict_update__doc__},
        1317                 :            :     {"clear",           (PyCFunction)odict_clear,       METH_NOARGS,
        1318                 :            :      odict_clear__doc__},
        1319                 :            :     {"copy",            (PyCFunction)odict_copy,        METH_NOARGS,
        1320                 :            :      odict_copy__doc__},
        1321                 :            :
        1322                 :            :     /* new methods */
        1323                 :            :     {"__reversed__",    (PyCFunction)odict_reversed,    METH_NOARGS,
        1324                 :            :      odict_reversed__doc__},
        1325                 :            :     ORDEREDDICT_MOVE_TO_END_METHODDEF
        1326                 :            :
        1327                 :            :     {NULL,              NULL}   /* sentinel */
        1328                 :            : };
        1329                 :            :
        1330                 :            :
        1331                 :            : /* ----------------------------------------------
        1332                 :            :  * OrderedDict members
        1333                 :            :  */
        1334                 :            :
        1335                 :            : /* tp_getset */
        1336                 :            :
        1337                 :            : static PyGetSetDef odict_getset[] = {
        1338                 :            :     {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
        1339                 :            :     {NULL}
        1340                 :            : };
        1341                 :            :
        1342                 :            : /* ----------------------------------------------
        1343                 :            :  * OrderedDict type slot methods
        1344                 :            :  */
        1345                 :            :
        1346                 :            : /* tp_dealloc */
        1347                 :            :
        1348                 :            : static void
        1349                 :          0 : odict_dealloc(PyODictObject *self)
        1350                 :            : {
        1351                 :          0 :     PyObject_GC_UnTrack(self);
        1352   [ #  #  #  # ]:          0 :     Py_TRASHCAN_BEGIN(self, odict_dealloc)
        1353                 :            :
        1354                 :          0 :     Py_XDECREF(self->od_inst_dict);
        1355         [ #  # ]:          0 :     if (self->od_weakreflist != NULL)
        1356                 :          0 :         PyObject_ClearWeakRefs((PyObject *)self);
        1357                 :            :
        1358                 :          0 :     _odict_clear_nodes(self);
        1359                 :          0 :     PyDict_Type.tp_dealloc((PyObject *)self);
        1360                 :            :
        1361         [ #  # ]:          0 :     Py_TRASHCAN_END
        1362                 :          0 : }
        1363                 :            :
        1364                 :            : /* tp_repr */
        1365                 :            :
        1366                 :            : static PyObject *
        1367                 :          0 : odict_repr(PyODictObject *self)
        1368                 :            : {
        1369                 :            :     int i;
        1370                 :          0 :     PyObject *result = NULL, *dcopy = NULL;
        1371                 :            :
        1372         [ #  # ]:          0 :     if (PyODict_SIZE(self) == 0)
        1373                 :          0 :         return PyUnicode_FromFormat("%s()", _PyType_Name(Py_TYPE(self)));
        1374                 :            :
        1375                 :          0 :     i = Py_ReprEnter((PyObject *)self);
        1376         [ #  # ]:          0 :     if (i != 0) {
        1377         [ #  # ]:          0 :         return i > 0 ? PyUnicode_FromString("...") : NULL;
        1378                 :            :     }
        1379                 :            :
        1380                 :          0 :     dcopy = PyDict_Copy((PyObject *)self);
        1381         [ #  # ]:          0 :     if (dcopy == NULL) {
        1382                 :          0 :         goto Done;
        1383                 :            :     }
        1384                 :            :
        1385                 :          0 :     result = PyUnicode_FromFormat("%s(%R)",
        1386                 :            :                                   _PyType_Name(Py_TYPE(self)),
        1387                 :            :                                   dcopy);
        1388                 :          0 :     Py_DECREF(dcopy);
        1389                 :            :
        1390                 :          0 : Done:
        1391                 :          0 :     Py_ReprLeave((PyObject *)self);
        1392                 :          0 :     return result;
        1393                 :            : }
        1394                 :            :
        1395                 :            : /* tp_doc */
        1396                 :            :
        1397                 :            : PyDoc_STRVAR(odict_doc,
        1398                 :            :         "Dictionary that remembers insertion order");
        1399                 :            :
        1400                 :            : /* tp_traverse */
        1401                 :            :
        1402                 :            : static int
        1403                 :          0 : odict_traverse(PyODictObject *od, visitproc visit, void *arg)
        1404                 :            : {
        1405                 :            :     _ODictNode *node;
        1406                 :            :
        1407   [ #  #  #  # ]:          0 :     Py_VISIT(od->od_inst_dict);
        1408         [ #  # ]:          0 :     _odict_FOREACH(od, node) {
        1409   [ #  #  #  # ]:          0 :         Py_VISIT(_odictnode_KEY(node));
        1410                 :            :     }
        1411                 :          0 :     return PyDict_Type.tp_traverse((PyObject *)od, visit, arg);
        1412                 :            : }
        1413                 :            :
        1414                 :            : /* tp_clear */
        1415                 :            :
        1416                 :            : static int
        1417                 :          0 : odict_tp_clear(PyODictObject *od)
        1418                 :            : {
        1419         [ #  # ]:          0 :     Py_CLEAR(od->od_inst_dict);
        1420                 :          0 :     PyDict_Clear((PyObject *)od);
        1421                 :          0 :     _odict_clear_nodes(od);
        1422                 :          0 :     return 0;
        1423                 :            : }
        1424                 :            :
        1425                 :            : /* tp_richcompare */
        1426                 :            :
        1427                 :            : static PyObject *
        1428                 :          0 : odict_richcompare(PyObject *v, PyObject *w, int op)
        1429                 :            : {
        1430   [ #  #  #  # ]:          0 :     if (!PyODict_Check(v) || !PyDict_Check(w)) {
        1431                 :          0 :         Py_RETURN_NOTIMPLEMENTED;
        1432                 :            :     }
        1433                 :            :
        1434   [ #  #  #  # ]:          0 :     if (op == Py_EQ || op == Py_NE) {
        1435                 :            :         PyObject *res, *cmp;
        1436                 :            :         int eq;
        1437                 :            :
        1438                 :          0 :         cmp = PyDict_Type.tp_richcompare(v, w, op);
        1439         [ #  # ]:          0 :         if (cmp == NULL)
        1440                 :          0 :             return NULL;
        1441         [ #  # ]:          0 :         if (!PyODict_Check(w))
        1442                 :          0 :             return cmp;
        1443   [ #  #  #  # ]:          0 :         if (op == Py_EQ && cmp == Py_False)
        1444                 :          0 :             return cmp;
        1445   [ #  #  #  # ]:          0 :         if (op == Py_NE && cmp == Py_True)
        1446                 :          0 :             return cmp;
        1447                 :          0 :         Py_DECREF(cmp);
        1448                 :            :
        1449                 :            :         /* Try comparing odict keys. */
        1450                 :          0 :         eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w);
        1451         [ #  # ]:          0 :         if (eq < 0)
        1452                 :          0 :             return NULL;
        1453                 :            :
        1454         [ #  # ]:          0 :         res = (eq == (op == Py_EQ)) ? Py_True : Py_False;
        1455                 :          0 :         return Py_NewRef(res);
        1456                 :            :     } else {
        1457                 :          0 :         Py_RETURN_NOTIMPLEMENTED;
        1458                 :            :     }
        1459                 :            : }
        1460                 :            :
        1461                 :            : /* tp_iter */
        1462                 :            :
        1463                 :            : static PyObject *
        1464                 :          0 : odict_iter(PyODictObject *od)
        1465                 :            : {
        1466                 :          0 :     return odictiter_new(od, _odict_ITER_KEYS);
        1467                 :            : }
        1468                 :            :
        1469                 :            : /* tp_init */
        1470                 :            :
        1471                 :            : static int
        1472                 :          0 : odict_init(PyObject *self, PyObject *args, PyObject *kwds)
        1473                 :            : {
        1474                 :            :     PyObject *res;
        1475                 :          0 :     Py_ssize_t len = PyObject_Length(args);
        1476                 :            :
        1477         [ #  # ]:          0 :     if (len == -1)
        1478                 :          0 :         return -1;
        1479         [ #  # ]:          0 :     if (len > 1) {
        1480                 :          0 :         const char *msg = "expected at most 1 arguments, got %zd";
        1481                 :          0 :         PyErr_Format(PyExc_TypeError, msg, len);
        1482                 :          0 :         return -1;
        1483                 :            :     }
        1484                 :            :
        1485                 :            :     /* __init__() triggering update() is just the way things are! */
        1486                 :          0 :     res = odict_update(self, args, kwds);
        1487         [ #  # ]:          0 :     if (res == NULL) {
        1488                 :          0 :         return -1;
        1489                 :            :     } else {
        1490                 :          0 :         Py_DECREF(res);
        1491                 :          0 :         return 0;
        1492                 :            :     }
        1493                 :            : }
        1494                 :            :
        1495                 :            : /* PyODict_Type */
        1496                 :            :
        1497                 :            : PyTypeObject PyODict_Type = {
        1498                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        1499                 :            :     "collections.OrderedDict",                  /* tp_name */
        1500                 :            :     sizeof(PyODictObject),                      /* tp_basicsize */
        1501                 :            :     0,                                          /* tp_itemsize */
        1502                 :            :     (destructor)odict_dealloc,                  /* tp_dealloc */
        1503                 :            :     0,                                          /* tp_vectorcall_offset */
        1504                 :            :     0,                                          /* tp_getattr */
        1505                 :            :     0,                                          /* tp_setattr */
        1506                 :            :     0,                                          /* tp_as_async */
        1507                 :            :     (reprfunc)odict_repr,                       /* tp_repr */
        1508                 :            :     &odict_as_number,                           /* tp_as_number */
        1509                 :            :     0,                                          /* tp_as_sequence */
        1510                 :            :     &odict_as_mapping,                          /* tp_as_mapping */
        1511                 :            :     0,                                          /* tp_hash */
        1512                 :            :     0,                                          /* tp_call */
        1513                 :            :     0,                                          /* tp_str */
        1514                 :            :     0,                                          /* tp_getattro */
        1515                 :            :     0,                                          /* tp_setattro */
        1516                 :            :     0,                                          /* tp_as_buffer */
        1517                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */
        1518                 :            :     odict_doc,                                  /* tp_doc */
        1519                 :            :     (traverseproc)odict_traverse,               /* tp_traverse */
        1520                 :            :     (inquiry)odict_tp_clear,                    /* tp_clear */
        1521                 :            :     (richcmpfunc)odict_richcompare,             /* tp_richcompare */
        1522                 :            :     offsetof(PyODictObject, od_weakreflist),    /* tp_weaklistoffset */
        1523                 :            :     (getiterfunc)odict_iter,                    /* tp_iter */
        1524                 :            :     0,                                          /* tp_iternext */
        1525                 :            :     odict_methods,                              /* tp_methods */
        1526                 :            :     0,                                          /* tp_members */
        1527                 :            :     odict_getset,                               /* tp_getset */
        1528                 :            :     &PyDict_Type,                               /* tp_base */
        1529                 :            :     0,                                          /* tp_dict */
        1530                 :            :     0,                                          /* tp_descr_get */
        1531                 :            :     0,                                          /* tp_descr_set */
        1532                 :            :     offsetof(PyODictObject, od_inst_dict),      /* tp_dictoffset */
        1533                 :            :     (initproc)odict_init,                       /* tp_init */
        1534                 :            :     PyType_GenericAlloc,                        /* tp_alloc */
        1535                 :            :     0,                                          /* tp_new */
        1536                 :            :     0,                                          /* tp_free */
        1537                 :            : };
        1538                 :            :
        1539                 :            :
        1540                 :            : /* ----------------------------------------------
        1541                 :            :  * the public OrderedDict API
        1542                 :            :  */
        1543                 :            :
        1544                 :            : PyObject *
        1545                 :          0 : PyODict_New(void)
        1546                 :            : {
        1547                 :          0 :     return PyDict_Type.tp_new(&PyODict_Type, NULL, NULL);
        1548                 :            : }
        1549                 :            :
        1550                 :            : static int
        1551                 :          0 : _PyODict_SetItem_KnownHash(PyObject *od, PyObject *key, PyObject *value,
        1552                 :            :                            Py_hash_t hash)
        1553                 :            : {
        1554                 :          0 :     int res = _PyDict_SetItem_KnownHash(od, key, value, hash);
        1555         [ #  # ]:          0 :     if (res == 0) {
        1556                 :          0 :         res = _odict_add_new_node((PyODictObject *)od, key, hash);
        1557         [ #  # ]:          0 :         if (res < 0) {
        1558                 :            :             /* Revert setting the value on the dict */
        1559                 :          0 :             PyObject *exc = PyErr_GetRaisedException();
        1560                 :          0 :             (void) _PyDict_DelItem_KnownHash(od, key, hash);
        1561                 :          0 :             _PyErr_ChainExceptions1(exc);
        1562                 :            :         }
        1563                 :            :     }
        1564                 :          0 :     return res;
        1565                 :            : }
        1566                 :            :
        1567                 :            : int
        1568                 :          0 : PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value)
        1569                 :            : {
        1570                 :          0 :     Py_hash_t hash = PyObject_Hash(key);
        1571         [ #  # ]:          0 :     if (hash == -1)
        1572                 :          0 :         return -1;
        1573                 :          0 :     return _PyODict_SetItem_KnownHash(od, key, value, hash);
        1574                 :            : }
        1575                 :            :
        1576                 :            : int
        1577                 :          0 : PyODict_DelItem(PyObject *od, PyObject *key)
        1578                 :            : {
        1579                 :            :     int res;
        1580                 :          0 :     Py_hash_t hash = PyObject_Hash(key);
        1581         [ #  # ]:          0 :     if (hash == -1)
        1582                 :          0 :         return -1;
        1583                 :          0 :     res = _odict_clear_node((PyODictObject *)od, NULL, key, hash);
        1584         [ #  # ]:          0 :     if (res < 0)
        1585                 :          0 :         return -1;
        1586                 :          0 :     return _PyDict_DelItem_KnownHash(od, key, hash);
        1587                 :            : }
        1588                 :            :
        1589                 :            :
        1590                 :            : /* -------------------------------------------
        1591                 :            :  * The OrderedDict views (keys/values/items)
        1592                 :            :  */
        1593                 :            :
        1594                 :            : typedef struct {
        1595                 :            :     PyObject_HEAD
        1596                 :            :     int kind;
        1597                 :            :     PyODictObject *di_odict;
        1598                 :            :     Py_ssize_t di_size;
        1599                 :            :     size_t di_state;
        1600                 :            :     PyObject *di_current;
        1601                 :            :     PyObject *di_result; /* reusable result tuple for iteritems */
        1602                 :            : } odictiterobject;
        1603                 :            :
        1604                 :            : static void
        1605                 :          0 : odictiter_dealloc(odictiterobject *di)
        1606                 :            : {
        1607                 :          0 :     _PyObject_GC_UNTRACK(di);
        1608                 :          0 :     Py_XDECREF(di->di_odict);
        1609                 :          0 :     Py_XDECREF(di->di_current);
        1610         [ #  # ]:          0 :     if ((di->kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) {
        1611                 :          0 :         Py_DECREF(di->di_result);
        1612                 :            :     }
        1613                 :          0 :     PyObject_GC_Del(di);
        1614                 :          0 : }
        1615                 :            :
        1616                 :            : static int
        1617                 :          0 : odictiter_traverse(odictiterobject *di, visitproc visit, void *arg)
        1618                 :            : {
        1619   [ #  #  #  # ]:          0 :     Py_VISIT(di->di_odict);
        1620   [ #  #  #  # ]:          0 :     Py_VISIT(di->di_current);  /* A key could be any type, not just str. */
        1621   [ #  #  #  # ]:          0 :     Py_VISIT(di->di_result);
        1622                 :          0 :     return 0;
        1623                 :            : }
        1624                 :            :
        1625                 :            : /* In order to protect against modifications during iteration, we track
        1626                 :            :  * the current key instead of the current node. */
        1627                 :            : static PyObject *
        1628                 :          0 : odictiter_nextkey(odictiterobject *di)
        1629                 :            : {
        1630                 :          0 :     PyObject *key = NULL;
        1631                 :            :     _ODictNode *node;
        1632                 :          0 :     int reversed = di->kind & _odict_ITER_REVERSED;
        1633                 :            :
        1634         [ #  # ]:          0 :     if (di->di_odict == NULL)
        1635                 :          0 :         return NULL;
        1636         [ #  # ]:          0 :     if (di->di_current == NULL)
        1637                 :          0 :         goto done;  /* We're already done. */
        1638                 :            :
        1639                 :            :     /* Check for unsupported changes. */
        1640         [ #  # ]:          0 :     if (di->di_odict->od_state != di->di_state) {
        1641                 :          0 :         PyErr_SetString(PyExc_RuntimeError,
        1642                 :            :                         "OrderedDict mutated during iteration");
        1643                 :          0 :         goto done;
        1644                 :            :     }
        1645         [ #  # ]:          0 :     if (di->di_size != PyODict_SIZE(di->di_odict)) {
        1646                 :          0 :         PyErr_SetString(PyExc_RuntimeError,
        1647                 :            :                         "OrderedDict changed size during iteration");
        1648                 :          0 :         di->di_size = -1; /* Make this state sticky */
        1649                 :          0 :         return NULL;
        1650                 :            :     }
        1651                 :            :
        1652                 :            :     /* Get the key. */
        1653                 :          0 :     node = _odict_find_node(di->di_odict, di->di_current);
        1654         [ #  # ]:          0 :     if (node == NULL) {
        1655         [ #  # ]:          0 :         if (!PyErr_Occurred())
        1656                 :          0 :             PyErr_SetObject(PyExc_KeyError, di->di_current);
        1657                 :            :         /* Must have been deleted. */
        1658         [ #  # ]:          0 :         Py_CLEAR(di->di_current);
        1659                 :          0 :         return NULL;
        1660                 :            :     }
        1661                 :          0 :     key = di->di_current;
        1662                 :            :
        1663                 :            :     /* Advance to the next key. */
        1664         [ #  # ]:          0 :     node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
        1665         [ #  # ]:          0 :     if (node == NULL) {
        1666                 :            :         /* Reached the end. */
        1667                 :          0 :         di->di_current = NULL;
        1668                 :            :     }
        1669                 :            :     else {
        1670                 :          0 :         di->di_current = Py_NewRef(_odictnode_KEY(node));
        1671                 :            :     }
        1672                 :            :
        1673                 :          0 :     return key;
        1674                 :            :
        1675                 :          0 : done:
        1676         [ #  # ]:          0 :     Py_CLEAR(di->di_odict);
        1677                 :          0 :     return key;
        1678                 :            : }
        1679                 :            :
        1680                 :            : static PyObject *
        1681                 :          0 : odictiter_iternext(odictiterobject *di)
        1682                 :            : {
        1683                 :            :     PyObject *result, *value;
        1684                 :          0 :     PyObject *key = odictiter_nextkey(di);  /* new reference */
        1685                 :            :
        1686         [ #  # ]:          0 :     if (key == NULL)
        1687                 :          0 :         return NULL;
        1688                 :            :
        1689                 :            :     /* Handle the keys case. */
        1690         [ #  # ]:          0 :     if (! (di->kind & _odict_ITER_VALUES)) {
        1691                 :          0 :         return key;
        1692                 :            :     }
        1693                 :            :
        1694                 :          0 :     value = PyODict_GetItem((PyObject *)di->di_odict, key);  /* borrowed */
        1695         [ #  # ]:          0 :     if (value == NULL) {
        1696         [ #  # ]:          0 :         if (!PyErr_Occurred())
        1697                 :          0 :             PyErr_SetObject(PyExc_KeyError, key);
        1698                 :          0 :         Py_DECREF(key);
        1699                 :          0 :         goto done;
        1700                 :            :     }
        1701                 :          0 :     Py_INCREF(value);
        1702                 :            :
        1703                 :            :     /* Handle the values case. */
        1704         [ #  # ]:          0 :     if (!(di->kind & _odict_ITER_KEYS)) {
        1705                 :          0 :         Py_DECREF(key);
        1706                 :          0 :         return value;
        1707                 :            :     }
        1708                 :            :
        1709                 :            :     /* Handle the items case. */
        1710                 :          0 :     result = di->di_result;
        1711                 :            :
        1712         [ #  # ]:          0 :     if (Py_REFCNT(result) == 1) {
        1713                 :            :         /* not in use so we can reuse it
        1714                 :            :          * (the common case during iteration) */
        1715                 :          0 :         Py_INCREF(result);
        1716                 :          0 :         Py_DECREF(PyTuple_GET_ITEM(result, 0));  /* borrowed */
        1717                 :          0 :         Py_DECREF(PyTuple_GET_ITEM(result, 1));  /* borrowed */
        1718                 :            :         // bpo-42536: The GC may have untracked this result tuple. Since we're
        1719                 :            :         // recycling it, make sure it's tracked again:
        1720         [ #  # ]:          0 :         if (!_PyObject_GC_IS_TRACKED(result)) {
        1721                 :          0 :             _PyObject_GC_TRACK(result);
        1722                 :            :         }
        1723                 :            :     }
        1724                 :            :     else {
        1725                 :          0 :         result = PyTuple_New(2);
        1726         [ #  # ]:          0 :         if (result == NULL) {
        1727                 :          0 :             Py_DECREF(key);
        1728                 :          0 :             Py_DECREF(value);
        1729                 :          0 :             goto done;
        1730                 :            :         }
        1731                 :            :     }
        1732                 :            :
        1733                 :          0 :     PyTuple_SET_ITEM(result, 0, key);  /* steals reference */
        1734                 :          0 :     PyTuple_SET_ITEM(result, 1, value);  /* steals reference */
        1735                 :          0 :     return result;
        1736                 :            :
        1737                 :          0 : done:
        1738         [ #  # ]:          0 :     Py_CLEAR(di->di_current);
        1739         [ #  # ]:          0 :     Py_CLEAR(di->di_odict);
        1740                 :          0 :     return NULL;
        1741                 :            : }
        1742                 :            :
        1743                 :            : /* No need for tp_clear because odictiterobject is not mutable. */
        1744                 :            :
        1745                 :            : PyDoc_STRVAR(reduce_doc, "Return state information for pickling");
        1746                 :            :
        1747                 :            : static PyObject *
        1748                 :          0 : odictiter_reduce(odictiterobject *di, PyObject *Py_UNUSED(ignored))
        1749                 :            : {
        1750                 :            :     /* copy the iterator state */
        1751                 :          0 :     odictiterobject tmp = *di;
        1752                 :          0 :     Py_XINCREF(tmp.di_odict);
        1753                 :          0 :     Py_XINCREF(tmp.di_current);
        1754                 :            :
        1755                 :            :     /* iterate the temporary into a list */
        1756                 :          0 :     PyObject *list = PySequence_List((PyObject*)&tmp);
        1757                 :          0 :     Py_XDECREF(tmp.di_odict);
        1758                 :          0 :     Py_XDECREF(tmp.di_current);
        1759         [ #  # ]:          0 :     if (list == NULL) {
        1760                 :          0 :         return NULL;
        1761                 :            :     }
        1762                 :          0 :     return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(iter)), list);
        1763                 :            : }
        1764                 :            :
        1765                 :            : static PyMethodDef odictiter_methods[] = {
        1766                 :            :     {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc},
        1767                 :            :     {NULL,              NULL}           /* sentinel */
        1768                 :            : };
        1769                 :            :
        1770                 :            : PyTypeObject PyODictIter_Type = {
        1771                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        1772                 :            :     "odict_iterator",                         /* tp_name */
        1773                 :            :     sizeof(odictiterobject),                  /* tp_basicsize */
        1774                 :            :     0,                                        /* tp_itemsize */
        1775                 :            :     /* methods */
        1776                 :            :     (destructor)odictiter_dealloc,            /* tp_dealloc */
        1777                 :            :     0,                                        /* tp_vectorcall_offset */
        1778                 :            :     0,                                        /* tp_getattr */
        1779                 :            :     0,                                        /* tp_setattr */
        1780                 :            :     0,                                        /* tp_as_async */
        1781                 :            :     0,                                        /* tp_repr */
        1782                 :            :     0,                                        /* tp_as_number */
        1783                 :            :     0,                                        /* tp_as_sequence */
        1784                 :            :     0,                                        /* tp_as_mapping */
        1785                 :            :     0,                                        /* tp_hash */
        1786                 :            :     0,                                        /* tp_call */
        1787                 :            :     0,                                        /* tp_str */
        1788                 :            :     PyObject_GenericGetAttr,                  /* tp_getattro */
        1789                 :            :     0,                                        /* tp_setattro */
        1790                 :            :     0,                                        /* tp_as_buffer */
        1791                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,  /* tp_flags */
        1792                 :            :     0,                                        /* tp_doc */
        1793                 :            :     (traverseproc)odictiter_traverse,         /* tp_traverse */
        1794                 :            :     0,                                        /* tp_clear */
        1795                 :            :     0,                                        /* tp_richcompare */
        1796                 :            :     0,                                        /* tp_weaklistoffset */
        1797                 :            :     PyObject_SelfIter,                        /* tp_iter */
        1798                 :            :     (iternextfunc)odictiter_iternext,         /* tp_iternext */
        1799                 :            :     odictiter_methods,                        /* tp_methods */
        1800                 :            :     0,
        1801                 :            : };
        1802                 :            :
        1803                 :            : static PyObject *
        1804                 :          0 : odictiter_new(PyODictObject *od, int kind)
        1805                 :            : {
        1806                 :            :     odictiterobject *di;
        1807                 :            :     _ODictNode *node;
        1808                 :          0 :     int reversed = kind & _odict_ITER_REVERSED;
        1809                 :            :
        1810                 :          0 :     di = PyObject_GC_New(odictiterobject, &PyODictIter_Type);
        1811         [ #  # ]:          0 :     if (di == NULL)
        1812                 :          0 :         return NULL;
        1813                 :            :
        1814         [ #  # ]:          0 :     if ((kind & _odict_ITER_ITEMS) == _odict_ITER_ITEMS) {
        1815                 :          0 :         di->di_result = PyTuple_Pack(2, Py_None, Py_None);
        1816         [ #  # ]:          0 :         if (di->di_result == NULL) {
        1817                 :          0 :             Py_DECREF(di);
        1818                 :          0 :             return NULL;
        1819                 :            :         }
        1820                 :            :     }
        1821                 :            :     else {
        1822                 :          0 :         di->di_result = NULL;
        1823                 :            :     }
        1824                 :            :
        1825                 :          0 :     di->kind = kind;
        1826         [ #  # ]:          0 :     node = reversed ? _odict_LAST(od) : _odict_FIRST(od);
        1827         [ #  # ]:          0 :     di->di_current = node ? Py_NewRef(_odictnode_KEY(node)) : NULL;
        1828                 :          0 :     di->di_size = PyODict_SIZE(od);
        1829                 :          0 :     di->di_state = od->od_state;
        1830                 :          0 :     di->di_odict = (PyODictObject*)Py_NewRef(od);
        1831                 :            :
        1832                 :          0 :     _PyObject_GC_TRACK(di);
        1833                 :          0 :     return (PyObject *)di;
        1834                 :            : }
        1835                 :            :
        1836                 :            : /* keys() */
        1837                 :            :
        1838                 :            : static PyObject *
        1839                 :          0 : odictkeys_iter(_PyDictViewObject *dv)
        1840                 :            : {
        1841         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1842                 :          0 :         Py_RETURN_NONE;
        1843                 :            :     }
        1844                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1845                 :            :             _odict_ITER_KEYS);
        1846                 :            : }
        1847                 :            :
        1848                 :            : static PyObject *
        1849                 :          0 : odictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
        1850                 :            : {
        1851         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1852                 :          0 :         Py_RETURN_NONE;
        1853                 :            :     }
        1854                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1855                 :            :             _odict_ITER_KEYS|_odict_ITER_REVERSED);
        1856                 :            : }
        1857                 :            :
        1858                 :            : static PyMethodDef odictkeys_methods[] = {
        1859                 :            :     {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL},
        1860                 :            :     {NULL,          NULL}           /* sentinel */
        1861                 :            : };
        1862                 :            :
        1863                 :            : PyTypeObject PyODictKeys_Type = {
        1864                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        1865                 :            :     "odict_keys",                             /* tp_name */
        1866                 :            :     0,                                        /* tp_basicsize */
        1867                 :            :     0,                                        /* tp_itemsize */
        1868                 :            :     0,                                        /* tp_dealloc */
        1869                 :            :     0,                                        /* tp_vectorcall_offset */
        1870                 :            :     0,                                        /* tp_getattr */
        1871                 :            :     0,                                        /* tp_setattr */
        1872                 :            :     0,                                        /* tp_as_async */
        1873                 :            :     0,                                        /* tp_repr */
        1874                 :            :     0,                                        /* tp_as_number */
        1875                 :            :     0,                                        /* tp_as_sequence */
        1876                 :            :     0,                                        /* tp_as_mapping */
        1877                 :            :     0,                                        /* tp_hash */
        1878                 :            :     0,                                        /* tp_call */
        1879                 :            :     0,                                        /* tp_str */
        1880                 :            :     0,                                        /* tp_getattro */
        1881                 :            :     0,                                        /* tp_setattro */
        1882                 :            :     0,                                        /* tp_as_buffer */
        1883                 :            :     0,                                        /* tp_flags */
        1884                 :            :     0,                                        /* tp_doc */
        1885                 :            :     0,                                        /* tp_traverse */
        1886                 :            :     0,                                        /* tp_clear */
        1887                 :            :     0,                                        /* tp_richcompare */
        1888                 :            :     0,                                        /* tp_weaklistoffset */
        1889                 :            :     (getiterfunc)odictkeys_iter,              /* tp_iter */
        1890                 :            :     0,                                        /* tp_iternext */
        1891                 :            :     odictkeys_methods,                        /* tp_methods */
        1892                 :            :     0,                                        /* tp_members */
        1893                 :            :     0,                                        /* tp_getset */
        1894                 :            :     &PyDictKeys_Type,                         /* tp_base */
        1895                 :            : };
        1896                 :            :
        1897                 :            : static PyObject *
        1898                 :          0 : odictkeys_new(PyObject *od, PyObject *Py_UNUSED(ignored))
        1899                 :            : {
        1900                 :          0 :     return _PyDictView_New(od, &PyODictKeys_Type);
        1901                 :            : }
        1902                 :            :
        1903                 :            : /* items() */
        1904                 :            :
        1905                 :            : static PyObject *
        1906                 :          0 : odictitems_iter(_PyDictViewObject *dv)
        1907                 :            : {
        1908         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1909                 :          0 :         Py_RETURN_NONE;
        1910                 :            :     }
        1911                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1912                 :            :             _odict_ITER_KEYS|_odict_ITER_VALUES);
        1913                 :            : }
        1914                 :            :
        1915                 :            : static PyObject *
        1916                 :          0 : odictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
        1917                 :            : {
        1918         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1919                 :          0 :         Py_RETURN_NONE;
        1920                 :            :     }
        1921                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1922                 :            :             _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED);
        1923                 :            : }
        1924                 :            :
        1925                 :            : static PyMethodDef odictitems_methods[] = {
        1926                 :            :     {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL},
        1927                 :            :     {NULL,          NULL}           /* sentinel */
        1928                 :            : };
        1929                 :            :
        1930                 :            : PyTypeObject PyODictItems_Type = {
        1931                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        1932                 :            :     "odict_items",                            /* tp_name */
        1933                 :            :     0,                                        /* tp_basicsize */
        1934                 :            :     0,                                        /* tp_itemsize */
        1935                 :            :     0,                                        /* tp_dealloc */
        1936                 :            :     0,                                        /* tp_vectorcall_offset */
        1937                 :            :     0,                                        /* tp_getattr */
        1938                 :            :     0,                                        /* tp_setattr */
        1939                 :            :     0,                                        /* tp_as_async */
        1940                 :            :     0,                                        /* tp_repr */
        1941                 :            :     0,                                        /* tp_as_number */
        1942                 :            :     0,                                        /* tp_as_sequence */
        1943                 :            :     0,                                        /* tp_as_mapping */
        1944                 :            :     0,                                        /* tp_hash */
        1945                 :            :     0,                                        /* tp_call */
        1946                 :            :     0,                                        /* tp_str */
        1947                 :            :     0,                                        /* tp_getattro */
        1948                 :            :     0,                                        /* tp_setattro */
        1949                 :            :     0,                                        /* tp_as_buffer */
        1950                 :            :     0,                                        /* tp_flags */
        1951                 :            :     0,                                        /* tp_doc */
        1952                 :            :     0,                                        /* tp_traverse */
        1953                 :            :     0,                                        /* tp_clear */
        1954                 :            :     0,                                        /* tp_richcompare */
        1955                 :            :     0,                                        /* tp_weaklistoffset */
        1956                 :            :     (getiterfunc)odictitems_iter,             /* tp_iter */
        1957                 :            :     0,                                        /* tp_iternext */
        1958                 :            :     odictitems_methods,                       /* tp_methods */
        1959                 :            :     0,                                        /* tp_members */
        1960                 :            :     0,                                        /* tp_getset */
        1961                 :            :     &PyDictItems_Type,                        /* tp_base */
        1962                 :            : };
        1963                 :            :
        1964                 :            : static PyObject *
        1965                 :          0 : odictitems_new(PyObject *od, PyObject *Py_UNUSED(ignored))
        1966                 :            : {
        1967                 :          0 :     return _PyDictView_New(od, &PyODictItems_Type);
        1968                 :            : }
        1969                 :            :
        1970                 :            : /* values() */
        1971                 :            :
        1972                 :            : static PyObject *
        1973                 :          0 : odictvalues_iter(_PyDictViewObject *dv)
        1974                 :            : {
        1975         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1976                 :          0 :         Py_RETURN_NONE;
        1977                 :            :     }
        1978                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1979                 :            :             _odict_ITER_VALUES);
        1980                 :            : }
        1981                 :            :
        1982                 :            : static PyObject *
        1983                 :          0 : odictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored))
        1984                 :            : {
        1985         [ #  # ]:          0 :     if (dv->dv_dict == NULL) {
        1986                 :          0 :         Py_RETURN_NONE;
        1987                 :            :     }
        1988                 :          0 :     return odictiter_new((PyODictObject *)dv->dv_dict,
        1989                 :            :             _odict_ITER_VALUES|_odict_ITER_REVERSED);
        1990                 :            : }
        1991                 :            :
        1992                 :            : static PyMethodDef odictvalues_methods[] = {
        1993                 :            :     {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL},
        1994                 :            :     {NULL,          NULL}           /* sentinel */
        1995                 :            : };
        1996                 :            :
        1997                 :            : PyTypeObject PyODictValues_Type = {
        1998                 :            :     PyVarObject_HEAD_INIT(&PyType_Type, 0)
        1999                 :            :     "odict_values",                           /* tp_name */
        2000                 :            :     0,                                        /* tp_basicsize */
        2001                 :            :     0,                                        /* tp_itemsize */
        2002                 :            :     0,                                        /* tp_dealloc */
        2003                 :            :     0,                                        /* tp_vectorcall_offset */
        2004                 :            :     0,                                        /* tp_getattr */
        2005                 :            :     0,                                        /* tp_setattr */
        2006                 :            :     0,                                        /* tp_as_async */
        2007                 :            :     0,                                        /* tp_repr */
        2008                 :            :     0,                                        /* tp_as_number */
        2009                 :            :     0,                                        /* tp_as_sequence */
        2010                 :            :     0,                                        /* tp_as_mapping */
        2011                 :            :     0,                                        /* tp_hash */
        2012                 :            :     0,                                        /* tp_call */
        2013                 :            :     0,                                        /* tp_str */
        2014                 :            :     0,                                        /* tp_getattro */
        2015                 :            :     0,                                        /* tp_setattro */
        2016                 :            :     0,                                        /* tp_as_buffer */
        2017                 :            :     0,                                        /* tp_flags */
        2018                 :            :     0,                                        /* tp_doc */
        2019                 :            :     0,                                        /* tp_traverse */
        2020                 :            :     0,                                        /* tp_clear */
        2021                 :            :     0,                                        /* tp_richcompare */
        2022                 :            :     0,                                        /* tp_weaklistoffset */
        2023                 :            :     (getiterfunc)odictvalues_iter,            /* tp_iter */
        2024                 :            :     0,                                        /* tp_iternext */
        2025                 :            :     odictvalues_methods,                      /* tp_methods */
        2026                 :            :     0,                                        /* tp_members */
        2027                 :            :     0,                                        /* tp_getset */
        2028                 :            :     &PyDictValues_Type,                       /* tp_base */
        2029                 :            : };
        2030                 :            :
        2031                 :            : static PyObject *
        2032                 :          0 : odictvalues_new(PyObject *od, PyObject *Py_UNUSED(ignored))
        2033                 :            : {
        2034                 :          0 :     return _PyDictView_New(od, &PyODictValues_Type);
        2035                 :            : }
        2036                 :            :
        2037                 :            :
        2038                 :            : /* ----------------------------------------------
        2039                 :            :    MutableMapping implementations
        2040                 :            :
        2041                 :            : Mapping:
        2042                 :            :
        2043                 :            : ============ ===========
        2044                 :            : method       uses
        2045                 :            : ============ ===========
        2046                 :            : __contains__ __getitem__
        2047                 :            : __eq__       items
        2048                 :            : __getitem__  +
        2049                 :            : __iter__     +
        2050                 :            : __len__      +
        2051                 :            : __ne__       __eq__
        2052                 :            : get          __getitem__
        2053                 :            : items        ItemsView
        2054                 :            : keys         KeysView
        2055                 :            : values       ValuesView
        2056                 :            : ============ ===========
        2057                 :            :
        2058                 :            : ItemsView uses __len__, __iter__, and __getitem__.
        2059                 :            : KeysView uses __len__, __iter__, and __contains__.
        2060                 :            : ValuesView uses __len__, __iter__, and __getitem__.
        2061                 :            :
        2062                 :            : MutableMapping:
        2063                 :            :
        2064                 :            : ============ ===========
        2065                 :            : method       uses
        2066                 :            : ============ ===========
        2067                 :            : __delitem__  +
        2068                 :            : __setitem__  +
        2069                 :            : clear        popitem
        2070                 :            : pop          __getitem__
        2071                 :            :              __delitem__
        2072                 :            : popitem      __iter__
        2073                 :            :              _getitem__
        2074                 :            :              __delitem__
        2075                 :            : setdefault   __getitem__
        2076                 :            :              __setitem__
        2077                 :            : update       __setitem__
        2078                 :            : ============ ===========
        2079                 :            : */
        2080                 :            :
        2081                 :            : static int
        2082                 :          0 : mutablemapping_add_pairs(PyObject *self, PyObject *pairs)
        2083                 :            : {
        2084                 :            :     PyObject *pair, *iterator, *unexpected;
        2085                 :          0 :     int res = 0;
        2086                 :            :
        2087                 :          0 :     iterator = PyObject_GetIter(pairs);
        2088         [ #  # ]:          0 :     if (iterator == NULL)
        2089                 :          0 :         return -1;
        2090                 :          0 :     PyErr_Clear();
        2091                 :            :
        2092         [ #  # ]:          0 :     while ((pair = PyIter_Next(iterator)) != NULL) {
        2093                 :            :         /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */
        2094                 :          0 :         PyObject *key = NULL, *value = NULL;
        2095                 :          0 :         PyObject *pair_iterator = PyObject_GetIter(pair);
        2096         [ #  # ]:          0 :         if (pair_iterator == NULL)
        2097                 :          0 :             goto Done;
        2098                 :            :
        2099                 :          0 :         key = PyIter_Next(pair_iterator);
        2100         [ #  # ]:          0 :         if (key == NULL) {
        2101         [ #  # ]:          0 :             if (!PyErr_Occurred())
        2102                 :          0 :                 PyErr_SetString(PyExc_ValueError,
        2103                 :            :                                 "need more than 0 values to unpack");
        2104                 :          0 :             goto Done;
        2105                 :            :         }
        2106                 :            :
        2107                 :          0 :         value = PyIter_Next(pair_iterator);
        2108         [ #  # ]:          0 :         if (value == NULL) {
        2109         [ #  # ]:          0 :             if (!PyErr_Occurred())
        2110                 :          0 :                 PyErr_SetString(PyExc_ValueError,
        2111                 :            :                                 "need more than 1 value to unpack");
        2112                 :          0 :             goto Done;
        2113                 :            :         }
        2114                 :            :
        2115                 :          0 :         unexpected = PyIter_Next(pair_iterator);
        2116         [ #  # ]:          0 :         if (unexpected != NULL) {
        2117                 :          0 :             Py_DECREF(unexpected);
        2118                 :          0 :             PyErr_SetString(PyExc_ValueError,
        2119                 :            :                             "too many values to unpack (expected 2)");
        2120                 :          0 :             goto Done;
        2121                 :            :         }
        2122         [ #  # ]:          0 :         else if (PyErr_Occurred())
        2123                 :          0 :             goto Done;
        2124                 :            :
        2125                 :          0 :         res = PyObject_SetItem(self, key, value);
        2126                 :            :
        2127                 :          0 : Done:
        2128                 :          0 :         Py_DECREF(pair);
        2129                 :          0 :         Py_XDECREF(pair_iterator);
        2130                 :          0 :         Py_XDECREF(key);
        2131                 :          0 :         Py_XDECREF(value);
        2132         [ #  # ]:          0 :         if (PyErr_Occurred())
        2133                 :          0 :             break;
        2134                 :            :     }
        2135                 :          0 :     Py_DECREF(iterator);
        2136                 :            :
        2137   [ #  #  #  # ]:          0 :     if (res < 0 || PyErr_Occurred() != NULL)
        2138                 :          0 :         return -1;
        2139                 :            :     else
        2140                 :          0 :         return 0;
        2141                 :            : }
        2142                 :            :
        2143                 :            : static int
        2144                 :          0 : mutablemapping_update_arg(PyObject *self, PyObject *arg)
        2145                 :            : {
        2146                 :          0 :     int res = 0;
        2147         [ #  # ]:          0 :     if (PyDict_CheckExact(arg)) {
        2148                 :          0 :         PyObject *items = PyDict_Items(arg);
        2149         [ #  # ]:          0 :         if (items == NULL) {
        2150                 :          0 :             return -1;
        2151                 :            :         }
        2152                 :          0 :         res = mutablemapping_add_pairs(self, items);
        2153                 :          0 :         Py_DECREF(items);
        2154                 :          0 :         return res;
        2155                 :            :     }
        2156                 :            :     PyObject *func;
        2157         [ #  # ]:          0 :     if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) {
        2158                 :          0 :         return -1;
        2159                 :            :     }
        2160         [ #  # ]:          0 :     if (func != NULL) {
        2161                 :          0 :         PyObject *keys = _PyObject_CallNoArgs(func);
        2162                 :          0 :         Py_DECREF(func);
        2163         [ #  # ]:          0 :         if (keys == NULL) {
        2164                 :          0 :             return -1;
        2165                 :            :         }
        2166                 :          0 :         PyObject *iterator = PyObject_GetIter(keys);
        2167                 :          0 :         Py_DECREF(keys);
        2168         [ #  # ]:          0 :         if (iterator == NULL) {
        2169                 :          0 :             return -1;
        2170                 :            :         }
        2171                 :            :         PyObject *key;
        2172   [ #  #  #  # ]:          0 :         while (res == 0 && (key = PyIter_Next(iterator))) {
        2173                 :          0 :             PyObject *value = PyObject_GetItem(arg, key);
        2174         [ #  # ]:          0 :             if (value != NULL) {
        2175                 :          0 :                 res = PyObject_SetItem(self, key, value);
        2176                 :          0 :                 Py_DECREF(value);
        2177                 :            :             }
        2178                 :            :             else {
        2179                 :          0 :                 res = -1;
        2180                 :            :             }
        2181                 :          0 :             Py_DECREF(key);
        2182                 :            :         }
        2183                 :          0 :         Py_DECREF(iterator);
        2184   [ #  #  #  # ]:          0 :         if (res != 0 || PyErr_Occurred()) {
        2185                 :          0 :             return -1;
        2186                 :            :         }
        2187                 :          0 :         return 0;
        2188                 :            :     }
        2189         [ #  # ]:          0 :     if (_PyObject_LookupAttr(arg, &_Py_ID(items), &func) < 0) {
        2190                 :          0 :         return -1;
        2191                 :            :     }
        2192         [ #  # ]:          0 :     if (func != NULL) {
        2193                 :          0 :         PyObject *items = _PyObject_CallNoArgs(func);
        2194                 :          0 :         Py_DECREF(func);
        2195         [ #  # ]:          0 :         if (items == NULL) {
        2196                 :          0 :             return -1;
        2197                 :            :         }
        2198                 :          0 :         res = mutablemapping_add_pairs(self, items);
        2199                 :          0 :         Py_DECREF(items);
        2200                 :          0 :         return res;
        2201                 :            :     }
        2202                 :          0 :     res = mutablemapping_add_pairs(self, arg);
        2203                 :          0 :     return res;
        2204                 :            : }
        2205                 :            :
        2206                 :            : static PyObject *
        2207                 :          0 : mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs)
        2208                 :            : {
        2209                 :            :     int res;
        2210                 :            :     /* first handle args, if any */
        2211                 :            :     assert(args == NULL || PyTuple_Check(args));
        2212         [ #  # ]:          0 :     Py_ssize_t len = (args != NULL) ? PyTuple_GET_SIZE(args) : 0;
        2213         [ #  # ]:          0 :     if (len > 1) {
        2214                 :          0 :         const char *msg = "update() takes at most 1 positional argument (%zd given)";
        2215                 :          0 :         PyErr_Format(PyExc_TypeError, msg, len);
        2216                 :          0 :         return NULL;
        2217                 :            :     }
        2218                 :            :
        2219         [ #  # ]:          0 :     if (len) {
        2220                 :          0 :         PyObject *other = PyTuple_GET_ITEM(args, 0);  /* borrowed reference */
        2221                 :            :         assert(other != NULL);
        2222                 :          0 :         Py_INCREF(other);
        2223                 :          0 :         res = mutablemapping_update_arg(self, other);
        2224                 :          0 :         Py_DECREF(other);
        2225         [ #  # ]:          0 :         if (res < 0) {
        2226                 :          0 :             return NULL;
        2227                 :            :         }
        2228                 :            :     }
        2229                 :            :
        2230                 :            :     /* now handle kwargs */
        2231                 :            :     assert(kwargs == NULL || PyDict_Check(kwargs));
        2232   [ #  #  #  # ]:          0 :     if (kwargs != NULL && PyDict_GET_SIZE(kwargs)) {
        2233                 :          0 :         PyObject *items = PyDict_Items(kwargs);
        2234         [ #  # ]:          0 :         if (items == NULL)
        2235                 :          0 :             return NULL;
        2236                 :          0 :         res = mutablemapping_add_pairs(self, items);
        2237                 :          0 :         Py_DECREF(items);
        2238         [ #  # ]:          0 :         if (res == -1)
        2239                 :          0 :             return NULL;
        2240                 :            :     }
        2241                 :            :
        2242                 :          0 :     Py_RETURN_NONE;
        2243                 :            : }

Generated by: LCOV version 1.14