Python code coverage for Objects/dictobject.c

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