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