Python code coverage for Objects/odictobject.c

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