ยปCore Development>Code coverage>Objects/dictobject.c

Python code coverage for Objects/dictobject.c

#countcontent
1n/a/* Dictionary object implementation using a hash table */
2n/a
3n/a/* The distribution includes a separate file, Objects/dictnotes.txt,
4n/a describing explorations into dictionary design and optimization.
5n/a It covers typical dictionary use patterns, the parameters for
6n/a tuning dictionaries, and several ideas for possible optimizations.
7n/a*/
8n/a
9n/a/* PyDictKeysObject
10n/a
11n/aThis implements the dictionary's hashtable.
12n/a
13n/aAs of Python 3.6, this is compact and ordered. Basic idea is described here:
14n/a* https://mail.python.org/pipermail/python-dev/2012-December/123028.html
15n/a* https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
16n/a
17n/alayout:
18n/a
19n/a+---------------+
20n/a| dk_refcnt |
21n/a| dk_size |
22n/a| dk_lookup |
23n/a| dk_usable |
24n/a| dk_nentries |
25n/a+---------------+
26n/a| dk_indices |
27n/a| |
28n/a+---------------+
29n/a| dk_entries |
30n/a| |
31n/a+---------------+
32n/a
33n/adk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
34n/aor DKIX_DUMMY(-2).
35n/aSize of indices is dk_size. Type of each index in indices is vary on dk_size:
36n/a
37n/a* int8 for dk_size <= 128
38n/a* int16 for 256 <= dk_size <= 2**15
39n/a* int32 for 2**16 <= dk_size <= 2**31
40n/a* int64 for 2**32 <= dk_size
41n/a
42n/adk_entries is array of PyDictKeyEntry. It's size is USABLE_FRACTION(dk_size).
43n/aDK_ENTRIES(dk) can be used to get pointer to entries.
44n/a
45n/aNOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of
46n/adk_indices entry is signed integer and int16 is used for table which
47n/adk_size == 256.
48n/a*/
49n/a
50n/a
51n/a/*
52n/aThe DictObject can be in one of two forms.
53n/a
54n/aEither:
55n/a A combined table:
56n/a ma_values == NULL, dk_refcnt == 1.
57n/a Values are stored in the me_value field of the PyDictKeysObject.
58n/aOr:
59n/a A split table:
60n/a ma_values != NULL, dk_refcnt >= 1
61n/a Values are stored in the ma_values array.
62n/a Only string (unicode) keys are allowed.
63n/a All dicts sharing same key must have same insertion order.
64n/a
65n/aThere are four kinds of slots in the table (slot is index, and
66n/aDK_ENTRIES(keys)[index] if index >= 0):
67n/a
68n/a1. Unused. index == DKIX_EMPTY
69n/a Does not hold an active (key, value) pair now and never did. Unused can
70n/a transition to Active upon key insertion. This is each slot's initial state.
71n/a
72n/a2. Active. index >= 0, me_key != NULL and me_value != NULL
73n/a Holds an active (key, value) pair. Active can transition to Dummy or
74n/a Pending upon key deletion (for combined and split tables respectively).
75n/a This is the only case in which me_value != NULL.
76n/a
77n/a3. Dummy. index == DKIX_DUMMY (combined only)
78n/a Previously held an active (key, value) pair, but that was deleted and an
79n/a active pair has not yet overwritten the slot. Dummy can transition to
80n/a Active upon key insertion. Dummy slots cannot be made Unused again
81n/a else the probe sequence in case of collision would have no way to know
82n/a they were once active.
83n/a
84n/a4. Pending. index >= 0, key != NULL, and value == NULL (split only)
85n/a Not yet inserted in split-table.
86n/a*/
87n/a
88n/a/*
89n/aPreserving insertion order
90n/a
91n/aIt's simple for combined table. Since dk_entries is mostly append only, we can
92n/aget insertion order by just iterating dk_entries.
93n/a
94n/aOne exception is .popitem(). It removes last item in dk_entries and decrement
95n/adk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in
96n/adk_indices, we can't increment dk_usable even though dk_nentries is
97n/adecremented.
98n/a
99n/aIn split table, inserting into pending entry is allowed only for dk_entries[ix]
100n/awhere ix == mp->ma_used. Inserting into other index and deleting item cause
101n/aconverting the dict to the combined table.
102n/a*/
103n/a
104n/a/* PyDict_MINSIZE is the starting size for any new dict.
105n/a * 8 allows dicts with no more than 5 active entries; experiments suggested
106n/a * this suffices for the majority of dicts (consisting mostly of usually-small
107n/a * dicts created to pass keyword arguments).
108n/a * Making this 8, rather than 4 reduces the number of resizes for most
109n/a * dictionaries, without any significant extra memory use.
110n/a */
111n/a#define PyDict_MINSIZE 8
112n/a
113n/a#include "Python.h"
114n/a#include "dict-common.h"
115n/a#include "stringlib/eq.h" /* to get unicode_eq() */
116n/a
117n/a/*[clinic input]
118n/aclass dict "PyDictObject *" "&PyDict_Type"
119n/a[clinic start generated code]*/
120n/a/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/
121n/a
122n/a
123n/a/*
124n/aTo ensure the lookup algorithm terminates, there must be at least one Unused
125n/aslot (NULL key) in the table.
126n/aTo avoid slowing down lookups on a near-full table, we resize the table when
127n/ait's USABLE_FRACTION (currently two-thirds) full.
128n/a*/
129n/a
130n/a#define PERTURB_SHIFT 5
131n/a
132n/a/*
133n/aMajor subtleties ahead: Most hash schemes depend on having a "good" hash
134n/afunction, in the sense of simulating randomness. Python doesn't: its most
135n/aimportant hash functions (for ints) are very regular in common
136n/acases:
137n/a
138n/a >>>[hash(i) for i in range(4)]
139n/a [0, 1, 2, 3]
140n/a
141n/aThis isn't necessarily bad! To the contrary, in a table of size 2**i, taking
142n/athe low-order i bits as the initial table index is extremely fast, and there
143n/aare no collisions at all for dicts indexed by a contiguous range of ints. So
144n/athis gives better-than-random behavior in common cases, and that's very
145n/adesirable.
146n/a
147n/aOTOH, when collisions occur, the tendency to fill contiguous slices of the
148n/ahash table makes a good collision resolution strategy crucial. Taking only
149n/athe last i bits of the hash code is also vulnerable: for example, consider
150n/athe list [i << 16 for i in range(20000)] as a set of keys. Since ints are
151n/atheir own hash codes, and this fits in a dict of size 2**15, the last 15 bits
152n/a of every hash code are all 0: they *all* map to the same table index.
153n/a
154n/aBut catering to unusual cases should not slow the usual ones, so we just take
155n/athe last i bits anyway. It's up to collision resolution to do the rest. If
156n/awe *usually* find the key we're looking for on the first try (and, it turns
157n/aout, we usually do -- the table load factor is kept under 2/3, so the odds
158n/aare solidly in our favor), then it makes best sense to keep the initial index
159n/acomputation dirt cheap.
160n/a
161n/aThe first half of collision resolution is to visit table indices via this
162n/arecurrence:
163n/a
164n/a j = ((5*j) + 1) mod 2**i
165n/a
166n/aFor any initial j in range(2**i), repeating that 2**i times generates each
167n/aint in range(2**i) exactly once (see any text on random-number generation for
168n/aproof). By itself, this doesn't help much: like linear probing (setting
169n/aj += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed
170n/aorder. This would be bad, except that's not the only thing we do, and it's
171n/aactually *good* in the common cases where hash keys are consecutive. In an
172n/aexample that's really too small to make this entirely clear, for a table of
173n/asize 2**3 the order of indices is:
174n/a
175n/a 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]
176n/a
177n/aIf two things come in at index 5, the first place we look after is index 2,
178n/anot 6, so if another comes in at index 6 the collision at 5 didn't hurt it.
179n/aLinear probing is deadly in this case because there the fixed probe order
180n/ais the *same* as the order consecutive keys are likely to arrive. But it's
181n/aextremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
182n/aand certain that consecutive hash codes do not.
183n/a
184n/aThe other half of the strategy is to get the other bits of the hash code
185n/ainto play. This is done by initializing a (unsigned) vrbl "perturb" to the
186n/afull hash code, and changing the recurrence to:
187n/a
188n/a perturb >>= PERTURB_SHIFT;
189n/a j = (5*j) + 1 + perturb;
190n/a use j % 2**i as the next table index;
191n/a
192n/aNow the probe sequence depends (eventually) on every bit in the hash code,
193n/aand the pseudo-scrambling property of recurring on 5*j+1 is more valuable,
194n/abecause it quickly magnifies small differences in the bits that didn't affect
195n/athe initial index. Note that because perturb is unsigned, if the recurrence
196n/ais executed often enough perturb eventually becomes and remains 0. At that
197n/apoint (very rarely reached) the recurrence is on (just) 5*j+1 again, and
198n/athat's certain to find an empty slot eventually (since it generates every int
199n/ain range(2**i), and we make sure there's always at least one empty slot).
200n/a
201n/aSelecting a good value for PERTURB_SHIFT is a balancing act. You want it
202n/asmall so that the high bits of the hash code continue to affect the probe
203n/asequence across iterations; but you want it large so that in really bad cases
204n/athe high-order hash bits have an effect on early iterations. 5 was "the
205n/abest" in minimizing total collisions across experiments Tim Peters ran (on
206n/aboth normal and pathological cases), but 4 and 6 weren't significantly worse.
207n/a
208n/aHistorical: Reimer Behrends contributed the idea of using a polynomial-based
209n/aapproach, using repeated multiplication by x in GF(2**n) where an irreducible
210n/apolynomial for each table size was chosen such that x was a primitive root.
211n/aChristian Tismer later extended that to use division by x instead, as an
212n/aefficient way to get the high bits of the hash code into play. This scheme
213n/aalso gave excellent collision statistics, but was more expensive: two
214n/aif-tests were required inside the loop; computing "the next" index took about
215n/athe same number of operations but without as much potential parallelism
216n/a(e.g., computing 5*j can go on at the same time as computing 1+perturb in the
217n/aabove, and then shifting perturb can be done while the table index is being
218n/amasked); and the PyDictObject struct required a member to hold the table's
219n/apolynomial. In Tim's experiments the current scheme ran faster, produced
220n/aequally good collision statistics, needed less code & used less memory.
221n/a
222n/a*/
223n/a
224n/a/* forward declarations */
225n/astatic Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
226n/a Py_hash_t hash, PyObject **value_addr,
227n/a Py_ssize_t *hashpos);
228n/astatic Py_ssize_t lookdict_unicode(PyDictObject *mp, PyObject *key,
229n/a Py_hash_t hash, PyObject **value_addr,
230n/a Py_ssize_t *hashpos);
231n/astatic Py_ssize_t
232n/alookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
233n/a Py_hash_t hash, PyObject **value_addr,
234n/a Py_ssize_t *hashpos);
235n/astatic Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key,
236n/a Py_hash_t hash, PyObject **value_addr,
237n/a Py_ssize_t *hashpos);
238n/a
239n/astatic int dictresize(PyDictObject *mp, Py_ssize_t minused);
240n/a
241n/a/*Global counter used to set ma_version_tag field of dictionary.
242n/a * It is incremented each time that a dictionary is created and each
243n/a * time that a dictionary is modified. */
244n/astatic uint64_t pydict_global_version = 0;
245n/a
246n/a#define DICT_NEXT_VERSION() (++pydict_global_version)
247n/a
248n/a/* Dictionary reuse scheme to save calls to malloc and free */
249n/a#ifndef PyDict_MAXFREELIST
250n/a#define PyDict_MAXFREELIST 80
251n/a#endif
252n/astatic PyDictObject *free_list[PyDict_MAXFREELIST];
253n/astatic int numfree = 0;
254n/astatic PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
255n/astatic int numfreekeys = 0;
256n/a
257n/a#include "clinic/dictobject.c.h"
258n/a
259n/aint
260n/aPyDict_ClearFreeList(void)
261n/a{
262n/a PyDictObject *op;
263n/a int ret = numfree + numfreekeys;
264n/a while (numfree) {
265n/a op = free_list[--numfree];
266n/a assert(PyDict_CheckExact(op));
267n/a PyObject_GC_Del(op);
268n/a }
269n/a while (numfreekeys) {
270n/a PyObject_FREE(keys_free_list[--numfreekeys]);
271n/a }
272n/a return ret;
273n/a}
274n/a
275n/a/* Print summary info about the state of the optimized allocator */
276n/avoid
277n/a_PyDict_DebugMallocStats(FILE *out)
278n/a{
279n/a _PyDebugAllocatorStats(out,
280n/a "free PyDictObject", numfree, sizeof(PyDictObject));
281n/a}
282n/a
283n/a
284n/avoid
285n/aPyDict_Fini(void)
286n/a{
287n/a PyDict_ClearFreeList();
288n/a}
289n/a
290n/a#define DK_SIZE(dk) ((dk)->dk_size)
291n/a#if SIZEOF_VOID_P > 4
292n/a#define DK_IXSIZE(dk) \
293n/a (DK_SIZE(dk) <= 0xff ? \
294n/a 1 : DK_SIZE(dk) <= 0xffff ? \
295n/a 2 : DK_SIZE(dk) <= 0xffffffff ? \
296n/a 4 : sizeof(int64_t))
297n/a#else
298n/a#define DK_IXSIZE(dk) \
299n/a (DK_SIZE(dk) <= 0xff ? \
300n/a 1 : DK_SIZE(dk) <= 0xffff ? \
301n/a 2 : sizeof(int32_t))
302n/a#endif
303n/a#define DK_ENTRIES(dk) \
304n/a ((PyDictKeyEntry*)(&(dk)->dk_indices.as_1[DK_SIZE(dk) * DK_IXSIZE(dk)]))
305n/a
306n/a#define DK_DEBUG_INCREF _Py_INC_REFTOTAL _Py_REF_DEBUG_COMMA
307n/a#define DK_DEBUG_DECREF _Py_DEC_REFTOTAL _Py_REF_DEBUG_COMMA
308n/a
309n/a#define DK_INCREF(dk) (DK_DEBUG_INCREF ++(dk)->dk_refcnt)
310n/a#define DK_DECREF(dk) if (DK_DEBUG_DECREF (--(dk)->dk_refcnt) == 0) free_keys_object(dk)
311n/a#define DK_MASK(dk) (((dk)->dk_size)-1)
312n/a#define IS_POWER_OF_2(x) (((x) & (x-1)) == 0)
313n/a
314n/a/* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
315n/astatic inline Py_ssize_t
316n/adk_get_index(PyDictKeysObject *keys, Py_ssize_t i)
317n/a{
318n/a Py_ssize_t s = DK_SIZE(keys);
319n/a Py_ssize_t ix;
320n/a
321n/a if (s <= 0xff) {
322n/a int8_t *indices = keys->dk_indices.as_1;
323n/a ix = indices[i];
324n/a }
325n/a else if (s <= 0xffff) {
326n/a int16_t *indices = keys->dk_indices.as_2;
327n/a ix = indices[i];
328n/a }
329n/a#if SIZEOF_VOID_P > 4
330n/a else if (s > 0xffffffff) {
331n/a int64_t *indices = keys->dk_indices.as_8;
332n/a ix = indices[i];
333n/a }
334n/a#endif
335n/a else {
336n/a int32_t *indices = keys->dk_indices.as_4;
337n/a ix = indices[i];
338n/a }
339n/a assert(ix >= DKIX_DUMMY);
340n/a return ix;
341n/a}
342n/a
343n/a/* write to indices. */
344n/astatic inline void
345n/adk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)
346n/a{
347n/a Py_ssize_t s = DK_SIZE(keys);
348n/a
349n/a assert(ix >= DKIX_DUMMY);
350n/a
351n/a if (s <= 0xff) {
352n/a int8_t *indices = keys->dk_indices.as_1;
353n/a assert(ix <= 0x7f);
354n/a indices[i] = (char)ix;
355n/a }
356n/a else if (s <= 0xffff) {
357n/a int16_t *indices = keys->dk_indices.as_2;
358n/a assert(ix <= 0x7fff);
359n/a indices[i] = (int16_t)ix;
360n/a }
361n/a#if SIZEOF_VOID_P > 4
362n/a else if (s > 0xffffffff) {
363n/a int64_t *indices = keys->dk_indices.as_8;
364n/a indices[i] = ix;
365n/a }
366n/a#endif
367n/a else {
368n/a int32_t *indices = keys->dk_indices.as_4;
369n/a assert(ix <= 0x7fffffff);
370n/a indices[i] = (int32_t)ix;
371n/a }
372n/a}
373n/a
374n/a
375n/a/* USABLE_FRACTION is the maximum dictionary load.
376n/a * Increasing this ratio makes dictionaries more dense resulting in more
377n/a * collisions. Decreasing it improves sparseness at the expense of spreading
378n/a * indices over more cache lines and at the cost of total memory consumed.
379n/a *
380n/a * USABLE_FRACTION must obey the following:
381n/a * (0 < USABLE_FRACTION(n) < n) for all n >= 2
382n/a *
383n/a * USABLE_FRACTION should be quick to calculate.
384n/a * Fractions around 1/2 to 2/3 seem to work well in practice.
385n/a */
386n/a#define USABLE_FRACTION(n) (((n) << 1)/3)
387n/a
388n/a/* ESTIMATE_SIZE is reverse function of USABLE_FRACTION.
389n/a * This can be used to reserve enough size to insert n entries without
390n/a * resizing.
391n/a */
392n/a#define ESTIMATE_SIZE(n) (((n)*3+1) >> 1)
393n/a
394n/a/* Alternative fraction that is otherwise close enough to 2n/3 to make
395n/a * little difference. 8 * 2/3 == 8 * 5/8 == 5. 16 * 2/3 == 16 * 5/8 == 10.
396n/a * 32 * 2/3 = 21, 32 * 5/8 = 20.
397n/a * Its advantage is that it is faster to compute on machines with slow division.
398n/a * #define USABLE_FRACTION(n) (((n) >> 1) + ((n) >> 2) - ((n) >> 3))
399n/a */
400n/a
401n/a/* GROWTH_RATE. Growth rate upon hitting maximum load.
402n/a * Currently set to used*2 + capacity/2.
403n/a * This means that dicts double in size when growing without deletions,
404n/a * but have more head room when the number of deletions is on a par with the
405n/a * number of insertions.
406n/a * Raising this to used*4 doubles memory consumption depending on the size of
407n/a * the dictionary, but results in half the number of resizes, less effort to
408n/a * resize.
409n/a * GROWTH_RATE was set to used*4 up to version 3.2.
410n/a * GROWTH_RATE was set to used*2 in version 3.3.0
411n/a */
412n/a#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))
413n/a
414n/a#define ENSURE_ALLOWS_DELETIONS(d) \
415n/a if ((d)->ma_keys->dk_lookup == lookdict_unicode_nodummy) { \
416n/a (d)->ma_keys->dk_lookup = lookdict_unicode; \
417n/a }
418n/a
419n/a/* This immutable, empty PyDictKeysObject is used for PyDict_Clear()
420n/a * (which cannot fail and thus can do no allocation).
421n/a */
422n/astatic PyDictKeysObject empty_keys_struct = {
423n/a 1, /* dk_refcnt */
424n/a 1, /* dk_size */
425n/a lookdict_split, /* dk_lookup */
426n/a 0, /* dk_usable (immutable) */
427n/a 0, /* dk_nentries */
428n/a .dk_indices = { .as_1 = {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
429n/a DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}},
430n/a};
431n/a
432n/astatic PyObject *empty_values[1] = { NULL };
433n/a
434n/a#define Py_EMPTY_KEYS &empty_keys_struct
435n/a
436n/a/* Uncomment to check the dict content in _PyDict_CheckConsistency() */
437n/a/* #define DEBUG_PYDICT */
438n/a
439n/a
440n/a#ifdef Py_DEBUG
441n/astatic int
442n/a_PyDict_CheckConsistency(PyDictObject *mp)
443n/a{
444n/a PyDictKeysObject *keys = mp->ma_keys;
445n/a int splitted = _PyDict_HasSplitTable(mp);
446n/a Py_ssize_t usable = USABLE_FRACTION(keys->dk_size);
447n/a#ifdef DEBUG_PYDICT
448n/a PyDictKeyEntry *entries = DK_ENTRIES(keys);
449n/a Py_ssize_t i;
450n/a#endif
451n/a
452n/a assert(0 <= mp->ma_used && mp->ma_used <= usable);
453n/a assert(IS_POWER_OF_2(keys->dk_size));
454n/a assert(0 <= keys->dk_usable
455n/a && keys->dk_usable <= usable);
456n/a assert(0 <= keys->dk_nentries
457n/a && keys->dk_nentries <= usable);
458n/a assert(keys->dk_usable + keys->dk_nentries <= usable);
459n/a
460n/a if (!splitted) {
461n/a /* combined table */
462n/a assert(keys->dk_refcnt == 1);
463n/a }
464n/a
465n/a#ifdef DEBUG_PYDICT
466n/a for (i=0; i < keys->dk_size; i++) {
467n/a Py_ssize_t ix = dk_get_index(keys, i);
468n/a assert(DKIX_DUMMY <= ix && ix <= usable);
469n/a }
470n/a
471n/a for (i=0; i < usable; i++) {
472n/a PyDictKeyEntry *entry = &entries[i];
473n/a PyObject *key = entry->me_key;
474n/a
475n/a if (key != NULL) {
476n/a if (PyUnicode_CheckExact(key)) {
477n/a Py_hash_t hash = ((PyASCIIObject *)key)->hash;
478n/a assert(hash != -1);
479n/a assert(entry->me_hash == hash);
480n/a }
481n/a else {
482n/a /* test_dict fails if PyObject_Hash() is called again */
483n/a assert(entry->me_hash != -1);
484n/a }
485n/a if (!splitted) {
486n/a assert(entry->me_value != NULL);
487n/a }
488n/a }
489n/a
490n/a if (splitted) {
491n/a assert(entry->me_value == NULL);
492n/a }
493n/a }
494n/a
495n/a if (splitted) {
496n/a /* splitted table */
497n/a for (i=0; i < mp->ma_used; i++) {
498n/a assert(mp->ma_values[i] != NULL);
499n/a }
500n/a }
501n/a#endif
502n/a
503n/a return 1;
504n/a}
505n/a#endif
506n/a
507n/a
508n/astatic PyDictKeysObject *new_keys_object(Py_ssize_t size)
509n/a{
510n/a PyDictKeysObject *dk;
511n/a Py_ssize_t es, usable;
512n/a
513n/a assert(size >= PyDict_MINSIZE);
514n/a assert(IS_POWER_OF_2(size));
515n/a
516n/a usable = USABLE_FRACTION(size);
517n/a if (size <= 0xff) {
518n/a es = 1;
519n/a }
520n/a else if (size <= 0xffff) {
521n/a es = 2;
522n/a }
523n/a#if SIZEOF_VOID_P > 4
524n/a else if (size <= 0xffffffff) {
525n/a es = 4;
526n/a }
527n/a#endif
528n/a else {
529n/a es = sizeof(Py_ssize_t);
530n/a }
531n/a
532n/a if (size == PyDict_MINSIZE && numfreekeys > 0) {
533n/a dk = keys_free_list[--numfreekeys];
534n/a }
535n/a else {
536n/a dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
537n/a - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
538n/a + es * size
539n/a + sizeof(PyDictKeyEntry) * usable);
540n/a if (dk == NULL) {
541n/a PyErr_NoMemory();
542n/a return NULL;
543n/a }
544n/a }
545n/a DK_DEBUG_INCREF dk->dk_refcnt = 1;
546n/a dk->dk_size = size;
547n/a dk->dk_usable = usable;
548n/a dk->dk_lookup = lookdict_unicode_nodummy;
549n/a dk->dk_nentries = 0;
550n/a memset(&dk->dk_indices.as_1[0], 0xff, es * size);
551n/a memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
552n/a return dk;
553n/a}
554n/a
555n/astatic void
556n/afree_keys_object(PyDictKeysObject *keys)
557n/a{
558n/a PyDictKeyEntry *entries = DK_ENTRIES(keys);
559n/a Py_ssize_t i, n;
560n/a for (i = 0, n = keys->dk_nentries; i < n; i++) {
561n/a Py_XDECREF(entries[i].me_key);
562n/a Py_XDECREF(entries[i].me_value);
563n/a }
564n/a if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
565n/a keys_free_list[numfreekeys++] = keys;
566n/a return;
567n/a }
568n/a PyObject_FREE(keys);
569n/a}
570n/a
571n/a#define new_values(size) PyMem_NEW(PyObject *, size)
572n/a#define free_values(values) PyMem_FREE(values)
573n/a
574n/a/* Consumes a reference to the keys object */
575n/astatic PyObject *
576n/anew_dict(PyDictKeysObject *keys, PyObject **values)
577n/a{
578n/a PyDictObject *mp;
579n/a assert(keys != NULL);
580n/a if (numfree) {
581n/a mp = free_list[--numfree];
582n/a assert (mp != NULL);
583n/a assert (Py_TYPE(mp) == &PyDict_Type);
584n/a _Py_NewReference((PyObject *)mp);
585n/a }
586n/a else {
587n/a mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
588n/a if (mp == NULL) {
589n/a DK_DECREF(keys);
590n/a free_values(values);
591n/a return NULL;
592n/a }
593n/a }
594n/a mp->ma_keys = keys;
595n/a mp->ma_values = values;
596n/a mp->ma_used = 0;
597n/a mp->ma_version_tag = DICT_NEXT_VERSION();
598n/a assert(_PyDict_CheckConsistency(mp));
599n/a return (PyObject *)mp;
600n/a}
601n/a
602n/a/* Consumes a reference to the keys object */
603n/astatic PyObject *
604n/anew_dict_with_shared_keys(PyDictKeysObject *keys)
605n/a{
606n/a PyObject **values;
607n/a Py_ssize_t i, size;
608n/a
609n/a size = USABLE_FRACTION(DK_SIZE(keys));
610n/a values = new_values(size);
611n/a if (values == NULL) {
612n/a DK_DECREF(keys);
613n/a return PyErr_NoMemory();
614n/a }
615n/a for (i = 0; i < size; i++) {
616n/a values[i] = NULL;
617n/a }
618n/a return new_dict(keys, values);
619n/a}
620n/a
621n/aPyObject *
622n/aPyDict_New(void)
623n/a{
624n/a PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
625n/a if (keys == NULL)
626n/a return NULL;
627n/a return new_dict(keys, NULL);
628n/a}
629n/a
630n/a/* Search index of hash table from offset of entry table */
631n/astatic Py_ssize_t
632n/alookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
633n/a{
634n/a size_t i;
635n/a size_t mask = DK_MASK(k);
636n/a Py_ssize_t ix;
637n/a
638n/a i = (size_t)hash & mask;
639n/a ix = dk_get_index(k, i);
640n/a if (ix == index) {
641n/a return i;
642n/a }
643n/a if (ix == DKIX_EMPTY) {
644n/a return DKIX_EMPTY;
645n/a }
646n/a
647n/a for (size_t perturb = hash;;) {
648n/a perturb >>= PERTURB_SHIFT;
649n/a i = mask & ((i << 2) + i + perturb + 1);
650n/a ix = dk_get_index(k, i);
651n/a if (ix == index) {
652n/a return i;
653n/a }
654n/a if (ix == DKIX_EMPTY) {
655n/a return DKIX_EMPTY;
656n/a }
657n/a }
658n/a assert(0); /* NOT REACHED */
659n/a return DKIX_ERROR;
660n/a}
661n/a
662n/a/*
663n/aThe basic lookup function used by all operations.
664n/aThis is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
665n/aOpen addressing is preferred over chaining since the link overhead for
666n/achaining would be substantial (100% with typical malloc overhead).
667n/a
668n/aThe initial probe index is computed as hash mod the table size. Subsequent
669n/aprobe indices are computed as explained earlier.
670n/a
671n/aAll arithmetic on hash should ignore overflow.
672n/a
673n/aThe details in this version are due to Tim Peters, building on many past
674n/acontributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and
675n/aChristian Tismer.
676n/a
677n/alookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a
678n/acomparison raises an exception.
679n/alookdict_unicode() below is specialized to string keys, comparison of which can
680n/anever raise an exception; that function can never return DKIX_ERROR.
681n/alookdict_unicode_nodummy is further specialized for string keys that cannot be
682n/athe <dummy> value.
683n/aFor both, when the key isn't found a DKIX_EMPTY is returned. hashpos returns
684n/awhere the key index should be inserted.
685n/a*/
686n/astatic Py_ssize_t _Py_HOT_FUNCTION
687n/alookdict(PyDictObject *mp, PyObject *key,
688n/a Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos)
689n/a{
690n/a size_t i, mask;
691n/a Py_ssize_t ix, freeslot;
692n/a int cmp;
693n/a PyDictKeysObject *dk;
694n/a PyDictKeyEntry *ep0, *ep;
695n/a PyObject *startkey;
696n/a
697n/atop:
698n/a dk = mp->ma_keys;
699n/a mask = DK_MASK(dk);
700n/a ep0 = DK_ENTRIES(dk);
701n/a i = (size_t)hash & mask;
702n/a
703n/a ix = dk_get_index(dk, i);
704n/a if (ix == DKIX_EMPTY) {
705n/a if (hashpos != NULL)
706n/a *hashpos = i;
707n/a *value_addr = NULL;
708n/a return DKIX_EMPTY;
709n/a }
710n/a if (ix == DKIX_DUMMY) {
711n/a freeslot = i;
712n/a }
713n/a else {
714n/a ep = &ep0[ix];
715n/a assert(ep->me_key != NULL);
716n/a if (ep->me_key == key) {
717n/a *value_addr = ep->me_value;
718n/a if (hashpos != NULL)
719n/a *hashpos = i;
720n/a return ix;
721n/a }
722n/a if (ep->me_hash == hash) {
723n/a startkey = ep->me_key;
724n/a Py_INCREF(startkey);
725n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
726n/a Py_DECREF(startkey);
727n/a if (cmp < 0) {
728n/a *value_addr = NULL;
729n/a return DKIX_ERROR;
730n/a }
731n/a if (dk == mp->ma_keys && ep->me_key == startkey) {
732n/a if (cmp > 0) {
733n/a *value_addr = ep->me_value;
734n/a if (hashpos != NULL)
735n/a *hashpos = i;
736n/a return ix;
737n/a }
738n/a }
739n/a else {
740n/a /* The dict was mutated, restart */
741n/a goto top;
742n/a }
743n/a }
744n/a freeslot = -1;
745n/a }
746n/a
747n/a for (size_t perturb = hash;;) {
748n/a perturb >>= PERTURB_SHIFT;
749n/a i = ((i << 2) + i + perturb + 1) & mask;
750n/a ix = dk_get_index(dk, i);
751n/a if (ix == DKIX_EMPTY) {
752n/a if (hashpos != NULL) {
753n/a *hashpos = (freeslot == -1) ? (Py_ssize_t)i : freeslot;
754n/a }
755n/a *value_addr = NULL;
756n/a return ix;
757n/a }
758n/a if (ix == DKIX_DUMMY) {
759n/a if (freeslot == -1)
760n/a freeslot = i;
761n/a continue;
762n/a }
763n/a ep = &ep0[ix];
764n/a assert(ep->me_key != NULL);
765n/a if (ep->me_key == key) {
766n/a if (hashpos != NULL) {
767n/a *hashpos = i;
768n/a }
769n/a *value_addr = ep->me_value;
770n/a return ix;
771n/a }
772n/a if (ep->me_hash == hash) {
773n/a startkey = ep->me_key;
774n/a Py_INCREF(startkey);
775n/a cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
776n/a Py_DECREF(startkey);
777n/a if (cmp < 0) {
778n/a *value_addr = NULL;
779n/a return DKIX_ERROR;
780n/a }
781n/a if (dk == mp->ma_keys && ep->me_key == startkey) {
782n/a if (cmp > 0) {
783n/a if (hashpos != NULL) {
784n/a *hashpos = i;
785n/a }
786n/a *value_addr = ep->me_value;
787n/a return ix;
788n/a }
789n/a }
790n/a else {
791n/a /* The dict was mutated, restart */
792n/a goto top;
793n/a }
794n/a }
795n/a }
796n/a assert(0); /* NOT REACHED */
797n/a return 0;
798n/a}
799n/a
800n/a/* Specialized version for string-only keys */
801n/astatic Py_ssize_t _Py_HOT_FUNCTION
802n/alookdict_unicode(PyDictObject *mp, PyObject *key,
803n/a Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos)
804n/a{
805n/a size_t i;
806n/a size_t mask = DK_MASK(mp->ma_keys);
807n/a Py_ssize_t ix, freeslot;
808n/a PyDictKeyEntry *ep, *ep0 = DK_ENTRIES(mp->ma_keys);
809n/a
810n/a assert(mp->ma_values == NULL);
811n/a /* Make sure this function doesn't have to handle non-unicode keys,
812n/a including subclasses of str; e.g., one reason to subclass
813n/a unicodes is to override __eq__, and for speed we don't cater to
814n/a that here. */
815n/a if (!PyUnicode_CheckExact(key)) {
816n/a mp->ma_keys->dk_lookup = lookdict;
817n/a return lookdict(mp, key, hash, value_addr, hashpos);
818n/a }
819n/a i = (size_t)hash & mask;
820n/a ix = dk_get_index(mp->ma_keys, i);
821n/a if (ix == DKIX_EMPTY) {
822n/a if (hashpos != NULL)
823n/a *hashpos = i;
824n/a *value_addr = NULL;
825n/a return DKIX_EMPTY;
826n/a }
827n/a if (ix == DKIX_DUMMY) {
828n/a freeslot = i;
829n/a }
830n/a else {
831n/a ep = &ep0[ix];
832n/a assert(ep->me_key != NULL);
833n/a if (ep->me_key == key
834n/a || (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
835n/a if (hashpos != NULL)
836n/a *hashpos = i;
837n/a *value_addr = ep->me_value;
838n/a return ix;
839n/a }
840n/a freeslot = -1;
841n/a }
842n/a
843n/a for (size_t perturb = hash;;) {
844n/a perturb >>= PERTURB_SHIFT;
845n/a i = mask & ((i << 2) + i + perturb + 1);
846n/a ix = dk_get_index(mp->ma_keys, i);
847n/a if (ix == DKIX_EMPTY) {
848n/a if (hashpos != NULL) {
849n/a *hashpos = (freeslot == -1) ? (Py_ssize_t)i : freeslot;
850n/a }
851n/a *value_addr = NULL;
852n/a return DKIX_EMPTY;
853n/a }
854n/a if (ix == DKIX_DUMMY) {
855n/a if (freeslot == -1)
856n/a freeslot = i;
857n/a continue;
858n/a }
859n/a ep = &ep0[ix];
860n/a assert(ep->me_key != NULL);
861n/a if (ep->me_key == key
862n/a || (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
863n/a *value_addr = ep->me_value;
864n/a if (hashpos != NULL) {
865n/a *hashpos = i;
866n/a }
867n/a return ix;
868n/a }
869n/a }
870n/a assert(0); /* NOT REACHED */
871n/a return 0;
872n/a}
873n/a
874n/a/* Faster version of lookdict_unicode when it is known that no <dummy> keys
875n/a * will be present. */
876n/astatic Py_ssize_t _Py_HOT_FUNCTION
877n/alookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
878n/a Py_hash_t hash, PyObject **value_addr,
879n/a Py_ssize_t *hashpos)
880n/a{
881n/a size_t i;
882n/a size_t mask = DK_MASK(mp->ma_keys);
883n/a Py_ssize_t ix;
884n/a PyDictKeyEntry *ep, *ep0 = DK_ENTRIES(mp->ma_keys);
885n/a
886n/a assert(mp->ma_values == NULL);
887n/a /* Make sure this function doesn't have to handle non-unicode keys,
888n/a including subclasses of str; e.g., one reason to subclass
889n/a unicodes is to override __eq__, and for speed we don't cater to
890n/a that here. */
891n/a if (!PyUnicode_CheckExact(key)) {
892n/a mp->ma_keys->dk_lookup = lookdict;
893n/a return lookdict(mp, key, hash, value_addr, hashpos);
894n/a }
895n/a i = (size_t)hash & mask;
896n/a ix = dk_get_index(mp->ma_keys, i);
897n/a assert (ix != DKIX_DUMMY);
898n/a if (ix == DKIX_EMPTY) {
899n/a if (hashpos != NULL)
900n/a *hashpos = i;
901n/a *value_addr = NULL;
902n/a return DKIX_EMPTY;
903n/a }
904n/a ep = &ep0[ix];
905n/a assert(ep->me_key != NULL);
906n/a assert(PyUnicode_CheckExact(ep->me_key));
907n/a if (ep->me_key == key ||
908n/a (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
909n/a if (hashpos != NULL)
910n/a *hashpos = i;
911n/a *value_addr = ep->me_value;
912n/a return ix;
913n/a }
914n/a for (size_t perturb = hash;;) {
915n/a perturb >>= PERTURB_SHIFT;
916n/a i = mask & ((i << 2) + i + perturb + 1);
917n/a ix = dk_get_index(mp->ma_keys, i);
918n/a assert (ix != DKIX_DUMMY);
919n/a if (ix == DKIX_EMPTY) {
920n/a if (hashpos != NULL)
921n/a *hashpos = i;
922n/a *value_addr = NULL;
923n/a return DKIX_EMPTY;
924n/a }
925n/a ep = &ep0[ix];
926n/a assert(ep->me_key != NULL && PyUnicode_CheckExact(ep->me_key));
927n/a if (ep->me_key == key ||
928n/a (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
929n/a if (hashpos != NULL)
930n/a *hashpos = i;
931n/a *value_addr = ep->me_value;
932n/a return ix;
933n/a }
934n/a }
935n/a assert(0); /* NOT REACHED */
936n/a return 0;
937n/a}
938n/a
939n/a/* Version of lookdict for split tables.
940n/a * All split tables and only split tables use this lookup function.
941n/a * Split tables only contain unicode keys and no dummy keys,
942n/a * so algorithm is the same as lookdict_unicode_nodummy.
943n/a */
944n/astatic Py_ssize_t _Py_HOT_FUNCTION
945n/alookdict_split(PyDictObject *mp, PyObject *key,
946n/a Py_hash_t hash, PyObject **value_addr, Py_ssize_t *hashpos)
947n/a{
948n/a size_t i;
949n/a size_t mask = DK_MASK(mp->ma_keys);
950n/a Py_ssize_t ix;
951n/a PyDictKeyEntry *ep, *ep0 = DK_ENTRIES(mp->ma_keys);
952n/a
953n/a /* mp must split table */
954n/a assert(mp->ma_values != NULL);
955n/a if (!PyUnicode_CheckExact(key)) {
956n/a ix = lookdict(mp, key, hash, value_addr, hashpos);
957n/a if (ix >= 0) {
958n/a *value_addr = mp->ma_values[ix];
959n/a }
960n/a return ix;
961n/a }
962n/a
963n/a i = (size_t)hash & mask;
964n/a ix = dk_get_index(mp->ma_keys, i);
965n/a if (ix == DKIX_EMPTY) {
966n/a if (hashpos != NULL)
967n/a *hashpos = i;
968n/a *value_addr = NULL;
969n/a return DKIX_EMPTY;
970n/a }
971n/a assert(ix >= 0);
972n/a ep = &ep0[ix];
973n/a assert(ep->me_key != NULL && PyUnicode_CheckExact(ep->me_key));
974n/a if (ep->me_key == key ||
975n/a (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
976n/a if (hashpos != NULL)
977n/a *hashpos = i;
978n/a *value_addr = mp->ma_values[ix];
979n/a return ix;
980n/a }
981n/a for (size_t perturb = hash;;) {
982n/a perturb >>= PERTURB_SHIFT;
983n/a i = mask & ((i << 2) + i + perturb + 1);
984n/a ix = dk_get_index(mp->ma_keys, i);
985n/a if (ix == DKIX_EMPTY) {
986n/a if (hashpos != NULL)
987n/a *hashpos = i;
988n/a *value_addr = NULL;
989n/a return DKIX_EMPTY;
990n/a }
991n/a assert(ix >= 0);
992n/a ep = &ep0[ix];
993n/a assert(ep->me_key != NULL && PyUnicode_CheckExact(ep->me_key));
994n/a if (ep->me_key == key ||
995n/a (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
996n/a if (hashpos != NULL)
997n/a *hashpos = i;
998n/a *value_addr = mp->ma_values[ix];
999n/a return ix;
1000n/a }
1001n/a }
1002n/a assert(0); /* NOT REACHED */
1003n/a return 0;
1004n/a}
1005n/a
1006n/aint
1007n/a_PyDict_HasOnlyStringKeys(PyObject *dict)
1008n/a{
1009n/a Py_ssize_t pos = 0;
1010n/a PyObject *key, *value;
1011n/a assert(PyDict_Check(dict));
1012n/a /* Shortcut */
1013n/a if (((PyDictObject *)dict)->ma_keys->dk_lookup != lookdict)
1014n/a return 1;
1015n/a while (PyDict_Next(dict, &pos, &key, &value))
1016n/a if (!PyUnicode_Check(key))
1017n/a return 0;
1018n/a return 1;
1019n/a}
1020n/a
1021n/a#define MAINTAIN_TRACKING(mp, key, value) \
1022n/a do { \
1023n/a if (!_PyObject_GC_IS_TRACKED(mp)) { \
1024n/a if (_PyObject_GC_MAY_BE_TRACKED(key) || \
1025n/a _PyObject_GC_MAY_BE_TRACKED(value)) { \
1026n/a _PyObject_GC_TRACK(mp); \
1027n/a } \
1028n/a } \
1029n/a } while(0)
1030n/a
1031n/avoid
1032n/a_PyDict_MaybeUntrack(PyObject *op)
1033n/a{
1034n/a PyDictObject *mp;
1035n/a PyObject *value;
1036n/a Py_ssize_t i, numentries;
1037n/a PyDictKeyEntry *ep0;
1038n/a
1039n/a if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
1040n/a return;
1041n/a
1042n/a mp = (PyDictObject *) op;
1043n/a ep0 = DK_ENTRIES(mp->ma_keys);
1044n/a numentries = mp->ma_keys->dk_nentries;
1045n/a if (_PyDict_HasSplitTable(mp)) {
1046n/a for (i = 0; i < numentries; i++) {
1047n/a if ((value = mp->ma_values[i]) == NULL)
1048n/a continue;
1049n/a if (_PyObject_GC_MAY_BE_TRACKED(value)) {
1050n/a assert(!_PyObject_GC_MAY_BE_TRACKED(ep0[i].me_key));
1051n/a return;
1052n/a }
1053n/a }
1054n/a }
1055n/a else {
1056n/a for (i = 0; i < numentries; i++) {
1057n/a if ((value = ep0[i].me_value) == NULL)
1058n/a continue;
1059n/a if (_PyObject_GC_MAY_BE_TRACKED(value) ||
1060n/a _PyObject_GC_MAY_BE_TRACKED(ep0[i].me_key))
1061n/a return;
1062n/a }
1063n/a }
1064n/a _PyObject_GC_UNTRACK(op);
1065n/a}
1066n/a
1067n/a/* Internal function to find slot for an item from its hash
1068n/a when it is known that the key is not present in the dict.
1069n/a
1070n/a The dict must be combined. */
1071n/astatic Py_ssize_t
1072n/afind_empty_slot(PyDictKeysObject *keys, PyObject *key, Py_hash_t hash)
1073n/a{
1074n/a size_t i;
1075n/a size_t mask = DK_MASK(keys);
1076n/a Py_ssize_t ix;
1077n/a
1078n/a assert(key != NULL);
1079n/a
1080n/a i = hash & mask;
1081n/a ix = dk_get_index(keys, i);
1082n/a for (size_t perturb = hash; ix != DKIX_EMPTY;) {
1083n/a perturb >>= PERTURB_SHIFT;
1084n/a i = (i << 2) + i + perturb + 1;
1085n/a ix = dk_get_index(keys, i & mask);
1086n/a }
1087n/a assert(DK_ENTRIES(keys)[keys->dk_nentries].me_value == NULL);
1088n/a return i & mask;
1089n/a}
1090n/a
1091n/astatic int
1092n/ainsertion_resize(PyDictObject *mp)
1093n/a{
1094n/a return dictresize(mp, GROWTH_RATE(mp));
1095n/a}
1096n/a
1097n/a/*
1098n/aInternal routine to insert a new item into the table.
1099n/aUsed both by the internal resize routine and by the public insert routine.
1100n/aReturns -1 if an error occurred, or 0 on success.
1101n/a*/
1102n/astatic int
1103n/ainsertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1104n/a{
1105n/a PyObject *old_value;
1106n/a PyDictKeyEntry *ep;
1107n/a Py_ssize_t hashpos, ix;
1108n/a
1109n/a if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
1110n/a if (insertion_resize(mp) < 0)
1111n/a return -1;
1112n/a }
1113n/a
1114n/a ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value, &hashpos);
1115n/a if (ix == DKIX_ERROR) {
1116n/a return -1;
1117n/a }
1118n/a
1119n/a assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
1120n/a Py_INCREF(value);
1121n/a MAINTAIN_TRACKING(mp, key, value);
1122n/a
1123n/a /* When insertion order is different from shared key, we can't share
1124n/a * the key anymore. Convert this instance to combine table.
1125n/a */
1126n/a if (_PyDict_HasSplitTable(mp) &&
1127n/a ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
1128n/a (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
1129n/a if (insertion_resize(mp) < 0) {
1130n/a Py_DECREF(value);
1131n/a return -1;
1132n/a }
1133n/a hashpos = find_empty_slot(mp->ma_keys, key, hash);
1134n/a ix = DKIX_EMPTY;
1135n/a }
1136n/a
1137n/a if (ix == DKIX_EMPTY) {
1138n/a /* Insert into new slot. */
1139n/a assert(old_value == NULL);
1140n/a if (mp->ma_keys->dk_usable <= 0) {
1141n/a /* Need to resize. */
1142n/a if (insertion_resize(mp) < 0) {
1143n/a Py_DECREF(value);
1144n/a return -1;
1145n/a }
1146n/a hashpos = find_empty_slot(mp->ma_keys, key, hash);
1147n/a }
1148n/a ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1149n/a dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
1150n/a Py_INCREF(key);
1151n/a ep->me_key = key;
1152n/a ep->me_hash = hash;
1153n/a if (mp->ma_values) {
1154n/a assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
1155n/a mp->ma_values[mp->ma_keys->dk_nentries] = value;
1156n/a }
1157n/a else {
1158n/a ep->me_value = value;
1159n/a }
1160n/a mp->ma_used++;
1161n/a mp->ma_version_tag = DICT_NEXT_VERSION();
1162n/a mp->ma_keys->dk_usable--;
1163n/a mp->ma_keys->dk_nentries++;
1164n/a assert(mp->ma_keys->dk_usable >= 0);
1165n/a assert(_PyDict_CheckConsistency(mp));
1166n/a return 0;
1167n/a }
1168n/a
1169n/a if (_PyDict_HasSplitTable(mp)) {
1170n/a mp->ma_values[ix] = value;
1171n/a if (old_value == NULL) {
1172n/a /* pending state */
1173n/a assert(ix == mp->ma_used);
1174n/a mp->ma_used++;
1175n/a }
1176n/a }
1177n/a else {
1178n/a assert(old_value != NULL);
1179n/a DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1180n/a }
1181n/a
1182n/a mp->ma_version_tag = DICT_NEXT_VERSION();
1183n/a Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
1184n/a assert(_PyDict_CheckConsistency(mp));
1185n/a return 0;
1186n/a}
1187n/a
1188n/a/*
1189n/aInternal routine used by dictresize() to buid a hashtable of entries.
1190n/a*/
1191n/astatic void
1192n/abuild_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n)
1193n/a{
1194n/a size_t mask = (size_t)DK_SIZE(keys) - 1;
1195n/a for (Py_ssize_t ix = 0; ix != n; ix++, ep++) {
1196n/a Py_hash_t hash = ep->me_hash;
1197n/a size_t i = hash & mask;
1198n/a for (size_t perturb = hash; dk_get_index(keys, i) != DKIX_EMPTY;) {
1199n/a perturb >>= PERTURB_SHIFT;
1200n/a i = mask & ((i << 2) + i + perturb + 1);
1201n/a }
1202n/a dk_set_index(keys, i, ix);
1203n/a }
1204n/a}
1205n/a
1206n/a/*
1207n/aRestructure the table by allocating a new table and reinserting all
1208n/aitems again. When entries have been deleted, the new table may
1209n/aactually be smaller than the old one.
1210n/aIf a table is split (its keys and hashes are shared, its values are not),
1211n/athen the values are temporarily copied into the table, it is resized as
1212n/aa combined table, then the me_value slots in the old table are NULLed out.
1213n/aAfter resizing a table is always combined,
1214n/abut can be resplit by make_keys_shared().
1215n/a*/
1216n/astatic int
1217n/adictresize(PyDictObject *mp, Py_ssize_t minsize)
1218n/a{
1219n/a Py_ssize_t newsize, numentries;
1220n/a PyDictKeysObject *oldkeys;
1221n/a PyObject **oldvalues;
1222n/a PyDictKeyEntry *oldentries, *newentries;
1223n/a
1224n/a /* Find the smallest table size > minused. */
1225n/a for (newsize = PyDict_MINSIZE;
1226n/a newsize < minsize && newsize > 0;
1227n/a newsize <<= 1)
1228n/a ;
1229n/a if (newsize <= 0) {
1230n/a PyErr_NoMemory();
1231n/a return -1;
1232n/a }
1233n/a
1234n/a oldkeys = mp->ma_keys;
1235n/a
1236n/a /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
1237n/a * So we can't reuse oldkeys even if oldkeys->dk_size == newsize.
1238n/a * TODO: Try reusing oldkeys when reimplement odict.
1239n/a */
1240n/a
1241n/a /* Allocate a new table. */
1242n/a mp->ma_keys = new_keys_object(newsize);
1243n/a if (mp->ma_keys == NULL) {
1244n/a mp->ma_keys = oldkeys;
1245n/a return -1;
1246n/a }
1247n/a // New table must be large enough.
1248n/a assert(mp->ma_keys->dk_usable >= mp->ma_used);
1249n/a if (oldkeys->dk_lookup == lookdict)
1250n/a mp->ma_keys->dk_lookup = lookdict;
1251n/a
1252n/a numentries = mp->ma_used;
1253n/a oldentries = DK_ENTRIES(oldkeys);
1254n/a newentries = DK_ENTRIES(mp->ma_keys);
1255n/a oldvalues = mp->ma_values;
1256n/a if (oldvalues != NULL) {
1257n/a /* Convert split table into new combined table.
1258n/a * We must incref keys; we can transfer values.
1259n/a * Note that values of split table is always dense.
1260n/a */
1261n/a for (Py_ssize_t i = 0; i < numentries; i++) {
1262n/a assert(oldvalues[i] != NULL);
1263n/a PyDictKeyEntry *ep = &oldentries[i];
1264n/a PyObject *key = ep->me_key;
1265n/a Py_INCREF(key);
1266n/a newentries[i].me_key = key;
1267n/a newentries[i].me_hash = ep->me_hash;
1268n/a newentries[i].me_value = oldvalues[i];
1269n/a }
1270n/a
1271n/a DK_DECREF(oldkeys);
1272n/a mp->ma_values = NULL;
1273n/a if (oldvalues != empty_values) {
1274n/a free_values(oldvalues);
1275n/a }
1276n/a }
1277n/a else { // combined table.
1278n/a if (oldkeys->dk_nentries == numentries) {
1279n/a memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));
1280n/a }
1281n/a else {
1282n/a PyDictKeyEntry *ep = oldentries;
1283n/a for (Py_ssize_t i = 0; i < numentries; i++) {
1284n/a while (ep->me_value == NULL)
1285n/a ep++;
1286n/a newentries[i] = *ep++;
1287n/a }
1288n/a }
1289n/a
1290n/a assert(oldkeys->dk_lookup != lookdict_split);
1291n/a assert(oldkeys->dk_refcnt == 1);
1292n/a if (oldkeys->dk_size == PyDict_MINSIZE &&
1293n/a numfreekeys < PyDict_MAXFREELIST) {
1294n/a DK_DEBUG_DECREF keys_free_list[numfreekeys++] = oldkeys;
1295n/a }
1296n/a else {
1297n/a DK_DEBUG_DECREF PyObject_FREE(oldkeys);
1298n/a }
1299n/a }
1300n/a
1301n/a build_indices(mp->ma_keys, newentries, numentries);
1302n/a mp->ma_keys->dk_usable -= numentries;
1303n/a mp->ma_keys->dk_nentries = numentries;
1304n/a return 0;
1305n/a}
1306n/a
1307n/a/* Returns NULL if unable to split table.
1308n/a * A NULL return does not necessarily indicate an error */
1309n/astatic PyDictKeysObject *
1310n/amake_keys_shared(PyObject *op)
1311n/a{
1312n/a Py_ssize_t i;
1313n/a Py_ssize_t size;
1314n/a PyDictObject *mp = (PyDictObject *)op;
1315n/a
1316n/a if (!PyDict_CheckExact(op))
1317n/a return NULL;
1318n/a if (!_PyDict_HasSplitTable(mp)) {
1319n/a PyDictKeyEntry *ep0;
1320n/a PyObject **values;
1321n/a assert(mp->ma_keys->dk_refcnt == 1);
1322n/a if (mp->ma_keys->dk_lookup == lookdict) {
1323n/a return NULL;
1324n/a }
1325n/a else if (mp->ma_keys->dk_lookup == lookdict_unicode) {
1326n/a /* Remove dummy keys */
1327n/a if (dictresize(mp, DK_SIZE(mp->ma_keys)))
1328n/a return NULL;
1329n/a }
1330n/a assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);
1331n/a /* Copy values into a new array */
1332n/a ep0 = DK_ENTRIES(mp->ma_keys);
1333n/a size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
1334n/a values = new_values(size);
1335n/a if (values == NULL) {
1336n/a PyErr_SetString(PyExc_MemoryError,
1337n/a "Not enough memory to allocate new values array");
1338n/a return NULL;
1339n/a }
1340n/a for (i = 0; i < size; i++) {
1341n/a values[i] = ep0[i].me_value;
1342n/a ep0[i].me_value = NULL;
1343n/a }
1344n/a mp->ma_keys->dk_lookup = lookdict_split;
1345n/a mp->ma_values = values;
1346n/a }
1347n/a DK_INCREF(mp->ma_keys);
1348n/a return mp->ma_keys;
1349n/a}
1350n/a
1351n/aPyObject *
1352n/a_PyDict_NewPresized(Py_ssize_t minused)
1353n/a{
1354n/a const Py_ssize_t max_presize = 128 * 1024;
1355n/a Py_ssize_t newsize;
1356n/a PyDictKeysObject *new_keys;
1357n/a
1358n/a /* There are no strict guarantee that returned dict can contain minused
1359n/a * items without resize. So we create medium size dict instead of very
1360n/a * large dict or MemoryError.
1361n/a */
1362n/a if (minused > USABLE_FRACTION(max_presize)) {
1363n/a newsize = max_presize;
1364n/a }
1365n/a else {
1366n/a Py_ssize_t minsize = ESTIMATE_SIZE(minused);
1367n/a newsize = PyDict_MINSIZE;
1368n/a while (newsize < minsize) {
1369n/a newsize <<= 1;
1370n/a }
1371n/a }
1372n/a assert(IS_POWER_OF_2(newsize));
1373n/a
1374n/a new_keys = new_keys_object(newsize);
1375n/a if (new_keys == NULL)
1376n/a return NULL;
1377n/a return new_dict(new_keys, NULL);
1378n/a}
1379n/a
1380n/a/* Note that, for historical reasons, PyDict_GetItem() suppresses all errors
1381n/a * that may occur (originally dicts supported only string keys, and exceptions
1382n/a * weren't possible). So, while the original intent was that a NULL return
1383n/a * meant the key wasn't present, in reality it can mean that, or that an error
1384n/a * (suppressed) occurred while computing the key's hash, or that some error
1385n/a * (suppressed) occurred when comparing keys in the dict's internal probe
1386n/a * sequence. A nasty example of the latter is when a Python-coded comparison
1387n/a * function hits a stack-depth error, which can cause this to return NULL
1388n/a * even if the key is present.
1389n/a */
1390n/aPyObject *
1391n/aPyDict_GetItem(PyObject *op, PyObject *key)
1392n/a{
1393n/a Py_hash_t hash;
1394n/a Py_ssize_t ix;
1395n/a PyDictObject *mp = (PyDictObject *)op;
1396n/a PyThreadState *tstate;
1397n/a PyObject *value;
1398n/a
1399n/a if (!PyDict_Check(op))
1400n/a return NULL;
1401n/a if (!PyUnicode_CheckExact(key) ||
1402n/a (hash = ((PyASCIIObject *) key)->hash) == -1)
1403n/a {
1404n/a hash = PyObject_Hash(key);
1405n/a if (hash == -1) {
1406n/a PyErr_Clear();
1407n/a return NULL;
1408n/a }
1409n/a }
1410n/a
1411n/a /* We can arrive here with a NULL tstate during initialization: try
1412n/a running "python -Wi" for an example related to string interning.
1413n/a Let's just hope that no exception occurs then... This must be
1414n/a _PyThreadState_Current and not PyThreadState_GET() because in debug
1415n/a mode, the latter complains if tstate is NULL. */
1416n/a tstate = PyThreadState_GET();
1417n/a if (tstate != NULL && tstate->curexc_type != NULL) {
1418n/a /* preserve the existing exception */
1419n/a PyObject *err_type, *err_value, *err_tb;
1420n/a PyErr_Fetch(&err_type, &err_value, &err_tb);
1421n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
1422n/a /* ignore errors */
1423n/a PyErr_Restore(err_type, err_value, err_tb);
1424n/a if (ix < 0)
1425n/a return NULL;
1426n/a }
1427n/a else {
1428n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
1429n/a if (ix < 0) {
1430n/a PyErr_Clear();
1431n/a return NULL;
1432n/a }
1433n/a }
1434n/a return value;
1435n/a}
1436n/a
1437n/a/* Same as PyDict_GetItemWithError() but with hash supplied by caller.
1438n/a This returns NULL *with* an exception set if an exception occurred.
1439n/a It returns NULL *without* an exception set if the key wasn't present.
1440n/a*/
1441n/aPyObject *
1442n/a_PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1443n/a{
1444n/a Py_ssize_t ix;
1445n/a PyDictObject *mp = (PyDictObject *)op;
1446n/a PyObject *value;
1447n/a
1448n/a if (!PyDict_Check(op)) {
1449n/a PyErr_BadInternalCall();
1450n/a return NULL;
1451n/a }
1452n/a
1453n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
1454n/a if (ix < 0) {
1455n/a return NULL;
1456n/a }
1457n/a return value;
1458n/a}
1459n/a
1460n/a/* Variant of PyDict_GetItem() that doesn't suppress exceptions.
1461n/a This returns NULL *with* an exception set if an exception occurred.
1462n/a It returns NULL *without* an exception set if the key wasn't present.
1463n/a*/
1464n/aPyObject *
1465n/aPyDict_GetItemWithError(PyObject *op, PyObject *key)
1466n/a{
1467n/a Py_ssize_t ix;
1468n/a Py_hash_t hash;
1469n/a PyDictObject*mp = (PyDictObject *)op;
1470n/a PyObject *value;
1471n/a
1472n/a if (!PyDict_Check(op)) {
1473n/a PyErr_BadInternalCall();
1474n/a return NULL;
1475n/a }
1476n/a if (!PyUnicode_CheckExact(key) ||
1477n/a (hash = ((PyASCIIObject *) key)->hash) == -1)
1478n/a {
1479n/a hash = PyObject_Hash(key);
1480n/a if (hash == -1) {
1481n/a return NULL;
1482n/a }
1483n/a }
1484n/a
1485n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
1486n/a if (ix < 0)
1487n/a return NULL;
1488n/a return value;
1489n/a}
1490n/a
1491n/aPyObject *
1492n/a_PyDict_GetItemIdWithError(PyObject *dp, struct _Py_Identifier *key)
1493n/a{
1494n/a PyObject *kv;
1495n/a kv = _PyUnicode_FromId(key); /* borrowed */
1496n/a if (kv == NULL)
1497n/a return NULL;
1498n/a return PyDict_GetItemWithError(dp, kv);
1499n/a}
1500n/a
1501n/a/* Fast version of global value lookup (LOAD_GLOBAL).
1502n/a * Lookup in globals, then builtins.
1503n/a *
1504n/a * Raise an exception and return NULL if an error occurred (ex: computing the
1505n/a * key hash failed, key comparison failed, ...). Return NULL if the key doesn't
1506n/a * exist. Return the value if the key exists.
1507n/a */
1508n/aPyObject *
1509n/a_PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key)
1510n/a{
1511n/a Py_ssize_t ix;
1512n/a Py_hash_t hash;
1513n/a PyObject *value;
1514n/a
1515n/a if (!PyUnicode_CheckExact(key) ||
1516n/a (hash = ((PyASCIIObject *) key)->hash) == -1)
1517n/a {
1518n/a hash = PyObject_Hash(key);
1519n/a if (hash == -1)
1520n/a return NULL;
1521n/a }
1522n/a
1523n/a /* namespace 1: globals */
1524n/a ix = globals->ma_keys->dk_lookup(globals, key, hash, &value, NULL);
1525n/a if (ix == DKIX_ERROR)
1526n/a return NULL;
1527n/a if (ix != DKIX_EMPTY && value != NULL)
1528n/a return value;
1529n/a
1530n/a /* namespace 2: builtins */
1531n/a ix = builtins->ma_keys->dk_lookup(builtins, key, hash, &value, NULL);
1532n/a if (ix < 0)
1533n/a return NULL;
1534n/a return value;
1535n/a}
1536n/a
1537n/a/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the
1538n/a * dictionary if it's merely replacing the value for an existing key.
1539n/a * This means that it's safe to loop over a dictionary with PyDict_Next()
1540n/a * and occasionally replace a value -- but you can't insert new keys or
1541n/a * remove them.
1542n/a */
1543n/aint
1544n/aPyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
1545n/a{
1546n/a PyDictObject *mp;
1547n/a Py_hash_t hash;
1548n/a if (!PyDict_Check(op)) {
1549n/a PyErr_BadInternalCall();
1550n/a return -1;
1551n/a }
1552n/a assert(key);
1553n/a assert(value);
1554n/a mp = (PyDictObject *)op;
1555n/a if (!PyUnicode_CheckExact(key) ||
1556n/a (hash = ((PyASCIIObject *) key)->hash) == -1)
1557n/a {
1558n/a hash = PyObject_Hash(key);
1559n/a if (hash == -1)
1560n/a return -1;
1561n/a }
1562n/a
1563n/a /* insertdict() handles any resizing that might be necessary */
1564n/a return insertdict(mp, key, hash, value);
1565n/a}
1566n/a
1567n/aint
1568n/a_PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value,
1569n/a Py_hash_t hash)
1570n/a{
1571n/a PyDictObject *mp;
1572n/a
1573n/a if (!PyDict_Check(op)) {
1574n/a PyErr_BadInternalCall();
1575n/a return -1;
1576n/a }
1577n/a assert(key);
1578n/a assert(value);
1579n/a assert(hash != -1);
1580n/a mp = (PyDictObject *)op;
1581n/a
1582n/a /* insertdict() handles any resizing that might be necessary */
1583n/a return insertdict(mp, key, hash, value);
1584n/a}
1585n/a
1586n/astatic int
1587n/adelitem_common(PyDictObject *mp, Py_ssize_t hashpos, Py_ssize_t ix,
1588n/a PyObject *old_value)
1589n/a{
1590n/a PyObject *old_key;
1591n/a PyDictKeyEntry *ep;
1592n/a
1593n/a mp->ma_used--;
1594n/a mp->ma_version_tag = DICT_NEXT_VERSION();
1595n/a ep = &DK_ENTRIES(mp->ma_keys)[ix];
1596n/a dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1597n/a ENSURE_ALLOWS_DELETIONS(mp);
1598n/a old_key = ep->me_key;
1599n/a ep->me_key = NULL;
1600n/a ep->me_value = NULL;
1601n/a Py_DECREF(old_key);
1602n/a Py_DECREF(old_value);
1603n/a
1604n/a assert(_PyDict_CheckConsistency(mp));
1605n/a return 0;
1606n/a}
1607n/a
1608n/aint
1609n/aPyDict_DelItem(PyObject *op, PyObject *key)
1610n/a{
1611n/a Py_hash_t hash;
1612n/a assert(key);
1613n/a if (!PyUnicode_CheckExact(key) ||
1614n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
1615n/a hash = PyObject_Hash(key);
1616n/a if (hash == -1)
1617n/a return -1;
1618n/a }
1619n/a
1620n/a return _PyDict_DelItem_KnownHash(op, key, hash);
1621n/a}
1622n/a
1623n/aint
1624n/a_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1625n/a{
1626n/a Py_ssize_t hashpos, ix;
1627n/a PyDictObject *mp;
1628n/a PyObject *old_value;
1629n/a
1630n/a if (!PyDict_Check(op)) {
1631n/a PyErr_BadInternalCall();
1632n/a return -1;
1633n/a }
1634n/a assert(key);
1635n/a assert(hash != -1);
1636n/a mp = (PyDictObject *)op;
1637n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1638n/a if (ix == DKIX_ERROR)
1639n/a return -1;
1640n/a if (ix == DKIX_EMPTY || old_value == NULL) {
1641n/a _PyErr_SetKeyError(key);
1642n/a return -1;
1643n/a }
1644n/a assert(dk_get_index(mp->ma_keys, hashpos) == ix);
1645n/a
1646n/a // Split table doesn't allow deletion. Combine it.
1647n/a if (_PyDict_HasSplitTable(mp)) {
1648n/a if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1649n/a return -1;
1650n/a }
1651n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1652n/a assert(ix >= 0);
1653n/a }
1654n/a
1655n/a return delitem_common(mp, hashpos, ix, old_value);
1656n/a}
1657n/a
1658n/a/* This function promises that the predicate -> deletion sequence is atomic
1659n/a * (i.e. protected by the GIL), assuming the predicate itself doesn't
1660n/a * release the GIL.
1661n/a */
1662n/aint
1663n/a_PyDict_DelItemIf(PyObject *op, PyObject *key,
1664n/a int (*predicate)(PyObject *value))
1665n/a{
1666n/a Py_ssize_t hashpos, ix;
1667n/a PyDictObject *mp;
1668n/a Py_hash_t hash;
1669n/a PyObject *old_value;
1670n/a int res;
1671n/a
1672n/a if (!PyDict_Check(op)) {
1673n/a PyErr_BadInternalCall();
1674n/a return -1;
1675n/a }
1676n/a assert(key);
1677n/a hash = PyObject_Hash(key);
1678n/a if (hash == -1)
1679n/a return -1;
1680n/a mp = (PyDictObject *)op;
1681n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1682n/a if (ix == DKIX_ERROR)
1683n/a return -1;
1684n/a if (ix == DKIX_EMPTY || old_value == NULL) {
1685n/a _PyErr_SetKeyError(key);
1686n/a return -1;
1687n/a }
1688n/a assert(dk_get_index(mp->ma_keys, hashpos) == ix);
1689n/a
1690n/a // Split table doesn't allow deletion. Combine it.
1691n/a if (_PyDict_HasSplitTable(mp)) {
1692n/a if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1693n/a return -1;
1694n/a }
1695n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1696n/a assert(ix >= 0);
1697n/a }
1698n/a
1699n/a res = predicate(old_value);
1700n/a if (res == -1)
1701n/a return -1;
1702n/a if (res > 0)
1703n/a return delitem_common(mp, hashpos, ix, old_value);
1704n/a else
1705n/a return 0;
1706n/a}
1707n/a
1708n/a
1709n/avoid
1710n/aPyDict_Clear(PyObject *op)
1711n/a{
1712n/a PyDictObject *mp;
1713n/a PyDictKeysObject *oldkeys;
1714n/a PyObject **oldvalues;
1715n/a Py_ssize_t i, n;
1716n/a
1717n/a if (!PyDict_Check(op))
1718n/a return;
1719n/a mp = ((PyDictObject *)op);
1720n/a oldkeys = mp->ma_keys;
1721n/a oldvalues = mp->ma_values;
1722n/a if (oldvalues == empty_values)
1723n/a return;
1724n/a /* Empty the dict... */
1725n/a DK_INCREF(Py_EMPTY_KEYS);
1726n/a mp->ma_keys = Py_EMPTY_KEYS;
1727n/a mp->ma_values = empty_values;
1728n/a mp->ma_used = 0;
1729n/a mp->ma_version_tag = DICT_NEXT_VERSION();
1730n/a /* ...then clear the keys and values */
1731n/a if (oldvalues != NULL) {
1732n/a n = oldkeys->dk_nentries;
1733n/a for (i = 0; i < n; i++)
1734n/a Py_CLEAR(oldvalues[i]);
1735n/a free_values(oldvalues);
1736n/a DK_DECREF(oldkeys);
1737n/a }
1738n/a else {
1739n/a assert(oldkeys->dk_refcnt == 1);
1740n/a DK_DECREF(oldkeys);
1741n/a }
1742n/a assert(_PyDict_CheckConsistency(mp));
1743n/a}
1744n/a
1745n/a/* Internal version of PyDict_Next that returns a hash value in addition
1746n/a * to the key and value.
1747n/a * Return 1 on success, return 0 when the reached the end of the dictionary
1748n/a * (or if op is not a dictionary)
1749n/a */
1750n/aint
1751n/a_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey,
1752n/a PyObject **pvalue, Py_hash_t *phash)
1753n/a{
1754n/a Py_ssize_t i;
1755n/a PyDictObject *mp;
1756n/a PyDictKeyEntry *entry_ptr;
1757n/a PyObject *value;
1758n/a
1759n/a if (!PyDict_Check(op))
1760n/a return 0;
1761n/a mp = (PyDictObject *)op;
1762n/a i = *ppos;
1763n/a if (mp->ma_values) {
1764n/a if (i < 0 || i >= mp->ma_used)
1765n/a return 0;
1766n/a /* values of split table is always dense */
1767n/a entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1768n/a value = mp->ma_values[i];
1769n/a assert(value != NULL);
1770n/a }
1771n/a else {
1772n/a Py_ssize_t n = mp->ma_keys->dk_nentries;
1773n/a if (i < 0 || i >= n)
1774n/a return 0;
1775n/a entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1776n/a while (i < n && entry_ptr->me_value == NULL) {
1777n/a entry_ptr++;
1778n/a i++;
1779n/a }
1780n/a if (i >= n)
1781n/a return 0;
1782n/a value = entry_ptr->me_value;
1783n/a }
1784n/a *ppos = i+1;
1785n/a if (pkey)
1786n/a *pkey = entry_ptr->me_key;
1787n/a if (phash)
1788n/a *phash = entry_ptr->me_hash;
1789n/a if (pvalue)
1790n/a *pvalue = value;
1791n/a return 1;
1792n/a}
1793n/a
1794n/a/*
1795n/a * Iterate over a dict. Use like so:
1796n/a *
1797n/a * Py_ssize_t i;
1798n/a * PyObject *key, *value;
1799n/a * i = 0; # important! i should not otherwise be changed by you
1800n/a * while (PyDict_Next(yourdict, &i, &key, &value)) {
1801n/a * Refer to borrowed references in key and value.
1802n/a * }
1803n/a *
1804n/a * Return 1 on success, return 0 when the reached the end of the dictionary
1805n/a * (or if op is not a dictionary)
1806n/a *
1807n/a * CAUTION: In general, it isn't safe to use PyDict_Next in a loop that
1808n/a * mutates the dict. One exception: it is safe if the loop merely changes
1809n/a * the values associated with the keys (but doesn't insert new keys or
1810n/a * delete keys), via PyDict_SetItem().
1811n/a */
1812n/aint
1813n/aPyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue)
1814n/a{
1815n/a return _PyDict_Next(op, ppos, pkey, pvalue, NULL);
1816n/a}
1817n/a
1818n/a/* Internal version of dict.pop(). */
1819n/aPyObject *
1820n/a_PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *deflt)
1821n/a{
1822n/a Py_ssize_t ix, hashpos;
1823n/a PyObject *old_value, *old_key;
1824n/a PyDictKeyEntry *ep;
1825n/a PyDictObject *mp;
1826n/a
1827n/a assert(PyDict_Check(dict));
1828n/a mp = (PyDictObject *)dict;
1829n/a
1830n/a if (mp->ma_used == 0) {
1831n/a if (deflt) {
1832n/a Py_INCREF(deflt);
1833n/a return deflt;
1834n/a }
1835n/a _PyErr_SetKeyError(key);
1836n/a return NULL;
1837n/a }
1838n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1839n/a if (ix == DKIX_ERROR)
1840n/a return NULL;
1841n/a if (ix == DKIX_EMPTY || old_value == NULL) {
1842n/a if (deflt) {
1843n/a Py_INCREF(deflt);
1844n/a return deflt;
1845n/a }
1846n/a _PyErr_SetKeyError(key);
1847n/a return NULL;
1848n/a }
1849n/a
1850n/a // Split table doesn't allow deletion. Combine it.
1851n/a if (_PyDict_HasSplitTable(mp)) {
1852n/a if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1853n/a return NULL;
1854n/a }
1855n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value, &hashpos);
1856n/a assert(ix >= 0);
1857n/a }
1858n/a
1859n/a assert(old_value != NULL);
1860n/a mp->ma_used--;
1861n/a mp->ma_version_tag = DICT_NEXT_VERSION();
1862n/a dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1863n/a ep = &DK_ENTRIES(mp->ma_keys)[ix];
1864n/a ENSURE_ALLOWS_DELETIONS(mp);
1865n/a old_key = ep->me_key;
1866n/a ep->me_key = NULL;
1867n/a ep->me_value = NULL;
1868n/a Py_DECREF(old_key);
1869n/a
1870n/a assert(_PyDict_CheckConsistency(mp));
1871n/a return old_value;
1872n/a}
1873n/a
1874n/aPyObject *
1875n/a_PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt)
1876n/a{
1877n/a Py_hash_t hash;
1878n/a
1879n/a if (((PyDictObject *)dict)->ma_used == 0) {
1880n/a if (deflt) {
1881n/a Py_INCREF(deflt);
1882n/a return deflt;
1883n/a }
1884n/a _PyErr_SetKeyError(key);
1885n/a return NULL;
1886n/a }
1887n/a if (!PyUnicode_CheckExact(key) ||
1888n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
1889n/a hash = PyObject_Hash(key);
1890n/a if (hash == -1)
1891n/a return NULL;
1892n/a }
1893n/a return _PyDict_Pop_KnownHash(dict, key, hash, deflt);
1894n/a}
1895n/a
1896n/a/* Internal version of dict.from_keys(). It is subclass-friendly. */
1897n/aPyObject *
1898n/a_PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value)
1899n/a{
1900n/a PyObject *it; /* iter(iterable) */
1901n/a PyObject *key;
1902n/a PyObject *d;
1903n/a int status;
1904n/a
1905n/a d = _PyObject_CallNoArg(cls);
1906n/a if (d == NULL)
1907n/a return NULL;
1908n/a
1909n/a if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) {
1910n/a if (PyDict_CheckExact(iterable)) {
1911n/a PyDictObject *mp = (PyDictObject *)d;
1912n/a PyObject *oldvalue;
1913n/a Py_ssize_t pos = 0;
1914n/a PyObject *key;
1915n/a Py_hash_t hash;
1916n/a
1917n/a if (dictresize(mp, ESTIMATE_SIZE(Py_SIZE(iterable)))) {
1918n/a Py_DECREF(d);
1919n/a return NULL;
1920n/a }
1921n/a
1922n/a while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
1923n/a if (insertdict(mp, key, hash, value)) {
1924n/a Py_DECREF(d);
1925n/a return NULL;
1926n/a }
1927n/a }
1928n/a return d;
1929n/a }
1930n/a if (PyAnySet_CheckExact(iterable)) {
1931n/a PyDictObject *mp = (PyDictObject *)d;
1932n/a Py_ssize_t pos = 0;
1933n/a PyObject *key;
1934n/a Py_hash_t hash;
1935n/a
1936n/a if (dictresize(mp, ESTIMATE_SIZE(PySet_GET_SIZE(iterable)))) {
1937n/a Py_DECREF(d);
1938n/a return NULL;
1939n/a }
1940n/a
1941n/a while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
1942n/a if (insertdict(mp, key, hash, value)) {
1943n/a Py_DECREF(d);
1944n/a return NULL;
1945n/a }
1946n/a }
1947n/a return d;
1948n/a }
1949n/a }
1950n/a
1951n/a it = PyObject_GetIter(iterable);
1952n/a if (it == NULL){
1953n/a Py_DECREF(d);
1954n/a return NULL;
1955n/a }
1956n/a
1957n/a if (PyDict_CheckExact(d)) {
1958n/a while ((key = PyIter_Next(it)) != NULL) {
1959n/a status = PyDict_SetItem(d, key, value);
1960n/a Py_DECREF(key);
1961n/a if (status < 0)
1962n/a goto Fail;
1963n/a }
1964n/a } else {
1965n/a while ((key = PyIter_Next(it)) != NULL) {
1966n/a status = PyObject_SetItem(d, key, value);
1967n/a Py_DECREF(key);
1968n/a if (status < 0)
1969n/a goto Fail;
1970n/a }
1971n/a }
1972n/a
1973n/a if (PyErr_Occurred())
1974n/a goto Fail;
1975n/a Py_DECREF(it);
1976n/a return d;
1977n/a
1978n/aFail:
1979n/a Py_DECREF(it);
1980n/a Py_DECREF(d);
1981n/a return NULL;
1982n/a}
1983n/a
1984n/a/* Methods */
1985n/a
1986n/astatic void
1987n/adict_dealloc(PyDictObject *mp)
1988n/a{
1989n/a PyObject **values = mp->ma_values;
1990n/a PyDictKeysObject *keys = mp->ma_keys;
1991n/a Py_ssize_t i, n;
1992n/a PyObject_GC_UnTrack(mp);
1993n/a Py_TRASHCAN_SAFE_BEGIN(mp)
1994n/a if (values != NULL) {
1995n/a if (values != empty_values) {
1996n/a for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
1997n/a Py_XDECREF(values[i]);
1998n/a }
1999n/a free_values(values);
2000n/a }
2001n/a DK_DECREF(keys);
2002n/a }
2003n/a else if (keys != NULL) {
2004n/a assert(keys->dk_refcnt == 1);
2005n/a DK_DECREF(keys);
2006n/a }
2007n/a if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
2008n/a free_list[numfree++] = mp;
2009n/a else
2010n/a Py_TYPE(mp)->tp_free((PyObject *)mp);
2011n/a Py_TRASHCAN_SAFE_END(mp)
2012n/a}
2013n/a
2014n/a
2015n/astatic PyObject *
2016n/adict_repr(PyDictObject *mp)
2017n/a{
2018n/a Py_ssize_t i;
2019n/a PyObject *key = NULL, *value = NULL;
2020n/a _PyUnicodeWriter writer;
2021n/a int first;
2022n/a
2023n/a i = Py_ReprEnter((PyObject *)mp);
2024n/a if (i != 0) {
2025n/a return i > 0 ? PyUnicode_FromString("{...}") : NULL;
2026n/a }
2027n/a
2028n/a if (mp->ma_used == 0) {
2029n/a Py_ReprLeave((PyObject *)mp);
2030n/a return PyUnicode_FromString("{}");
2031n/a }
2032n/a
2033n/a _PyUnicodeWriter_Init(&writer);
2034n/a writer.overallocate = 1;
2035n/a /* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */
2036n/a writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
2037n/a
2038n/a if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0)
2039n/a goto error;
2040n/a
2041n/a /* Do repr() on each key+value pair, and insert ": " between them.
2042n/a Note that repr may mutate the dict. */
2043n/a i = 0;
2044n/a first = 1;
2045n/a while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
2046n/a PyObject *s;
2047n/a int res;
2048n/a
2049n/a /* Prevent repr from deleting key or value during key format. */
2050n/a Py_INCREF(key);
2051n/a Py_INCREF(value);
2052n/a
2053n/a if (!first) {
2054n/a if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
2055n/a goto error;
2056n/a }
2057n/a first = 0;
2058n/a
2059n/a s = PyObject_Repr(key);
2060n/a if (s == NULL)
2061n/a goto error;
2062n/a res = _PyUnicodeWriter_WriteStr(&writer, s);
2063n/a Py_DECREF(s);
2064n/a if (res < 0)
2065n/a goto error;
2066n/a
2067n/a if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0)
2068n/a goto error;
2069n/a
2070n/a s = PyObject_Repr(value);
2071n/a if (s == NULL)
2072n/a goto error;
2073n/a res = _PyUnicodeWriter_WriteStr(&writer, s);
2074n/a Py_DECREF(s);
2075n/a if (res < 0)
2076n/a goto error;
2077n/a
2078n/a Py_CLEAR(key);
2079n/a Py_CLEAR(value);
2080n/a }
2081n/a
2082n/a writer.overallocate = 0;
2083n/a if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0)
2084n/a goto error;
2085n/a
2086n/a Py_ReprLeave((PyObject *)mp);
2087n/a
2088n/a return _PyUnicodeWriter_Finish(&writer);
2089n/a
2090n/aerror:
2091n/a Py_ReprLeave((PyObject *)mp);
2092n/a _PyUnicodeWriter_Dealloc(&writer);
2093n/a Py_XDECREF(key);
2094n/a Py_XDECREF(value);
2095n/a return NULL;
2096n/a}
2097n/a
2098n/astatic Py_ssize_t
2099n/adict_length(PyDictObject *mp)
2100n/a{
2101n/a return mp->ma_used;
2102n/a}
2103n/a
2104n/astatic PyObject *
2105n/adict_subscript(PyDictObject *mp, PyObject *key)
2106n/a{
2107n/a Py_ssize_t ix;
2108n/a Py_hash_t hash;
2109n/a PyObject *value;
2110n/a
2111n/a if (!PyUnicode_CheckExact(key) ||
2112n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
2113n/a hash = PyObject_Hash(key);
2114n/a if (hash == -1)
2115n/a return NULL;
2116n/a }
2117n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
2118n/a if (ix == DKIX_ERROR)
2119n/a return NULL;
2120n/a if (ix == DKIX_EMPTY || value == NULL) {
2121n/a if (!PyDict_CheckExact(mp)) {
2122n/a /* Look up __missing__ method if we're a subclass. */
2123n/a PyObject *missing, *res;
2124n/a _Py_IDENTIFIER(__missing__);
2125n/a missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
2126n/a if (missing != NULL) {
2127n/a res = PyObject_CallFunctionObjArgs(missing,
2128n/a key, NULL);
2129n/a Py_DECREF(missing);
2130n/a return res;
2131n/a }
2132n/a else if (PyErr_Occurred())
2133n/a return NULL;
2134n/a }
2135n/a _PyErr_SetKeyError(key);
2136n/a return NULL;
2137n/a }
2138n/a Py_INCREF(value);
2139n/a return value;
2140n/a}
2141n/a
2142n/astatic int
2143n/adict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
2144n/a{
2145n/a if (w == NULL)
2146n/a return PyDict_DelItem((PyObject *)mp, v);
2147n/a else
2148n/a return PyDict_SetItem((PyObject *)mp, v, w);
2149n/a}
2150n/a
2151n/astatic PyMappingMethods dict_as_mapping = {
2152n/a (lenfunc)dict_length, /*mp_length*/
2153n/a (binaryfunc)dict_subscript, /*mp_subscript*/
2154n/a (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
2155n/a};
2156n/a
2157n/astatic PyObject *
2158n/adict_keys(PyDictObject *mp)
2159n/a{
2160n/a PyObject *v;
2161n/a Py_ssize_t i, j;
2162n/a PyDictKeyEntry *ep;
2163n/a Py_ssize_t size, n, offset;
2164n/a PyObject **value_ptr;
2165n/a
2166n/a again:
2167n/a n = mp->ma_used;
2168n/a v = PyList_New(n);
2169n/a if (v == NULL)
2170n/a return NULL;
2171n/a if (n != mp->ma_used) {
2172n/a /* Durnit. The allocations caused the dict to resize.
2173n/a * Just start over, this shouldn't normally happen.
2174n/a */
2175n/a Py_DECREF(v);
2176n/a goto again;
2177n/a }
2178n/a ep = DK_ENTRIES(mp->ma_keys);
2179n/a size = mp->ma_keys->dk_nentries;
2180n/a if (mp->ma_values) {
2181n/a value_ptr = mp->ma_values;
2182n/a offset = sizeof(PyObject *);
2183n/a }
2184n/a else {
2185n/a value_ptr = &ep[0].me_value;
2186n/a offset = sizeof(PyDictKeyEntry);
2187n/a }
2188n/a for (i = 0, j = 0; i < size; i++) {
2189n/a if (*value_ptr != NULL) {
2190n/a PyObject *key = ep[i].me_key;
2191n/a Py_INCREF(key);
2192n/a PyList_SET_ITEM(v, j, key);
2193n/a j++;
2194n/a }
2195n/a value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2196n/a }
2197n/a assert(j == n);
2198n/a return v;
2199n/a}
2200n/a
2201n/astatic PyObject *
2202n/adict_values(PyDictObject *mp)
2203n/a{
2204n/a PyObject *v;
2205n/a Py_ssize_t i, j;
2206n/a PyDictKeyEntry *ep;
2207n/a Py_ssize_t size, n, offset;
2208n/a PyObject **value_ptr;
2209n/a
2210n/a again:
2211n/a n = mp->ma_used;
2212n/a v = PyList_New(n);
2213n/a if (v == NULL)
2214n/a return NULL;
2215n/a if (n != mp->ma_used) {
2216n/a /* Durnit. The allocations caused the dict to resize.
2217n/a * Just start over, this shouldn't normally happen.
2218n/a */
2219n/a Py_DECREF(v);
2220n/a goto again;
2221n/a }
2222n/a ep = DK_ENTRIES(mp->ma_keys);
2223n/a size = mp->ma_keys->dk_nentries;
2224n/a if (mp->ma_values) {
2225n/a value_ptr = mp->ma_values;
2226n/a offset = sizeof(PyObject *);
2227n/a }
2228n/a else {
2229n/a value_ptr = &ep[0].me_value;
2230n/a offset = sizeof(PyDictKeyEntry);
2231n/a }
2232n/a for (i = 0, j = 0; i < size; i++) {
2233n/a PyObject *value = *value_ptr;
2234n/a value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2235n/a if (value != NULL) {
2236n/a Py_INCREF(value);
2237n/a PyList_SET_ITEM(v, j, value);
2238n/a j++;
2239n/a }
2240n/a }
2241n/a assert(j == n);
2242n/a return v;
2243n/a}
2244n/a
2245n/astatic PyObject *
2246n/adict_items(PyDictObject *mp)
2247n/a{
2248n/a PyObject *v;
2249n/a Py_ssize_t i, j, n;
2250n/a Py_ssize_t size, offset;
2251n/a PyObject *item, *key;
2252n/a PyDictKeyEntry *ep;
2253n/a PyObject **value_ptr;
2254n/a
2255n/a /* Preallocate the list of tuples, to avoid allocations during
2256n/a * the loop over the items, which could trigger GC, which
2257n/a * could resize the dict. :-(
2258n/a */
2259n/a again:
2260n/a n = mp->ma_used;
2261n/a v = PyList_New(n);
2262n/a if (v == NULL)
2263n/a return NULL;
2264n/a for (i = 0; i < n; i++) {
2265n/a item = PyTuple_New(2);
2266n/a if (item == NULL) {
2267n/a Py_DECREF(v);
2268n/a return NULL;
2269n/a }
2270n/a PyList_SET_ITEM(v, i, item);
2271n/a }
2272n/a if (n != mp->ma_used) {
2273n/a /* Durnit. The allocations caused the dict to resize.
2274n/a * Just start over, this shouldn't normally happen.
2275n/a */
2276n/a Py_DECREF(v);
2277n/a goto again;
2278n/a }
2279n/a /* Nothing we do below makes any function calls. */
2280n/a ep = DK_ENTRIES(mp->ma_keys);
2281n/a size = mp->ma_keys->dk_nentries;
2282n/a if (mp->ma_values) {
2283n/a value_ptr = mp->ma_values;
2284n/a offset = sizeof(PyObject *);
2285n/a }
2286n/a else {
2287n/a value_ptr = &ep[0].me_value;
2288n/a offset = sizeof(PyDictKeyEntry);
2289n/a }
2290n/a for (i = 0, j = 0; i < size; i++) {
2291n/a PyObject *value = *value_ptr;
2292n/a value_ptr = (PyObject **)(((char *)value_ptr) + offset);
2293n/a if (value != NULL) {
2294n/a key = ep[i].me_key;
2295n/a item = PyList_GET_ITEM(v, j);
2296n/a Py_INCREF(key);
2297n/a PyTuple_SET_ITEM(item, 0, key);
2298n/a Py_INCREF(value);
2299n/a PyTuple_SET_ITEM(item, 1, value);
2300n/a j++;
2301n/a }
2302n/a }
2303n/a assert(j == n);
2304n/a return v;
2305n/a}
2306n/a
2307n/a/*[clinic input]
2308n/a@classmethod
2309n/adict.fromkeys
2310n/a iterable: object
2311n/a value: object=None
2312n/a /
2313n/a
2314n/aCreate a new dictionary with keys from iterable and values set to value.
2315n/a[clinic start generated code]*/
2316n/a
2317n/astatic PyObject *
2318n/adict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value)
2319n/a/*[clinic end generated code: output=8fb98e4b10384999 input=382ba4855d0f74c3]*/
2320n/a{
2321n/a return _PyDict_FromKeys((PyObject *)type, iterable, value);
2322n/a}
2323n/a
2324n/astatic int
2325n/adict_update_common(PyObject *self, PyObject *args, PyObject *kwds,
2326n/a const char *methname)
2327n/a{
2328n/a PyObject *arg = NULL;
2329n/a int result = 0;
2330n/a
2331n/a if (!PyArg_UnpackTuple(args, methname, 0, 1, &arg))
2332n/a result = -1;
2333n/a
2334n/a else if (arg != NULL) {
2335n/a _Py_IDENTIFIER(keys);
2336n/a if (_PyObject_HasAttrId(arg, &PyId_keys))
2337n/a result = PyDict_Merge(self, arg, 1);
2338n/a else
2339n/a result = PyDict_MergeFromSeq2(self, arg, 1);
2340n/a }
2341n/a if (result == 0 && kwds != NULL) {
2342n/a if (PyArg_ValidateKeywordArguments(kwds))
2343n/a result = PyDict_Merge(self, kwds, 1);
2344n/a else
2345n/a result = -1;
2346n/a }
2347n/a return result;
2348n/a}
2349n/a
2350n/a/* Note: dict.update() uses the METH_VARARGS|METH_KEYWORDS calling convention.
2351n/a Using METH_FASTCALL would make dict.update(**dict2) calls slower, see the
2352n/a issue #29312. */
2353n/astatic PyObject *
2354n/adict_update(PyObject *self, PyObject *args, PyObject *kwds)
2355n/a{
2356n/a if (dict_update_common(self, args, kwds, "update") != -1)
2357n/a Py_RETURN_NONE;
2358n/a return NULL;
2359n/a}
2360n/a
2361n/a/* Update unconditionally replaces existing items.
2362n/a Merge has a 3rd argument 'override'; if set, it acts like Update,
2363n/a otherwise it leaves existing items unchanged.
2364n/a
2365n/a PyDict_{Update,Merge} update/merge from a mapping object.
2366n/a
2367n/a PyDict_MergeFromSeq2 updates/merges from any iterable object
2368n/a producing iterable objects of length 2.
2369n/a*/
2370n/a
2371n/aint
2372n/aPyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
2373n/a{
2374n/a PyObject *it; /* iter(seq2) */
2375n/a Py_ssize_t i; /* index into seq2 of current element */
2376n/a PyObject *item; /* seq2[i] */
2377n/a PyObject *fast; /* item as a 2-tuple or 2-list */
2378n/a
2379n/a assert(d != NULL);
2380n/a assert(PyDict_Check(d));
2381n/a assert(seq2 != NULL);
2382n/a
2383n/a it = PyObject_GetIter(seq2);
2384n/a if (it == NULL)
2385n/a return -1;
2386n/a
2387n/a for (i = 0; ; ++i) {
2388n/a PyObject *key, *value;
2389n/a Py_ssize_t n;
2390n/a
2391n/a fast = NULL;
2392n/a item = PyIter_Next(it);
2393n/a if (item == NULL) {
2394n/a if (PyErr_Occurred())
2395n/a goto Fail;
2396n/a break;
2397n/a }
2398n/a
2399n/a /* Convert item to sequence, and verify length 2. */
2400n/a fast = PySequence_Fast(item, "");
2401n/a if (fast == NULL) {
2402n/a if (PyErr_ExceptionMatches(PyExc_TypeError))
2403n/a PyErr_Format(PyExc_TypeError,
2404n/a "cannot convert dictionary update "
2405n/a "sequence element #%zd to a sequence",
2406n/a i);
2407n/a goto Fail;
2408n/a }
2409n/a n = PySequence_Fast_GET_SIZE(fast);
2410n/a if (n != 2) {
2411n/a PyErr_Format(PyExc_ValueError,
2412n/a "dictionary update sequence element #%zd "
2413n/a "has length %zd; 2 is required",
2414n/a i, n);
2415n/a goto Fail;
2416n/a }
2417n/a
2418n/a /* Update/merge with this (key, value) pair. */
2419n/a key = PySequence_Fast_GET_ITEM(fast, 0);
2420n/a value = PySequence_Fast_GET_ITEM(fast, 1);
2421n/a if (override || PyDict_GetItem(d, key) == NULL) {
2422n/a int status = PyDict_SetItem(d, key, value);
2423n/a if (status < 0)
2424n/a goto Fail;
2425n/a }
2426n/a Py_DECREF(fast);
2427n/a Py_DECREF(item);
2428n/a }
2429n/a
2430n/a i = 0;
2431n/a assert(_PyDict_CheckConsistency((PyDictObject *)d));
2432n/a goto Return;
2433n/aFail:
2434n/a Py_XDECREF(item);
2435n/a Py_XDECREF(fast);
2436n/a i = -1;
2437n/aReturn:
2438n/a Py_DECREF(it);
2439n/a return Py_SAFE_DOWNCAST(i, Py_ssize_t, int);
2440n/a}
2441n/a
2442n/astatic int
2443n/adict_merge(PyObject *a, PyObject *b, int override)
2444n/a{
2445n/a PyDictObject *mp, *other;
2446n/a Py_ssize_t i, n;
2447n/a PyDictKeyEntry *entry, *ep0;
2448n/a
2449n/a assert(0 <= override && override <= 2);
2450n/a
2451n/a /* We accept for the argument either a concrete dictionary object,
2452n/a * or an abstract "mapping" object. For the former, we can do
2453n/a * things quite efficiently. For the latter, we only require that
2454n/a * PyMapping_Keys() and PyObject_GetItem() be supported.
2455n/a */
2456n/a if (a == NULL || !PyDict_Check(a) || b == NULL) {
2457n/a PyErr_BadInternalCall();
2458n/a return -1;
2459n/a }
2460n/a mp = (PyDictObject*)a;
2461n/a if (PyDict_Check(b)) {
2462n/a other = (PyDictObject*)b;
2463n/a if (other == mp || other->ma_used == 0)
2464n/a /* a.update(a) or a.update({}); nothing to do */
2465n/a return 0;
2466n/a if (mp->ma_used == 0)
2467n/a /* Since the target dict is empty, PyDict_GetItem()
2468n/a * always returns NULL. Setting override to 1
2469n/a * skips the unnecessary test.
2470n/a */
2471n/a override = 1;
2472n/a /* Do one big resize at the start, rather than
2473n/a * incrementally resizing as we insert new items. Expect
2474n/a * that there will be no (or few) overlapping keys.
2475n/a */
2476n/a if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
2477n/a if (dictresize(mp, ESTIMATE_SIZE(mp->ma_used + other->ma_used))) {
2478n/a return -1;
2479n/a }
2480n/a }
2481n/a ep0 = DK_ENTRIES(other->ma_keys);
2482n/a for (i = 0, n = other->ma_keys->dk_nentries; i < n; i++) {
2483n/a PyObject *key, *value;
2484n/a Py_hash_t hash;
2485n/a entry = &ep0[i];
2486n/a key = entry->me_key;
2487n/a hash = entry->me_hash;
2488n/a if (other->ma_values)
2489n/a value = other->ma_values[i];
2490n/a else
2491n/a value = entry->me_value;
2492n/a
2493n/a if (value != NULL) {
2494n/a int err = 0;
2495n/a Py_INCREF(key);
2496n/a Py_INCREF(value);
2497n/a if (override == 1)
2498n/a err = insertdict(mp, key, hash, value);
2499n/a else if (_PyDict_GetItem_KnownHash(a, key, hash) == NULL) {
2500n/a if (PyErr_Occurred()) {
2501n/a Py_DECREF(value);
2502n/a Py_DECREF(key);
2503n/a return -1;
2504n/a }
2505n/a err = insertdict(mp, key, hash, value);
2506n/a }
2507n/a else if (override != 0) {
2508n/a _PyErr_SetKeyError(key);
2509n/a Py_DECREF(value);
2510n/a Py_DECREF(key);
2511n/a return -1;
2512n/a }
2513n/a Py_DECREF(value);
2514n/a Py_DECREF(key);
2515n/a if (err != 0)
2516n/a return -1;
2517n/a
2518n/a if (n != other->ma_keys->dk_nentries) {
2519n/a PyErr_SetString(PyExc_RuntimeError,
2520n/a "dict mutated during update");
2521n/a return -1;
2522n/a }
2523n/a }
2524n/a }
2525n/a }
2526n/a else {
2527n/a /* Do it the generic, slower way */
2528n/a PyObject *keys = PyMapping_Keys(b);
2529n/a PyObject *iter;
2530n/a PyObject *key, *value;
2531n/a int status;
2532n/a
2533n/a if (keys == NULL)
2534n/a /* Docstring says this is equivalent to E.keys() so
2535n/a * if E doesn't have a .keys() method we want
2536n/a * AttributeError to percolate up. Might as well
2537n/a * do the same for any other error.
2538n/a */
2539n/a return -1;
2540n/a
2541n/a iter = PyObject_GetIter(keys);
2542n/a Py_DECREF(keys);
2543n/a if (iter == NULL)
2544n/a return -1;
2545n/a
2546n/a for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
2547n/a if (override != 1 && PyDict_GetItem(a, key) != NULL) {
2548n/a if (override != 0) {
2549n/a _PyErr_SetKeyError(key);
2550n/a Py_DECREF(key);
2551n/a Py_DECREF(iter);
2552n/a return -1;
2553n/a }
2554n/a Py_DECREF(key);
2555n/a continue;
2556n/a }
2557n/a value = PyObject_GetItem(b, key);
2558n/a if (value == NULL) {
2559n/a Py_DECREF(iter);
2560n/a Py_DECREF(key);
2561n/a return -1;
2562n/a }
2563n/a status = PyDict_SetItem(a, key, value);
2564n/a Py_DECREF(key);
2565n/a Py_DECREF(value);
2566n/a if (status < 0) {
2567n/a Py_DECREF(iter);
2568n/a return -1;
2569n/a }
2570n/a }
2571n/a Py_DECREF(iter);
2572n/a if (PyErr_Occurred())
2573n/a /* Iterator completed, via error */
2574n/a return -1;
2575n/a }
2576n/a assert(_PyDict_CheckConsistency((PyDictObject *)a));
2577n/a return 0;
2578n/a}
2579n/a
2580n/aint
2581n/aPyDict_Update(PyObject *a, PyObject *b)
2582n/a{
2583n/a return dict_merge(a, b, 1);
2584n/a}
2585n/a
2586n/aint
2587n/aPyDict_Merge(PyObject *a, PyObject *b, int override)
2588n/a{
2589n/a /* XXX Deprecate override not in (0, 1). */
2590n/a return dict_merge(a, b, override != 0);
2591n/a}
2592n/a
2593n/aint
2594n/a_PyDict_MergeEx(PyObject *a, PyObject *b, int override)
2595n/a{
2596n/a return dict_merge(a, b, override);
2597n/a}
2598n/a
2599n/astatic PyObject *
2600n/adict_copy(PyDictObject *mp)
2601n/a{
2602n/a return PyDict_Copy((PyObject*)mp);
2603n/a}
2604n/a
2605n/aPyObject *
2606n/aPyDict_Copy(PyObject *o)
2607n/a{
2608n/a PyObject *copy;
2609n/a PyDictObject *mp;
2610n/a Py_ssize_t i, n;
2611n/a
2612n/a if (o == NULL || !PyDict_Check(o)) {
2613n/a PyErr_BadInternalCall();
2614n/a return NULL;
2615n/a }
2616n/a mp = (PyDictObject *)o;
2617n/a if (_PyDict_HasSplitTable(mp)) {
2618n/a PyDictObject *split_copy;
2619n/a Py_ssize_t size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
2620n/a PyObject **newvalues;
2621n/a newvalues = new_values(size);
2622n/a if (newvalues == NULL)
2623n/a return PyErr_NoMemory();
2624n/a split_copy = PyObject_GC_New(PyDictObject, &PyDict_Type);
2625n/a if (split_copy == NULL) {
2626n/a free_values(newvalues);
2627n/a return NULL;
2628n/a }
2629n/a split_copy->ma_values = newvalues;
2630n/a split_copy->ma_keys = mp->ma_keys;
2631n/a split_copy->ma_used = mp->ma_used;
2632n/a DK_INCREF(mp->ma_keys);
2633n/a for (i = 0, n = size; i < n; i++) {
2634n/a PyObject *value = mp->ma_values[i];
2635n/a Py_XINCREF(value);
2636n/a split_copy->ma_values[i] = value;
2637n/a }
2638n/a if (_PyObject_GC_IS_TRACKED(mp))
2639n/a _PyObject_GC_TRACK(split_copy);
2640n/a return (PyObject *)split_copy;
2641n/a }
2642n/a copy = PyDict_New();
2643n/a if (copy == NULL)
2644n/a return NULL;
2645n/a if (PyDict_Merge(copy, o, 1) == 0)
2646n/a return copy;
2647n/a Py_DECREF(copy);
2648n/a return NULL;
2649n/a}
2650n/a
2651n/aPy_ssize_t
2652n/aPyDict_Size(PyObject *mp)
2653n/a{
2654n/a if (mp == NULL || !PyDict_Check(mp)) {
2655n/a PyErr_BadInternalCall();
2656n/a return -1;
2657n/a }
2658n/a return ((PyDictObject *)mp)->ma_used;
2659n/a}
2660n/a
2661n/aPyObject *
2662n/aPyDict_Keys(PyObject *mp)
2663n/a{
2664n/a if (mp == NULL || !PyDict_Check(mp)) {
2665n/a PyErr_BadInternalCall();
2666n/a return NULL;
2667n/a }
2668n/a return dict_keys((PyDictObject *)mp);
2669n/a}
2670n/a
2671n/aPyObject *
2672n/aPyDict_Values(PyObject *mp)
2673n/a{
2674n/a if (mp == NULL || !PyDict_Check(mp)) {
2675n/a PyErr_BadInternalCall();
2676n/a return NULL;
2677n/a }
2678n/a return dict_values((PyDictObject *)mp);
2679n/a}
2680n/a
2681n/aPyObject *
2682n/aPyDict_Items(PyObject *mp)
2683n/a{
2684n/a if (mp == NULL || !PyDict_Check(mp)) {
2685n/a PyErr_BadInternalCall();
2686n/a return NULL;
2687n/a }
2688n/a return dict_items((PyDictObject *)mp);
2689n/a}
2690n/a
2691n/a/* Return 1 if dicts equal, 0 if not, -1 if error.
2692n/a * Gets out as soon as any difference is detected.
2693n/a * Uses only Py_EQ comparison.
2694n/a */
2695n/astatic int
2696n/adict_equal(PyDictObject *a, PyDictObject *b)
2697n/a{
2698n/a Py_ssize_t i;
2699n/a
2700n/a if (a->ma_used != b->ma_used)
2701n/a /* can't be equal if # of entries differ */
2702n/a return 0;
2703n/a /* Same # of entries -- check all of 'em. Exit early on any diff. */
2704n/a for (i = 0; i < a->ma_keys->dk_nentries; i++) {
2705n/a PyDictKeyEntry *ep = &DK_ENTRIES(a->ma_keys)[i];
2706n/a PyObject *aval;
2707n/a if (a->ma_values)
2708n/a aval = a->ma_values[i];
2709n/a else
2710n/a aval = ep->me_value;
2711n/a if (aval != NULL) {
2712n/a int cmp;
2713n/a PyObject *bval;
2714n/a PyObject *key = ep->me_key;
2715n/a /* temporarily bump aval's refcount to ensure it stays
2716n/a alive until we're done with it */
2717n/a Py_INCREF(aval);
2718n/a /* ditto for key */
2719n/a Py_INCREF(key);
2720n/a /* reuse the known hash value */
2721n/a b->ma_keys->dk_lookup(b, key, ep->me_hash, &bval, NULL);
2722n/a Py_DECREF(key);
2723n/a if (bval == NULL) {
2724n/a Py_DECREF(aval);
2725n/a if (PyErr_Occurred())
2726n/a return -1;
2727n/a return 0;
2728n/a }
2729n/a cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
2730n/a Py_DECREF(aval);
2731n/a if (cmp <= 0) /* error or not equal */
2732n/a return cmp;
2733n/a }
2734n/a }
2735n/a return 1;
2736n/a}
2737n/a
2738n/astatic PyObject *
2739n/adict_richcompare(PyObject *v, PyObject *w, int op)
2740n/a{
2741n/a int cmp;
2742n/a PyObject *res;
2743n/a
2744n/a if (!PyDict_Check(v) || !PyDict_Check(w)) {
2745n/a res = Py_NotImplemented;
2746n/a }
2747n/a else if (op == Py_EQ || op == Py_NE) {
2748n/a cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
2749n/a if (cmp < 0)
2750n/a return NULL;
2751n/a res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
2752n/a }
2753n/a else
2754n/a res = Py_NotImplemented;
2755n/a Py_INCREF(res);
2756n/a return res;
2757n/a}
2758n/a
2759n/a/*[clinic input]
2760n/a
2761n/a@coexist
2762n/adict.__contains__
2763n/a
2764n/a key: object
2765n/a /
2766n/a
2767n/aTrue if the dictionary has the specified key, else False.
2768n/a[clinic start generated code]*/
2769n/a
2770n/astatic PyObject *
2771n/adict___contains__(PyDictObject *self, PyObject *key)
2772n/a/*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/
2773n/a{
2774n/a register PyDictObject *mp = self;
2775n/a Py_hash_t hash;
2776n/a Py_ssize_t ix;
2777n/a PyObject *value;
2778n/a
2779n/a if (!PyUnicode_CheckExact(key) ||
2780n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
2781n/a hash = PyObject_Hash(key);
2782n/a if (hash == -1)
2783n/a return NULL;
2784n/a }
2785n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
2786n/a if (ix == DKIX_ERROR)
2787n/a return NULL;
2788n/a if (ix == DKIX_EMPTY || value == NULL)
2789n/a Py_RETURN_FALSE;
2790n/a Py_RETURN_TRUE;
2791n/a}
2792n/a
2793n/a/*[clinic input]
2794n/adict.get
2795n/a
2796n/a key: object
2797n/a default: object = None
2798n/a /
2799n/a
2800n/aReturn the value for key if key is in the dictionary, else default.
2801n/a[clinic start generated code]*/
2802n/a
2803n/astatic PyObject *
2804n/adict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value)
2805n/a/*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/
2806n/a{
2807n/a PyObject *val = NULL;
2808n/a Py_hash_t hash;
2809n/a Py_ssize_t ix;
2810n/a
2811n/a if (!PyUnicode_CheckExact(key) ||
2812n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
2813n/a hash = PyObject_Hash(key);
2814n/a if (hash == -1)
2815n/a return NULL;
2816n/a }
2817n/a ix = (self->ma_keys->dk_lookup) (self, key, hash, &val, NULL);
2818n/a if (ix == DKIX_ERROR)
2819n/a return NULL;
2820n/a if (ix == DKIX_EMPTY || val == NULL) {
2821n/a val = default_value;
2822n/a }
2823n/a Py_INCREF(val);
2824n/a return val;
2825n/a}
2826n/a
2827n/aPyObject *
2828n/aPyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
2829n/a{
2830n/a PyDictObject *mp = (PyDictObject *)d;
2831n/a PyObject *value;
2832n/a Py_hash_t hash;
2833n/a Py_ssize_t hashpos, ix;
2834n/a
2835n/a if (!PyDict_Check(d)) {
2836n/a PyErr_BadInternalCall();
2837n/a return NULL;
2838n/a }
2839n/a
2840n/a if (!PyUnicode_CheckExact(key) ||
2841n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
2842n/a hash = PyObject_Hash(key);
2843n/a if (hash == -1)
2844n/a return NULL;
2845n/a }
2846n/a
2847n/a if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
2848n/a if (insertion_resize(mp) < 0)
2849n/a return NULL;
2850n/a }
2851n/a
2852n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, &hashpos);
2853n/a if (ix == DKIX_ERROR)
2854n/a return NULL;
2855n/a
2856n/a if (_PyDict_HasSplitTable(mp) &&
2857n/a ((ix >= 0 && value == NULL && mp->ma_used != ix) ||
2858n/a (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
2859n/a if (insertion_resize(mp) < 0) {
2860n/a return NULL;
2861n/a }
2862n/a hashpos = find_empty_slot(mp->ma_keys, key, hash);
2863n/a ix = DKIX_EMPTY;
2864n/a }
2865n/a
2866n/a if (ix == DKIX_EMPTY) {
2867n/a PyDictKeyEntry *ep, *ep0;
2868n/a value = defaultobj;
2869n/a if (mp->ma_keys->dk_usable <= 0) {
2870n/a if (insertion_resize(mp) < 0) {
2871n/a return NULL;
2872n/a }
2873n/a hashpos = find_empty_slot(mp->ma_keys, key, hash);
2874n/a }
2875n/a ep0 = DK_ENTRIES(mp->ma_keys);
2876n/a ep = &ep0[mp->ma_keys->dk_nentries];
2877n/a dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
2878n/a Py_INCREF(key);
2879n/a Py_INCREF(value);
2880n/a MAINTAIN_TRACKING(mp, key, value);
2881n/a ep->me_key = key;
2882n/a ep->me_hash = hash;
2883n/a if (_PyDict_HasSplitTable(mp)) {
2884n/a assert(mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
2885n/a mp->ma_values[mp->ma_keys->dk_nentries] = value;
2886n/a }
2887n/a else {
2888n/a ep->me_value = value;
2889n/a }
2890n/a mp->ma_used++;
2891n/a mp->ma_version_tag = DICT_NEXT_VERSION();
2892n/a mp->ma_keys->dk_usable--;
2893n/a mp->ma_keys->dk_nentries++;
2894n/a assert(mp->ma_keys->dk_usable >= 0);
2895n/a }
2896n/a else if (value == NULL) {
2897n/a value = defaultobj;
2898n/a assert(_PyDict_HasSplitTable(mp));
2899n/a assert(ix == mp->ma_used);
2900n/a Py_INCREF(value);
2901n/a MAINTAIN_TRACKING(mp, key, value);
2902n/a mp->ma_values[ix] = value;
2903n/a mp->ma_used++;
2904n/a mp->ma_version_tag = DICT_NEXT_VERSION();
2905n/a }
2906n/a
2907n/a assert(_PyDict_CheckConsistency(mp));
2908n/a return value;
2909n/a}
2910n/a
2911n/a/*[clinic input]
2912n/adict.setdefault
2913n/a
2914n/a key: object
2915n/a default: object = None
2916n/a /
2917n/a
2918n/aInsert key with a value of default if key is not in the dictionary.
2919n/a
2920n/aReturn the value for key if key is in the dictionary, else default.
2921n/a[clinic start generated code]*/
2922n/a
2923n/astatic PyObject *
2924n/adict_setdefault_impl(PyDictObject *self, PyObject *key,
2925n/a PyObject *default_value)
2926n/a/*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/
2927n/a{
2928n/a PyObject *val;
2929n/a
2930n/a val = PyDict_SetDefault((PyObject *)self, key, default_value);
2931n/a Py_XINCREF(val);
2932n/a return val;
2933n/a}
2934n/a
2935n/astatic PyObject *
2936n/adict_clear(PyDictObject *mp)
2937n/a{
2938n/a PyDict_Clear((PyObject *)mp);
2939n/a Py_RETURN_NONE;
2940n/a}
2941n/a
2942n/astatic PyObject *
2943n/adict_pop(PyDictObject *mp, PyObject *args)
2944n/a{
2945n/a PyObject *key, *deflt = NULL;
2946n/a
2947n/a if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt))
2948n/a return NULL;
2949n/a
2950n/a return _PyDict_Pop((PyObject*)mp, key, deflt);
2951n/a}
2952n/a
2953n/astatic PyObject *
2954n/adict_popitem(PyDictObject *mp)
2955n/a{
2956n/a Py_ssize_t i, j;
2957n/a PyDictKeyEntry *ep0, *ep;
2958n/a PyObject *res;
2959n/a
2960n/a /* Allocate the result tuple before checking the size. Believe it
2961n/a * or not, this allocation could trigger a garbage collection which
2962n/a * could empty the dict, so if we checked the size first and that
2963n/a * happened, the result would be an infinite loop (searching for an
2964n/a * entry that no longer exists). Note that the usual popitem()
2965n/a * idiom is "while d: k, v = d.popitem()". so needing to throw the
2966n/a * tuple away if the dict *is* empty isn't a significant
2967n/a * inefficiency -- possible, but unlikely in practice.
2968n/a */
2969n/a res = PyTuple_New(2);
2970n/a if (res == NULL)
2971n/a return NULL;
2972n/a if (mp->ma_used == 0) {
2973n/a Py_DECREF(res);
2974n/a PyErr_SetString(PyExc_KeyError,
2975n/a "popitem(): dictionary is empty");
2976n/a return NULL;
2977n/a }
2978n/a /* Convert split table to combined table */
2979n/a if (mp->ma_keys->dk_lookup == lookdict_split) {
2980n/a if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
2981n/a Py_DECREF(res);
2982n/a return NULL;
2983n/a }
2984n/a }
2985n/a ENSURE_ALLOWS_DELETIONS(mp);
2986n/a
2987n/a /* Pop last item */
2988n/a ep0 = DK_ENTRIES(mp->ma_keys);
2989n/a i = mp->ma_keys->dk_nentries - 1;
2990n/a while (i >= 0 && ep0[i].me_value == NULL) {
2991n/a i--;
2992n/a }
2993n/a assert(i >= 0);
2994n/a
2995n/a ep = &ep0[i];
2996n/a j = lookdict_index(mp->ma_keys, ep->me_hash, i);
2997n/a assert(j >= 0);
2998n/a assert(dk_get_index(mp->ma_keys, j) == i);
2999n/a dk_set_index(mp->ma_keys, j, DKIX_DUMMY);
3000n/a
3001n/a PyTuple_SET_ITEM(res, 0, ep->me_key);
3002n/a PyTuple_SET_ITEM(res, 1, ep->me_value);
3003n/a ep->me_key = NULL;
3004n/a ep->me_value = NULL;
3005n/a /* We can't dk_usable++ since there is DKIX_DUMMY in indices */
3006n/a mp->ma_keys->dk_nentries = i;
3007n/a mp->ma_used--;
3008n/a mp->ma_version_tag = DICT_NEXT_VERSION();
3009n/a assert(_PyDict_CheckConsistency(mp));
3010n/a return res;
3011n/a}
3012n/a
3013n/astatic int
3014n/adict_traverse(PyObject *op, visitproc visit, void *arg)
3015n/a{
3016n/a PyDictObject *mp = (PyDictObject *)op;
3017n/a PyDictKeysObject *keys = mp->ma_keys;
3018n/a PyDictKeyEntry *entries = DK_ENTRIES(keys);
3019n/a Py_ssize_t i, n = keys->dk_nentries;
3020n/a
3021n/a if (keys->dk_lookup == lookdict) {
3022n/a for (i = 0; i < n; i++) {
3023n/a if (entries[i].me_value != NULL) {
3024n/a Py_VISIT(entries[i].me_value);
3025n/a Py_VISIT(entries[i].me_key);
3026n/a }
3027n/a }
3028n/a }
3029n/a else {
3030n/a if (mp->ma_values != NULL) {
3031n/a for (i = 0; i < n; i++) {
3032n/a Py_VISIT(mp->ma_values[i]);
3033n/a }
3034n/a }
3035n/a else {
3036n/a for (i = 0; i < n; i++) {
3037n/a Py_VISIT(entries[i].me_value);
3038n/a }
3039n/a }
3040n/a }
3041n/a return 0;
3042n/a}
3043n/a
3044n/astatic int
3045n/adict_tp_clear(PyObject *op)
3046n/a{
3047n/a PyDict_Clear(op);
3048n/a return 0;
3049n/a}
3050n/a
3051n/astatic PyObject *dictiter_new(PyDictObject *, PyTypeObject *);
3052n/a
3053n/aPy_ssize_t
3054n/a_PyDict_SizeOf(PyDictObject *mp)
3055n/a{
3056n/a Py_ssize_t size, usable, res;
3057n/a
3058n/a size = DK_SIZE(mp->ma_keys);
3059n/a usable = USABLE_FRACTION(size);
3060n/a
3061n/a res = _PyObject_SIZE(Py_TYPE(mp));
3062n/a if (mp->ma_values)
3063n/a res += usable * sizeof(PyObject*);
3064n/a /* If the dictionary is split, the keys portion is accounted-for
3065n/a in the type object. */
3066n/a if (mp->ma_keys->dk_refcnt == 1)
3067n/a res += (sizeof(PyDictKeysObject)
3068n/a - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
3069n/a + DK_IXSIZE(mp->ma_keys) * size
3070n/a + sizeof(PyDictKeyEntry) * usable);
3071n/a return res;
3072n/a}
3073n/a
3074n/aPy_ssize_t
3075n/a_PyDict_KeysSize(PyDictKeysObject *keys)
3076n/a{
3077n/a return (sizeof(PyDictKeysObject)
3078n/a - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
3079n/a + DK_IXSIZE(keys) * DK_SIZE(keys)
3080n/a + USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry));
3081n/a}
3082n/a
3083n/astatic PyObject *
3084n/adict_sizeof(PyDictObject *mp)
3085n/a{
3086n/a return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
3087n/a}
3088n/a
3089n/aPyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]");
3090n/a
3091n/aPyDoc_STRVAR(sizeof__doc__,
3092n/a"D.__sizeof__() -> size of D in memory, in bytes");
3093n/a
3094n/aPyDoc_STRVAR(pop__doc__,
3095n/a"D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n\
3096n/aIf key is not found, d is returned if given, otherwise KeyError is raised");
3097n/a
3098n/aPyDoc_STRVAR(popitem__doc__,
3099n/a"D.popitem() -> (k, v), remove and return some (key, value) pair as a\n\
3100n/a2-tuple; but raise KeyError if D is empty.");
3101n/a
3102n/aPyDoc_STRVAR(update__doc__,
3103n/a"D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n\
3104n/aIf E is present and has a .keys() method, then does: for k in E: D[k] = E[k]\n\
3105n/aIf E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v\n\
3106n/aIn either case, this is followed by: for k in F: D[k] = F[k]");
3107n/a
3108n/aPyDoc_STRVAR(clear__doc__,
3109n/a"D.clear() -> None. Remove all items from D.");
3110n/a
3111n/aPyDoc_STRVAR(copy__doc__,
3112n/a"D.copy() -> a shallow copy of D");
3113n/a
3114n/a/* Forward */
3115n/astatic PyObject *dictkeys_new(PyObject *);
3116n/astatic PyObject *dictitems_new(PyObject *);
3117n/astatic PyObject *dictvalues_new(PyObject *);
3118n/a
3119n/aPyDoc_STRVAR(keys__doc__,
3120n/a "D.keys() -> a set-like object providing a view on D's keys");
3121n/aPyDoc_STRVAR(items__doc__,
3122n/a "D.items() -> a set-like object providing a view on D's items");
3123n/aPyDoc_STRVAR(values__doc__,
3124n/a "D.values() -> an object providing a view on D's values");
3125n/a
3126n/astatic PyMethodDef mapp_methods[] = {
3127n/a DICT___CONTAINS___METHODDEF
3128n/a {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
3129n/a getitem__doc__},
3130n/a {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
3131n/a sizeof__doc__},
3132n/a DICT_GET_METHODDEF
3133n/a DICT_SETDEFAULT_METHODDEF
3134n/a {"pop", (PyCFunction)dict_pop, METH_VARARGS,
3135n/a pop__doc__},
3136n/a {"popitem", (PyCFunction)dict_popitem, METH_NOARGS,
3137n/a popitem__doc__},
3138n/a {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
3139n/a keys__doc__},
3140n/a {"items", (PyCFunction)dictitems_new, METH_NOARGS,
3141n/a items__doc__},
3142n/a {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
3143n/a values__doc__},
3144n/a {"update", (PyCFunction)dict_update, METH_VARARGS | METH_KEYWORDS,
3145n/a update__doc__},
3146n/a DICT_FROMKEYS_METHODDEF
3147n/a {"clear", (PyCFunction)dict_clear, METH_NOARGS,
3148n/a clear__doc__},
3149n/a {"copy", (PyCFunction)dict_copy, METH_NOARGS,
3150n/a copy__doc__},
3151n/a {NULL, NULL} /* sentinel */
3152n/a};
3153n/a
3154n/a/* Return 1 if `key` is in dict `op`, 0 if not, and -1 on error. */
3155n/aint
3156n/aPyDict_Contains(PyObject *op, PyObject *key)
3157n/a{
3158n/a Py_hash_t hash;
3159n/a Py_ssize_t ix;
3160n/a PyDictObject *mp = (PyDictObject *)op;
3161n/a PyObject *value;
3162n/a
3163n/a if (!PyUnicode_CheckExact(key) ||
3164n/a (hash = ((PyASCIIObject *) key)->hash) == -1) {
3165n/a hash = PyObject_Hash(key);
3166n/a if (hash == -1)
3167n/a return -1;
3168n/a }
3169n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
3170n/a if (ix == DKIX_ERROR)
3171n/a return -1;
3172n/a return (ix != DKIX_EMPTY && value != NULL);
3173n/a}
3174n/a
3175n/a/* Internal version of PyDict_Contains used when the hash value is already known */
3176n/aint
3177n/a_PyDict_Contains(PyObject *op, PyObject *key, Py_hash_t hash)
3178n/a{
3179n/a PyDictObject *mp = (PyDictObject *)op;
3180n/a PyObject *value;
3181n/a Py_ssize_t ix;
3182n/a
3183n/a ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value, NULL);
3184n/a if (ix == DKIX_ERROR)
3185n/a return -1;
3186n/a return (ix != DKIX_EMPTY && value != NULL);
3187n/a}
3188n/a
3189n/a/* Hack to implement "key in dict" */
3190n/astatic PySequenceMethods dict_as_sequence = {
3191n/a 0, /* sq_length */
3192n/a 0, /* sq_concat */
3193n/a 0, /* sq_repeat */
3194n/a 0, /* sq_item */
3195n/a 0, /* sq_slice */
3196n/a 0, /* sq_ass_item */
3197n/a 0, /* sq_ass_slice */
3198n/a PyDict_Contains, /* sq_contains */
3199n/a 0, /* sq_inplace_concat */
3200n/a 0, /* sq_inplace_repeat */
3201n/a};
3202n/a
3203n/astatic PyObject *
3204n/adict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3205n/a{
3206n/a PyObject *self;
3207n/a PyDictObject *d;
3208n/a
3209n/a assert(type != NULL && type->tp_alloc != NULL);
3210n/a self = type->tp_alloc(type, 0);
3211n/a if (self == NULL)
3212n/a return NULL;
3213n/a d = (PyDictObject *)self;
3214n/a
3215n/a /* The object has been implicitly tracked by tp_alloc */
3216n/a if (type == &PyDict_Type)
3217n/a _PyObject_GC_UNTRACK(d);
3218n/a
3219n/a d->ma_used = 0;
3220n/a d->ma_version_tag = DICT_NEXT_VERSION();
3221n/a d->ma_keys = new_keys_object(PyDict_MINSIZE);
3222n/a if (d->ma_keys == NULL) {
3223n/a Py_DECREF(self);
3224n/a return NULL;
3225n/a }
3226n/a assert(_PyDict_CheckConsistency(d));
3227n/a return self;
3228n/a}
3229n/a
3230n/astatic int
3231n/adict_init(PyObject *self, PyObject *args, PyObject *kwds)
3232n/a{
3233n/a return dict_update_common(self, args, kwds, "dict");
3234n/a}
3235n/a
3236n/astatic PyObject *
3237n/adict_iter(PyDictObject *dict)
3238n/a{
3239n/a return dictiter_new(dict, &PyDictIterKey_Type);
3240n/a}
3241n/a
3242n/aPyDoc_STRVAR(dictionary_doc,
3243n/a"dict() -> new empty dictionary\n"
3244n/a"dict(mapping) -> new dictionary initialized from a mapping object's\n"
3245n/a" (key, value) pairs\n"
3246n/a"dict(iterable) -> new dictionary initialized as if via:\n"
3247n/a" d = {}\n"
3248n/a" for k, v in iterable:\n"
3249n/a" d[k] = v\n"
3250n/a"dict(**kwargs) -> new dictionary initialized with the name=value pairs\n"
3251n/a" in the keyword argument list. For example: dict(one=1, two=2)");
3252n/a
3253n/aPyTypeObject PyDict_Type = {
3254n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
3255n/a "dict",
3256n/a sizeof(PyDictObject),
3257n/a 0,
3258n/a (destructor)dict_dealloc, /* tp_dealloc */
3259n/a 0, /* tp_print */
3260n/a 0, /* tp_getattr */
3261n/a 0, /* tp_setattr */
3262n/a 0, /* tp_reserved */
3263n/a (reprfunc)dict_repr, /* tp_repr */
3264n/a 0, /* tp_as_number */
3265n/a &dict_as_sequence, /* tp_as_sequence */
3266n/a &dict_as_mapping, /* tp_as_mapping */
3267n/a PyObject_HashNotImplemented, /* tp_hash */
3268n/a 0, /* tp_call */
3269n/a 0, /* tp_str */
3270n/a PyObject_GenericGetAttr, /* tp_getattro */
3271n/a 0, /* tp_setattro */
3272n/a 0, /* tp_as_buffer */
3273n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3274n/a Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS, /* tp_flags */
3275n/a dictionary_doc, /* tp_doc */
3276n/a dict_traverse, /* tp_traverse */
3277n/a dict_tp_clear, /* tp_clear */
3278n/a dict_richcompare, /* tp_richcompare */
3279n/a 0, /* tp_weaklistoffset */
3280n/a (getiterfunc)dict_iter, /* tp_iter */
3281n/a 0, /* tp_iternext */
3282n/a mapp_methods, /* tp_methods */
3283n/a 0, /* tp_members */
3284n/a 0, /* tp_getset */
3285n/a 0, /* tp_base */
3286n/a 0, /* tp_dict */
3287n/a 0, /* tp_descr_get */
3288n/a 0, /* tp_descr_set */
3289n/a 0, /* tp_dictoffset */
3290n/a dict_init, /* tp_init */
3291n/a PyType_GenericAlloc, /* tp_alloc */
3292n/a dict_new, /* tp_new */
3293n/a PyObject_GC_Del, /* tp_free */
3294n/a};
3295n/a
3296n/aPyObject *
3297n/a_PyDict_GetItemId(PyObject *dp, struct _Py_Identifier *key)
3298n/a{
3299n/a PyObject *kv;
3300n/a kv = _PyUnicode_FromId(key); /* borrowed */
3301n/a if (kv == NULL) {
3302n/a PyErr_Clear();
3303n/a return NULL;
3304n/a }
3305n/a return PyDict_GetItem(dp, kv);
3306n/a}
3307n/a
3308n/a/* For backward compatibility with old dictionary interface */
3309n/a
3310n/aPyObject *
3311n/aPyDict_GetItemString(PyObject *v, const char *key)
3312n/a{
3313n/a PyObject *kv, *rv;
3314n/a kv = PyUnicode_FromString(key);
3315n/a if (kv == NULL) {
3316n/a PyErr_Clear();
3317n/a return NULL;
3318n/a }
3319n/a rv = PyDict_GetItem(v, kv);
3320n/a Py_DECREF(kv);
3321n/a return rv;
3322n/a}
3323n/a
3324n/aint
3325n/a_PyDict_SetItemId(PyObject *v, struct _Py_Identifier *key, PyObject *item)
3326n/a{
3327n/a PyObject *kv;
3328n/a kv = _PyUnicode_FromId(key); /* borrowed */
3329n/a if (kv == NULL)
3330n/a return -1;
3331n/a return PyDict_SetItem(v, kv, item);
3332n/a}
3333n/a
3334n/aint
3335n/aPyDict_SetItemString(PyObject *v, const char *key, PyObject *item)
3336n/a{
3337n/a PyObject *kv;
3338n/a int err;
3339n/a kv = PyUnicode_FromString(key);
3340n/a if (kv == NULL)
3341n/a return -1;
3342n/a PyUnicode_InternInPlace(&kv); /* XXX Should we really? */
3343n/a err = PyDict_SetItem(v, kv, item);
3344n/a Py_DECREF(kv);
3345n/a return err;
3346n/a}
3347n/a
3348n/aint
3349n/a_PyDict_DelItemId(PyObject *v, _Py_Identifier *key)
3350n/a{
3351n/a PyObject *kv = _PyUnicode_FromId(key); /* borrowed */
3352n/a if (kv == NULL)
3353n/a return -1;
3354n/a return PyDict_DelItem(v, kv);
3355n/a}
3356n/a
3357n/aint
3358n/aPyDict_DelItemString(PyObject *v, const char *key)
3359n/a{
3360n/a PyObject *kv;
3361n/a int err;
3362n/a kv = PyUnicode_FromString(key);
3363n/a if (kv == NULL)
3364n/a return -1;
3365n/a err = PyDict_DelItem(v, kv);
3366n/a Py_DECREF(kv);
3367n/a return err;
3368n/a}
3369n/a
3370n/a/* Dictionary iterator types */
3371n/a
3372n/atypedef struct {
3373n/a PyObject_HEAD
3374n/a PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */
3375n/a Py_ssize_t di_used;
3376n/a Py_ssize_t di_pos;
3377n/a PyObject* di_result; /* reusable result tuple for iteritems */
3378n/a Py_ssize_t len;
3379n/a} dictiterobject;
3380n/a
3381n/astatic PyObject *
3382n/adictiter_new(PyDictObject *dict, PyTypeObject *itertype)
3383n/a{
3384n/a dictiterobject *di;
3385n/a di = PyObject_GC_New(dictiterobject, itertype);
3386n/a if (di == NULL)
3387n/a return NULL;
3388n/a Py_INCREF(dict);
3389n/a di->di_dict = dict;
3390n/a di->di_used = dict->ma_used;
3391n/a di->di_pos = 0;
3392n/a di->len = dict->ma_used;
3393n/a if (itertype == &PyDictIterItem_Type) {
3394n/a di->di_result = PyTuple_Pack(2, Py_None, Py_None);
3395n/a if (di->di_result == NULL) {
3396n/a Py_DECREF(di);
3397n/a return NULL;
3398n/a }
3399n/a }
3400n/a else
3401n/a di->di_result = NULL;
3402n/a _PyObject_GC_TRACK(di);
3403n/a return (PyObject *)di;
3404n/a}
3405n/a
3406n/astatic void
3407n/adictiter_dealloc(dictiterobject *di)
3408n/a{
3409n/a Py_XDECREF(di->di_dict);
3410n/a Py_XDECREF(di->di_result);
3411n/a PyObject_GC_Del(di);
3412n/a}
3413n/a
3414n/astatic int
3415n/adictiter_traverse(dictiterobject *di, visitproc visit, void *arg)
3416n/a{
3417n/a Py_VISIT(di->di_dict);
3418n/a Py_VISIT(di->di_result);
3419n/a return 0;
3420n/a}
3421n/a
3422n/astatic PyObject *
3423n/adictiter_len(dictiterobject *di)
3424n/a{
3425n/a Py_ssize_t len = 0;
3426n/a if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used)
3427n/a len = di->len;
3428n/a return PyLong_FromSize_t(len);
3429n/a}
3430n/a
3431n/aPyDoc_STRVAR(length_hint_doc,
3432n/a "Private method returning an estimate of len(list(it)).");
3433n/a
3434n/astatic PyObject *
3435n/adictiter_reduce(dictiterobject *di);
3436n/a
3437n/aPyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
3438n/a
3439n/astatic PyMethodDef dictiter_methods[] = {
3440n/a {"__length_hint__", (PyCFunction)dictiter_len, METH_NOARGS,
3441n/a length_hint_doc},
3442n/a {"__reduce__", (PyCFunction)dictiter_reduce, METH_NOARGS,
3443n/a reduce_doc},
3444n/a {NULL, NULL} /* sentinel */
3445n/a};
3446n/a
3447n/astatic PyObject*
3448n/adictiter_iternextkey(dictiterobject *di)
3449n/a{
3450n/a PyObject *key;
3451n/a Py_ssize_t i;
3452n/a PyDictKeysObject *k;
3453n/a PyDictObject *d = di->di_dict;
3454n/a
3455n/a if (d == NULL)
3456n/a return NULL;
3457n/a assert (PyDict_Check(d));
3458n/a
3459n/a if (di->di_used != d->ma_used) {
3460n/a PyErr_SetString(PyExc_RuntimeError,
3461n/a "dictionary changed size during iteration");
3462n/a di->di_used = -1; /* Make this state sticky */
3463n/a return NULL;
3464n/a }
3465n/a
3466n/a i = di->di_pos;
3467n/a k = d->ma_keys;
3468n/a assert(i >= 0);
3469n/a if (d->ma_values) {
3470n/a if (i >= d->ma_used)
3471n/a goto fail;
3472n/a key = DK_ENTRIES(k)[i].me_key;
3473n/a assert(d->ma_values[i] != NULL);
3474n/a }
3475n/a else {
3476n/a Py_ssize_t n = k->dk_nentries;
3477n/a PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
3478n/a while (i < n && entry_ptr->me_value == NULL) {
3479n/a entry_ptr++;
3480n/a i++;
3481n/a }
3482n/a if (i >= n)
3483n/a goto fail;
3484n/a key = entry_ptr->me_key;
3485n/a }
3486n/a di->di_pos = i+1;
3487n/a di->len--;
3488n/a Py_INCREF(key);
3489n/a return key;
3490n/a
3491n/afail:
3492n/a di->di_dict = NULL;
3493n/a Py_DECREF(d);
3494n/a return NULL;
3495n/a}
3496n/a
3497n/aPyTypeObject PyDictIterKey_Type = {
3498n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
3499n/a "dict_keyiterator", /* tp_name */
3500n/a sizeof(dictiterobject), /* tp_basicsize */
3501n/a 0, /* tp_itemsize */
3502n/a /* methods */
3503n/a (destructor)dictiter_dealloc, /* tp_dealloc */
3504n/a 0, /* tp_print */
3505n/a 0, /* tp_getattr */
3506n/a 0, /* tp_setattr */
3507n/a 0, /* tp_reserved */
3508n/a 0, /* tp_repr */
3509n/a 0, /* tp_as_number */
3510n/a 0, /* tp_as_sequence */
3511n/a 0, /* tp_as_mapping */
3512n/a 0, /* tp_hash */
3513n/a 0, /* tp_call */
3514n/a 0, /* tp_str */
3515n/a PyObject_GenericGetAttr, /* tp_getattro */
3516n/a 0, /* tp_setattro */
3517n/a 0, /* tp_as_buffer */
3518n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3519n/a 0, /* tp_doc */
3520n/a (traverseproc)dictiter_traverse, /* tp_traverse */
3521n/a 0, /* tp_clear */
3522n/a 0, /* tp_richcompare */
3523n/a 0, /* tp_weaklistoffset */
3524n/a PyObject_SelfIter, /* tp_iter */
3525n/a (iternextfunc)dictiter_iternextkey, /* tp_iternext */
3526n/a dictiter_methods, /* tp_methods */
3527n/a 0,
3528n/a};
3529n/a
3530n/astatic PyObject *
3531n/adictiter_iternextvalue(dictiterobject *di)
3532n/a{
3533n/a PyObject *value;
3534n/a Py_ssize_t i;
3535n/a PyDictObject *d = di->di_dict;
3536n/a
3537n/a if (d == NULL)
3538n/a return NULL;
3539n/a assert (PyDict_Check(d));
3540n/a
3541n/a if (di->di_used != d->ma_used) {
3542n/a PyErr_SetString(PyExc_RuntimeError,
3543n/a "dictionary changed size during iteration");
3544n/a di->di_used = -1; /* Make this state sticky */
3545n/a return NULL;
3546n/a }
3547n/a
3548n/a i = di->di_pos;
3549n/a assert(i >= 0);
3550n/a if (d->ma_values) {
3551n/a if (i >= d->ma_used)
3552n/a goto fail;
3553n/a value = d->ma_values[i];
3554n/a assert(value != NULL);
3555n/a }
3556n/a else {
3557n/a Py_ssize_t n = d->ma_keys->dk_nentries;
3558n/a PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
3559n/a while (i < n && entry_ptr->me_value == NULL) {
3560n/a entry_ptr++;
3561n/a i++;
3562n/a }
3563n/a if (i >= n)
3564n/a goto fail;
3565n/a value = entry_ptr->me_value;
3566n/a }
3567n/a di->di_pos = i+1;
3568n/a di->len--;
3569n/a Py_INCREF(value);
3570n/a return value;
3571n/a
3572n/afail:
3573n/a di->di_dict = NULL;
3574n/a Py_DECREF(d);
3575n/a return NULL;
3576n/a}
3577n/a
3578n/aPyTypeObject PyDictIterValue_Type = {
3579n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
3580n/a "dict_valueiterator", /* tp_name */
3581n/a sizeof(dictiterobject), /* tp_basicsize */
3582n/a 0, /* tp_itemsize */
3583n/a /* methods */
3584n/a (destructor)dictiter_dealloc, /* tp_dealloc */
3585n/a 0, /* tp_print */
3586n/a 0, /* tp_getattr */
3587n/a 0, /* tp_setattr */
3588n/a 0, /* tp_reserved */
3589n/a 0, /* tp_repr */
3590n/a 0, /* tp_as_number */
3591n/a 0, /* tp_as_sequence */
3592n/a 0, /* tp_as_mapping */
3593n/a 0, /* tp_hash */
3594n/a 0, /* tp_call */
3595n/a 0, /* tp_str */
3596n/a PyObject_GenericGetAttr, /* tp_getattro */
3597n/a 0, /* tp_setattro */
3598n/a 0, /* tp_as_buffer */
3599n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
3600n/a 0, /* tp_doc */
3601n/a (traverseproc)dictiter_traverse, /* tp_traverse */
3602n/a 0, /* tp_clear */
3603n/a 0, /* tp_richcompare */
3604n/a 0, /* tp_weaklistoffset */
3605n/a PyObject_SelfIter, /* tp_iter */
3606n/a (iternextfunc)dictiter_iternextvalue, /* tp_iternext */
3607n/a dictiter_methods, /* tp_methods */
3608n/a 0,
3609n/a};
3610n/a
3611n/astatic PyObject *
3612n/adictiter_iternextitem(dictiterobject *di)
3613n/a{
3614n/a PyObject *key, *value, *result = di->di_result;
3615n/a Py_ssize_t i;
3616n/a PyDictObject *d = di->di_dict;
3617n/a
3618n/a if (d == NULL)
3619n/a return NULL;
3620n/a assert (PyDict_Check(d));
3621n/a
3622n/a if (di->di_used != d->ma_used) {
3623n/a PyErr_SetString(PyExc_RuntimeError,
3624n/a "dictionary changed size during iteration");
3625n/a di->di_used = -1; /* Make this state sticky */
3626n/a return NULL;
3627n/a }
3628n/a
3629n/a i = di->di_pos;
3630n/a assert(i >= 0);
3631n/a if (d->ma_values) {
3632n/a if (i >= d->ma_used)
3633n/a goto fail;
3634n/a key = DK_ENTRIES(d->ma_keys)[i].me_key;
3635n/a value = d->ma_values[i];
3636n/a assert(value != NULL);
3637n/a }
3638n/a else {
3639n/a Py_ssize_t n = d->ma_keys->dk_nentries;
3640n/a PyDictKeyEntry *entry_ptr = &DK_ENTRIES(d->ma_keys)[i];
3641n/a while (i < n && entry_ptr->me_value == NULL) {
3642n/a entry_ptr++;
3643n/a i++;
3644n/a }
3645n/a if (i >= n)
3646n/a goto fail;
3647n/a key = entry_ptr->me_key;
3648n/a value = entry_ptr->me_value;
3649n/a }
3650n/a di->di_pos = i+1;
3651n/a di->len--;
3652n/a if (result->ob_refcnt == 1) {
3653n/a Py_INCREF(result);
3654n/a Py_DECREF(PyTuple_GET_ITEM(result, 0));
3655n/a Py_DECREF(PyTuple_GET_ITEM(result, 1));
3656n/a }
3657n/a else {
3658n/a result = PyTuple_New(2);
3659n/a if (result == NULL)
3660n/a return NULL;
3661n/a }
3662n/a Py_INCREF(key);
3663n/a Py_INCREF(value);
3664n/a PyTuple_SET_ITEM(result, 0, key); /* steals reference */
3665n/a PyTuple_SET_ITEM(result, 1, value); /* steals reference */
3666n/a return result;
3667n/a
3668n/afail:
3669n/a di->di_dict = NULL;
3670n/a Py_DECREF(d);
3671n/a return NULL;
3672n/a}
3673n/a
3674n/aPyTypeObject PyDictIterItem_Type = {
3675n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
3676n/a "dict_itemiterator", /* tp_name */
3677n/a sizeof(dictiterobject), /* tp_basicsize */
3678n/a 0, /* tp_itemsize */
3679n/a /* methods */
3680n/a (destructor)dictiter_dealloc, /* tp_dealloc */
3681n/a 0, /* tp_print */
3682n/a 0, /* tp_getattr */
3683n/a 0, /* tp_setattr */
3684n/a 0, /* tp_reserved */
3685n/a 0, /* tp_repr */
3686n/a 0, /* tp_as_number */
3687n/a 0, /* tp_as_sequence */
3688n/a 0, /* tp_as_mapping */
3689n/a 0, /* tp_hash */
3690n/a 0, /* tp_call */
3691n/a 0, /* tp_str */
3692n/a PyObject_GenericGetAttr, /* tp_getattro */
3693n/a 0, /* tp_setattro */
3694n/a 0, /* tp_as_buffer */
3695n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3696n/a 0, /* tp_doc */
3697n/a (traverseproc)dictiter_traverse, /* tp_traverse */
3698n/a 0, /* tp_clear */
3699n/a 0, /* tp_richcompare */
3700n/a 0, /* tp_weaklistoffset */
3701n/a PyObject_SelfIter, /* tp_iter */
3702n/a (iternextfunc)dictiter_iternextitem, /* tp_iternext */
3703n/a dictiter_methods, /* tp_methods */
3704n/a 0,
3705n/a};
3706n/a
3707n/a
3708n/astatic PyObject *
3709n/adictiter_reduce(dictiterobject *di)
3710n/a{
3711n/a PyObject *list;
3712n/a dictiterobject tmp;
3713n/a
3714n/a list = PyList_New(0);
3715n/a if (!list)
3716n/a return NULL;
3717n/a
3718n/a /* copy the itertor state */
3719n/a tmp = *di;
3720n/a Py_XINCREF(tmp.di_dict);
3721n/a
3722n/a /* iterate the temporary into a list */
3723n/a for(;;) {
3724n/a PyObject *element = 0;
3725n/a if (Py_TYPE(di) == &PyDictIterItem_Type)
3726n/a element = dictiter_iternextitem(&tmp);
3727n/a else if (Py_TYPE(di) == &PyDictIterKey_Type)
3728n/a element = dictiter_iternextkey(&tmp);
3729n/a else if (Py_TYPE(di) == &PyDictIterValue_Type)
3730n/a element = dictiter_iternextvalue(&tmp);
3731n/a else
3732n/a assert(0);
3733n/a if (element) {
3734n/a if (PyList_Append(list, element)) {
3735n/a Py_DECREF(element);
3736n/a Py_DECREF(list);
3737n/a Py_XDECREF(tmp.di_dict);
3738n/a return NULL;
3739n/a }
3740n/a Py_DECREF(element);
3741n/a } else
3742n/a break;
3743n/a }
3744n/a Py_XDECREF(tmp.di_dict);
3745n/a /* check for error */
3746n/a if (tmp.di_dict != NULL) {
3747n/a /* we have an error */
3748n/a Py_DECREF(list);
3749n/a return NULL;
3750n/a }
3751n/a return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
3752n/a}
3753n/a
3754n/a/***********************************************/
3755n/a/* View objects for keys(), items(), values(). */
3756n/a/***********************************************/
3757n/a
3758n/a/* The instance lay-out is the same for all three; but the type differs. */
3759n/a
3760n/astatic void
3761n/adictview_dealloc(_PyDictViewObject *dv)
3762n/a{
3763n/a Py_XDECREF(dv->dv_dict);
3764n/a PyObject_GC_Del(dv);
3765n/a}
3766n/a
3767n/astatic int
3768n/adictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg)
3769n/a{
3770n/a Py_VISIT(dv->dv_dict);
3771n/a return 0;
3772n/a}
3773n/a
3774n/astatic Py_ssize_t
3775n/adictview_len(_PyDictViewObject *dv)
3776n/a{
3777n/a Py_ssize_t len = 0;
3778n/a if (dv->dv_dict != NULL)
3779n/a len = dv->dv_dict->ma_used;
3780n/a return len;
3781n/a}
3782n/a
3783n/aPyObject *
3784n/a_PyDictView_New(PyObject *dict, PyTypeObject *type)
3785n/a{
3786n/a _PyDictViewObject *dv;
3787n/a if (dict == NULL) {
3788n/a PyErr_BadInternalCall();
3789n/a return NULL;
3790n/a }
3791n/a if (!PyDict_Check(dict)) {
3792n/a /* XXX Get rid of this restriction later */
3793n/a PyErr_Format(PyExc_TypeError,
3794n/a "%s() requires a dict argument, not '%s'",
3795n/a type->tp_name, dict->ob_type->tp_name);
3796n/a return NULL;
3797n/a }
3798n/a dv = PyObject_GC_New(_PyDictViewObject, type);
3799n/a if (dv == NULL)
3800n/a return NULL;
3801n/a Py_INCREF(dict);
3802n/a dv->dv_dict = (PyDictObject *)dict;
3803n/a _PyObject_GC_TRACK(dv);
3804n/a return (PyObject *)dv;
3805n/a}
3806n/a
3807n/a/* TODO(guido): The views objects are not complete:
3808n/a
3809n/a * support more set operations
3810n/a * support arbitrary mappings?
3811n/a - either these should be static or exported in dictobject.h
3812n/a - if public then they should probably be in builtins
3813n/a*/
3814n/a
3815n/a/* Return 1 if self is a subset of other, iterating over self;
3816n/a 0 if not; -1 if an error occurred. */
3817n/astatic int
3818n/aall_contained_in(PyObject *self, PyObject *other)
3819n/a{
3820n/a PyObject *iter = PyObject_GetIter(self);
3821n/a int ok = 1;
3822n/a
3823n/a if (iter == NULL)
3824n/a return -1;
3825n/a for (;;) {
3826n/a PyObject *next = PyIter_Next(iter);
3827n/a if (next == NULL) {
3828n/a if (PyErr_Occurred())
3829n/a ok = -1;
3830n/a break;
3831n/a }
3832n/a ok = PySequence_Contains(other, next);
3833n/a Py_DECREF(next);
3834n/a if (ok <= 0)
3835n/a break;
3836n/a }
3837n/a Py_DECREF(iter);
3838n/a return ok;
3839n/a}
3840n/a
3841n/astatic PyObject *
3842n/adictview_richcompare(PyObject *self, PyObject *other, int op)
3843n/a{
3844n/a Py_ssize_t len_self, len_other;
3845n/a int ok;
3846n/a PyObject *result;
3847n/a
3848n/a assert(self != NULL);
3849n/a assert(PyDictViewSet_Check(self));
3850n/a assert(other != NULL);
3851n/a
3852n/a if (!PyAnySet_Check(other) && !PyDictViewSet_Check(other))
3853n/a Py_RETURN_NOTIMPLEMENTED;
3854n/a
3855n/a len_self = PyObject_Size(self);
3856n/a if (len_self < 0)
3857n/a return NULL;
3858n/a len_other = PyObject_Size(other);
3859n/a if (len_other < 0)
3860n/a return NULL;
3861n/a
3862n/a ok = 0;
3863n/a switch(op) {
3864n/a
3865n/a case Py_NE:
3866n/a case Py_EQ:
3867n/a if (len_self == len_other)
3868n/a ok = all_contained_in(self, other);
3869n/a if (op == Py_NE && ok >= 0)
3870n/a ok = !ok;
3871n/a break;
3872n/a
3873n/a case Py_LT:
3874n/a if (len_self < len_other)
3875n/a ok = all_contained_in(self, other);
3876n/a break;
3877n/a
3878n/a case Py_LE:
3879n/a if (len_self <= len_other)
3880n/a ok = all_contained_in(self, other);
3881n/a break;
3882n/a
3883n/a case Py_GT:
3884n/a if (len_self > len_other)
3885n/a ok = all_contained_in(other, self);
3886n/a break;
3887n/a
3888n/a case Py_GE:
3889n/a if (len_self >= len_other)
3890n/a ok = all_contained_in(other, self);
3891n/a break;
3892n/a
3893n/a }
3894n/a if (ok < 0)
3895n/a return NULL;
3896n/a result = ok ? Py_True : Py_False;
3897n/a Py_INCREF(result);
3898n/a return result;
3899n/a}
3900n/a
3901n/astatic PyObject *
3902n/adictview_repr(_PyDictViewObject *dv)
3903n/a{
3904n/a PyObject *seq;
3905n/a PyObject *result;
3906n/a
3907n/a seq = PySequence_List((PyObject *)dv);
3908n/a if (seq == NULL)
3909n/a return NULL;
3910n/a
3911n/a result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq);
3912n/a Py_DECREF(seq);
3913n/a return result;
3914n/a}
3915n/a
3916n/a/*** dict_keys ***/
3917n/a
3918n/astatic PyObject *
3919n/adictkeys_iter(_PyDictViewObject *dv)
3920n/a{
3921n/a if (dv->dv_dict == NULL) {
3922n/a Py_RETURN_NONE;
3923n/a }
3924n/a return dictiter_new(dv->dv_dict, &PyDictIterKey_Type);
3925n/a}
3926n/a
3927n/astatic int
3928n/adictkeys_contains(_PyDictViewObject *dv, PyObject *obj)
3929n/a{
3930n/a if (dv->dv_dict == NULL)
3931n/a return 0;
3932n/a return PyDict_Contains((PyObject *)dv->dv_dict, obj);
3933n/a}
3934n/a
3935n/astatic PySequenceMethods dictkeys_as_sequence = {
3936n/a (lenfunc)dictview_len, /* sq_length */
3937n/a 0, /* sq_concat */
3938n/a 0, /* sq_repeat */
3939n/a 0, /* sq_item */
3940n/a 0, /* sq_slice */
3941n/a 0, /* sq_ass_item */
3942n/a 0, /* sq_ass_slice */
3943n/a (objobjproc)dictkeys_contains, /* sq_contains */
3944n/a};
3945n/a
3946n/astatic PyObject*
3947n/adictviews_sub(PyObject* self, PyObject *other)
3948n/a{
3949n/a PyObject *result = PySet_New(self);
3950n/a PyObject *tmp;
3951n/a _Py_IDENTIFIER(difference_update);
3952n/a
3953n/a if (result == NULL)
3954n/a return NULL;
3955n/a
3956n/a tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_difference_update, other, NULL);
3957n/a if (tmp == NULL) {
3958n/a Py_DECREF(result);
3959n/a return NULL;
3960n/a }
3961n/a
3962n/a Py_DECREF(tmp);
3963n/a return result;
3964n/a}
3965n/a
3966n/aPyObject*
3967n/a_PyDictView_Intersect(PyObject* self, PyObject *other)
3968n/a{
3969n/a PyObject *result = PySet_New(self);
3970n/a PyObject *tmp;
3971n/a _Py_IDENTIFIER(intersection_update);
3972n/a
3973n/a if (result == NULL)
3974n/a return NULL;
3975n/a
3976n/a tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_intersection_update, other, NULL);
3977n/a if (tmp == NULL) {
3978n/a Py_DECREF(result);
3979n/a return NULL;
3980n/a }
3981n/a
3982n/a Py_DECREF(tmp);
3983n/a return result;
3984n/a}
3985n/a
3986n/astatic PyObject*
3987n/adictviews_or(PyObject* self, PyObject *other)
3988n/a{
3989n/a PyObject *result = PySet_New(self);
3990n/a PyObject *tmp;
3991n/a _Py_IDENTIFIER(update);
3992n/a
3993n/a if (result == NULL)
3994n/a return NULL;
3995n/a
3996n/a tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_update, other, NULL);
3997n/a if (tmp == NULL) {
3998n/a Py_DECREF(result);
3999n/a return NULL;
4000n/a }
4001n/a
4002n/a Py_DECREF(tmp);
4003n/a return result;
4004n/a}
4005n/a
4006n/astatic PyObject*
4007n/adictviews_xor(PyObject* self, PyObject *other)
4008n/a{
4009n/a PyObject *result = PySet_New(self);
4010n/a PyObject *tmp;
4011n/a _Py_IDENTIFIER(symmetric_difference_update);
4012n/a
4013n/a if (result == NULL)
4014n/a return NULL;
4015n/a
4016n/a tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_symmetric_difference_update, other, NULL);
4017n/a if (tmp == NULL) {
4018n/a Py_DECREF(result);
4019n/a return NULL;
4020n/a }
4021n/a
4022n/a Py_DECREF(tmp);
4023n/a return result;
4024n/a}
4025n/a
4026n/astatic PyNumberMethods dictviews_as_number = {
4027n/a 0, /*nb_add*/
4028n/a (binaryfunc)dictviews_sub, /*nb_subtract*/
4029n/a 0, /*nb_multiply*/
4030n/a 0, /*nb_remainder*/
4031n/a 0, /*nb_divmod*/
4032n/a 0, /*nb_power*/
4033n/a 0, /*nb_negative*/
4034n/a 0, /*nb_positive*/
4035n/a 0, /*nb_absolute*/
4036n/a 0, /*nb_bool*/
4037n/a 0, /*nb_invert*/
4038n/a 0, /*nb_lshift*/
4039n/a 0, /*nb_rshift*/
4040n/a (binaryfunc)_PyDictView_Intersect, /*nb_and*/
4041n/a (binaryfunc)dictviews_xor, /*nb_xor*/
4042n/a (binaryfunc)dictviews_or, /*nb_or*/
4043n/a};
4044n/a
4045n/astatic PyObject*
4046n/adictviews_isdisjoint(PyObject *self, PyObject *other)
4047n/a{
4048n/a PyObject *it;
4049n/a PyObject *item = NULL;
4050n/a
4051n/a if (self == other) {
4052n/a if (dictview_len((_PyDictViewObject *)self) == 0)
4053n/a Py_RETURN_TRUE;
4054n/a else
4055n/a Py_RETURN_FALSE;
4056n/a }
4057n/a
4058n/a /* Iterate over the shorter object (only if other is a set,
4059n/a * because PySequence_Contains may be expensive otherwise): */
4060n/a if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) {
4061n/a Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self);
4062n/a Py_ssize_t len_other = PyObject_Size(other);
4063n/a if (len_other == -1)
4064n/a return NULL;
4065n/a
4066n/a if ((len_other > len_self)) {
4067n/a PyObject *tmp = other;
4068n/a other = self;
4069n/a self = tmp;
4070n/a }
4071n/a }
4072n/a
4073n/a it = PyObject_GetIter(other);
4074n/a if (it == NULL)
4075n/a return NULL;
4076n/a
4077n/a while ((item = PyIter_Next(it)) != NULL) {
4078n/a int contains = PySequence_Contains(self, item);
4079n/a Py_DECREF(item);
4080n/a if (contains == -1) {
4081n/a Py_DECREF(it);
4082n/a return NULL;
4083n/a }
4084n/a
4085n/a if (contains) {
4086n/a Py_DECREF(it);
4087n/a Py_RETURN_FALSE;
4088n/a }
4089n/a }
4090n/a Py_DECREF(it);
4091n/a if (PyErr_Occurred())
4092n/a return NULL; /* PyIter_Next raised an exception. */
4093n/a Py_RETURN_TRUE;
4094n/a}
4095n/a
4096n/aPyDoc_STRVAR(isdisjoint_doc,
4097n/a"Return True if the view and the given iterable have a null intersection.");
4098n/a
4099n/astatic PyMethodDef dictkeys_methods[] = {
4100n/a {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
4101n/a isdisjoint_doc},
4102n/a {NULL, NULL} /* sentinel */
4103n/a};
4104n/a
4105n/aPyTypeObject PyDictKeys_Type = {
4106n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
4107n/a "dict_keys", /* tp_name */
4108n/a sizeof(_PyDictViewObject), /* tp_basicsize */
4109n/a 0, /* tp_itemsize */
4110n/a /* methods */
4111n/a (destructor)dictview_dealloc, /* tp_dealloc */
4112n/a 0, /* tp_print */
4113n/a 0, /* tp_getattr */
4114n/a 0, /* tp_setattr */
4115n/a 0, /* tp_reserved */
4116n/a (reprfunc)dictview_repr, /* tp_repr */
4117n/a &dictviews_as_number, /* tp_as_number */
4118n/a &dictkeys_as_sequence, /* tp_as_sequence */
4119n/a 0, /* tp_as_mapping */
4120n/a 0, /* tp_hash */
4121n/a 0, /* tp_call */
4122n/a 0, /* tp_str */
4123n/a PyObject_GenericGetAttr, /* tp_getattro */
4124n/a 0, /* tp_setattro */
4125n/a 0, /* tp_as_buffer */
4126n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4127n/a 0, /* tp_doc */
4128n/a (traverseproc)dictview_traverse, /* tp_traverse */
4129n/a 0, /* tp_clear */
4130n/a dictview_richcompare, /* tp_richcompare */
4131n/a 0, /* tp_weaklistoffset */
4132n/a (getiterfunc)dictkeys_iter, /* tp_iter */
4133n/a 0, /* tp_iternext */
4134n/a dictkeys_methods, /* tp_methods */
4135n/a 0,
4136n/a};
4137n/a
4138n/astatic PyObject *
4139n/adictkeys_new(PyObject *dict)
4140n/a{
4141n/a return _PyDictView_New(dict, &PyDictKeys_Type);
4142n/a}
4143n/a
4144n/a/*** dict_items ***/
4145n/a
4146n/astatic PyObject *
4147n/adictitems_iter(_PyDictViewObject *dv)
4148n/a{
4149n/a if (dv->dv_dict == NULL) {
4150n/a Py_RETURN_NONE;
4151n/a }
4152n/a return dictiter_new(dv->dv_dict, &PyDictIterItem_Type);
4153n/a}
4154n/a
4155n/astatic int
4156n/adictitems_contains(_PyDictViewObject *dv, PyObject *obj)
4157n/a{
4158n/a PyObject *key, *value, *found;
4159n/a if (dv->dv_dict == NULL)
4160n/a return 0;
4161n/a if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2)
4162n/a return 0;
4163n/a key = PyTuple_GET_ITEM(obj, 0);
4164n/a value = PyTuple_GET_ITEM(obj, 1);
4165n/a found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key);
4166n/a if (found == NULL) {
4167n/a if (PyErr_Occurred())
4168n/a return -1;
4169n/a return 0;
4170n/a }
4171n/a return PyObject_RichCompareBool(value, found, Py_EQ);
4172n/a}
4173n/a
4174n/astatic PySequenceMethods dictitems_as_sequence = {
4175n/a (lenfunc)dictview_len, /* sq_length */
4176n/a 0, /* sq_concat */
4177n/a 0, /* sq_repeat */
4178n/a 0, /* sq_item */
4179n/a 0, /* sq_slice */
4180n/a 0, /* sq_ass_item */
4181n/a 0, /* sq_ass_slice */
4182n/a (objobjproc)dictitems_contains, /* sq_contains */
4183n/a};
4184n/a
4185n/astatic PyMethodDef dictitems_methods[] = {
4186n/a {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O,
4187n/a isdisjoint_doc},
4188n/a {NULL, NULL} /* sentinel */
4189n/a};
4190n/a
4191n/aPyTypeObject PyDictItems_Type = {
4192n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
4193n/a "dict_items", /* tp_name */
4194n/a sizeof(_PyDictViewObject), /* tp_basicsize */
4195n/a 0, /* tp_itemsize */
4196n/a /* methods */
4197n/a (destructor)dictview_dealloc, /* tp_dealloc */
4198n/a 0, /* tp_print */
4199n/a 0, /* tp_getattr */
4200n/a 0, /* tp_setattr */
4201n/a 0, /* tp_reserved */
4202n/a (reprfunc)dictview_repr, /* tp_repr */
4203n/a &dictviews_as_number, /* tp_as_number */
4204n/a &dictitems_as_sequence, /* tp_as_sequence */
4205n/a 0, /* tp_as_mapping */
4206n/a 0, /* tp_hash */
4207n/a 0, /* tp_call */
4208n/a 0, /* tp_str */
4209n/a PyObject_GenericGetAttr, /* tp_getattro */
4210n/a 0, /* tp_setattro */
4211n/a 0, /* tp_as_buffer */
4212n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4213n/a 0, /* tp_doc */
4214n/a (traverseproc)dictview_traverse, /* tp_traverse */
4215n/a 0, /* tp_clear */
4216n/a dictview_richcompare, /* tp_richcompare */
4217n/a 0, /* tp_weaklistoffset */
4218n/a (getiterfunc)dictitems_iter, /* tp_iter */
4219n/a 0, /* tp_iternext */
4220n/a dictitems_methods, /* tp_methods */
4221n/a 0,
4222n/a};
4223n/a
4224n/astatic PyObject *
4225n/adictitems_new(PyObject *dict)
4226n/a{
4227n/a return _PyDictView_New(dict, &PyDictItems_Type);
4228n/a}
4229n/a
4230n/a/*** dict_values ***/
4231n/a
4232n/astatic PyObject *
4233n/adictvalues_iter(_PyDictViewObject *dv)
4234n/a{
4235n/a if (dv->dv_dict == NULL) {
4236n/a Py_RETURN_NONE;
4237n/a }
4238n/a return dictiter_new(dv->dv_dict, &PyDictIterValue_Type);
4239n/a}
4240n/a
4241n/astatic PySequenceMethods dictvalues_as_sequence = {
4242n/a (lenfunc)dictview_len, /* sq_length */
4243n/a 0, /* sq_concat */
4244n/a 0, /* sq_repeat */
4245n/a 0, /* sq_item */
4246n/a 0, /* sq_slice */
4247n/a 0, /* sq_ass_item */
4248n/a 0, /* sq_ass_slice */
4249n/a (objobjproc)0, /* sq_contains */
4250n/a};
4251n/a
4252n/astatic PyMethodDef dictvalues_methods[] = {
4253n/a {NULL, NULL} /* sentinel */
4254n/a};
4255n/a
4256n/aPyTypeObject PyDictValues_Type = {
4257n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
4258n/a "dict_values", /* tp_name */
4259n/a sizeof(_PyDictViewObject), /* tp_basicsize */
4260n/a 0, /* tp_itemsize */
4261n/a /* methods */
4262n/a (destructor)dictview_dealloc, /* tp_dealloc */
4263n/a 0, /* tp_print */
4264n/a 0, /* tp_getattr */
4265n/a 0, /* tp_setattr */
4266n/a 0, /* tp_reserved */
4267n/a (reprfunc)dictview_repr, /* tp_repr */
4268n/a 0, /* tp_as_number */
4269n/a &dictvalues_as_sequence, /* tp_as_sequence */
4270n/a 0, /* tp_as_mapping */
4271n/a 0, /* tp_hash */
4272n/a 0, /* tp_call */
4273n/a 0, /* tp_str */
4274n/a PyObject_GenericGetAttr, /* tp_getattro */
4275n/a 0, /* tp_setattro */
4276n/a 0, /* tp_as_buffer */
4277n/a Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
4278n/a 0, /* tp_doc */
4279n/a (traverseproc)dictview_traverse, /* tp_traverse */
4280n/a 0, /* tp_clear */
4281n/a 0, /* tp_richcompare */
4282n/a 0, /* tp_weaklistoffset */
4283n/a (getiterfunc)dictvalues_iter, /* tp_iter */
4284n/a 0, /* tp_iternext */
4285n/a dictvalues_methods, /* tp_methods */
4286n/a 0,
4287n/a};
4288n/a
4289n/astatic PyObject *
4290n/adictvalues_new(PyObject *dict)
4291n/a{
4292n/a return _PyDictView_New(dict, &PyDictValues_Type);
4293n/a}
4294n/a
4295n/a/* Returns NULL if cannot allocate a new PyDictKeysObject,
4296n/a but does not set an error */
4297n/aPyDictKeysObject *
4298n/a_PyDict_NewKeysForClass(void)
4299n/a{
4300n/a PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
4301n/a if (keys == NULL)
4302n/a PyErr_Clear();
4303n/a else
4304n/a keys->dk_lookup = lookdict_split;
4305n/a return keys;
4306n/a}
4307n/a
4308n/a#define CACHED_KEYS(tp) (((PyHeapTypeObject*)tp)->ht_cached_keys)
4309n/a
4310n/aPyObject *
4311n/aPyObject_GenericGetDict(PyObject *obj, void *context)
4312n/a{
4313n/a PyObject *dict, **dictptr = _PyObject_GetDictPtr(obj);
4314n/a if (dictptr == NULL) {
4315n/a PyErr_SetString(PyExc_AttributeError,
4316n/a "This object has no __dict__");
4317n/a return NULL;
4318n/a }
4319n/a dict = *dictptr;
4320n/a if (dict == NULL) {
4321n/a PyTypeObject *tp = Py_TYPE(obj);
4322n/a if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) {
4323n/a DK_INCREF(CACHED_KEYS(tp));
4324n/a *dictptr = dict = new_dict_with_shared_keys(CACHED_KEYS(tp));
4325n/a }
4326n/a else {
4327n/a *dictptr = dict = PyDict_New();
4328n/a }
4329n/a }
4330n/a Py_XINCREF(dict);
4331n/a return dict;
4332n/a}
4333n/a
4334n/aint
4335n/a_PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr,
4336n/a PyObject *key, PyObject *value)
4337n/a{
4338n/a PyObject *dict;
4339n/a int res;
4340n/a PyDictKeysObject *cached;
4341n/a
4342n/a assert(dictptr != NULL);
4343n/a if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) {
4344n/a assert(dictptr != NULL);
4345n/a dict = *dictptr;
4346n/a if (dict == NULL) {
4347n/a DK_INCREF(cached);
4348n/a dict = new_dict_with_shared_keys(cached);
4349n/a if (dict == NULL)
4350n/a return -1;
4351n/a *dictptr = dict;
4352n/a }
4353n/a if (value == NULL) {
4354n/a res = PyDict_DelItem(dict, key);
4355n/a if (cached != ((PyDictObject *)dict)->ma_keys) {
4356n/a CACHED_KEYS(tp) = NULL;
4357n/a DK_DECREF(cached);
4358n/a }
4359n/a }
4360n/a else {
4361n/a int was_shared = cached == ((PyDictObject *)dict)->ma_keys;
4362n/a res = PyDict_SetItem(dict, key, value);
4363n/a if (was_shared && cached != ((PyDictObject *)dict)->ma_keys) {
4364n/a /* PyDict_SetItem() may call dictresize and convert split table
4365n/a * into combined table. In such case, convert it to split
4366n/a * table again and update type's shared key only when this is
4367n/a * the only dict sharing key with the type.
4368n/a *
4369n/a * This is to allow using shared key in class like this:
4370n/a *
4371n/a * class C:
4372n/a * def __init__(self):
4373n/a * # one dict resize happens
4374n/a * self.a, self.b, self.c = 1, 2, 3
4375n/a * self.d, self.e, self.f = 4, 5, 6
4376n/a * a = C()
4377n/a */
4378n/a if (cached->dk_refcnt == 1) {
4379n/a CACHED_KEYS(tp) = make_keys_shared(dict);
4380n/a }
4381n/a else {
4382n/a CACHED_KEYS(tp) = NULL;
4383n/a }
4384n/a DK_DECREF(cached);
4385n/a if (CACHED_KEYS(tp) == NULL && PyErr_Occurred())
4386n/a return -1;
4387n/a }
4388n/a }
4389n/a } else {
4390n/a dict = *dictptr;
4391n/a if (dict == NULL) {
4392n/a dict = PyDict_New();
4393n/a if (dict == NULL)
4394n/a return -1;
4395n/a *dictptr = dict;
4396n/a }
4397n/a if (value == NULL) {
4398n/a res = PyDict_DelItem(dict, key);
4399n/a } else {
4400n/a res = PyDict_SetItem(dict, key, value);
4401n/a }
4402n/a }
4403n/a return res;
4404n/a}
4405n/a
4406n/avoid
4407n/a_PyDictKeys_DecRef(PyDictKeysObject *keys)
4408n/a{
4409n/a DK_DECREF(keys);
4410n/a}