Debian Codegraph @

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