ยปCore Development>Code coverage>Objects/odictobject.c

Python code coverage for Objects/odictobject.c

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