Debian Codegraph @

src/frozendict/c_src/3_7/frozendictobject.c

raw
1 #include <Python.h>
2 #include "frozendictobject.h"
3 static PyObject* frozendict_iter(PyDictObject *dict);
4 static int frozendict_equal(PyDictObject* a, PyDictObject* b);
5 #include "other.c"
6 #include "dictobject.c"
7
8 static void
9 frozendict_free_keys_object(PyDictKeysObject *keys, const int decref_items)
10 {
11 if (decref_items) {
12 PyDictKeyEntry *entries = DK_ENTRIES(keys);
13 Py_ssize_t i, n;
14 for (i = 0, n = keys->dk_nentries; i < n; i++) {
15 Py_XDECREF(entries[i].me_key);
16 Py_XDECREF(entries[i].me_value);
17 }
18 }
19
20 #if PyDict_MAXFREELIST > 0
21 if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
22 keys_free_list[numfreekeys++] = keys;
23 return;
24 }
25 #endif
26 PyObject_Free(keys);
27 }
28
29 static inline void
30 frozendict_keys_decref(PyDictKeysObject *dk, const int decref_items)
31 {
32 assert(dk->dk_refcnt > 0);
33 #ifdef Py_REF_DEBUG
34 _Py_RefTotal--;
35 #endif
36 if (--dk->dk_refcnt == 0) {
37 frozendict_free_keys_object(dk, decref_items);
38 }
39 }
40
41 static int frozendict_resize(PyDictObject* mp, Py_ssize_t minsize) {
42 const Py_ssize_t newsize = calculate_keysize(minsize);
43
44 if (newsize <= 0) {
45 PyErr_NoMemory();
46 return -1;
47 }
48
49 assert(IS_POWER_OF_2(newsize));
50 assert(newsize >= PyDict_MINSIZE);
51
52 PyDictKeysObject* oldkeys = mp->ma_keys;
53
54 /* Allocate a new table. */
55 PyDictKeysObject* new_keys = new_keys_object(newsize);
56
57 if (new_keys == NULL) {
58 return -1;
59 }
60
61 // New table must be large enough.
62 assert(new_keys->dk_usable >= mp->ma_used);
63
64 new_keys->dk_lookup = oldkeys->dk_lookup;
65
66 const Py_ssize_t numentries = mp->ma_used;
67 PyDictKeyEntry* newentries = DK_ENTRIES(new_keys);
68
69 memcpy(
70 newentries,
71 DK_ENTRIES(oldkeys),
72 numentries * sizeof(PyDictKeyEntry)
73 );
74
75 build_indices(new_keys, newentries, numentries);
76 new_keys->dk_usable -= numentries;
77 new_keys->dk_nentries = numentries;
78
79 // do not decref the keys inside!
80 frozendict_keys_decref(oldkeys, 0);
81
82 mp->ma_keys = new_keys;
83
84 return 0;
85 }
86
87 static int frozendict_insert(PyDictObject *mp,
88 PyObject *key,
89 const Py_hash_t hash,
90 PyObject *value,
91 int empty) {
92 Py_ssize_t ix;
93 PyObject *old_value;
94 PyDictKeysObject* keys = mp->ma_keys;
95
96 Py_INCREF(key);
97 Py_INCREF(value);
98 MAINTAIN_TRACKING(mp, key, value);
99
100 if (! empty) {
101 ix = keys->dk_lookup(mp, key, hash, &old_value);
102
103 if (ix == DKIX_ERROR) {
104 Py_DECREF(value);
105 Py_DECREF(key);
106 return -1;
107 }
108
109 empty = (ix == DKIX_EMPTY);
110 }
111
112 if (empty) {
113 /* Insert into new slot. */
114
115 if (mp->ma_keys->dk_usable <= 0) {
116 /* Need to resize. */
117 if (frozendict_resize(mp, GROWTH_RATE(mp))) {
118 Py_DECREF(value);
119 Py_DECREF(key);
120 return -1;
121 }
122
123 // resize changes keys
124 keys = mp->ma_keys;
125 }
126
127 const Py_ssize_t hashpos = find_empty_slot(keys, hash);
128 const Py_ssize_t dk_nentries = keys->dk_nentries;
129 PyDictKeyEntry* ep = &DK_ENTRIES(keys)[dk_nentries];
130 dictkeys_set_index(keys, hashpos, dk_nentries);
131 ep->me_key = key;
132 ep->me_hash = hash;
133 ep->me_value = value;
134 mp->ma_used++;
135 keys->dk_usable--;
136 keys->dk_nentries++;
137 assert(keys->dk_usable >= 0);
138 }
139 else {
140 DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
141 Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
142 Py_DECREF(key);
143 }
144
145 ASSERT_CONSISTENT(mp);
146 return 0;
147 }
148
149 static int frozendict_setitem(PyObject *op,
150 PyObject *key,
151 PyObject *value,
152 int empty) {
153 Py_hash_t hash;
154
155 assert(key);
156 assert(value);
157
158 if (!PyUnicode_CheckExact(key) ||
159 (hash = ((PyASCIIObject *) key)->hash) == -1) {
160 hash = PyObject_Hash(key);
161
162 if (hash == -1) {
163 return -1;
164 }
165 }
166 return frozendict_insert((PyDictObject*) op, key, hash, value, empty);
167 }
168
169 // int _PyFrozendict_SetItem(PyObject *op,
170 // PyObject *key,
171 // PyObject *value,
172 // int empty) {
173 // if (! PyAnyFrozenDict_Check(op)) {
174 // PyErr_BadInternalCall();
175 // return -1;
176 // }
177
178 // return frozendict_setitem(op, key, value, empty);
179 // }
180
181 static PyObject* _frozendict_new(
182 PyTypeObject* type,
183 PyObject* args,
184 PyObject* kwds,
185 const int use_empty_frozendict
186 );
187
188 static PyObject *
189 frozendict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value)
190 {
191 PyObject *it; /* iter(iterable) */
192 PyObject *key;
193 PyObject *d;
194 int status;
195
196 d = _frozendict_new(&PyFrozenDict_Type, NULL, NULL, 0);
197
198 if (d == NULL)
199 return NULL;
200
201 Py_ssize_t size;
202 PyDictObject *mp = (PyDictObject *)d;
203 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
204
205 if (PyAnyDict_CheckExact(iterable)) {
206 PyObject *oldvalue;
207 Py_ssize_t pos = 0;
208 PyObject *key;
209 Py_hash_t hash;
210
211 size = PyDict_GET_SIZE(iterable);
212
213 if (mp->ma_keys->dk_usable < size) {
214 if (frozendict_resize(mp, estimate_keysize(size))) {
215 Py_DECREF(d);
216 return NULL;
217 }
218 }
219
220 while (_d_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
221 if (frozendict_insert(mp, key, hash, value, 0)) {
222 Py_DECREF(d);
223 return NULL;
224 }
225 }
226 return d;
227 }
228 else if (PyAnySet_CheckExact(iterable)) {
229 Py_ssize_t pos = 0;
230 PyObject *key;
231 Py_hash_t hash;
232
233 size = PySet_GET_SIZE(iterable);
234
235 if (mp->ma_keys->dk_usable < size) {
236 if (frozendict_resize(mp, estimate_keysize(size))) {
237 Py_DECREF(d);
238 return NULL;
239 }
240 }
241
242 while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
243 if (frozendict_insert(mp, key, hash, value, 0)) {
244 Py_DECREF(d);
245 return NULL;
246 }
247 }
248 }
249 else {
250 it = PyObject_GetIter(iterable);
251 if (it == NULL){
252 Py_DECREF(d);
253 return NULL;
254 }
255
256 while ((key = PyIter_Next(it)) != NULL) {
257 status = frozendict_setitem(d, key, value, 0);
258 Py_DECREF(key);
259 if (status < 0) {
260 Py_DECREF(it);
261 Py_DECREF(d);
262 return NULL;
263 }
264 }
265
266 Py_DECREF(it);
267
268 if (PyErr_Occurred()) {
269 Py_DECREF(d);
270 return NULL;
271 }
272 }
273
274 ASSERT_CONSISTENT(mp);
275
276 if (type == &PyFrozenDict_Type) {
277 return d;
278 }
279
280 PyObject* args = PyTuple_New(1);
281
282 if (args == NULL) {
283 Py_DECREF(d);
284 return NULL;
285 }
286
287 PyTuple_SET_ITEM(args, 0, d);
288
289 PyObject* res = PyObject_Call((PyObject*) type, args, NULL);
290
291 Py_DECREF(args);
292
293 return res;
294 }
295
296 /* Methods */
297
298 #define REPR_GENERIC_START "("
299 #define REPR_GENERIC_END ")"
300 #define REPR_GENERIC_START_LEN 1
301 #define REPR_GENERIC_END_LEN 1
302
303 static PyObject* frozendict_repr(PyFrozenDictObject* mp) {
304 PyObject* dict_repr_res = dict_repr((PyDictObject*) mp);
305
306 if (dict_repr_res == NULL) {
307 return NULL;
308 }
309
310 _PyUnicodeWriter writer;
311 _PyUnicodeWriter_Init(&writer);
312
313 int error = 0;
314
315 PyObject* o = (PyObject*) mp;
316
317 Py_ReprEnter(o);
318
319 PyTypeObject* type = Py_TYPE(mp);
320 size_t frozendict_name_len = strlen(type->tp_name);
321
322 writer.min_length = (
323 frozendict_name_len +
324 REPR_GENERIC_START_LEN +
325 PyObject_Length(dict_repr_res) +
326 REPR_GENERIC_END_LEN
327 );
328
329 if (_PyUnicodeWriter_WriteASCIIString(
330 &writer,
331 type->tp_name,
332 frozendict_name_len
333 )) {
334 error = 1;
335 }
336 else {
337 if (_PyUnicodeWriter_WriteASCIIString(
338 &writer,
339 REPR_GENERIC_START,
340 REPR_GENERIC_START_LEN
341 )) {
342 error = 1;
343 }
344 else {
345 if (_PyUnicodeWriter_WriteStr(&writer, dict_repr_res)) {
346 error = 1;
347 }
348 else {
349 error = _PyUnicodeWriter_WriteASCIIString(
350 &writer,
351 REPR_GENERIC_END,
352 REPR_GENERIC_END_LEN
353 );
354 }
355 }
356 }
357
358 Py_ReprLeave(o);
359
360 Py_DECREF(dict_repr_res);
361
362 if (error) {
363 _PyUnicodeWriter_Dealloc(&writer);
364 return NULL;
365 }
366
367 return _PyUnicodeWriter_Finish(&writer);
368 }
369
370 static PyMappingMethods frozendict_as_mapping = {
371 (lenfunc)dict_length, /*mp_length*/
372 (binaryfunc)dict_subscript, /*mp_subscript*/
373 };
374
375 static int frozendict_merge(PyObject* a, PyObject* b, int empty) {
376 /* We accept for the argument either a concrete dictionary object,
377 * or an abstract "mapping" object. For the former, we can do
378 * things quite efficiently. For the latter, we only require that
379 * PyMapping_Keys() and PyObject_GetItem() be supported.
380 */
381 assert(a != NULL);
382 assert(PyAnyFrozenDict_Check(a));
383 assert(b != NULL);
384
385 PyDictObject* mp = (PyDictObject*) a;
386
387 if (
388 PyAnyDict_Check(b) &&
389 (
390 Py_TYPE(b)->tp_iter == PyDict_Type.tp_iter ||
391 Py_TYPE(b)->tp_iter == (getiterfunc)frozendict_iter
392 )
393 ) {
394 PyDictObject* other = (PyDictObject*)b;
395 const Py_ssize_t numentries = other->ma_used;
396
397 if (other == mp || numentries == 0) {
398 /* a.update(a) or a.update({}); nothing to do */
399 return 0;
400 }
401
402 const int is_other_combined = other->ma_values == NULL;
403
404 PyDictKeysObject* okeys = other->ma_keys;
405
406 if (
407 empty
408 && is_other_combined
409 && numentries == okeys->dk_nentries
410 ) {
411 PyDictKeysObject *keys = clone_combined_dict_keys(other);
412 if (keys == NULL) {
413 return -1;
414 }
415
416 mp->ma_keys = keys;
417
418 mp->ma_used = numentries;
419 mp->ma_version_tag = DICT_NEXT_VERSION();
420 ASSERT_CONSISTENT(mp);
421
422 if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) {
423 PyObject_GC_Track(mp);
424 }
425
426 return 0;
427 }
428
429 PyDictKeyEntry* ep0 = DK_ENTRIES(okeys);
430 PyDictKeyEntry* entry;
431 PyObject* key;
432 PyObject* value;
433 Py_hash_t hash;
434 int err;
435
436 if (mp->ma_keys == NULL) {
437 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
438 }
439
440 /* Do one big resize at the start, rather than
441 * incrementally resizing as we insert new items. Expect
442 * that there will be no (or few) overlapping keys.
443 */
444 if (mp->ma_keys->dk_usable < numentries) {
445 if (frozendict_resize(mp, estimate_keysize(mp->ma_used + numentries))) {
446 return -1;
447 }
448 }
449
450 for (Py_ssize_t i = 0, n = okeys->dk_nentries; i < n; i++) {
451 entry = &ep0[i];
452 key = entry->me_key;
453 hash = entry->me_hash;
454
455 if (is_other_combined) {
456 value = entry->me_value;
457 }
458 else {
459 value = other->ma_values[i];
460 }
461
462 if (value != NULL) {
463 Py_INCREF(key);
464 Py_INCREF(value);
465 err = frozendict_insert(mp, key, hash, value, empty);
466 Py_DECREF(value);
467 Py_DECREF(key);
468
469 if (err != 0) {
470 return -1;
471 }
472
473 if (n != other->ma_keys->dk_nentries) {
474 PyErr_SetString(PyExc_RuntimeError,
475 "dict mutated during update");
476 return -1;
477 }
478 }
479 }
480 }
481 else {
482 /* Do it the generic, slower way */
483 PyObject *keys = PyMapping_Keys(b);
484 PyObject *iter;
485 PyObject *key, *value;
486 int status;
487
488 if (mp->ma_keys == NULL) {
489 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
490 }
491
492 if (keys == NULL)
493 /* Docstring says this is equivalent to E.keys() so
494 * if E doesn't have a .keys() method we want
495 * AttributeError to percolate up. Might as well
496 * do the same for any other error.
497 */
498 return -1;
499
500 iter = PyObject_GetIter(keys);
501 Py_DECREF(keys);
502 if (iter == NULL)
503 return -1;
504
505 for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
506 value = PyObject_GetItem(b, key);
507 if (value == NULL) {
508 Py_DECREF(iter);
509 Py_DECREF(key);
510 return -1;
511 }
512 status = frozendict_setitem(a, key, value, 0);
513 Py_DECREF(key);
514 Py_DECREF(value);
515 if (status < 0) {
516 Py_DECREF(iter);
517 return -1;
518 }
519 }
520 Py_DECREF(iter);
521 if (PyErr_Occurred())
522 /* Iterator completed, via error */
523 return -1;
524 }
525 ASSERT_CONSISTENT(a);
526 return 0;
527 }
528
529 static int frozendict_merge_from_seq2(PyObject* d, PyObject* seq2) {
530 assert(d != NULL);
531 assert(PyAnyFrozenDict_Check(d));
532 assert(seq2 != NULL);
533
534 PyObject* it = PyObject_GetIter(seq2);
535
536 if (it == NULL) {
537 return -1;
538 }
539
540 PyObject* fast; /* item as a 2-tuple or 2-list */
541 PyObject* key = NULL;
542 PyObject* value = NULL;
543 Py_ssize_t n;
544 PyObject* item;
545 int res = 0;
546
547 PyDictObject* mp = (PyDictObject*) d;
548
549 if (mp->ma_keys == NULL) {
550 mp->ma_keys = new_keys_object(PyDict_MINSIZE);
551 }
552
553 for (Py_ssize_t i = 0; ; ++i) {
554 fast = NULL;
555 item = PyIter_Next(it);
556
557 if (item == NULL) {
558 if (PyErr_Occurred()) {
559 res = -1;
560 }
561
562 break;
563 }
564
565 /* Convert item to sequence, and verify length 2. */
566 fast = PySequence_Fast(item, "");
567
568 if (fast == NULL) {
569 if (PyErr_ExceptionMatches(PyExc_TypeError)) {
570 PyErr_Format(PyExc_TypeError,
571 "cannot convert dictionary update "
572 "sequence element #%zd to a sequence",
573 i);
574 }
575 Py_DECREF(item);
576 res = -1;
577 break;
578 }
579
580 n = PySequence_Fast_GET_SIZE(fast);
581
582 if (n != 2) {
583 PyErr_Format(PyExc_ValueError,
584 "dictionary update sequence element #%zd "
585 "has length %zd; 2 is required",
586 i, n);
587 Py_DECREF(fast);
588 Py_DECREF(item);
589 res = -1;
590 break;
591 }
592
593 /* Update/merge with this (key, value) pair. */
594 key = PySequence_Fast_GET_ITEM(fast, 0);
595 Py_INCREF(key);
596 value = PySequence_Fast_GET_ITEM(fast, 1);
597 Py_INCREF(value);
598
599 if (frozendict_setitem(d, key, value, 0) < 0) {
600 Py_DECREF(key);
601 Py_DECREF(value);
602 Py_DECREF(fast);
603 Py_DECREF(item);
604 res = -1;
605 break;
606 }
607
608 Py_DECREF(key);
609 Py_DECREF(value);
610 Py_DECREF(fast);
611 Py_DECREF(item);
612 }
613
614 Py_DECREF(it);
615 ASSERT_CONSISTENT(d);
616 return res;
617 }
618
619 static int frozendict_update_arg(PyObject *self,
620 PyObject *arg,
621 const int empty) {
622 if (PyAnyDict_CheckExact(arg)) {
623 return frozendict_merge(self, arg, empty);
624 }
625 _Py_IDENTIFIER(keys);
626 PyObject *func;
627 if (_PyObject_LookupAttrId(arg, &PyId_keys, &func) < 0) {
628 return -1;
629 }
630 if (func != NULL) {
631 Py_DECREF(func);
632 return frozendict_merge(self, arg, empty);
633 }
634 return frozendict_merge_from_seq2(self, arg);
635 }
636
637 static int frozendict_update_common(PyObject* self,
638 PyObject* arg,
639 PyObject* kwds) {
640 int result = 0;
641 const int no_arg = (arg == NULL);
642
643 if (! no_arg) {
644 result = frozendict_update_arg(self, arg, 1);
645 }
646
647 if (result == 0 && kwds != NULL) {
648 if (PyArg_ValidateKeywordArguments(kwds)) {
649 result = frozendict_merge(self, kwds, no_arg);
650 }
651 else {
652 result = -1;
653 }
654 }
655
656 return result;
657 }
658
659 /* Forward */
660 static PyObject *frozendictkeys_new(PyObject *, PyObject *);
661 static PyObject *frozendictitems_new(PyObject *, PyObject *);
662 static PyObject *frozendictvalues_new(PyObject *, PyObject *);
663
664 #define MINUSONE_HASH ((Py_hash_t) -1)
665
666 static Py_hash_t frozendict_hash(PyObject* self) {
667 PyFrozenDictObject* frozen_self = (PyFrozenDictObject*) self;
668 Py_hash_t hash;
669
670 if (frozen_self->ma_hash != MINUSONE_HASH) {
671 hash = frozen_self->ma_hash;
672 }
673 else {
674 PyObject* frozen_items_tmp = frozendictitems_new(self, NULL);
675 int save_hash = 1;
676
677 if (frozen_items_tmp == NULL) {
678 hash = MINUSONE_HASH;
679 save_hash = 0;
680 }
681 else {
682 PyObject* frozen_items = PyFrozenSet_New(frozen_items_tmp);
683 Py_DECREF(frozen_items_tmp);
684
685 if (frozen_items == NULL) {
686 hash = MINUSONE_HASH;
687 save_hash = 0;
688 }
689 else {
690 hash = PyFrozenSet_Type.tp_hash(frozen_items);
691 Py_DECREF(frozen_items);
692 }
693 }
694
695 if (save_hash) {
696 frozen_self->ma_hash = hash;
697 }
698 }
699
700 return hash;
701 }
702
703 static PyObject* frozendict_copy(PyObject* o, PyObject* Py_UNUSED(ignored)) {
704 if (PyAnyFrozenDict_CheckExact(o)) {
705 Py_INCREF(o);
706 return o;
707 }
708
709 PyObject* args = PyTuple_New(1);
710
711 if (args == NULL) {
712 return NULL;
713 }
714
715 Py_INCREF(o);
716 PyTuple_SET_ITEM(args, 0, o);
717
718 PyTypeObject* type = Py_TYPE(o);
719
720 PyObject* res = PyObject_Call((PyObject *) type, args, NULL);
721
722 Py_DECREF(args);
723
724 return res;
725 }
726
727 PyObject* frozendict_deepcopy(PyObject* self, PyObject* memo) {
728 if (PyAnyFrozenDict_CheckExact(self)) {
729 frozendict_hash(self);
730
731 if (PyErr_Occurred()) {
732 PyErr_Clear();
733 }
734 else {
735 Py_INCREF(self);
736 return self;
737 }
738 }
739
740 if (! PyAnyFrozenDict_Check(self)) {
741 Py_RETURN_NOTIMPLEMENTED;
742 }
743
744 PyObject* d = PyDict_New();
745
746 if (d == NULL) {
747 return NULL;
748 }
749
750 PyObject* copy_module_name = NULL;
751 PyObject* copy_module = NULL;
752 PyObject* deepcopy_fun = NULL;
753 PyObject* deep_args = NULL;
754 PyObject* deep_d = NULL;
755 PyObject* args = NULL;
756 PyObject* res = NULL;
757 int decref_d = 1;
758 int decref_deep_d = 1;
759
760 if (PyDict_Merge(d, self, 1)) {
761 goto end;
762 }
763
764 copy_module_name = PyUnicode_FromString("copy");
765
766 if (copy_module_name == NULL) {
767 goto end;
768 }
769
770 copy_module = PyImport_Import(copy_module_name);
771
772 if (copy_module == NULL) {
773 goto end;
774 }
775
776 deepcopy_fun = PyObject_GetAttrString(copy_module, "deepcopy");
777
778 if (deepcopy_fun == NULL) {
779 goto end;
780 }
781
782 deep_args = PyTuple_New(2);
783
784 if (deep_args == NULL) {
785 goto end;
786 }
787
788 PyTuple_SET_ITEM(deep_args, 0, d);
789 decref_d = 0;
790
791 Py_INCREF(memo);
792 PyTuple_SET_ITEM(deep_args, 1, memo);
793
794 deep_d = PyObject_CallObject(deepcopy_fun, deep_args);
795
796 if (deep_d == NULL) {
797 goto end;
798 }
799
800 args = PyTuple_New(1);
801
802 if (args == NULL) {
803 goto end;
804 }
805
806 PyTuple_SET_ITEM(args, 0, deep_d);
807 decref_deep_d = 0;
808
809 PyTypeObject* type = Py_TYPE(self);
810
811 res = PyObject_Call((PyObject *) type, args, NULL);
812
813 end:
814 Py_XDECREF(args);
815 Py_XDECREF(deep_args);
816 Py_XDECREF(deepcopy_fun);
817 Py_XDECREF(copy_module);
818 Py_XDECREF(copy_module_name);
819
820 if (decref_d) {
821 Py_DECREF(d);
822 }
823
824 if (decref_deep_d) {
825 Py_DECREF(deep_d);
826 }
827
828 return res;
829 }
830
831 static int frozendict_equal(PyDictObject* a, PyDictObject* b) {
832 if (a == b) {
833 return 1;
834 }
835
836 if (a->ma_used != b->ma_used) {
837 /* can't be equal if # of entries differ */
838 return 0;
839 }
840
841 PyDictKeysObject* keys = a->ma_keys;
842 PyDictKeyEntry* ep;
843 PyObject* aval;
844 int cmp = 1;
845 PyObject* bval;
846 PyObject* key;
847
848 /* Same # of entries -- check all of 'em. Exit early on any diff. */
849 for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) {
850 ep = &DK_ENTRIES(keys)[i];
851 aval = ep->me_value;
852 Py_INCREF(aval);
853 key = ep->me_key;
854 Py_INCREF(key);
855
856 /* reuse the known hash value */
857 b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval);
858
859 if (bval == NULL) {
860 if (PyErr_Occurred()) {
861 cmp = -1;
862 }
863 else {
864 cmp = 0;
865 }
866 }
867 else {
868 Py_INCREF(bval);
869 cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
870 Py_DECREF(bval);
871 }
872
873 Py_DECREF(key);
874 Py_DECREF(aval);
875 if (cmp <= 0) { /* error or not equal */
876 break;
877 }
878 }
879
880 return cmp;
881 }
882
883 static Py_ssize_t dict_get_index(PyDictObject *self, PyObject *key) {
884 Py_hash_t hash;
885 PyObject* val;
886
887 if (!PyUnicode_CheckExact(key) ||
888 (hash = ((PyASCIIObject *) key)->hash) == -1) {
889 hash = PyObject_Hash(key);
890 if (hash == -1)
891 return DKIX_ERROR;
892 }
893 return (self->ma_keys->dk_lookup) (self, key, hash, &val);
894 }
895
896 static PyObject *
897 frozendict_reduce(PyFrozenDictObject* mp, PyObject *Py_UNUSED(ignored))
898 {
899 PyObject *d = PyDict_New();
900
901 if (d == NULL) {
902 return NULL;
903 }
904
905 if (PyDict_Merge(d, (PyObject *)mp, 1)) {
906 Py_DECREF(d);
907 return NULL;
908 }
909
910 return Py_BuildValue("O(N)", Py_TYPE(mp), d);
911 }
912
913 static PyObject* frozendict_clone(PyObject* self) {
914 PyTypeObject* type = Py_TYPE(self);
915 PyObject* new_op = type->tp_alloc(type, 0);
916
917 if (new_op == NULL){
918 return NULL;
919 }
920
921 if (type == &PyFrozenDict_Type) {
922 PyObject_GC_UnTrack(new_op);
923 }
924
925 PyDictObject* mp = (PyDictObject*) self;
926
927 PyDictKeysObject *keys = clone_combined_dict_keys(mp);
928
929 if (keys == NULL) {
930 return NULL;
931 }
932
933 PyFrozenDictObject* new_mp = (PyFrozenDictObject*) new_op;
934 new_mp->ma_keys = keys;
935
936 if (_PyObject_GC_IS_TRACKED(mp) && !_PyObject_GC_IS_TRACKED(new_mp)) {
937 PyObject_GC_Track(new_mp);
938 }
939
940 new_mp->ma_used = mp->ma_used;
941 new_mp->ma_hash = MINUSONE_HASH;
942 new_mp->ma_version_tag = DICT_NEXT_VERSION();
943
944 ASSERT_CONSISTENT(new_mp);
945
946 return new_op;
947 }
948
949 static PyObject* frozendict_set(
950 PyObject* self,
951 PyObject* const* args,
952 Py_ssize_t nargs
953 ) {
954 PyObject* set_key;
955 PyObject* set_val;
956
957 if (!_PyArg_UnpackStack(args, nargs, "set",
958 2, 2,
959 &set_key, &set_val)) {
960 return NULL;
961 }
962
963 PyObject* new_op = frozendict_clone(self);
964
965 if (new_op == NULL) {
966 return NULL;
967 }
968
969 if (frozendict_setitem(new_op, set_key, set_val, 0)) {
970 Py_DECREF(new_op);
971 return NULL;
972 }
973
974 if (
975 ((PyDictObject*) self)->ma_keys->dk_lookup == lookdict_unicode_nodummy &&
976 ! PyUnicode_CheckExact(set_key)
977 ) {
978 ((PyFrozenDictObject*) new_op)->ma_keys->dk_lookup = lookdict;
979 }
980
981 return new_op;
982 }
983
984 static PyObject* frozendict_setdefault(
985 PyObject* self,
986 PyObject* const* args,
987 Py_ssize_t nargs
988 ) {
989 PyObject* set_key;
990 PyObject* val = Py_None;
991
992 if (!_PyArg_UnpackStack(args, nargs, "setdefault",
993 1, 2,
994 &set_key, &val)) {
995 return NULL;
996 }
997
998 if (PyDict_Contains(self, set_key)) {
999 Py_INCREF(self);
1000 return self;
1001 }
1002
1003 PyObject* new_op = frozendict_clone(self);
1004
1005 if (new_op == NULL) {
1006 return NULL;
1007 }
1008
1009 if (frozendict_setitem(new_op, set_key, val, 0)) {
1010 Py_DECREF(new_op);
1011
1012 return NULL;
1013 }
1014
1015 if (
1016 ((PyDictObject*) self)->ma_keys->dk_lookup == lookdict_unicode_nodummy &&
1017 ! PyUnicode_CheckExact(set_key)
1018 ) {
1019 ((PyFrozenDictObject*) new_op)->ma_keys->dk_lookup = lookdict;
1020 }
1021
1022 return new_op;
1023 }
1024
1025 static PyObject* frozendict_delete(
1026 PyObject* self,
1027 PyObject *const *args,
1028 Py_ssize_t nargs
1029 ) {
1030 PyObject* del_key;
1031
1032 if (!_PyArg_UnpackStack(args, nargs, "delete",
1033 1, 1,
1034 &del_key)) {
1035 return NULL;
1036 }
1037
1038 PyDictObject* mp = (PyDictObject*) self;
1039 const Py_ssize_t ix = dict_get_index(mp, del_key);
1040
1041 if (ix == DKIX_ERROR) {
1042 return NULL;
1043 }
1044
1045 if (ix == DKIX_EMPTY) {
1046 _PyErr_SetKeyError(del_key);
1047 return NULL;
1048 }
1049
1050 const Py_ssize_t size = mp->ma_used;
1051 const Py_ssize_t sizemm = size - 1;
1052
1053 if (sizemm == 0) {
1054 PyObject* args = PyTuple_New(0);
1055
1056 if (args == NULL) {
1057 return NULL;
1058 }
1059
1060 return PyObject_Call((PyObject*) Py_TYPE(self), args, NULL);
1061 }
1062
1063 PyTypeObject* type = Py_TYPE(self);
1064 PyObject* new_op = type->tp_alloc(type, 0);
1065
1066 if (new_op == NULL) {
1067 return NULL;
1068 }
1069
1070 if (type == &PyFrozenDict_Type) {
1071 PyObject_GC_UnTrack(new_op);
1072 }
1073
1074 const Py_ssize_t newsize = estimate_keysize(sizemm);
1075
1076 if (newsize <= 0) {
1077 Py_DECREF(new_op);
1078 PyErr_NoMemory();
1079 return NULL;
1080 }
1081
1082 assert(IS_POWER_OF_2(newsize));
1083 assert(newsize >= PyDict_MINSIZE);
1084
1085 /* Allocate a new table. */
1086 PyDictKeysObject* new_keys = new_keys_object(newsize);
1087
1088 if (new_keys == NULL) {
1089 Py_DECREF(new_op);
1090 return NULL;
1091 }
1092
1093 const PyDictKeysObject* old_keys = mp->ma_keys;
1094 new_keys->dk_lookup = old_keys->dk_lookup;
1095
1096 PyFrozenDictObject* new_mp = (PyFrozenDictObject*) new_op;
1097
1098 // New table must be large enough.
1099 assert(new_keys->dk_usable >= new_mp->ma_used);
1100
1101 new_mp->ma_keys = new_keys;
1102 new_mp->ma_hash = MINUSONE_HASH;
1103 new_mp->ma_version_tag = DICT_NEXT_VERSION();
1104
1105 PyObject* key;
1106 PyObject* value;
1107 Py_hash_t hash;
1108 Py_ssize_t hashpos;
1109 PyDictKeyEntry* old_entries = DK_ENTRIES(old_keys);
1110 PyDictKeyEntry* new_entries = DK_ENTRIES(new_keys);
1111 PyDictKeyEntry* old_entry;
1112 PyDictKeyEntry* new_entry;
1113 Py_ssize_t new_i;
1114 int deleted = 0;
1115
1116 for (Py_ssize_t i = 0; i < size; i++) {
1117 if (i == ix) {
1118 deleted = 1;
1119 continue;
1120 }
1121
1122 new_i = i - deleted;
1123
1124 old_entry = &old_entries[i];
1125 hash = old_entry->me_hash;
1126 key = old_entry->me_key;
1127 value = old_entry->me_value;
1128 Py_INCREF(key);
1129 Py_INCREF(value);
1130 hashpos = find_empty_slot(new_keys, hash);
1131 dictkeys_set_index(new_keys, hashpos, new_i);
1132 new_entry = &new_entries[new_i];
1133 new_entry->me_key = key;
1134 new_entry->me_hash = hash;
1135 new_entry->me_value = value;
1136 }
1137
1138 new_mp->ma_used = sizemm;
1139 new_keys->dk_usable -= sizemm;
1140 new_keys->dk_nentries = sizemm;
1141
1142 ASSERT_CONSISTENT(new_mp);
1143
1144 return new_op;
1145 }
1146
1147
1148 static const PyObject* frozendict_key(
1149 PyObject* self,
1150 PyObject *const *args,
1151 Py_ssize_t nargs
1152 ) {
1153 PyObject* i;
1154
1155 if (!_PyArg_UnpackStack(args, nargs, "key",
1156 0, 1,
1157 &i)) {
1158 return NULL;
1159 }
1160
1161 Py_ssize_t index;
1162 Py_ssize_t passed_index;
1163 PyDictObject* d = (PyDictObject*) self;
1164 const Py_ssize_t size = d->ma_used;
1165
1166 if (nargs > 0) {
1167 index = PyLong_AsSsize_t(i);
1168 passed_index = index;
1169
1170 if (index < 0) {
1171 if (PyErr_Occurred()) {
1172 return NULL;
1173 }
1174
1175 index += size;
1176 }
1177 }
1178 else {
1179 index = 0;
1180 passed_index = index;
1181 }
1182
1183 const Py_ssize_t maxindex = size - 1;
1184
1185 if (index > maxindex || index < 0) {
1186 PyErr_Format(
1187 PyExc_IndexError,
1188 "%s index %zd out of range %zd",
1189 Py_TYPE(self)->tp_name,
1190 passed_index,
1191 maxindex
1192 );
1193
1194 return NULL;
1195 }
1196
1197 const PyObject* res = DK_ENTRIES(d->ma_keys)[index].me_key;
1198 Py_INCREF(res);
1199
1200 return res;
1201 }
1202
1203 static const PyObject* frozendict_value(
1204 PyObject* self,
1205 PyObject *const *args,
1206 Py_ssize_t nargs
1207 ) {
1208 PyObject* i;
1209
1210 if (!_PyArg_UnpackStack(args, nargs, "value",
1211 0, 1,
1212 &i)) {
1213 return NULL;
1214 }
1215
1216 Py_ssize_t index;
1217 Py_ssize_t passed_index;
1218 PyDictObject* d = (PyDictObject*) self;
1219 const Py_ssize_t size = d->ma_used;
1220
1221 if (nargs > 0) {
1222 index = PyLong_AsSsize_t(i);
1223 passed_index = index;
1224
1225 if (index < 0) {
1226 if (PyErr_Occurred()) {
1227 return NULL;
1228 }
1229
1230 index += size;
1231 }
1232 }
1233 else {
1234 index = 0;
1235 passed_index = index;
1236 }
1237
1238 const Py_ssize_t maxindex = size - 1;
1239
1240 if (index > maxindex || index < 0) {
1241 PyErr_Format(
1242 PyExc_IndexError,
1243 "%s index %zd out of range %zd",
1244 Py_TYPE(self)->tp_name,
1245 passed_index,
1246 maxindex
1247 );
1248
1249 return NULL;
1250 }
1251
1252 const PyObject* res = DK_ENTRIES(d->ma_keys)[index].me_value;
1253 Py_INCREF(res);
1254
1255 return res;
1256 }
1257
1258 static const PyObject* frozendict_item(
1259 PyObject* self,
1260 PyObject *const *args,
1261 Py_ssize_t nargs
1262 ) {
1263 PyObject* i;
1264
1265 if (!_PyArg_UnpackStack(args, nargs, "item",
1266 0, 1,
1267 &i)) {
1268 return NULL;
1269 }
1270
1271 Py_ssize_t index;
1272 Py_ssize_t passed_index;
1273 PyDictObject* d = (PyDictObject*) self;
1274 const Py_ssize_t size = d->ma_used;
1275
1276 if (nargs > 0) {
1277 index = PyLong_AsSsize_t(i);
1278 passed_index = index;
1279
1280 if (index < 0) {
1281 if (PyErr_Occurred()) {
1282 return NULL;
1283 }
1284
1285 index += size;
1286 }
1287 }
1288 else {
1289 index = 0;
1290 passed_index = index;
1291 }
1292
1293 const Py_ssize_t maxindex = size - 1;
1294
1295 if (index > maxindex || index < 0) {
1296 PyErr_Format(
1297 PyExc_IndexError,
1298 "%s index %zd out of range %zd",
1299 Py_TYPE(self)->tp_name,
1300 passed_index,
1301 maxindex
1302 );
1303
1304 return NULL;
1305 }
1306
1307 PyObject* key = DK_ENTRIES(d->ma_keys)[index].me_key;
1308 Py_INCREF(key);
1309 PyObject* val = DK_ENTRIES(d->ma_keys)[index].me_value;
1310 Py_INCREF(val);
1311
1312 const PyObject* res = PyTuple_New(2);
1313 PyTuple_SET_ITEM(res, 0, key);
1314 PyTuple_SET_ITEM(res, 1, val);
1315
1316 return res;
1317 }
1318
1319 PyDoc_STRVAR(frozendict_set_doc,
1320 "set($self, key, value, /)\n"
1321 "--\n"
1322 "\n"
1323 "Returns a copy of the dictionary with the new (key, value) item. ");
1324
1325 PyDoc_STRVAR(frozendict_setdefault_doc,
1326 "set($self, key[, default], /)\n"
1327 "--\n"
1328 "\n"
1329 "If key is in the dictionary, it returns the dictionary unchanged. \n"
1330 "Otherwise, it returns a copy of the dictionary with the new (key, default) item; \n"
1331 "default argument is optional and is None by default. ");
1332
1333 PyDoc_STRVAR(frozendict_delete_doc,
1334 "delete($self, key, /)\n"
1335 "--\n"
1336 "\n"
1337 "Returns a copy of the dictionary without the item of the corresponding key. ");
1338
1339 PyDoc_STRVAR(frozendict_key_doc,
1340 "key($self[, index], /)\n"
1341 "--\n"
1342 "\n"
1343 "Get the key at the specified index (insertion order). If index is not \n"
1344 "passed, it defaults to 0. If index is negative, returns the key at \n"
1345 "position size + index. ");
1346
1347 PyDoc_STRVAR(frozendict_value_doc,
1348 "value($self[, index], /)\n"
1349 "--\n"
1350 "\n"
1351 "Get the value at the specified index (insertion order). If index is not \n"
1352 "passed, it defaults to 0. If index is negative, returns the value at \n"
1353 "position size + index. ");
1354
1355 PyDoc_STRVAR(frozendict_item_doc,
1356 "item($self[, index], /)\n"
1357 "--\n"
1358 "\n"
1359 "Get the (key, value) item at the specified index (insertion order). If \n"
1360 "index is not passed, it defaults to 0. If index is negative, returns the \n"
1361 "item at position size + index. ");
1362
1363 static PyMethodDef frozendict_mapp_methods[] = {
1364 DICT___CONTAINS___METHODDEF
1365 {"__getitem__", (PyCFunction)(void(*)(void))dict_subscript, METH_O | METH_COEXIST,
1366 getitem__doc__},
1367 {"__sizeof__", (PyCFunction)(void(*)(void))dict_sizeof, METH_NOARGS,
1368 sizeof__doc__},
1369 DICT_GET_METHODDEF
1370 {"keys", frozendictkeys_new, METH_NOARGS,
1371 keys__doc__},
1372 {"items", frozendictitems_new, METH_NOARGS,
1373 items__doc__},
1374 {"values", frozendictvalues_new, METH_NOARGS,
1375 values__doc__},
1376 {"fromkeys", (PyCFunction)(void(*)(void))dict_fromkeys, METH_FASTCALL|METH_CLASS,
1377 dict_fromkeys__doc__},
1378 {"copy", (PyCFunction)frozendict_copy, METH_NOARGS,
1379 copy__doc__},
1380 {"__copy__", (PyCFunction)frozendict_copy, METH_NOARGS,
1381 "Returns a copy of the object."},
1382 {"__deepcopy__", (PyCFunction)frozendict_deepcopy, METH_O,
1383 "Returns a deepcopy of the object."},
1384 DICT___REVERSED___METHODDEF
1385 {"__reduce__", (PyCFunction)(void(*)(void))frozendict_reduce, METH_NOARGS,
1386 ""},
1387 {"set", (PyCFunction)(void(*)(void))
1388 frozendict_set, METH_FASTCALL,
1389 frozendict_set_doc},
1390 {"setdefault", (PyCFunction)(void(*)(void))
1391 frozendict_setdefault, METH_FASTCALL,
1392 frozendict_setdefault_doc},
1393 {"delete", (PyCFunction)(void(*)(void))
1394 frozendict_delete, METH_FASTCALL,
1395 frozendict_delete_doc},
1396 {"key", (PyCFunction)(void(*)(void))
1397 frozendict_key, METH_FASTCALL,
1398 frozendict_key_doc},
1399 {"value", (PyCFunction)(void(*)(void))
1400 frozendict_value, METH_FASTCALL,
1401 frozendict_value_doc},
1402 {"item", (PyCFunction)(void(*)(void))
1403 frozendict_item, METH_FASTCALL,
1404 frozendict_item_doc},
1405 {NULL, NULL} /* sentinel */
1406 };
1407
1408 static PyObject* frozendict_new_barebone(PyTypeObject* type) {
1409 PyObject* self = type->tp_alloc(type, 0);
1410
1411 if (self == NULL) {
1412 return NULL;
1413 }
1414
1415 /* The object has been implicitly tracked by tp_alloc */
1416 if (type == &PyFrozenDict_Type) {
1417 PyObject_GC_UnTrack(self);
1418 }
1419
1420 PyFrozenDictObject* mp = (PyFrozenDictObject*) self;
1421
1422 mp->ma_keys = NULL;
1423 mp->ma_values = NULL;
1424 mp->ma_used = 0;
1425 mp->ma_hash = MINUSONE_HASH;
1426
1427 return self;
1428 }
1429
1430 // empty frozendict singleton
1431 static PyObject* empty_frozendict = NULL;
1432
1433 // if frozendict is empty, return the empty singleton
1434 static PyObject* frozendict_create_empty(
1435 PyFrozenDictObject* mp,
1436 const PyTypeObject* type,
1437 const int use_empty_frozendict
1438 ) {
1439 if (mp->ma_used == 0) {
1440 if (use_empty_frozendict && type == &PyFrozenDict_Type) {
1441 if (empty_frozendict == NULL) {
1442 empty_frozendict = (PyObject*) mp;
1443 Py_INCREF(Py_EMPTY_KEYS);
1444 ((PyDictObject*) empty_frozendict)->ma_keys = Py_EMPTY_KEYS;
1445 mp->ma_version_tag = DICT_NEXT_VERSION();
1446 }
1447 else {
1448 Py_DECREF(mp);
1449 }
1450
1451 Py_INCREF(empty_frozendict);
1452
1453 return empty_frozendict;
1454 }
1455 else {
1456 if (mp->ma_keys != NULL) {
1457 frozendict_keys_decref(mp->ma_keys, 0);
1458 }
1459
1460 Py_INCREF(Py_EMPTY_KEYS);
1461 mp->ma_keys = Py_EMPTY_KEYS;
1462
1463 return NULL;
1464 }
1465 }
1466
1467 return NULL;
1468 }
1469
1470 static PyObject* _frozendict_new(
1471 PyTypeObject* type,
1472 PyObject* args,
1473 PyObject* kwds,
1474 const int use_empty_frozendict
1475 ) {
1476 assert(type != NULL && type->tp_alloc != NULL);
1477
1478 PyObject* arg = NULL;
1479
1480 if (args != NULL && ! PyArg_UnpackTuple(args, "dict", 0, 1, &arg)) {
1481 return NULL;
1482 }
1483
1484 const int arg_is_frozendict = (arg != NULL && PyAnyFrozenDict_CheckExact(arg));
1485 const int kwds_size = ((kwds != NULL)
1486 ? ((PyDictObject*) kwds)->ma_used
1487 : 0
1488 );
1489
1490 // only argument is a frozendict
1491 if (arg_is_frozendict && kwds_size == 0 && type == &PyFrozenDict_Type) {
1492 Py_INCREF(arg);
1493
1494 return arg;
1495 }
1496
1497 PyObject* self = frozendict_new_barebone(type);
1498
1499 PyFrozenDictObject* mp = (PyFrozenDictObject*) self;
1500
1501 if (frozendict_update_common(self, arg, kwds)) {
1502 Py_DECREF(self);
1503 return NULL;
1504 }
1505
1506 PyObject* empty = frozendict_create_empty(mp, type, use_empty_frozendict);
1507
1508 if (empty != NULL) {
1509 return empty;
1510 }
1511
1512 mp->ma_version_tag = DICT_NEXT_VERSION();
1513
1514 return self;
1515 }
1516
1517 static PyObject* frozendict_new(PyTypeObject* type, PyObject* args, PyObject* kwds) {
1518 return _frozendict_new(type, args, kwds, 1);
1519 }
1520
1521 static PyObject* frozendict_or(PyObject *self, PyObject *other) {
1522 if (! PyAnyFrozenDict_Check(self) || ! PyAnyDict_Check(other)) {
1523 Py_RETURN_NOTIMPLEMENTED;
1524 }
1525
1526 PyObject* new = frozendict_clone(self);
1527
1528 if (new == NULL) {
1529 return NULL;
1530 }
1531
1532 if (frozendict_update_arg(new, other, 0)) {
1533 Py_DECREF(new);
1534 return NULL;
1535 }
1536
1537 return new;
1538 }
1539
1540 static PyNumberMethods frozendict_as_number = {
1541 .nb_or = frozendict_or,
1542 };
1543
1544 #define FROZENDICT_CLASS_NAME "frozendict"
1545 #define FROZENDICT_MODULE_NAME "frozendict"
1546 #define FROZENDICT_FULL_NAME FROZENDICT_MODULE_NAME "." FROZENDICT_CLASS_NAME
1547
1548 PyDoc_STRVAR(frozendict_doc,
1549 "An immutable version of dict.\n"
1550 "\n"
1551 FROZENDICT_FULL_NAME "() -> returns an empty immutable dictionary\n"
1552 FROZENDICT_FULL_NAME "(mapping) -> returns an immutable dictionary initialized from a mapping object's\n"
1553 " (key, value) pairs\n"
1554 FROZENDICT_FULL_NAME "(iterable) -> returns an immutable dictionary, equivalent to:\n"
1555 " d = {}\n"
1556 " "
1557 " for k, v in iterable:\n"
1558 " d[k] = v\n"
1559 " "
1560 " " FROZENDICT_FULL_NAME "(d)\n"
1561 FROZENDICT_FULL_NAME "(**kwargs) -> returns an immutable dictionary initialized with the name=value pairs\n"
1562 " in the keyword argument list. For example: " FROZENDICT_FULL_NAME "(one=1, two=2)");
1563
1564 static PyTypeObject PyFrozenDict_Type = {
1565 PyVarObject_HEAD_INIT(NULL, 0)
1566 FROZENDICT_FULL_NAME, /* tp_name */
1567 sizeof(PyFrozenDictObject), /* tp_basicsize */
1568 0, /* tp_itemsize */
1569 (destructor)dict_dealloc, /* tp_dealloc */
1570 0, /* tp_vectorcall_offset */
1571 0, /* tp_getattr */
1572 0, /* tp_setattr */
1573 0, /* tp_as_async */
1574 (reprfunc)frozendict_repr, /* tp_repr */
1575 &frozendict_as_number, /* tp_as_number */
1576 &dict_as_sequence, /* tp_as_sequence */
1577 &frozendict_as_mapping, /* tp_as_mapping */
1578 (hashfunc)frozendict_hash, /* tp_hash */
1579 0, /* tp_call */
1580 0, /* tp_str */
1581 PyObject_GenericGetAttr, /* tp_getattro */
1582 0, /* tp_setattro */
1583 0, /* tp_as_buffer */
1584 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC
1585 | Py_TPFLAGS_BASETYPE, /* tp_flags */
1586 frozendict_doc, /* tp_doc */
1587 dict_traverse, /* tp_traverse */
1588 0, /* tp_clear */
1589 dict_richcompare, /* tp_richcompare */
1590 0, /* tp_weaklistoffset */
1591 (getiterfunc)frozendict_iter, /* tp_iter */
1592 0, /* tp_iternext */
1593 frozendict_mapp_methods, /* tp_methods */
1594 0, /* tp_members */
1595 0, /* tp_getset */
1596 0, /* tp_base */
1597 0, /* tp_dict */
1598 0, /* tp_descr_get */
1599 0, /* tp_descr_set */
1600 0, /* tp_dictoffset */
1601 0, /* tp_init */
1602 PyType_GenericAlloc, /* tp_alloc */
1603 frozendict_new, /* tp_new */
1604 PyObject_GC_Del, /* tp_free */
1605 };
1606
1607 /* Dictionary iterator types */
1608
1609 static PyObject* frozendict_iter(PyDictObject *dict) {
1610 return dictiter_new(dict, &PyFrozenDictIterKey_Type);
1611 }
1612
1613 static PyObject* frozendictiter_iternextkey(dictiterobject* di) {
1614 Py_ssize_t pos = di->di_pos;
1615 assert(pos >= 0);
1616 PyDictObject* d = di->di_dict;
1617
1618 if (d == NULL) {
1619 return NULL;
1620 }
1621
1622 assert(PyAnyFrozenDict_Check(d));
1623
1624 if (pos >= d->ma_used) {
1625 di->di_dict = NULL;
1626 Py_DECREF(d);
1627 return NULL;
1628 }
1629
1630 PyObject* key = DK_ENTRIES(d->ma_keys)[pos].me_key;
1631 assert(key != NULL);
1632 di->di_pos++;
1633 di->len--;
1634 Py_INCREF(key);
1635 return key;
1636 }
1637
1638 static PyTypeObject PyFrozenDictIterKey_Type = {
1639 PyVarObject_HEAD_INIT(NULL, 0)
1640 FROZENDICT_MODULE_NAME ".keyiterator", /* tp_name */
1641 sizeof(dictiterobject), /* tp_basicsize */
1642 0, /* tp_itemsize */
1643 /* methods */
1644 (destructor)dictiter_dealloc, /* tp_dealloc */
1645 0, /* tp_vectorcall_offset */
1646 0, /* tp_getattr */
1647 0, /* tp_setattr */
1648 0, /* tp_as_async */
1649 0, /* tp_repr */
1650 0, /* tp_as_number */
1651 0, /* tp_as_sequence */
1652 0, /* tp_as_mapping */
1653 0, /* tp_hash */
1654 0, /* tp_call */
1655 0, /* tp_str */
1656 PyObject_GenericGetAttr, /* tp_getattro */
1657 0, /* tp_setattro */
1658 0, /* tp_as_buffer */
1659 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1660 0, /* tp_doc */
1661 (traverseproc)dictiter_traverse, /* tp_traverse */
1662 0, /* tp_clear */
1663 0, /* tp_richcompare */
1664 0, /* tp_weaklistoffset */
1665 PyObject_SelfIter, /* tp_iter */
1666 (iternextfunc)frozendictiter_iternextkey, /* tp_iternext */
1667 dictiter_methods, /* tp_methods */
1668 0,
1669 };
1670
1671 static PyObject* frozendictiter_iternextvalue(dictiterobject* di) {
1672 Py_ssize_t pos = di->di_pos;
1673 assert(pos >= 0);
1674 PyDictObject* d = di->di_dict;
1675
1676 if (d == NULL) {
1677 return NULL;
1678 }
1679
1680 assert(PyAnyFrozenDict_Check(d));
1681
1682 if (pos >= d->ma_used) {
1683 di->di_dict = NULL;
1684 Py_DECREF(d);
1685 return NULL;
1686 }
1687
1688 PyObject* val = DK_ENTRIES(d->ma_keys)[pos].me_value;
1689 assert(val != NULL);
1690 di->di_pos++;
1691 di->len--;
1692 Py_INCREF(val);
1693 return val;
1694 }
1695
1696 static PyTypeObject PyFrozenDictIterValue_Type = {
1697 PyVarObject_HEAD_INIT(NULL, 0)
1698 FROZENDICT_MODULE_NAME ".valueiterator", /* tp_name */
1699 sizeof(dictiterobject), /* tp_basicsize */
1700 0, /* tp_itemsize */
1701 /* methods */
1702 (destructor)dictiter_dealloc, /* tp_dealloc */
1703 0, /* tp_vectorcall_offset */
1704 0, /* tp_getattr */
1705 0, /* tp_setattr */
1706 0, /* tp_as_async */
1707 0, /* tp_repr */
1708 0, /* tp_as_number */
1709 0, /* tp_as_sequence */
1710 0, /* tp_as_mapping */
1711 0, /* tp_hash */
1712 0, /* tp_call */
1713 0, /* tp_str */
1714 PyObject_GenericGetAttr, /* tp_getattro */
1715 0, /* tp_setattro */
1716 0, /* tp_as_buffer */
1717 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1718 0, /* tp_doc */
1719 (traverseproc)dictiter_traverse, /* tp_traverse */
1720 0, /* tp_clear */
1721 0, /* tp_richcompare */
1722 0, /* tp_weaklistoffset */
1723 PyObject_SelfIter, /* tp_iter */
1724 (iternextfunc)frozendictiter_iternextvalue, /* tp_iternext */
1725 dictiter_methods, /* tp_methods */
1726 0,
1727 };
1728
1729 static PyObject* frozendictiter_iternextitem(dictiterobject* di) {
1730 Py_ssize_t pos = di->di_pos;
1731 assert(pos >= 0);
1732 PyDictObject* d = di->di_dict;
1733
1734 if (d == NULL) {
1735 return NULL;
1736 }
1737
1738 assert(PyAnyFrozenDict_Check(d));
1739
1740 if (pos >= d->ma_used) {
1741 di->di_dict = NULL;
1742 Py_DECREF(d);
1743 return NULL;
1744 }
1745
1746 PyDictKeyEntry* entry_ptr = &DK_ENTRIES(d->ma_keys)[pos];
1747 PyObject* key = entry_ptr->me_key;
1748 PyObject* val = entry_ptr->me_value;
1749 assert(key != NULL);
1750 assert(val != NULL);
1751 di->di_pos++;
1752 di->len--;
1753 Py_INCREF(key);
1754 Py_INCREF(val);
1755
1756 PyObject* result;
1757 if (Py_REFCNT(di->di_result) == 1) {
1758 result = di->di_result;
1759 PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
1760 PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
1761 Py_INCREF(result);
1762 Py_DECREF(oldkey);
1763 Py_DECREF(oldvalue);
1764
1765 if (!_PyObject_GC_IS_TRACKED(result)) {
1766 PyObject_GC_Track(result);
1767 }
1768 }
1769 else {
1770 result = PyTuple_New(2);
1771 if (result == NULL)
1772 return NULL;
1773 }
1774
1775 PyTuple_SET_ITEM(result, 0, key); /* steals reference */
1776 PyTuple_SET_ITEM(result, 1, val); /* steals reference */
1777 return result;
1778 }
1779
1780 static PyTypeObject PyFrozenDictIterItem_Type = {
1781 PyVarObject_HEAD_INIT(NULL, 0)
1782 FROZENDICT_MODULE_NAME ".itemiterator", /* tp_name */
1783 sizeof(dictiterobject), /* tp_basicsize */
1784 0, /* tp_itemsize */
1785 /* methods */
1786 (destructor)dictiter_dealloc, /* tp_dealloc */
1787 0, /* tp_vectorcall_offset */
1788 0, /* tp_getattr */
1789 0, /* tp_setattr */
1790 0, /* tp_as_async */
1791 0, /* tp_repr */
1792 0, /* tp_as_number */
1793 0, /* tp_as_sequence */
1794 0, /* tp_as_mapping */
1795 0, /* tp_hash */
1796 0, /* tp_call */
1797 0, /* tp_str */
1798 PyObject_GenericGetAttr, /* tp_getattro */
1799 0, /* tp_setattro */
1800 0, /* tp_as_buffer */
1801 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1802 0, /* tp_doc */
1803 (traverseproc)dictiter_traverse, /* tp_traverse */
1804 0, /* tp_clear */
1805 0, /* tp_richcompare */
1806 0, /* tp_weaklistoffset */
1807 PyObject_SelfIter, /* tp_iter */
1808 (iternextfunc)frozendictiter_iternextitem, /* tp_iternext */
1809 dictiter_methods, /* tp_methods */
1810 0,
1811 };
1812
1813 /*** dict_keys ***/
1814
1815 static PyObject *
1816 frozendictkeys_iter(_PyDictViewObject *dv)
1817 {
1818 if (dv->dv_dict == NULL) {
1819 Py_RETURN_NONE;
1820 }
1821 return dictiter_new(dv->dv_dict, &PyFrozenDictIterKey_Type);
1822 }
1823
1824 static PyTypeObject PyFrozenDictKeys_Type = {
1825 PyVarObject_HEAD_INIT(NULL, 0)
1826 FROZENDICT_MODULE_NAME ".keys", /* tp_name */
1827 sizeof(_PyDictViewObject), /* tp_basicsize */
1828 0, /* tp_itemsize */
1829 /* methods */
1830 (destructor)dictview_dealloc, /* tp_dealloc */
1831 0, /* tp_vectorcall_offset */
1832 0, /* tp_getattr */
1833 0, /* tp_setattr */
1834 0, /* tp_as_async */
1835 (reprfunc)dictview_repr, /* tp_repr */
1836 &dictviews_as_number, /* tp_as_number */
1837 &dictkeys_as_sequence, /* tp_as_sequence */
1838 0, /* tp_as_mapping */
1839 0, /* tp_hash */
1840 0, /* tp_call */
1841 0, /* tp_str */
1842 PyObject_GenericGetAttr, /* tp_getattro */
1843 0, /* tp_setattro */
1844 0, /* tp_as_buffer */
1845 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1846 0, /* tp_doc */
1847 (traverseproc)dictview_traverse, /* tp_traverse */
1848 0, /* tp_clear */
1849 dictview_richcompare, /* tp_richcompare */
1850 0, /* tp_weaklistoffset */
1851 (getiterfunc)frozendictkeys_iter, /* tp_iter */
1852 0, /* tp_iternext */
1853 dictkeys_methods, /* tp_methods */
1854 .tp_getset = dictview_getset,
1855 };
1856
1857 static PyObject *
1858 frozendictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
1859 {
1860 return _d_PyDictView_New(dict, &PyFrozenDictKeys_Type);
1861 }
1862
1863 /*** dict_items ***/
1864
1865 static PyObject *
1866 frozendictitems_iter(_PyDictViewObject *dv)
1867 {
1868 if (dv->dv_dict == NULL) {
1869 Py_RETURN_NONE;
1870 }
1871 return dictiter_new(dv->dv_dict, &PyFrozenDictIterItem_Type);
1872 }
1873
1874 static PyTypeObject PyFrozenDictItems_Type = {
1875 PyVarObject_HEAD_INIT(NULL, 0)
1876 FROZENDICT_MODULE_NAME ".items", /* tp_name */
1877 sizeof(_PyDictViewObject), /* tp_basicsize */
1878 0, /* tp_itemsize */
1879 /* methods */
1880 (destructor)dictview_dealloc, /* tp_dealloc */
1881 0, /* tp_vectorcall_offset */
1882 0, /* tp_getattr */
1883 0, /* tp_setattr */
1884 0, /* tp_as_async */
1885 (reprfunc)dictview_repr, /* tp_repr */
1886 &dictviews_as_number, /* tp_as_number */
1887 &dictitems_as_sequence, /* tp_as_sequence */
1888 0, /* tp_as_mapping */
1889 0, /* tp_hash */
1890 0, /* tp_call */
1891 0, /* tp_str */
1892 PyObject_GenericGetAttr, /* tp_getattro */
1893 0, /* tp_setattro */
1894 0, /* tp_as_buffer */
1895 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1896 0, /* tp_doc */
1897 (traverseproc)dictview_traverse, /* tp_traverse */
1898 0, /* tp_clear */
1899 dictview_richcompare, /* tp_richcompare */
1900 0, /* tp_weaklistoffset */
1901 (getiterfunc)frozendictitems_iter, /* tp_iter */
1902 0, /* tp_iternext */
1903 dictitems_methods, /* tp_methods */
1904 .tp_getset = dictview_getset,
1905 };
1906
1907 static PyObject *
1908 frozendictitems_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
1909 {
1910 return _d_PyDictView_New(dict, &PyFrozenDictItems_Type);
1911 }
1912
1913 /*** dict_values ***/
1914
1915 static PyObject *
1916 frozendictvalues_iter(_PyDictViewObject *dv)
1917 {
1918 if (dv->dv_dict == NULL) {
1919 Py_RETURN_NONE;
1920 }
1921 return dictiter_new(dv->dv_dict, &PyFrozenDictIterValue_Type);
1922 }
1923
1924 static PyTypeObject PyFrozenDictValues_Type = {
1925 PyVarObject_HEAD_INIT(NULL, 0)
1926 FROZENDICT_MODULE_NAME ".values", /* tp_name */
1927 sizeof(_PyDictViewObject), /* tp_basicsize */
1928 0, /* tp_itemsize */
1929 /* methods */
1930 (destructor)dictview_dealloc, /* tp_dealloc */
1931 0, /* tp_vectorcall_offset */
1932 0, /* tp_getattr */
1933 0, /* tp_setattr */
1934 0, /* tp_as_async */
1935 (reprfunc)dictview_repr, /* tp_repr */
1936 0, /* tp_as_number */
1937 &dictvalues_as_sequence, /* tp_as_sequence */
1938 0, /* tp_as_mapping */
1939 0, /* tp_hash */
1940 0, /* tp_call */
1941 0, /* tp_str */
1942 PyObject_GenericGetAttr, /* tp_getattro */
1943 0, /* tp_setattro */
1944 0, /* tp_as_buffer */
1945 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1946 0, /* tp_doc */
1947 (traverseproc)dictview_traverse, /* tp_traverse */
1948 0, /* tp_clear */
1949 0, /* tp_richcompare */
1950 0, /* tp_weaklistoffset */
1951 (getiterfunc)frozendictvalues_iter, /* tp_iter */
1952 0, /* tp_iternext */
1953 dictvalues_methods, /* tp_methods */
1954 .tp_getset = dictview_getset,
1955 };
1956
1957 static PyObject *
1958 frozendictvalues_new(PyObject *dict, PyObject *Py_UNUSED(ignored))
1959 {
1960 return _d_PyDictView_New(dict, &PyFrozenDictValues_Type);
1961 }
1962
1963 static int
1964 frozendict_exec(PyObject *m)
1965 {
1966 /* Finalize the type object including setting type of the new type
1967 * object; doing it here is required for portability, too. */
1968 if (PyType_Ready(&PyFrozenDict_Type) < 0) {
1969 goto fail;
1970 }
1971
1972 if (PyType_Ready(&PyFrozenDictIterKey_Type) < 0) {
1973 goto fail;
1974 }
1975
1976 if (PyType_Ready(&PyFrozenDictIterValue_Type) < 0) {
1977 goto fail;
1978 }
1979
1980 if (PyType_Ready(&PyFrozenDictIterItem_Type) < 0) {
1981 goto fail;
1982 }
1983
1984 if (PyType_Ready(&PyFrozenDictKeys_Type) < 0) {
1985 goto fail;
1986 }
1987
1988 if (PyType_Ready(&PyFrozenDictItems_Type) < 0) {
1989 goto fail;
1990 }
1991
1992 if (PyType_Ready(&PyFrozenDictValues_Type) < 0) {
1993 goto fail;
1994 }
1995
1996 if (PyType_Ready(&PyDictRevIterKey_Type) < 0) {
1997 goto fail;
1998 }
1999
2000 if (PyType_Ready(&PyDictRevIterItem_Type) < 0) {
2001 goto fail;
2002 }
2003
2004 if (PyType_Ready(&PyDictRevIterValue_Type) < 0) {
2005 goto fail;
2006 }
2007
2008 PyModule_AddObject(m, FROZENDICT_CLASS_NAME, (PyObject *)&PyFrozenDict_Type);
2009 return 0;
2010 fail:
2011 Py_XDECREF(m);
2012 return -1;
2013 }
2014
2015 static struct PyModuleDef_Slot frozendict_slots[] = {
2016 {Py_mod_exec, frozendict_exec},
2017 {0, NULL},
2018 };
2019
2020 static struct PyModuleDef frozendictmodule = {
2021 PyModuleDef_HEAD_INIT,
2022 FROZENDICT_MODULE_NAME, /* name of module */
2023 NULL, /* module documentation, may be NULL */
2024 0, /* size of per-interpreter state of the module,
2025 or -1 if the module keeps state in global variables. */
2026 NULL,
2027 frozendict_slots,
2028 NULL,
2029 NULL,
2030 NULL
2031 };
2032
2033 PyMODINIT_FUNC
2034 PyInit__frozendict(void)
2035 {
2036 return PyModuleDef_Init(&frozendictmodule);
2037 }