Debian Codegraph @

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