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