Debian Codegraph @

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

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