| 1 |
/* Dictionary object implementation using a hash table */ |
| 2 |
|
| 3 |
/* The distribution includes a separate file, Objects/dictnotes.txt, |
| 4 |
describing explorations into dictionary design and optimization. |
| 5 |
It covers typical dictionary use patterns, the parameters for |
| 6 |
tuning dictionaries, and several ideas for possible optimizations. |
| 7 |
*/ |
| 8 |
|
| 9 |
/* PyDictKeysObject |
| 10 |
|
| 11 |
This implements the dictionary's hashtable. |
| 12 |
|
| 13 |
As of Python 3.6, this is compact and ordered. Basic idea is described here: |
| 14 |
* https://mail.python.org/pipermail/python-dev/2012-December/123028.html |
| 15 |
* https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html |
| 16 |
|
| 17 |
layout: |
| 18 |
|
| 19 |
+---------------+ |
| 20 |
| dk_refcnt | |
| 21 |
| dk_size | |
| 22 |
| dk_lookup | |
| 23 |
| dk_usable | |
| 24 |
| dk_nentries | |
| 25 |
+---------------+ |
| 26 |
| dk_indices | |
| 27 |
| | |
| 28 |
+---------------+ |
| 29 |
| dk_entries | |
| 30 |
| | |
| 31 |
+---------------+ |
| 32 |
|
| 33 |
dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1) |
| 34 |
or DKIX_DUMMY(-2). |
| 35 |
Size of indices is dk_size. Type of each index in indices is vary on dk_size: |
| 36 |
|
| 37 |
* int8 for dk_size <= 128 |
| 38 |
* int16 for 256 <= dk_size <= 2**15 |
| 39 |
* int32 for 2**16 <= dk_size <= 2**31 |
| 40 |
* int64 for 2**32 <= dk_size |
| 41 |
|
| 42 |
dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size). |
| 43 |
DK_ENTRIES(dk) can be used to get pointer to entries. |
| 44 |
|
| 45 |
NOTE: Since negative value is used for DKIX_EMPTY and DKIX_DUMMY, type of |
| 46 |
dk_indices entry is signed integer and int16 is used for table which |
| 47 |
dk_size == 256. |
| 48 |
*/ |
| 49 |
|
| 50 |
|
| 51 |
/* |
| 52 |
The DictObject can be in one of two forms. |
| 53 |
|
| 54 |
Either: |
| 55 |
A combined table: |
| 56 |
ma_values == NULL, dk_refcnt == 1. |
| 57 |
Values are stored in the me_value field of the PyDictKeysObject. |
| 58 |
Or: |
| 59 |
A split table: |
| 60 |
ma_values != NULL, dk_refcnt >= 1 |
| 61 |
Values are stored in the ma_values array. |
| 62 |
Only string (unicode) keys are allowed. |
| 63 |
All dicts sharing same key must have same insertion order. |
| 64 |
|
| 65 |
There are four kinds of slots in the table (slot is index, and |
| 66 |
DK_ENTRIES(keys)[index] if index >= 0): |
| 67 |
|
| 68 |
1. Unused. index == DKIX_EMPTY |
| 69 |
Does not hold an active (key, value) pair now and never did. Unused can |
| 70 |
transition to Active upon key insertion. This is each slot's initial state. |
| 71 |
|
| 72 |
2. Active. index >= 0, me_key != NULL and me_value != NULL |
| 73 |
Holds an active (key, value) pair. Active can transition to Dummy or |
| 74 |
Pending upon key deletion (for combined and split tables respectively). |
| 75 |
This is the only case in which me_value != NULL. |
| 76 |
|
| 77 |
3. Dummy. index == DKIX_DUMMY (combined only) |
| 78 |
Previously held an active (key, value) pair, but that was deleted and an |
| 79 |
active pair has not yet overwritten the slot. Dummy can transition to |
| 80 |
Active upon key insertion. Dummy slots cannot be made Unused again |
| 81 |
else the probe sequence in case of collision would have no way to know |
| 82 |
they were once active. |
| 83 |
|
| 84 |
4. Pending. index >= 0, key != NULL, and value == NULL (split only) |
| 85 |
Not yet inserted in split-table. |
| 86 |
*/ |
| 87 |
|
| 88 |
/* |
| 89 |
Preserving insertion order |
| 90 |
|
| 91 |
It's simple for combined table. Since dk_entries is mostly append only, we can |
| 92 |
get insertion order by just iterating dk_entries. |
| 93 |
|
| 94 |
One exception is .popitem(). It removes last item in dk_entries and decrement |
| 95 |
dk_nentries to achieve amortized O(1). Since there are DKIX_DUMMY remains in |
| 96 |
dk_indices, we can't increment dk_usable even though dk_nentries is |
| 97 |
decremented. |
| 98 |
|
| 99 |
In split table, inserting into pending entry is allowed only for dk_entries[ix] |
| 100 |
where ix == mp->ma_used. Inserting into other index and deleting item cause |
| 101 |
converting the dict to the combined table. |
| 102 |
*/ |
| 103 |
|
| 104 |
/* PyDict_MINSIZE is the starting size for any new dict. |
| 105 |
* 8 allows dicts with no more than 5 active entries; experiments suggested |
| 106 |
* this suffices for the majority of dicts (consisting mostly of usually-small |
| 107 |
* dicts created to pass keyword arguments). |
| 108 |
* Making this 8, rather than 4 reduces the number of resizes for most |
| 109 |
* dictionaries, without any significant extra memory use. |
| 110 |
*/ |
| 111 |
#define PyDict_MINSIZE 8 |
| 112 |
|
| 113 |
#include "Python.h" |
| 114 |
#include "dict-common.h" |
| 115 |
#include "stringlib/eq.h" // unicode_eq() |
| 116 |
|
| 117 |
/*[clinic input] |
| 118 |
class dict "PyDictObject *" "&PyDict_Type" |
| 119 |
[clinic start generated code]*/ |
| 120 |
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/ |
| 121 |
|
| 122 |
|
| 123 |
/* |
| 124 |
To ensure the lookup algorithm terminates, there must be at least one Unused |
| 125 |
slot (NULL key) in the table. |
| 126 |
To avoid slowing down lookups on a near-full table, we resize the table when |
| 127 |
it's USABLE_FRACTION (currently two-thirds) full. |
| 128 |
*/ |
| 129 |
|
| 130 |
#define PERTURB_SHIFT 5 |
| 131 |
|
| 132 |
/* |
| 133 |
Major subtleties ahead: Most hash schemes depend on having a "good" hash |
| 134 |
function, in the sense of simulating randomness. Python doesn't: its most |
| 135 |
important hash functions (for ints) are very regular in common |
| 136 |
cases: |
| 137 |
|
| 138 |
>>>[hash(i) for i in range(4)] |
| 139 |
[0, 1, 2, 3] |
| 140 |
|
| 141 |
This isn't necessarily bad! To the contrary, in a table of size 2**i, taking |
| 142 |
the low-order i bits as the initial table index is extremely fast, and there |
| 143 |
are no collisions at all for dicts indexed by a contiguous range of ints. So |
| 144 |
this gives better-than-random behavior in common cases, and that's very |
| 145 |
desirable. |
| 146 |
|
| 147 |
OTOH, when collisions occur, the tendency to fill contiguous slices of the |
| 148 |
hash table makes a good collision resolution strategy crucial. Taking only |
| 149 |
the last i bits of the hash code is also vulnerable: for example, consider |
| 150 |
the list [i << 16 for i in range(20000)] as a set of keys. Since ints are |
| 151 |
their own hash codes, and this fits in a dict of size 2**15, the last 15 bits |
| 152 |
of every hash code are all 0: they *all* map to the same table index. |
| 153 |
|
| 154 |
But catering to unusual cases should not slow the usual ones, so we just take |
| 155 |
the last i bits anyway. It's up to collision resolution to do the rest. If |
| 156 |
we *usually* find the key we're looking for on the first try (and, it turns |
| 157 |
out, we usually do -- the table load factor is kept under 2/3, so the odds |
| 158 |
are solidly in our favor), then it makes best sense to keep the initial index |
| 159 |
computation dirt cheap. |
| 160 |
|
| 161 |
The first half of collision resolution is to visit table indices via this |
| 162 |
recurrence: |
| 163 |
|
| 164 |
j = ((5*j) + 1) mod 2**i |
| 165 |
|
| 166 |
For any initial j in range(2**i), repeating that 2**i times generates each |
| 167 |
int in range(2**i) exactly once (see any text on random-number generation for |
| 168 |
proof). By itself, this doesn't help much: like linear probing (setting |
| 169 |
j += 1, or j -= 1, on each loop trip), it scans the table entries in a fixed |
| 170 |
order. This would be bad, except that's not the only thing we do, and it's |
| 171 |
actually *good* in the common cases where hash keys are consecutive. In an |
| 172 |
example that's really too small to make this entirely clear, for a table of |
| 173 |
size 2**3 the order of indices is: |
| 174 |
|
| 175 |
0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating] |
| 176 |
|
| 177 |
If two things come in at index 5, the first place we look after is index 2, |
| 178 |
not 6, so if another comes in at index 6 the collision at 5 didn't hurt it. |
| 179 |
Linear probing is deadly in this case because there the fixed probe order |
| 180 |
is the *same* as the order consecutive keys are likely to arrive. But it's |
| 181 |
extremely unlikely hash codes will follow a 5*j+1 recurrence by accident, |
| 182 |
and certain that consecutive hash codes do not. |
| 183 |
|
| 184 |
The other half of the strategy is to get the other bits of the hash code |
| 185 |
into play. This is done by initializing a (unsigned) vrbl "perturb" to the |
| 186 |
full hash code, and changing the recurrence to: |
| 187 |
|
| 188 |
perturb >>= PERTURB_SHIFT; |
| 189 |
j = (5*j) + 1 + perturb; |
| 190 |
use j % 2**i as the next table index; |
| 191 |
|
| 192 |
Now the probe sequence depends (eventually) on every bit in the hash code, |
| 193 |
and the pseudo-scrambling property of recurring on 5*j+1 is more valuable, |
| 194 |
because it quickly magnifies small differences in the bits that didn't affect |
| 195 |
the initial index. Note that because perturb is unsigned, if the recurrence |
| 196 |
is executed often enough perturb eventually becomes and remains 0. At that |
| 197 |
point (very rarely reached) the recurrence is on (just) 5*j+1 again, and |
| 198 |
that's certain to find an empty slot eventually (since it generates every int |
| 199 |
in range(2**i), and we make sure there's always at least one empty slot). |
| 200 |
|
| 201 |
Selecting a good value for PERTURB_SHIFT is a balancing act. You want it |
| 202 |
small so that the high bits of the hash code continue to affect the probe |
| 203 |
sequence across iterations; but you want it large so that in really bad cases |
| 204 |
the high-order hash bits have an effect on early iterations. 5 was "the |
| 205 |
best" in minimizing total collisions across experiments Tim Peters ran (on |
| 206 |
both normal and pathological cases), but 4 and 6 weren't significantly worse. |
| 207 |
|
| 208 |
Historical: Reimer Behrends contributed the idea of using a polynomial-based |
| 209 |
approach, using repeated multiplication by x in GF(2**n) where an irreducible |
| 210 |
polynomial for each table size was chosen such that x was a primitive root. |
| 211 |
Christian Tismer later extended that to use division by x instead, as an |
| 212 |
efficient way to get the high bits of the hash code into play. This scheme |
| 213 |
also gave excellent collision statistics, but was more expensive: two |
| 214 |
if-tests were required inside the loop; computing "the next" index took about |
| 215 |
the same number of operations but without as much potential parallelism |
| 216 |
(e.g., computing 5*j can go on at the same time as computing 1+perturb in the |
| 217 |
above, and then shifting perturb can be done while the table index is being |
| 218 |
masked); and the PyDictObject struct required a member to hold the table's |
| 219 |
polynomial. In Tim's experiments the current scheme ran faster, produced |
| 220 |
equally good collision statistics, needed less code & used less memory. |
| 221 |
|
| 222 |
*/ |
| 223 |
|
| 224 |
/* forward declarations */ |
| 225 |
static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key, |
| 226 |
Py_hash_t hash, PyObject ***value_addr, |
| 227 |
Py_ssize_t *hashpos); |
| 228 |
static Py_ssize_t |
| 229 |
lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, |
| 230 |
Py_hash_t hash, PyObject ***value_addr, |
| 231 |
Py_ssize_t *hashpos); |
| 232 |
|
| 233 |
/*Global counter used to set ma_version_tag field of dictionary. |
| 234 |
* It is incremented each time that a dictionary is created and each |
| 235 |
* time that a dictionary is modified. */ |
| 236 |
static uint64_t pydict_global_version = 0; |
| 237 |
|
| 238 |
#define DICT_NEXT_VERSION() (++pydict_global_version) |
| 239 |
|
| 240 |
/* Dictionary reuse scheme to save calls to malloc and free */ |
| 241 |
#ifndef PyDict_MAXFREELIST |
| 242 |
#define PyDict_MAXFREELIST 80 |
| 243 |
#endif |
| 244 |
|
| 245 |
#if PyDict_MAXFREELIST > 0 |
| 246 |
static PyDictObject *free_list[PyDict_MAXFREELIST]; |
| 247 |
static int numfree = 0; |
| 248 |
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST]; |
| 249 |
static int numfreekeys = 0; |
| 250 |
#endif |
| 251 |
|
| 252 |
#include "clinic/dictobject.c.h" |
| 253 |
|
| 254 |
#define DK_SIZE(dk) ((dk)->dk_size) |
| 255 |
#if SIZEOF_VOID_P > 4 |
| 256 |
#define DK_IXSIZE(dk) \ |
| 257 |
(DK_SIZE(dk) <= 0xff ? \ |
| 258 |
1 : DK_SIZE(dk) <= 0xffff ? \ |
| 259 |
2 : DK_SIZE(dk) <= 0xffffffff ? \ |
| 260 |
4 : sizeof(int64_t)) |
| 261 |
#else |
| 262 |
#define DK_IXSIZE(dk) \ |
| 263 |
(DK_SIZE(dk) <= 0xff ? \ |
| 264 |
1 : DK_SIZE(dk) <= 0xffff ? \ |
| 265 |
2 : sizeof(int32_t)) |
| 266 |
#endif |
| 267 |
#define DK_ENTRIES(dk) \ |
| 268 |
((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)])) |
| 269 |
|
| 270 |
#define DK_MASK(dk) (((dk)->dk_size)-1) |
| 271 |
#define IS_POWER_OF_2(x) (((x) & (x-1)) == 0) |
| 272 |
|
| 273 |
static void free_keys_object(PyDictKeysObject *keys); |
| 274 |
|
| 275 |
static inline void |
| 276 |
dictkeys_incref(PyDictKeysObject *dk) |
| 277 |
{ |
| 278 |
_Py_INC_REFTOTAL; |
| 279 |
dk->dk_refcnt++; |
| 280 |
} |
| 281 |
|
| 282 |
static inline void |
| 283 |
dictkeys_decref(PyDictKeysObject *dk) |
| 284 |
{ |
| 285 |
assert(dk->dk_refcnt > 0); |
| 286 |
_Py_DEC_REFTOTAL; |
| 287 |
if (--dk->dk_refcnt == 0) { |
| 288 |
free_keys_object(dk); |
| 289 |
} |
| 290 |
} |
| 291 |
|
| 292 |
/* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */ |
| 293 |
static inline Py_ssize_t |
| 294 |
dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) |
| 295 |
{ |
| 296 |
Py_ssize_t s = DK_SIZE(keys); |
| 297 |
Py_ssize_t ix; |
| 298 |
|
| 299 |
if (s <= 0xff) { |
| 300 |
const int8_t *indices = (const int8_t*)(keys->dk_indices); |
| 301 |
ix = indices[i]; |
| 302 |
} |
| 303 |
else if (s <= 0xffff) { |
| 304 |
const int16_t *indices = (const int16_t*)(keys->dk_indices); |
| 305 |
ix = indices[i]; |
| 306 |
} |
| 307 |
#if SIZEOF_VOID_P > 4 |
| 308 |
else if (s > 0xffffffff) { |
| 309 |
const int64_t *indices = (const int64_t*)(keys->dk_indices); |
| 310 |
ix = indices[i]; |
| 311 |
} |
| 312 |
#endif |
| 313 |
else { |
| 314 |
const int32_t *indices = (const int32_t*)(keys->dk_indices); |
| 315 |
ix = indices[i]; |
| 316 |
} |
| 317 |
assert(ix >= DKIX_DUMMY); |
| 318 |
return ix; |
| 319 |
} |
| 320 |
|
| 321 |
/* write to indices. */ |
| 322 |
static inline void |
| 323 |
dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix) |
| 324 |
{ |
| 325 |
Py_ssize_t s = DK_SIZE(keys); |
| 326 |
|
| 327 |
assert(ix >= DKIX_DUMMY); |
| 328 |
|
| 329 |
if (s <= 0xff) { |
| 330 |
int8_t *indices = (int8_t*)(keys->dk_indices); |
| 331 |
assert(ix <= 0x7f); |
| 332 |
indices[i] = (char)ix; |
| 333 |
} |
| 334 |
else if (s <= 0xffff) { |
| 335 |
int16_t *indices = (int16_t*)(keys->dk_indices); |
| 336 |
assert(ix <= 0x7fff); |
| 337 |
indices[i] = (int16_t)ix; |
| 338 |
} |
| 339 |
#if SIZEOF_VOID_P > 4 |
| 340 |
else if (s > 0xffffffff) { |
| 341 |
int64_t *indices = (int64_t*)(keys->dk_indices); |
| 342 |
indices[i] = ix; |
| 343 |
} |
| 344 |
#endif |
| 345 |
else { |
| 346 |
int32_t *indices = (int32_t*)(keys->dk_indices); |
| 347 |
assert(ix <= 0x7fffffff); |
| 348 |
indices[i] = (int32_t)ix; |
| 349 |
} |
| 350 |
} |
| 351 |
|
| 352 |
|
| 353 |
/* USABLE_FRACTION is the maximum dictionary load. |
| 354 |
* Increasing this ratio makes dictionaries more dense resulting in more |
| 355 |
* collisions. Decreasing it improves sparseness at the expense of spreading |
| 356 |
* indices over more cache lines and at the cost of total memory consumed. |
| 357 |
* |
| 358 |
* USABLE_FRACTION must obey the following: |
| 359 |
* (0 < USABLE_FRACTION(n) < n) for all n >= 2 |
| 360 |
* |
| 361 |
* USABLE_FRACTION should be quick to calculate. |
| 362 |
* Fractions around 1/2 to 2/3 seem to work well in practice. |
| 363 |
*/ |
| 364 |
#define USABLE_FRACTION(n) (((n) << 1)/3) |
| 365 |
|
| 366 |
/* Find the smallest dk_size >= minsize. */ |
| 367 |
static inline Py_ssize_t |
| 368 |
calculate_keysize(Py_ssize_t minsize) |
| 369 |
{ |
| 370 |
#if SIZEOF_LONG == SIZEOF_SIZE_T |
| 371 |
minsize = (minsize | PyDict_MINSIZE) - 1; |
| 372 |
return 1LL << _Py_bit_length(minsize | (PyDict_MINSIZE-1)); |
| 373 |
#elif defined(_MSC_VER) |
| 374 |
// On 64bit Windows, sizeof(long) == 4. |
| 375 |
minsize = (minsize | PyDict_MINSIZE) - 1; |
| 376 |
unsigned long msb; |
| 377 |
_BitScanReverse64(&msb, (uint64_t)minsize); |
| 378 |
return 1LL << (msb + 1); |
| 379 |
#else |
| 380 |
Py_ssize_t size; |
| 381 |
for (size = PyDict_MINSIZE; |
| 382 |
size < minsize && size > 0; |
| 383 |
size <<= 1) |
| 384 |
; |
| 385 |
return size; |
| 386 |
#endif |
| 387 |
} |
| 388 |
|
| 389 |
/* estimate_keysize is reverse function of USABLE_FRACTION. |
| 390 |
* |
| 391 |
* This can be used to reserve enough size to insert n entries without |
| 392 |
* resizing. |
| 393 |
*/ |
| 394 |
static inline Py_ssize_t |
| 395 |
estimate_keysize(Py_ssize_t n) |
| 396 |
{ |
| 397 |
return calculate_keysize((n*3 + 1) / 2); |
| 398 |
} |
| 399 |
|
| 400 |
|
| 401 |
/* GROWTH_RATE. Growth rate upon hitting maximum load. |
| 402 |
* Currently set to used*3. |
| 403 |
* This means that dicts double in size when growing without deletions, |
| 404 |
* but have more head room when the number of deletions is on a par with the |
| 405 |
* number of insertions. See also bpo-17563 and bpo-33205. |
| 406 |
* |
| 407 |
* GROWTH_RATE was set to used*4 up to version 3.2. |
| 408 |
* GROWTH_RATE was set to used*2 in version 3.3.0 |
| 409 |
* GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0. |
| 410 |
*/ |
| 411 |
#define GROWTH_RATE(d) ((d)->ma_used*3) |
| 412 |
|
| 413 |
/* This immutable, empty PyDictKeysObject is used for PyDict_Clear() |
| 414 |
* (which cannot fail and thus can do no allocation). |
| 415 |
*/ |
| 416 |
static PyDictKeysObject empty_keys_struct = { |
| 417 |
1, /* dk_refcnt */ |
| 418 |
1, /* dk_size */ |
| 419 |
lookdict_unicode_nodummy, /* dk_lookup */ |
| 420 |
0, /* dk_usable (immutable) */ |
| 421 |
0, /* dk_nentries */ |
| 422 |
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, |
| 423 |
DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */ |
| 424 |
}; |
| 425 |
|
| 426 |
static PyObject *empty_values[1] = { NULL }; |
| 427 |
|
| 428 |
#define Py_EMPTY_KEYS &empty_keys_struct |
| 429 |
|
| 430 |
/* Uncomment to check the dict content in _PyDict_CheckConsistency() */ |
| 431 |
/* #define DEBUG_PYDICT */ |
| 432 |
|
| 433 |
#ifdef DEBUG_PYDICT |
| 434 |
# define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 1)) |
| 435 |
#else |
| 436 |
# define ASSERT_CONSISTENT(op) assert(_PyDict_CheckConsistency((PyObject *)(op), 0)) |
| 437 |
#endif |
| 438 |
|
| 439 |
|
| 440 |
#ifndef NDEBUG |
| 441 |
static int |
| 442 |
_PyDict_CheckConsistency(PyObject *op, int check_content) |
| 443 |
{ |
| 444 |
assert(op != NULL); |
| 445 |
assert(PyAnyDict_Check(op)); |
| 446 |
PyDictObject *mp = (PyDictObject *)op; |
| 447 |
|
| 448 |
PyDictKeysObject *keys = mp->ma_keys; |
| 449 |
int splitted = _PyDict_HasSplitTable(mp); |
| 450 |
Py_ssize_t usable = USABLE_FRACTION(keys->dk_size); |
| 451 |
|
| 452 |
assert(0 <= mp->ma_used && mp->ma_used <= usable); |
| 453 |
assert(IS_POWER_OF_2(keys->dk_size)); |
| 454 |
assert(0 <= keys->dk_usable |
| 455 |
&& keys->dk_usable <= usable); |
| 456 |
assert(0 <= keys->dk_nentries |
| 457 |
&& keys->dk_nentries <= usable); |
| 458 |
assert(keys->dk_usable + keys->dk_nentries <= usable); |
| 459 |
|
| 460 |
if (!splitted) { |
| 461 |
/* combined table */ |
| 462 |
assert(keys->dk_refcnt == 1); |
| 463 |
} |
| 464 |
|
| 465 |
if (check_content) { |
| 466 |
PyDictKeyEntry *entries = DK_ENTRIES(keys); |
| 467 |
Py_ssize_t i; |
| 468 |
|
| 469 |
for (i=0; i < keys->dk_size; i++) { |
| 470 |
Py_ssize_t ix = dictkeys_get_index(keys, i); |
| 471 |
assert(DKIX_DUMMY <= ix && ix <= usable); |
| 472 |
} |
| 473 |
|
| 474 |
for (i=0; i < usable; i++) { |
| 475 |
PyDictKeyEntry *entry = &entries[i]; |
| 476 |
PyObject *key = entry->me_key; |
| 477 |
|
| 478 |
if (key != NULL) { |
| 479 |
if (PyUnicode_CheckExact(key)) { |
| 480 |
Py_hash_t hash = ((PyASCIIObject *)key)->hash; |
| 481 |
assert(hash != -1); |
| 482 |
assert(entry->me_hash == hash); |
| 483 |
} |
| 484 |
else { |
| 485 |
/* test_dict fails if PyObject_Hash() is called again */ |
| 486 |
assert(entry->me_hash != -1); |
| 487 |
} |
| 488 |
if (!splitted) { |
| 489 |
assert(entry->me_value != NULL); |
| 490 |
} |
| 491 |
} |
| 492 |
|
| 493 |
if (splitted) { |
| 494 |
assert(entry->me_value == NULL); |
| 495 |
} |
| 496 |
} |
| 497 |
|
| 498 |
if (splitted) { |
| 499 |
/* splitted table */ |
| 500 |
for (i=0; i < mp->ma_used; i++) { |
| 501 |
assert(mp->ma_values[i] != NULL); |
| 502 |
} |
| 503 |
} |
| 504 |
} |
| 505 |
return 1; |
| 506 |
} |
| 507 |
#endif |
| 508 |
|
| 509 |
|
| 510 |
static PyDictKeysObject* |
| 511 |
new_keys_object(Py_ssize_t size) |
| 512 |
{ |
| 513 |
PyDictKeysObject *dk; |
| 514 |
Py_ssize_t es, usable; |
| 515 |
|
| 516 |
assert(size >= PyDict_MINSIZE); |
| 517 |
assert(IS_POWER_OF_2(size)); |
| 518 |
|
| 519 |
usable = USABLE_FRACTION(size); |
| 520 |
if (size <= 0xff) { |
| 521 |
es = 1; |
| 522 |
} |
| 523 |
else if (size <= 0xffff) { |
| 524 |
es = 2; |
| 525 |
} |
| 526 |
#if SIZEOF_VOID_P > 4 |
| 527 |
else if (size <= 0xffffffff) { |
| 528 |
es = 4; |
| 529 |
} |
| 530 |
#endif |
| 531 |
else { |
| 532 |
es = sizeof(Py_ssize_t); |
| 533 |
} |
| 534 |
|
| 535 |
#if PyDict_MAXFREELIST > 0 |
| 536 |
if (size == PyDict_MINSIZE && numfreekeys > 0) { |
| 537 |
dk = keys_free_list[--numfreekeys]; |
| 538 |
} |
| 539 |
else |
| 540 |
#endif |
| 541 |
{ |
| 542 |
dk = PyObject_Malloc(sizeof(PyDictKeysObject) |
| 543 |
+ es * size |
| 544 |
+ sizeof(PyDictKeyEntry) * usable); |
| 545 |
if (dk == NULL) { |
| 546 |
PyErr_NoMemory(); |
| 547 |
return NULL; |
| 548 |
} |
| 549 |
} |
| 550 |
_Py_INC_REFTOTAL; |
| 551 |
dk->dk_refcnt = 1; |
| 552 |
dk->dk_size = size; |
| 553 |
dk->dk_usable = usable; |
| 554 |
dk->dk_lookup = lookdict_unicode_nodummy; |
| 555 |
dk->dk_nentries = 0; |
| 556 |
memset(&dk->dk_indices[0], 0xff, es * size); |
| 557 |
memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable); |
| 558 |
return dk; |
| 559 |
} |
| 560 |
|
| 561 |
static void |
| 562 |
free_keys_object(PyDictKeysObject *keys) |
| 563 |
{ |
| 564 |
PyDictKeyEntry *entries = DK_ENTRIES(keys); |
| 565 |
Py_ssize_t i, n; |
| 566 |
for (i = 0, n = keys->dk_nentries; i < n; i++) { |
| 567 |
Py_XDECREF(entries[i].me_key); |
| 568 |
Py_XDECREF(entries[i].me_value); |
| 569 |
} |
| 570 |
#if PyDict_MAXFREELIST > 0 |
| 571 |
if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) { |
| 572 |
keys_free_list[numfreekeys++] = keys; |
| 573 |
return; |
| 574 |
} |
| 575 |
#endif |
| 576 |
PyObject_Free(keys); |
| 577 |
} |
| 578 |
|
| 579 |
#define new_values(size) PyMem_NEW(PyObject *, size) |
| 580 |
#define free_values(values) PyMem_Free(values) |
| 581 |
|
| 582 |
static Py_ssize_t |
| 583 |
_d_PyDict_KeysSize(PyDictKeysObject *keys) |
| 584 |
{ |
| 585 |
return (sizeof(PyDictKeysObject) |
| 586 |
+ DK_IXSIZE(keys) * DK_SIZE(keys) |
| 587 |
+ USABLE_FRACTION(DK_SIZE(keys)) * sizeof(PyDictKeyEntry)); |
| 588 |
} |
| 589 |
|
| 590 |
static PyDictKeysObject * |
| 591 |
clone_combined_dict_keys(PyDictObject *orig) |
| 592 |
{ |
| 593 |
assert(PyAnyDict_Check(orig)); |
| 594 |
|
| 595 |
assert( |
| 596 |
Py_TYPE(orig)->tp_iter == PyDict_Type.tp_iter || |
| 597 |
Py_TYPE(orig)->tp_iter == (getiterfunc)frozendict_iter |
| 598 |
); |
| 599 |
|
| 600 |
assert(orig->ma_values == NULL); |
| 601 |
assert(orig->ma_keys->dk_refcnt == 1); |
| 602 |
|
| 603 |
Py_ssize_t keys_size = _d_PyDict_KeysSize(orig->ma_keys); |
| 604 |
PyDictKeysObject *keys = PyObject_Malloc(keys_size); |
| 605 |
if (keys == NULL) { |
| 606 |
PyErr_NoMemory(); |
| 607 |
return NULL; |
| 608 |
} |
| 609 |
|
| 610 |
memcpy(keys, orig->ma_keys, keys_size); |
| 611 |
|
| 612 |
/* After copying key/value pairs, we need to incref all |
| 613 |
keys and values and they are about to be co-owned by a |
| 614 |
new dict object. */ |
| 615 |
PyDictKeyEntry *ep0 = DK_ENTRIES(keys); |
| 616 |
Py_ssize_t n = keys->dk_nentries; |
| 617 |
for (Py_ssize_t i = 0; i < n; i++) { |
| 618 |
PyDictKeyEntry *entry = &ep0[i]; |
| 619 |
PyObject *value = entry->me_value; |
| 620 |
Py_INCREF(value); |
| 621 |
Py_INCREF(entry->me_key); |
| 622 |
} |
| 623 |
|
| 624 |
/* Since we copied the keys table we now have an extra reference |
| 625 |
in the system. Manually call _Py_INC_REFTOTAL to signal that |
| 626 |
we have it now; calling dictkeys_incref would be an error as |
| 627 |
keys->dk_refcnt is already set to 1 (after memcpy). */ |
| 628 |
_Py_INC_REFTOTAL; |
| 629 |
|
| 630 |
return keys; |
| 631 |
} |
| 632 |
|
| 633 |
/* |
| 634 |
The basic lookup function used by all operations. |
| 635 |
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. |
| 636 |
Open addressing is preferred over chaining since the link overhead for |
| 637 |
chaining would be substantial (100% with typical malloc overhead). |
| 638 |
|
| 639 |
The initial probe index is computed as hash mod the table size. Subsequent |
| 640 |
probe indices are computed as explained earlier. |
| 641 |
|
| 642 |
All arithmetic on hash should ignore overflow. |
| 643 |
|
| 644 |
The details in this version are due to Tim Peters, building on many past |
| 645 |
contributions by Reimer Behrends, Jyrki Alakuijala, Vladimir Marangozov and |
| 646 |
Christian Tismer. |
| 647 |
|
| 648 |
lookdict() is general-purpose, and may return DKIX_ERROR if (and only if) a |
| 649 |
comparison raises an exception. |
| 650 |
lookdict_unicode() below is specialized to string keys, comparison of which can |
| 651 |
never raise an exception; that function can never return DKIX_ERROR when key |
| 652 |
is string. Otherwise, it falls back to lookdict(). |
| 653 |
lookdict_unicode_nodummy is further specialized for string keys that cannot be |
| 654 |
the <dummy> value. |
| 655 |
For both, when the key isn't found a DKIX_EMPTY is returned. hashpos returns |
| 656 |
where the key index should be inserted. |
| 657 |
*/ |
| 658 |
static Py_ssize_t _Py_HOT_FUNCTION |
| 659 |
lookdict(PyDictObject *mp, PyObject *key, |
| 660 |
Py_hash_t hash, PyObject ***value_addr, Py_ssize_t *hashpos) |
| 661 |
{ |
| 662 |
size_t i, mask, perturb; |
| 663 |
PyDictKeysObject *dk; |
| 664 |
PyDictKeyEntry *ep0; |
| 665 |
|
| 666 |
top: |
| 667 |
dk = mp->ma_keys; |
| 668 |
ep0 = DK_ENTRIES(dk); |
| 669 |
mask = DK_MASK(dk); |
| 670 |
perturb = hash; |
| 671 |
i = (size_t)hash & mask; |
| 672 |
|
| 673 |
for (;;) { |
| 674 |
Py_ssize_t ix = dictkeys_get_index(dk, i); |
| 675 |
if (ix == DKIX_EMPTY) { |
| 676 |
if (hashpos != NULL) |
| 677 |
*hashpos = i; |
| 678 |
*value_addr = NULL; |
| 679 |
return ix; |
| 680 |
} |
| 681 |
if (ix >= 0) { |
| 682 |
PyDictKeyEntry *ep = &ep0[ix]; |
| 683 |
assert(ep->me_key != NULL); |
| 684 |
if (ep->me_key == key) { |
| 685 |
*value_addr = &ep->me_value; |
| 686 |
if (hashpos != NULL) |
| 687 |
*hashpos = i; |
| 688 |
return ix; |
| 689 |
} |
| 690 |
if (ep->me_hash == hash) { |
| 691 |
PyObject *startkey = ep->me_key; |
| 692 |
Py_INCREF(startkey); |
| 693 |
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); |
| 694 |
Py_DECREF(startkey); |
| 695 |
if (cmp < 0) { |
| 696 |
*value_addr = NULL; |
| 697 |
return DKIX_ERROR; |
| 698 |
} |
| 699 |
if (dk == mp->ma_keys && ep->me_key == startkey) { |
| 700 |
if (cmp > 0) { |
| 701 |
*value_addr = &ep->me_value; |
| 702 |
if (hashpos != NULL) |
| 703 |
*hashpos = i; |
| 704 |
return ix; |
| 705 |
} |
| 706 |
} |
| 707 |
else { |
| 708 |
/* The dict was mutated, restart */ |
| 709 |
goto top; |
| 710 |
} |
| 711 |
} |
| 712 |
} |
| 713 |
perturb >>= PERTURB_SHIFT; |
| 714 |
i = (i*5 + perturb + 1) & mask; |
| 715 |
} |
| 716 |
Py_UNREACHABLE(); |
| 717 |
} |
| 718 |
|
| 719 |
/* Faster version of lookdict_unicode when it is known that no <dummy> keys |
| 720 |
* will be present. */ |
| 721 |
static Py_ssize_t _Py_HOT_FUNCTION |
| 722 |
lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key, |
| 723 |
Py_hash_t hash, PyObject ***value_addr, |
| 724 |
Py_ssize_t *hashpos) |
| 725 |
{ |
| 726 |
assert(mp->ma_values == NULL); |
| 727 |
/* Make sure this function doesn't have to handle non-unicode keys, |
| 728 |
including subclasses of str; e.g., one reason to subclass |
| 729 |
unicodes is to override __eq__, and for speed we don't cater to |
| 730 |
that here. */ |
| 731 |
if (!PyUnicode_CheckExact(key)) { |
| 732 |
return lookdict(mp, key, hash, value_addr, hashpos); |
| 733 |
} |
| 734 |
|
| 735 |
PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys); |
| 736 |
size_t mask = DK_MASK(mp->ma_keys); |
| 737 |
size_t perturb = (size_t)hash; |
| 738 |
size_t i = (size_t)hash & mask; |
| 739 |
|
| 740 |
for (;;) { |
| 741 |
Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i); |
| 742 |
assert (ix != DKIX_DUMMY); |
| 743 |
if (ix == DKIX_EMPTY) { |
| 744 |
if (hashpos != NULL) |
| 745 |
*hashpos = i; |
| 746 |
*value_addr = NULL; |
| 747 |
return DKIX_EMPTY; |
| 748 |
} |
| 749 |
PyDictKeyEntry *ep = &ep0[ix]; |
| 750 |
assert(ep->me_key != NULL); |
| 751 |
assert(PyUnicode_CheckExact(ep->me_key)); |
| 752 |
if (ep->me_key == key || |
| 753 |
(ep->me_hash == hash && unicode_eq(ep->me_key, key))) { |
| 754 |
if (hashpos != NULL) |
| 755 |
*hashpos = i; |
| 756 |
*value_addr = &ep->me_value; |
| 757 |
return ix; |
| 758 |
} |
| 759 |
perturb >>= PERTURB_SHIFT; |
| 760 |
i = mask & (i*5 + perturb + 1); |
| 761 |
} |
| 762 |
Py_UNREACHABLE(); |
| 763 |
} |
| 764 |
|
| 765 |
#define MAINTAIN_TRACKING(mp, key, value) \ |
| 766 |
do { \ |
| 767 |
if (!_PyObject_GC_IS_TRACKED(mp)) { \ |
| 768 |
if (_PyObject_GC_MAY_BE_TRACKED(key) || \ |
| 769 |
_PyObject_GC_MAY_BE_TRACKED(value)) { \ |
| 770 |
PyObject_GC_Track(mp); \ |
| 771 |
} \ |
| 772 |
} \ |
| 773 |
} while(0) |
| 774 |
|
| 775 |
/* Internal function to find slot for an item from its hash |
| 776 |
when it is known that the key is not present in the dict. |
| 777 |
|
| 778 |
The dict must be combined. */ |
| 779 |
static Py_ssize_t |
| 780 |
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash) |
| 781 |
{ |
| 782 |
assert(keys != NULL); |
| 783 |
|
| 784 |
const size_t mask = DK_MASK(keys); |
| 785 |
size_t i = hash & mask; |
| 786 |
Py_ssize_t ix = dictkeys_get_index(keys, i); |
| 787 |
for (size_t perturb = hash; ix >= 0;) { |
| 788 |
perturb >>= PERTURB_SHIFT; |
| 789 |
i = (i*5 + perturb + 1) & mask; |
| 790 |
ix = dictkeys_get_index(keys, i); |
| 791 |
} |
| 792 |
return i; |
| 793 |
} |
| 794 |
|
| 795 |
/* |
| 796 |
Internal routine used by dictresize() to build a hashtable of entries. |
| 797 |
*/ |
| 798 |
static void |
| 799 |
build_indices(PyDictKeysObject *keys, PyDictKeyEntry *ep, Py_ssize_t n) |
| 800 |
{ |
| 801 |
size_t mask = (size_t)DK_SIZE(keys) - 1; |
| 802 |
for (Py_ssize_t ix = 0; ix != n; ix++, ep++) { |
| 803 |
Py_hash_t hash = ep->me_hash; |
| 804 |
size_t i = hash & mask; |
| 805 |
for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) { |
| 806 |
perturb >>= PERTURB_SHIFT; |
| 807 |
i = mask & (i*5 + perturb + 1); |
| 808 |
} |
| 809 |
dictkeys_set_index(keys, i, ix); |
| 810 |
} |
| 811 |
} |
| 812 |
|
| 813 |
static int |
| 814 |
_d_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, |
| 815 |
PyObject **pvalue, Py_hash_t *phash) |
| 816 |
{ |
| 817 |
Py_ssize_t i; |
| 818 |
PyDictObject *mp; |
| 819 |
PyDictKeyEntry *entry_ptr; |
| 820 |
PyObject *value; |
| 821 |
|
| 822 |
if (!PyAnyDict_Check(op)) |
| 823 |
return 0; |
| 824 |
mp = (PyDictObject *)op; |
| 825 |
i = *ppos; |
| 826 |
if (mp->ma_values) { |
| 827 |
if (i < 0 || i >= mp->ma_used) |
| 828 |
return 0; |
| 829 |
/* values of split table is always dense */ |
| 830 |
entry_ptr = &DK_ENTRIES(mp->ma_keys)[i]; |
| 831 |
value = mp->ma_values[i]; |
| 832 |
assert(value != NULL); |
| 833 |
} |
| 834 |
else { |
| 835 |
Py_ssize_t n = mp->ma_keys->dk_nentries; |
| 836 |
if (i < 0 || i >= n) |
| 837 |
return 0; |
| 838 |
entry_ptr = &DK_ENTRIES(mp->ma_keys)[i]; |
| 839 |
while (i < n && entry_ptr->me_value == NULL) { |
| 840 |
entry_ptr++; |
| 841 |
i++; |
| 842 |
} |
| 843 |
if (i >= n) |
| 844 |
return 0; |
| 845 |
value = entry_ptr->me_value; |
| 846 |
} |
| 847 |
*ppos = i+1; |
| 848 |
if (pkey) |
| 849 |
*pkey = entry_ptr->me_key; |
| 850 |
if (phash) |
| 851 |
*phash = entry_ptr->me_hash; |
| 852 |
if (pvalue) |
| 853 |
*pvalue = value; |
| 854 |
return 1; |
| 855 |
} |
| 856 |
|
| 857 |
/* Methods */ |
| 858 |
|
| 859 |
static void |
| 860 |
dict_dealloc(PyDictObject *mp) |
| 861 |
{ |
| 862 |
PyObject **values = mp->ma_values; |
| 863 |
PyDictKeysObject *keys = mp->ma_keys; |
| 864 |
Py_ssize_t i, n; |
| 865 |
|
| 866 |
/* bpo-31095: UnTrack is needed before calling any callbacks */ |
| 867 |
PyObject_GC_UnTrack(mp); |
| 868 |
Py_TRASHCAN_SAFE_BEGIN(mp) |
| 869 |
if (values != NULL) { |
| 870 |
if (values != empty_values) { |
| 871 |
for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) { |
| 872 |
Py_XDECREF(values[i]); |
| 873 |
} |
| 874 |
free_values(values); |
| 875 |
} |
| 876 |
dictkeys_decref(keys); |
| 877 |
} |
| 878 |
else if (keys != NULL) { |
| 879 |
assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS); |
| 880 |
dictkeys_decref(keys); |
| 881 |
} |
| 882 |
#if PyDict_MAXFREELIST > 0 |
| 883 |
if (numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) { |
| 884 |
free_list[numfree++] = mp; |
| 885 |
} |
| 886 |
else |
| 887 |
#endif |
| 888 |
{ |
| 889 |
Py_TYPE(mp)->tp_free((PyObject *)mp); |
| 890 |
} |
| 891 |
Py_TRASHCAN_SAFE_END(mp) |
| 892 |
} |
| 893 |
|
| 894 |
static PyObject * |
| 895 |
dict_repr(PyDictObject *mp) |
| 896 |
{ |
| 897 |
Py_ssize_t i; |
| 898 |
PyObject *key = NULL, *value = NULL; |
| 899 |
_PyUnicodeWriter writer; |
| 900 |
int first; |
| 901 |
|
| 902 |
i = Py_ReprEnter((PyObject *)mp); |
| 903 |
if (i != 0) { |
| 904 |
return i > 0 ? PyUnicode_FromString("{...}") : NULL; |
| 905 |
} |
| 906 |
|
| 907 |
if (mp->ma_used == 0) { |
| 908 |
Py_ReprLeave((PyObject *)mp); |
| 909 |
return PyUnicode_FromString("{}"); |
| 910 |
} |
| 911 |
|
| 912 |
_PyUnicodeWriter_Init(&writer); |
| 913 |
writer.overallocate = 1; |
| 914 |
/* "{" + "1: 2" + ", 3: 4" * (len - 1) + "}" */ |
| 915 |
writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1; |
| 916 |
|
| 917 |
if (_PyUnicodeWriter_WriteChar(&writer, '{') < 0) |
| 918 |
goto error; |
| 919 |
|
| 920 |
/* Do repr() on each key+value pair, and insert ": " between them. |
| 921 |
Note that repr may mutate the dict. */ |
| 922 |
i = 0; |
| 923 |
first = 1; |
| 924 |
while (_d_PyDict_Next((PyObject *)mp, &i, &key, &value, NULL)) { |
| 925 |
PyObject *s; |
| 926 |
int res; |
| 927 |
|
| 928 |
/* Prevent repr from deleting key or value during key format. */ |
| 929 |
Py_INCREF(key); |
| 930 |
Py_INCREF(value); |
| 931 |
|
| 932 |
if (!first) { |
| 933 |
if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0) |
| 934 |
goto error; |
| 935 |
} |
| 936 |
first = 0; |
| 937 |
|
| 938 |
s = PyObject_Repr(key); |
| 939 |
if (s == NULL) |
| 940 |
goto error; |
| 941 |
res = _PyUnicodeWriter_WriteStr(&writer, s); |
| 942 |
Py_DECREF(s); |
| 943 |
if (res < 0) |
| 944 |
goto error; |
| 945 |
|
| 946 |
if (_PyUnicodeWriter_WriteASCIIString(&writer, ": ", 2) < 0) |
| 947 |
goto error; |
| 948 |
|
| 949 |
s = PyObject_Repr(value); |
| 950 |
if (s == NULL) |
| 951 |
goto error; |
| 952 |
res = _PyUnicodeWriter_WriteStr(&writer, s); |
| 953 |
Py_DECREF(s); |
| 954 |
if (res < 0) |
| 955 |
goto error; |
| 956 |
|
| 957 |
Py_CLEAR(key); |
| 958 |
Py_CLEAR(value); |
| 959 |
} |
| 960 |
|
| 961 |
writer.overallocate = 0; |
| 962 |
if (_PyUnicodeWriter_WriteChar(&writer, '}') < 0) |
| 963 |
goto error; |
| 964 |
|
| 965 |
Py_ReprLeave((PyObject *)mp); |
| 966 |
|
| 967 |
return _PyUnicodeWriter_Finish(&writer); |
| 968 |
|
| 969 |
error: |
| 970 |
Py_ReprLeave((PyObject *)mp); |
| 971 |
_PyUnicodeWriter_Dealloc(&writer); |
| 972 |
Py_XDECREF(key); |
| 973 |
Py_XDECREF(value); |
| 974 |
return NULL; |
| 975 |
} |
| 976 |
|
| 977 |
static Py_ssize_t |
| 978 |
dict_length(PyDictObject *mp) |
| 979 |
{ |
| 980 |
return mp->ma_used; |
| 981 |
} |
| 982 |
|
| 983 |
static PyObject * |
| 984 |
dict_subscript(PyDictObject *mp, PyObject *key) |
| 985 |
{ |
| 986 |
PyObject *v; |
| 987 |
Py_ssize_t ix; |
| 988 |
Py_hash_t hash; |
| 989 |
PyObject **value_addr; |
| 990 |
|
| 991 |
if (!PyUnicode_CheckExact(key) || |
| 992 |
(hash = ((PyASCIIObject *) key)->hash) == -1) { |
| 993 |
hash = PyObject_Hash(key); |
| 994 |
if (hash == -1) |
| 995 |
return NULL; |
| 996 |
} |
| 997 |
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); |
| 998 |
if (ix == DKIX_ERROR) |
| 999 |
return NULL; |
| 1000 |
if (ix == DKIX_EMPTY || *value_addr == NULL) { |
| 1001 |
if (!PyAnyDict_CheckExact(mp)) { |
| 1002 |
/* Look up __missing__ method if we're a subclass. */ |
| 1003 |
PyObject *missing, *res; |
| 1004 |
_Py_IDENTIFIER(__missing__); |
| 1005 |
missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__); |
| 1006 |
if (missing != NULL) { |
| 1007 |
res = PyObject_CallFunctionObjArgs(missing, |
| 1008 |
key, NULL); |
| 1009 |
Py_DECREF(missing); |
| 1010 |
return res; |
| 1011 |
} |
| 1012 |
else if (PyErr_Occurred()) |
| 1013 |
return NULL; |
| 1014 |
} |
| 1015 |
_PyErr_SetKeyError(key); |
| 1016 |
return NULL; |
| 1017 |
} |
| 1018 |
v = *value_addr; |
| 1019 |
Py_INCREF(v); |
| 1020 |
return v; |
| 1021 |
} |
| 1022 |
|
| 1023 |
static PyObject * |
| 1024 |
dict_richcompare(PyObject *v, PyObject *w, int op) |
| 1025 |
{ |
| 1026 |
int cmp; |
| 1027 |
PyObject *res; |
| 1028 |
|
| 1029 |
if (!PyAnyDict_Check(v) || !PyAnyDict_Check(w)) { |
| 1030 |
res = Py_NotImplemented; |
| 1031 |
} |
| 1032 |
else if (op == Py_EQ || op == Py_NE) { |
| 1033 |
cmp = frozendict_equal((PyDictObject *)v, (PyDictObject *)w); |
| 1034 |
if (cmp < 0) |
| 1035 |
return NULL; |
| 1036 |
res = (cmp == (op == Py_EQ)) ? Py_True : Py_False; |
| 1037 |
} |
| 1038 |
else |
| 1039 |
res = Py_NotImplemented; |
| 1040 |
Py_INCREF(res); |
| 1041 |
return res; |
| 1042 |
} |
| 1043 |
|
| 1044 |
/*[clinic input] |
| 1045 |
|
| 1046 |
@coexist |
| 1047 |
dict.__contains__ |
| 1048 |
|
| 1049 |
key: object |
| 1050 |
/ |
| 1051 |
|
| 1052 |
True if the dictionary has the specified key, else False. |
| 1053 |
[clinic start generated code]*/ |
| 1054 |
|
| 1055 |
static PyObject * |
| 1056 |
dict___contains__(PyDictObject *self, PyObject *key) |
| 1057 |
/*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/ |
| 1058 |
{ |
| 1059 |
register PyDictObject *mp = self; |
| 1060 |
Py_hash_t hash; |
| 1061 |
Py_ssize_t ix; |
| 1062 |
PyObject **value_addr; |
| 1063 |
|
| 1064 |
if (!PyUnicode_CheckExact(key) || |
| 1065 |
(hash = ((PyASCIIObject *) key)->hash) == -1) { |
| 1066 |
hash = PyObject_Hash(key); |
| 1067 |
if (hash == -1) |
| 1068 |
return NULL; |
| 1069 |
} |
| 1070 |
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); |
| 1071 |
if (ix == DKIX_ERROR) |
| 1072 |
return NULL; |
| 1073 |
if (ix == DKIX_EMPTY || *value_addr == NULL) |
| 1074 |
Py_RETURN_FALSE; |
| 1075 |
Py_RETURN_TRUE; |
| 1076 |
} |
| 1077 |
|
| 1078 |
static PyObject * |
| 1079 |
dict_get(PyDictObject *self, PyObject *args) |
| 1080 |
{ |
| 1081 |
PyObject *key; |
| 1082 |
PyObject *default_value = Py_None; |
| 1083 |
PyObject *val = NULL; |
| 1084 |
Py_hash_t hash; |
| 1085 |
Py_ssize_t ix; |
| 1086 |
PyObject **value_addr; |
| 1087 |
|
| 1088 |
if (!PyArg_UnpackTuple(args, "get", 1, 2, &key, &default_value)) |
| 1089 |
return NULL; |
| 1090 |
|
| 1091 |
if (!PyUnicode_CheckExact(key) || |
| 1092 |
(hash = ((PyASCIIObject *) key)->hash) == -1) { |
| 1093 |
hash = PyObject_Hash(key); |
| 1094 |
if (hash == -1) |
| 1095 |
return NULL; |
| 1096 |
} |
| 1097 |
ix = (self->ma_keys->dk_lookup) (self, key, hash, &value_addr, NULL); |
| 1098 |
if (ix == DKIX_ERROR) |
| 1099 |
return NULL; |
| 1100 |
if (ix == DKIX_EMPTY || *value_addr == NULL) { |
| 1101 |
val = default_value; |
| 1102 |
} |
| 1103 |
else { |
| 1104 |
val = *value_addr; |
| 1105 |
} |
| 1106 |
Py_INCREF(val); |
| 1107 |
return val; |
| 1108 |
} |
| 1109 |
|
| 1110 |
static int |
| 1111 |
dict_traverse(PyObject *op, visitproc visit, void *arg) |
| 1112 |
{ |
| 1113 |
PyDictObject *mp = (PyDictObject *)op; |
| 1114 |
PyDictKeysObject *keys = mp->ma_keys; |
| 1115 |
PyDictKeyEntry *entries = DK_ENTRIES(keys); |
| 1116 |
Py_ssize_t i, n = keys->dk_nentries; |
| 1117 |
|
| 1118 |
if (keys->dk_lookup == lookdict) { |
| 1119 |
for (i = 0; i < n; i++) { |
| 1120 |
if (entries[i].me_value != NULL) { |
| 1121 |
Py_VISIT(entries[i].me_value); |
| 1122 |
Py_VISIT(entries[i].me_key); |
| 1123 |
} |
| 1124 |
} |
| 1125 |
} |
| 1126 |
else { |
| 1127 |
if (mp->ma_values != NULL) { |
| 1128 |
for (i = 0; i < n; i++) { |
| 1129 |
Py_VISIT(mp->ma_values[i]); |
| 1130 |
} |
| 1131 |
} |
| 1132 |
else { |
| 1133 |
for (i = 0; i < n; i++) { |
| 1134 |
Py_VISIT(entries[i].me_value); |
| 1135 |
} |
| 1136 |
} |
| 1137 |
} |
| 1138 |
return 0; |
| 1139 |
} |
| 1140 |
|
| 1141 |
static PyObject *dictiter_new(PyDictObject *, PyTypeObject *); |
| 1142 |
|
| 1143 |
static Py_ssize_t |
| 1144 |
_d_PyDict_SizeOf(PyDictObject *mp) |
| 1145 |
{ |
| 1146 |
Py_ssize_t size, usable, res; |
| 1147 |
|
| 1148 |
size = DK_SIZE(mp->ma_keys); |
| 1149 |
usable = USABLE_FRACTION(size); |
| 1150 |
|
| 1151 |
res = _PyObject_SIZE(Py_TYPE(mp)); |
| 1152 |
if (mp->ma_values) |
| 1153 |
res += usable * sizeof(PyObject*); |
| 1154 |
/* If the dictionary is split, the keys portion is accounted-for |
| 1155 |
in the type object. */ |
| 1156 |
if (mp->ma_keys->dk_refcnt == 1) |
| 1157 |
res += (sizeof(PyDictKeysObject) |
| 1158 |
+ DK_IXSIZE(mp->ma_keys) * size |
| 1159 |
+ sizeof(PyDictKeyEntry) * usable); |
| 1160 |
return res; |
| 1161 |
} |
| 1162 |
|
| 1163 |
static PyObject * |
| 1164 |
dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored)) |
| 1165 |
{ |
| 1166 |
return PyLong_FromSsize_t(_d_PyDict_SizeOf(mp)); |
| 1167 |
} |
| 1168 |
|
| 1169 |
PyDoc_STRVAR(getitem__doc__, "x.__getitem__(y) <==> x[y]"); |
| 1170 |
|
| 1171 |
PyDoc_STRVAR(sizeof__doc__, |
| 1172 |
"D.__sizeof__() -> size of D in memory, in bytes"); |
| 1173 |
|
| 1174 |
PyDoc_STRVAR(copy__doc__, |
| 1175 |
"D.copy() -> a shallow copy of D"); |
| 1176 |
|
| 1177 |
PyDoc_STRVAR(keys__doc__, |
| 1178 |
"D.keys() -> a set-like object providing a view on D's keys"); |
| 1179 |
PyDoc_STRVAR(items__doc__, |
| 1180 |
"D.items() -> a set-like object providing a view on D's items"); |
| 1181 |
PyDoc_STRVAR(values__doc__, |
| 1182 |
"D.values() -> an object providing a view on D's values"); |
| 1183 |
|
| 1184 |
/* Hack to implement "key in dict" */ |
| 1185 |
static PySequenceMethods dict_as_sequence = { |
| 1186 |
0, /* sq_length */ |
| 1187 |
0, /* sq_concat */ |
| 1188 |
0, /* sq_repeat */ |
| 1189 |
0, /* sq_item */ |
| 1190 |
0, /* sq_slice */ |
| 1191 |
0, /* sq_ass_item */ |
| 1192 |
0, /* sq_ass_slice */ |
| 1193 |
PyDict_Contains, /* sq_contains */ |
| 1194 |
0, /* sq_inplace_concat */ |
| 1195 |
0, /* sq_inplace_repeat */ |
| 1196 |
}; |
| 1197 |
|
| 1198 |
/* Dictionary iterator types */ |
| 1199 |
|
| 1200 |
typedef struct { |
| 1201 |
PyObject_HEAD |
| 1202 |
PyDictObject *di_dict; /* Set to NULL when iterator is exhausted */ |
| 1203 |
Py_ssize_t di_used; |
| 1204 |
Py_ssize_t di_pos; |
| 1205 |
PyObject* di_result; /* reusable result tuple for iteritems */ |
| 1206 |
Py_ssize_t len; |
| 1207 |
} dictiterobject; |
| 1208 |
|
| 1209 |
PyTypeObject PyDictRevIterKey_Type; |
| 1210 |
PyTypeObject PyDictRevIterValue_Type; |
| 1211 |
PyTypeObject PyDictRevIterItem_Type; |
| 1212 |
|
| 1213 |
static PyObject * |
| 1214 |
dictiter_new(PyDictObject *dict, PyTypeObject *itertype) |
| 1215 |
{ |
| 1216 |
dictiterobject *di; |
| 1217 |
di = PyObject_GC_New(dictiterobject, itertype); |
| 1218 |
if (di == NULL) { |
| 1219 |
return NULL; |
| 1220 |
} |
| 1221 |
Py_INCREF(dict); |
| 1222 |
di->di_dict = dict; |
| 1223 |
di->di_used = dict->ma_used; |
| 1224 |
di->len = dict->ma_used; |
| 1225 |
if (itertype == &PyDictRevIterKey_Type || |
| 1226 |
itertype == &PyDictRevIterItem_Type || |
| 1227 |
itertype == &PyDictRevIterValue_Type) { |
| 1228 |
if (dict->ma_values) { |
| 1229 |
di->di_pos = dict->ma_used - 1; |
| 1230 |
} |
| 1231 |
else { |
| 1232 |
di->di_pos = dict->ma_keys->dk_nentries - 1; |
| 1233 |
} |
| 1234 |
} |
| 1235 |
else { |
| 1236 |
di->di_pos = 0; |
| 1237 |
} |
| 1238 |
if ( |
| 1239 |
itertype == &PyFrozenDictIterItem_Type || |
| 1240 |
itertype == &PyDictRevIterItem_Type |
| 1241 |
) { |
| 1242 |
di->di_result = PyTuple_Pack(2, Py_None, Py_None); |
| 1243 |
if (di->di_result == NULL) { |
| 1244 |
Py_DECREF(di); |
| 1245 |
return NULL; |
| 1246 |
} |
| 1247 |
} |
| 1248 |
else { |
| 1249 |
di->di_result = NULL; |
| 1250 |
} |
| 1251 |
PyObject_GC_Track(di); |
| 1252 |
return (PyObject *)di; |
| 1253 |
} |
| 1254 |
|
| 1255 |
static void |
| 1256 |
dictiter_dealloc(dictiterobject *di) |
| 1257 |
{ |
| 1258 |
/* bpo-31095: UnTrack is needed before calling any callbacks */ |
| 1259 |
PyObject_GC_UnTrack(di); |
| 1260 |
Py_XDECREF(di->di_dict); |
| 1261 |
Py_XDECREF(di->di_result); |
| 1262 |
PyObject_GC_Del(di); |
| 1263 |
} |
| 1264 |
|
| 1265 |
static int |
| 1266 |
dictiter_traverse(dictiterobject *di, visitproc visit, void *arg) |
| 1267 |
{ |
| 1268 |
Py_VISIT(di->di_dict); |
| 1269 |
Py_VISIT(di->di_result); |
| 1270 |
return 0; |
| 1271 |
} |
| 1272 |
|
| 1273 |
static PyObject * |
| 1274 |
dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored)) |
| 1275 |
{ |
| 1276 |
Py_ssize_t len = 0; |
| 1277 |
if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used) |
| 1278 |
len = di->len; |
| 1279 |
return PyLong_FromSize_t(len); |
| 1280 |
} |
| 1281 |
|
| 1282 |
PyDoc_STRVAR(length_hint_doc, |
| 1283 |
"Private method returning an estimate of len(list(it))."); |
| 1284 |
|
| 1285 |
static PyObject * |
| 1286 |
dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored)); |
| 1287 |
|
| 1288 |
PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); |
| 1289 |
|
| 1290 |
static PyMethodDef dictiter_methods[] = { |
| 1291 |
{"__length_hint__", (PyCFunction)(void(*)(void))dictiter_len, METH_NOARGS, |
| 1292 |
length_hint_doc}, |
| 1293 |
{"__reduce__", (PyCFunction)(void(*)(void))dictiter_reduce, METH_NOARGS, |
| 1294 |
reduce_doc}, |
| 1295 |
{NULL, NULL} /* sentinel */ |
| 1296 |
}; |
| 1297 |
|
| 1298 |
/* dictreviter */ |
| 1299 |
|
| 1300 |
static PyObject * |
| 1301 |
dictreviter_iternext(dictiterobject *di) |
| 1302 |
{ |
| 1303 |
PyDictObject *d = di->di_dict; |
| 1304 |
|
| 1305 |
if (d == NULL) { |
| 1306 |
return NULL; |
| 1307 |
} |
| 1308 |
assert (PyAnyDict_Check(d)); |
| 1309 |
|
| 1310 |
if (di->di_used != d->ma_used) { |
| 1311 |
PyErr_SetString(PyExc_RuntimeError, |
| 1312 |
"dictionary changed size during iteration"); |
| 1313 |
di->di_used = -1; /* Make this state sticky */ |
| 1314 |
return NULL; |
| 1315 |
} |
| 1316 |
|
| 1317 |
Py_ssize_t i = di->di_pos; |
| 1318 |
PyDictKeysObject *k = d->ma_keys; |
| 1319 |
PyObject *key, *value, *result; |
| 1320 |
|
| 1321 |
if (i < 0) { |
| 1322 |
goto fail; |
| 1323 |
} |
| 1324 |
if (d->ma_values) { |
| 1325 |
key = DK_ENTRIES(k)[i].me_key; |
| 1326 |
value = d->ma_values[i]; |
| 1327 |
assert (value != NULL); |
| 1328 |
} |
| 1329 |
else { |
| 1330 |
PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i]; |
| 1331 |
while (entry_ptr->me_value == NULL) { |
| 1332 |
if (--i < 0) { |
| 1333 |
goto fail; |
| 1334 |
} |
| 1335 |
entry_ptr--; |
| 1336 |
} |
| 1337 |
key = entry_ptr->me_key; |
| 1338 |
value = entry_ptr->me_value; |
| 1339 |
} |
| 1340 |
di->di_pos = i-1; |
| 1341 |
di->len--; |
| 1342 |
|
| 1343 |
if (Py_IS_TYPE(di, &PyDictRevIterKey_Type)) { |
| 1344 |
Py_INCREF(key); |
| 1345 |
return key; |
| 1346 |
} |
| 1347 |
else if (Py_IS_TYPE(di, &PyDictRevIterValue_Type)) { |
| 1348 |
Py_INCREF(value); |
| 1349 |
return value; |
| 1350 |
} |
| 1351 |
else if (Py_IS_TYPE(di, &PyDictRevIterItem_Type)) { |
| 1352 |
Py_INCREF(key); |
| 1353 |
Py_INCREF(value); |
| 1354 |
result = di->di_result; |
| 1355 |
if (Py_REFCNT(result) == 1) { |
| 1356 |
PyObject *oldkey = PyTuple_GET_ITEM(result, 0); |
| 1357 |
PyObject *oldvalue = PyTuple_GET_ITEM(result, 1); |
| 1358 |
PyTuple_SET_ITEM(result, 0, key); /* steals reference */ |
| 1359 |
PyTuple_SET_ITEM(result, 1, value); /* steals reference */ |
| 1360 |
Py_INCREF(result); |
| 1361 |
Py_DECREF(oldkey); |
| 1362 |
Py_DECREF(oldvalue); |
| 1363 |
// bpo-42536: The GC may have untracked this result tuple. Since |
| 1364 |
// we're recycling it, make sure it's tracked again: |
| 1365 |
// if (!_PyObject_GC_IS_TRACKED(result)) { |
| 1366 |
// _PyObject_GC_TRACK(result); |
| 1367 |
// } |
| 1368 |
} |
| 1369 |
else { |
| 1370 |
result = PyTuple_New(2); |
| 1371 |
if (result == NULL) { |
| 1372 |
return NULL; |
| 1373 |
} |
| 1374 |
PyTuple_SET_ITEM(result, 0, key); /* steals reference */ |
| 1375 |
PyTuple_SET_ITEM(result, 1, value); /* steals reference */ |
| 1376 |
} |
| 1377 |
return result; |
| 1378 |
} |
| 1379 |
else { |
| 1380 |
Py_UNREACHABLE(); |
| 1381 |
} |
| 1382 |
|
| 1383 |
fail: |
| 1384 |
di->di_dict = NULL; |
| 1385 |
Py_DECREF(d); |
| 1386 |
return NULL; |
| 1387 |
} |
| 1388 |
|
| 1389 |
PyTypeObject PyDictRevIterKey_Type = { |
| 1390 |
PyVarObject_HEAD_INIT(NULL, 0) |
| 1391 |
"dict_reversekeyiterator", |
| 1392 |
sizeof(dictiterobject), |
| 1393 |
.tp_dealloc = (destructor)dictiter_dealloc, |
| 1394 |
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, |
| 1395 |
.tp_traverse = (traverseproc)dictiter_traverse, |
| 1396 |
.tp_iter = PyObject_SelfIter, |
| 1397 |
.tp_iternext = (iternextfunc)dictreviter_iternext, |
| 1398 |
.tp_methods = dictiter_methods |
| 1399 |
}; |
| 1400 |
|
| 1401 |
PyTypeObject PyDictRevIterItem_Type = { |
| 1402 |
PyVarObject_HEAD_INIT(NULL, 0) |
| 1403 |
"dict_reverseitemiterator", |
| 1404 |
sizeof(dictiterobject), |
| 1405 |
.tp_dealloc = (destructor)dictiter_dealloc, |
| 1406 |
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, |
| 1407 |
.tp_traverse = (traverseproc)dictiter_traverse, |
| 1408 |
.tp_iter = PyObject_SelfIter, |
| 1409 |
.tp_iternext = (iternextfunc)dictreviter_iternext, |
| 1410 |
.tp_methods = dictiter_methods |
| 1411 |
}; |
| 1412 |
|
| 1413 |
PyTypeObject PyDictRevIterValue_Type = { |
| 1414 |
PyVarObject_HEAD_INIT(NULL, 0) |
| 1415 |
"dict_reversevalueiterator", |
| 1416 |
sizeof(dictiterobject), |
| 1417 |
.tp_dealloc = (destructor)dictiter_dealloc, |
| 1418 |
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, |
| 1419 |
.tp_traverse = (traverseproc)dictiter_traverse, |
| 1420 |
.tp_iter = PyObject_SelfIter, |
| 1421 |
.tp_iternext = (iternextfunc)dictreviter_iternext, |
| 1422 |
.tp_methods = dictiter_methods |
| 1423 |
}; |
| 1424 |
|
| 1425 |
/*[clinic input] |
| 1426 |
dict.__reversed__ |
| 1427 |
|
| 1428 |
Return a reverse iterator over the dict keys. |
| 1429 |
[clinic start generated code]*/ |
| 1430 |
|
| 1431 |
static PyObject * |
| 1432 |
dict___reversed___impl(PyDictObject *self) |
| 1433 |
/*[clinic end generated code: output=e674483336d1ed51 input=23210ef3477d8c4d]*/ |
| 1434 |
{ |
| 1435 |
assert (PyAnyDict_Check(self)); |
| 1436 |
return dictiter_new(self, &PyDictRevIterKey_Type); |
| 1437 |
} |
| 1438 |
|
| 1439 |
static PyObject * |
| 1440 |
dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored)) |
| 1441 |
{ |
| 1442 |
_Py_IDENTIFIER(iter); |
| 1443 |
/* copy the iterator state */ |
| 1444 |
dictiterobject tmp = *di; |
| 1445 |
Py_XINCREF(tmp.di_dict); |
| 1446 |
|
| 1447 |
PyObject *list = PySequence_List((PyObject*)&tmp); |
| 1448 |
Py_XDECREF(tmp.di_dict); |
| 1449 |
if (list == NULL) { |
| 1450 |
return NULL; |
| 1451 |
} |
| 1452 |
return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list); |
| 1453 |
} |
| 1454 |
|
| 1455 |
/***********************************************/ |
| 1456 |
/* View objects for keys(), items(), values(). */ |
| 1457 |
/***********************************************/ |
| 1458 |
|
| 1459 |
/* The instance lay-out is the same for all three; but the type differs. */ |
| 1460 |
|
| 1461 |
static void |
| 1462 |
dictview_dealloc(_PyDictViewObject *dv) |
| 1463 |
{ |
| 1464 |
/* bpo-31095: UnTrack is needed before calling any callbacks */ |
| 1465 |
PyObject_GC_UnTrack(dv); |
| 1466 |
Py_XDECREF(dv->dv_dict); |
| 1467 |
PyObject_GC_Del(dv); |
| 1468 |
} |
| 1469 |
|
| 1470 |
static int |
| 1471 |
dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg) |
| 1472 |
{ |
| 1473 |
Py_VISIT(dv->dv_dict); |
| 1474 |
return 0; |
| 1475 |
} |
| 1476 |
|
| 1477 |
static Py_ssize_t |
| 1478 |
dictview_len(_PyDictViewObject *dv) |
| 1479 |
{ |
| 1480 |
Py_ssize_t len = 0; |
| 1481 |
if (dv->dv_dict != NULL) |
| 1482 |
len = dv->dv_dict->ma_used; |
| 1483 |
return len; |
| 1484 |
} |
| 1485 |
|
| 1486 |
static PyObject * |
| 1487 |
_d_PyDictView_New(PyObject *dict, PyTypeObject *type) |
| 1488 |
{ |
| 1489 |
_PyDictViewObject *dv; |
| 1490 |
if (dict == NULL) { |
| 1491 |
PyErr_BadInternalCall(); |
| 1492 |
return NULL; |
| 1493 |
} |
| 1494 |
if (!PyAnyDict_Check(dict)) { |
| 1495 |
/* XXX Get rid of this restriction later */ |
| 1496 |
PyErr_Format(PyExc_TypeError, |
| 1497 |
"%s() requires a dict argument, not '%s'", |
| 1498 |
type->tp_name, Py_TYPE(dict)->tp_name); |
| 1499 |
return NULL; |
| 1500 |
} |
| 1501 |
dv = PyObject_GC_New(_PyDictViewObject, type); |
| 1502 |
if (dv == NULL) |
| 1503 |
return NULL; |
| 1504 |
Py_INCREF(dict); |
| 1505 |
dv->dv_dict = (PyDictObject *)dict; |
| 1506 |
PyObject_GC_Track(dv); |
| 1507 |
return (PyObject *)dv; |
| 1508 |
} |
| 1509 |
|
| 1510 |
static PyObject * |
| 1511 |
dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) { |
| 1512 |
assert(view != NULL); |
| 1513 |
assert(PyAnyDictKeys_Check(view) |
| 1514 |
|| PyAnyDictValues_Check(view) |
| 1515 |
|| PyAnyDictItems_Check(view)); |
| 1516 |
PyObject *mapping = (PyObject *)((_PyDictViewObject *)view)->dv_dict; |
| 1517 |
return PyDictProxy_New(mapping); |
| 1518 |
} |
| 1519 |
|
| 1520 |
static PyGetSetDef dictview_getset[] = { |
| 1521 |
{"mapping", dictview_mapping, (setter)NULL, |
| 1522 |
"dictionary that this view refers to", NULL}, |
| 1523 |
{0} |
| 1524 |
}; |
| 1525 |
|
| 1526 |
/* TODO(guido): The views objects are not complete: |
| 1527 |
|
| 1528 |
* support more set operations |
| 1529 |
* support arbitrary mappings? |
| 1530 |
- either these should be static or exported in dictobject.h |
| 1531 |
- if public then they should probably be in builtins |
| 1532 |
*/ |
| 1533 |
|
| 1534 |
/* Return 1 if self is a subset of other, iterating over self; |
| 1535 |
0 if not; -1 if an error occurred. */ |
| 1536 |
static int |
| 1537 |
all_contained_in(PyObject *self, PyObject *other) |
| 1538 |
{ |
| 1539 |
PyObject *iter = PyObject_GetIter(self); |
| 1540 |
int ok = 1; |
| 1541 |
|
| 1542 |
if (iter == NULL) |
| 1543 |
return -1; |
| 1544 |
for (;;) { |
| 1545 |
PyObject *next = PyIter_Next(iter); |
| 1546 |
if (next == NULL) { |
| 1547 |
if (PyErr_Occurred()) |
| 1548 |
ok = -1; |
| 1549 |
break; |
| 1550 |
} |
| 1551 |
ok = PySequence_Contains(other, next); |
| 1552 |
Py_DECREF(next); |
| 1553 |
if (ok <= 0) |
| 1554 |
break; |
| 1555 |
} |
| 1556 |
Py_DECREF(iter); |
| 1557 |
return ok; |
| 1558 |
} |
| 1559 |
|
| 1560 |
static PyObject * |
| 1561 |
dictview_richcompare(PyObject *self, PyObject *other, int op) |
| 1562 |
{ |
| 1563 |
Py_ssize_t len_self, len_other; |
| 1564 |
int ok; |
| 1565 |
PyObject *result; |
| 1566 |
|
| 1567 |
assert(self != NULL); |
| 1568 |
assert(PyAnyDictViewSet_Check(self)); |
| 1569 |
assert(other != NULL); |
| 1570 |
|
| 1571 |
if (!PyAnySet_Check(other) && !PyAnyDictViewSet_Check(other)) |
| 1572 |
Py_RETURN_NOTIMPLEMENTED; |
| 1573 |
|
| 1574 |
len_self = PyObject_Size(self); |
| 1575 |
if (len_self < 0) |
| 1576 |
return NULL; |
| 1577 |
len_other = PyObject_Size(other); |
| 1578 |
if (len_other < 0) |
| 1579 |
return NULL; |
| 1580 |
|
| 1581 |
ok = 0; |
| 1582 |
switch(op) { |
| 1583 |
|
| 1584 |
case Py_NE: |
| 1585 |
case Py_EQ: |
| 1586 |
if (len_self == len_other) |
| 1587 |
ok = all_contained_in(self, other); |
| 1588 |
if (op == Py_NE && ok >= 0) |
| 1589 |
ok = !ok; |
| 1590 |
break; |
| 1591 |
|
| 1592 |
case Py_LT: |
| 1593 |
if (len_self < len_other) |
| 1594 |
ok = all_contained_in(self, other); |
| 1595 |
break; |
| 1596 |
|
| 1597 |
case Py_LE: |
| 1598 |
if (len_self <= len_other) |
| 1599 |
ok = all_contained_in(self, other); |
| 1600 |
break; |
| 1601 |
|
| 1602 |
case Py_GT: |
| 1603 |
if (len_self > len_other) |
| 1604 |
ok = all_contained_in(other, self); |
| 1605 |
break; |
| 1606 |
|
| 1607 |
case Py_GE: |
| 1608 |
if (len_self >= len_other) |
| 1609 |
ok = all_contained_in(other, self); |
| 1610 |
break; |
| 1611 |
|
| 1612 |
} |
| 1613 |
if (ok < 0) |
| 1614 |
return NULL; |
| 1615 |
result = ok ? Py_True : Py_False; |
| 1616 |
Py_INCREF(result); |
| 1617 |
return result; |
| 1618 |
} |
| 1619 |
|
| 1620 |
static PyObject * |
| 1621 |
dictview_repr(_PyDictViewObject *dv) |
| 1622 |
{ |
| 1623 |
PyObject *seq; |
| 1624 |
PyObject *result = NULL; |
| 1625 |
Py_ssize_t rc; |
| 1626 |
|
| 1627 |
rc = Py_ReprEnter((PyObject *)dv); |
| 1628 |
if (rc != 0) { |
| 1629 |
return rc > 0 ? PyUnicode_FromString("...") : NULL; |
| 1630 |
} |
| 1631 |
seq = PySequence_List((PyObject *)dv); |
| 1632 |
if (seq == NULL) { |
| 1633 |
goto Done; |
| 1634 |
} |
| 1635 |
result = PyUnicode_FromFormat("%s(%R)", Py_TYPE(dv)->tp_name, seq); |
| 1636 |
Py_DECREF(seq); |
| 1637 |
|
| 1638 |
Done: |
| 1639 |
Py_ReprLeave((PyObject *)dv); |
| 1640 |
return result; |
| 1641 |
} |
| 1642 |
|
| 1643 |
/*** dict_keys ***/ |
| 1644 |
|
| 1645 |
static int |
| 1646 |
dictkeys_contains(_PyDictViewObject *dv, PyObject *obj) |
| 1647 |
{ |
| 1648 |
if (dv->dv_dict == NULL) |
| 1649 |
return 0; |
| 1650 |
return PyDict_Contains((PyObject *)dv->dv_dict, obj); |
| 1651 |
} |
| 1652 |
|
| 1653 |
static PySequenceMethods dictkeys_as_sequence = { |
| 1654 |
(lenfunc)dictview_len, /* sq_length */ |
| 1655 |
0, /* sq_concat */ |
| 1656 |
0, /* sq_repeat */ |
| 1657 |
0, /* sq_item */ |
| 1658 |
0, /* sq_slice */ |
| 1659 |
0, /* sq_ass_item */ |
| 1660 |
0, /* sq_ass_slice */ |
| 1661 |
(objobjproc)dictkeys_contains, /* sq_contains */ |
| 1662 |
}; |
| 1663 |
|
| 1664 |
// Create an set object from dictviews object. |
| 1665 |
// Returns a new reference. |
| 1666 |
// This utility function is used by set operations. |
| 1667 |
static PyObject* |
| 1668 |
dictviews_to_set(PyObject *self) |
| 1669 |
{ |
| 1670 |
PyObject *left = self; |
| 1671 |
if (PyAnyDictKeys_Check(self)) { |
| 1672 |
// PySet_New() has fast path for the dict object. |
| 1673 |
PyObject *dict = (PyObject *)((_PyDictViewObject *)self)->dv_dict; |
| 1674 |
if (PyAnyDict_CheckExact(dict)) { |
| 1675 |
left = dict; |
| 1676 |
} |
| 1677 |
} |
| 1678 |
return PySet_New(left); |
| 1679 |
} |
| 1680 |
|
| 1681 |
static PyObject* |
| 1682 |
dictviews_sub(PyObject* self, PyObject *other) |
| 1683 |
{ |
| 1684 |
PyObject *result = dictviews_to_set(self); |
| 1685 |
if (result == NULL) { |
| 1686 |
return NULL; |
| 1687 |
} |
| 1688 |
|
| 1689 |
_Py_IDENTIFIER(difference_update); |
| 1690 |
PyObject *tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_difference_update, other, NULL); |
| 1691 |
if (tmp == NULL) { |
| 1692 |
Py_DECREF(result); |
| 1693 |
return NULL; |
| 1694 |
} |
| 1695 |
|
| 1696 |
Py_DECREF(tmp); |
| 1697 |
return result; |
| 1698 |
} |
| 1699 |
|
| 1700 |
static int |
| 1701 |
dictitems_contains(_PyDictViewObject *dv, PyObject *obj); |
| 1702 |
|
| 1703 |
static PyObject* |
| 1704 |
_d_PyDictView_Intersect(PyObject* self, PyObject *other) |
| 1705 |
{ |
| 1706 |
PyObject *result; |
| 1707 |
PyObject *it; |
| 1708 |
PyObject *key; |
| 1709 |
Py_ssize_t len_self; |
| 1710 |
int rv; |
| 1711 |
int (*dict_contains)(_PyDictViewObject *, PyObject *); |
| 1712 |
|
| 1713 |
/* Python interpreter swaps parameters when dict view |
| 1714 |
is on right side of & */ |
| 1715 |
if (!PyAnyDictViewSet_Check(self)) { |
| 1716 |
PyObject *tmp = other; |
| 1717 |
other = self; |
| 1718 |
self = tmp; |
| 1719 |
} |
| 1720 |
|
| 1721 |
len_self = dictview_len((_PyDictViewObject *)self); |
| 1722 |
|
| 1723 |
/* if other is a set and self is smaller than other, |
| 1724 |
reuse set intersection logic */ |
| 1725 |
if (PySet_CheckExact(other) && len_self <= PyObject_Size(other)) { |
| 1726 |
_Py_IDENTIFIER(intersection); |
| 1727 |
return _PyObject_CallMethodIdObjArgs(other, &PyId_intersection, self, NULL); |
| 1728 |
} |
| 1729 |
|
| 1730 |
/* if other is another dict view, and it is bigger than self, |
| 1731 |
swap them */ |
| 1732 |
if (PyAnyDictViewSet_Check(other)) { |
| 1733 |
Py_ssize_t len_other = dictview_len((_PyDictViewObject *)other); |
| 1734 |
if (len_other > len_self) { |
| 1735 |
PyObject *tmp = other; |
| 1736 |
other = self; |
| 1737 |
self = tmp; |
| 1738 |
} |
| 1739 |
} |
| 1740 |
|
| 1741 |
/* at this point, two things should be true |
| 1742 |
1. self is a dictview |
| 1743 |
2. if other is a dictview then it is smaller than self */ |
| 1744 |
result = PySet_New(NULL); |
| 1745 |
if (result == NULL) |
| 1746 |
return NULL; |
| 1747 |
|
| 1748 |
it = PyObject_GetIter(other); |
| 1749 |
if (it == NULL) { |
| 1750 |
Py_DECREF(result); |
| 1751 |
return NULL; |
| 1752 |
} |
| 1753 |
|
| 1754 |
if (PyAnyDictKeys_Check(self)) { |
| 1755 |
dict_contains = dictkeys_contains; |
| 1756 |
} |
| 1757 |
/* else PyDictItems_Check(self) */ |
| 1758 |
else { |
| 1759 |
dict_contains = dictitems_contains; |
| 1760 |
} |
| 1761 |
|
| 1762 |
while ((key = PyIter_Next(it)) != NULL) { |
| 1763 |
rv = dict_contains((_PyDictViewObject *)self, key); |
| 1764 |
if (rv < 0) { |
| 1765 |
goto error; |
| 1766 |
} |
| 1767 |
if (rv) { |
| 1768 |
if (PySet_Add(result, key)) { |
| 1769 |
goto error; |
| 1770 |
} |
| 1771 |
} |
| 1772 |
Py_DECREF(key); |
| 1773 |
} |
| 1774 |
Py_DECREF(it); |
| 1775 |
if (PyErr_Occurred()) { |
| 1776 |
Py_DECREF(result); |
| 1777 |
return NULL; |
| 1778 |
} |
| 1779 |
return result; |
| 1780 |
|
| 1781 |
error: |
| 1782 |
Py_DECREF(it); |
| 1783 |
Py_DECREF(result); |
| 1784 |
Py_DECREF(key); |
| 1785 |
return NULL; |
| 1786 |
} |
| 1787 |
|
| 1788 |
static PyObject* |
| 1789 |
dictviews_or(PyObject* self, PyObject *other) |
| 1790 |
{ |
| 1791 |
PyObject *result = dictviews_to_set(self); |
| 1792 |
if (result == NULL) { |
| 1793 |
return NULL; |
| 1794 |
} |
| 1795 |
|
| 1796 |
if (_PySet_Update(result, other) < 0) { |
| 1797 |
Py_DECREF(result); |
| 1798 |
return NULL; |
| 1799 |
} |
| 1800 |
return result; |
| 1801 |
} |
| 1802 |
|
| 1803 |
static PyObject* |
| 1804 |
dictitems_xor(PyObject *self, PyObject *other) |
| 1805 |
{ |
| 1806 |
assert(PyAnyDictItems_Check(self)); |
| 1807 |
assert(PyAnyDictItems_Check(other)); |
| 1808 |
PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict; |
| 1809 |
PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict; |
| 1810 |
|
| 1811 |
PyObject *temp_dict; |
| 1812 |
|
| 1813 |
if (PyDict_CheckExact(d1)) { |
| 1814 |
temp_dict = PyDict_Copy(d1); |
| 1815 |
} |
| 1816 |
else { |
| 1817 |
PyObject* args = PyTuple_New(1); |
| 1818 |
|
| 1819 |
if (args == NULL) { |
| 1820 |
return NULL; |
| 1821 |
} |
| 1822 |
|
| 1823 |
Py_INCREF(d1); |
| 1824 |
PyTuple_SET_ITEM(args, 0, d1); |
| 1825 |
|
| 1826 |
temp_dict = PyObject_Call((PyObject *) &PyDict_Type, args, NULL); |
| 1827 |
Py_DECREF(args); |
| 1828 |
} |
| 1829 |
if (temp_dict == NULL) { |
| 1830 |
return NULL; |
| 1831 |
} |
| 1832 |
PyObject *result_set = PySet_New(NULL); |
| 1833 |
if (result_set == NULL) { |
| 1834 |
Py_CLEAR(temp_dict); |
| 1835 |
return NULL; |
| 1836 |
} |
| 1837 |
|
| 1838 |
PyObject *key = NULL, *val1 = NULL, *val2 = NULL; |
| 1839 |
Py_ssize_t pos = 0; |
| 1840 |
Py_hash_t hash; |
| 1841 |
|
| 1842 |
while (_d_PyDict_Next(d2, &pos, &key, &val2, &hash)) { |
| 1843 |
Py_INCREF(key); |
| 1844 |
Py_INCREF(val2); |
| 1845 |
val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash); |
| 1846 |
|
| 1847 |
int to_delete; |
| 1848 |
if (val1 == NULL) { |
| 1849 |
if (PyErr_Occurred()) { |
| 1850 |
goto error; |
| 1851 |
} |
| 1852 |
to_delete = 0; |
| 1853 |
} |
| 1854 |
else { |
| 1855 |
Py_INCREF(val1); |
| 1856 |
to_delete = PyObject_RichCompareBool(val1, val2, Py_EQ); |
| 1857 |
if (to_delete < 0) { |
| 1858 |
goto error; |
| 1859 |
} |
| 1860 |
} |
| 1861 |
|
| 1862 |
if (to_delete) { |
| 1863 |
if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) { |
| 1864 |
goto error; |
| 1865 |
} |
| 1866 |
} |
| 1867 |
else { |
| 1868 |
PyObject *pair = PyTuple_Pack(2, key, val2); |
| 1869 |
if (pair == NULL) { |
| 1870 |
goto error; |
| 1871 |
} |
| 1872 |
if (PySet_Add(result_set, pair) < 0) { |
| 1873 |
Py_DECREF(pair); |
| 1874 |
goto error; |
| 1875 |
} |
| 1876 |
Py_DECREF(pair); |
| 1877 |
} |
| 1878 |
Py_DECREF(key); |
| 1879 |
Py_XDECREF(val1); |
| 1880 |
Py_DECREF(val2); |
| 1881 |
} |
| 1882 |
key = val1 = val2 = NULL; |
| 1883 |
|
| 1884 |
_Py_IDENTIFIER(items); |
| 1885 |
PyObject *remaining_pairs = _PyObject_CallMethodIdObjArgs(temp_dict, |
| 1886 |
&PyId_items, NULL); |
| 1887 |
if (remaining_pairs == NULL) { |
| 1888 |
goto error; |
| 1889 |
} |
| 1890 |
if (_PySet_Update(result_set, remaining_pairs) < 0) { |
| 1891 |
Py_DECREF(remaining_pairs); |
| 1892 |
goto error; |
| 1893 |
} |
| 1894 |
Py_DECREF(temp_dict); |
| 1895 |
Py_DECREF(remaining_pairs); |
| 1896 |
return result_set; |
| 1897 |
|
| 1898 |
error: |
| 1899 |
Py_XDECREF(temp_dict); |
| 1900 |
Py_XDECREF(result_set); |
| 1901 |
Py_XDECREF(key); |
| 1902 |
Py_XDECREF(val1); |
| 1903 |
Py_XDECREF(val2); |
| 1904 |
return NULL; |
| 1905 |
} |
| 1906 |
|
| 1907 |
static PyObject* |
| 1908 |
dictviews_xor(PyObject* self, PyObject *other) |
| 1909 |
{ |
| 1910 |
if (PyAnyDictItems_Check(self) && PyAnyDictItems_Check(other)) { |
| 1911 |
return dictitems_xor(self, other); |
| 1912 |
} |
| 1913 |
PyObject *result = dictviews_to_set(self); |
| 1914 |
if (result == NULL) { |
| 1915 |
return NULL; |
| 1916 |
} |
| 1917 |
|
| 1918 |
_Py_IDENTIFIER(symmetric_difference_update); |
| 1919 |
PyObject *tmp = _PyObject_CallMethodIdObjArgs(result, &PyId_symmetric_difference_update, other, NULL); |
| 1920 |
if (tmp == NULL) { |
| 1921 |
Py_DECREF(result); |
| 1922 |
return NULL; |
| 1923 |
} |
| 1924 |
|
| 1925 |
Py_DECREF(tmp); |
| 1926 |
return result; |
| 1927 |
} |
| 1928 |
|
| 1929 |
static PyNumberMethods dictviews_as_number = { |
| 1930 |
0, /*nb_add*/ |
| 1931 |
(binaryfunc)dictviews_sub, /*nb_subtract*/ |
| 1932 |
0, /*nb_multiply*/ |
| 1933 |
0, /*nb_remainder*/ |
| 1934 |
0, /*nb_divmod*/ |
| 1935 |
0, /*nb_power*/ |
| 1936 |
0, /*nb_negative*/ |
| 1937 |
0, /*nb_positive*/ |
| 1938 |
0, /*nb_absolute*/ |
| 1939 |
0, /*nb_bool*/ |
| 1940 |
0, /*nb_invert*/ |
| 1941 |
0, /*nb_lshift*/ |
| 1942 |
0, /*nb_rshift*/ |
| 1943 |
(binaryfunc)_d_PyDictView_Intersect,/*nb_and*/ |
| 1944 |
(binaryfunc)dictviews_xor, /*nb_xor*/ |
| 1945 |
(binaryfunc)dictviews_or, /*nb_or*/ |
| 1946 |
}; |
| 1947 |
|
| 1948 |
static PyObject* |
| 1949 |
dictviews_isdisjoint(PyObject *self, PyObject *other) |
| 1950 |
{ |
| 1951 |
PyObject *it; |
| 1952 |
PyObject *item = NULL; |
| 1953 |
|
| 1954 |
if (self == other) { |
| 1955 |
if (dictview_len((_PyDictViewObject *)self) == 0) |
| 1956 |
Py_RETURN_TRUE; |
| 1957 |
else |
| 1958 |
Py_RETURN_FALSE; |
| 1959 |
} |
| 1960 |
|
| 1961 |
/* Iterate over the shorter object (only if other is a set, |
| 1962 |
* because PySequence_Contains may be expensive otherwise): */ |
| 1963 |
if (PyAnySet_Check(other) || PyAnyDictViewSet_Check(other)) { |
| 1964 |
Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self); |
| 1965 |
Py_ssize_t len_other = PyObject_Size(other); |
| 1966 |
if (len_other == -1) |
| 1967 |
return NULL; |
| 1968 |
|
| 1969 |
if ((len_other > len_self)) { |
| 1970 |
PyObject *tmp = other; |
| 1971 |
other = self; |
| 1972 |
self = tmp; |
| 1973 |
} |
| 1974 |
} |
| 1975 |
|
| 1976 |
it = PyObject_GetIter(other); |
| 1977 |
if (it == NULL) |
| 1978 |
return NULL; |
| 1979 |
|
| 1980 |
while ((item = PyIter_Next(it)) != NULL) { |
| 1981 |
int contains = PySequence_Contains(self, item); |
| 1982 |
Py_DECREF(item); |
| 1983 |
if (contains == -1) { |
| 1984 |
Py_DECREF(it); |
| 1985 |
return NULL; |
| 1986 |
} |
| 1987 |
|
| 1988 |
if (contains) { |
| 1989 |
Py_DECREF(it); |
| 1990 |
Py_RETURN_FALSE; |
| 1991 |
} |
| 1992 |
} |
| 1993 |
Py_DECREF(it); |
| 1994 |
if (PyErr_Occurred()) |
| 1995 |
return NULL; /* PyIter_Next raised an exception. */ |
| 1996 |
Py_RETURN_TRUE; |
| 1997 |
} |
| 1998 |
|
| 1999 |
PyDoc_STRVAR(isdisjoint_doc, |
| 2000 |
"Return True if the view and the given iterable have a null intersection."); |
| 2001 |
|
| 2002 |
static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); |
| 2003 |
|
| 2004 |
PyDoc_STRVAR(reversed_keys_doc, |
| 2005 |
"Return a reverse iterator over the dict keys."); |
| 2006 |
|
| 2007 |
static PyMethodDef dictkeys_methods[] = { |
| 2008 |
{"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O, |
| 2009 |
isdisjoint_doc}, |
| 2010 |
{"__reversed__", (PyCFunction)(void(*)(void))dictkeys_reversed, METH_NOARGS, |
| 2011 |
reversed_keys_doc}, |
| 2012 |
{NULL, NULL} /* sentinel */ |
| 2013 |
}; |
| 2014 |
|
| 2015 |
static PyObject * |
| 2016 |
dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
| 2017 |
{ |
| 2018 |
if (dv->dv_dict == NULL) { |
| 2019 |
Py_RETURN_NONE; |
| 2020 |
} |
| 2021 |
return dictiter_new(dv->dv_dict, &PyDictRevIterKey_Type); |
| 2022 |
} |
| 2023 |
|
| 2024 |
/*** dict_items ***/ |
| 2025 |
|
| 2026 |
/* Variant of PyDict_GetItem() that doesn't suppress exceptions. |
| 2027 |
This returns NULL *with* an exception set if an exception occurred. |
| 2028 |
It returns NULL *without* an exception set if the key wasn't present. |
| 2029 |
*/ |
| 2030 |
static PyObject * |
| 2031 |
d_PyDict_GetItemWithError(PyObject *op, PyObject *key) |
| 2032 |
{ |
| 2033 |
Py_ssize_t ix; |
| 2034 |
Py_hash_t hash; |
| 2035 |
PyDictObject*mp = (PyDictObject *)op; |
| 2036 |
PyObject **value_addr; |
| 2037 |
|
| 2038 |
if (!PyAnyDict_Check(op)) { |
| 2039 |
PyErr_BadInternalCall(); |
| 2040 |
return NULL; |
| 2041 |
} |
| 2042 |
if (!PyUnicode_CheckExact(key) || |
| 2043 |
(hash = ((PyASCIIObject *) key)->hash) == -1) |
| 2044 |
{ |
| 2045 |
hash = PyObject_Hash(key); |
| 2046 |
if (hash == -1) { |
| 2047 |
return NULL; |
| 2048 |
} |
| 2049 |
} |
| 2050 |
|
| 2051 |
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, NULL); |
| 2052 |
if (ix < 0) |
| 2053 |
return NULL; |
| 2054 |
return *value_addr; |
| 2055 |
} |
| 2056 |
|
| 2057 |
static int |
| 2058 |
dictitems_contains(_PyDictViewObject *dv, PyObject *obj) |
| 2059 |
{ |
| 2060 |
int result; |
| 2061 |
PyObject *key, *value, *found; |
| 2062 |
if (dv->dv_dict == NULL) |
| 2063 |
return 0; |
| 2064 |
if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 2) |
| 2065 |
return 0; |
| 2066 |
key = PyTuple_GET_ITEM(obj, 0); |
| 2067 |
value = PyTuple_GET_ITEM(obj, 1); |
| 2068 |
found = d_PyDict_GetItemWithError((PyObject *)dv->dv_dict, key); |
| 2069 |
if (found == NULL) { |
| 2070 |
if (PyErr_Occurred()) |
| 2071 |
return -1; |
| 2072 |
return 0; |
| 2073 |
} |
| 2074 |
Py_INCREF(found); |
| 2075 |
result = PyObject_RichCompareBool(found, value, Py_EQ); |
| 2076 |
Py_DECREF(found); |
| 2077 |
return result; |
| 2078 |
} |
| 2079 |
|
| 2080 |
static PySequenceMethods dictitems_as_sequence = { |
| 2081 |
(lenfunc)dictview_len, /* sq_length */ |
| 2082 |
0, /* sq_concat */ |
| 2083 |
0, /* sq_repeat */ |
| 2084 |
0, /* sq_item */ |
| 2085 |
0, /* sq_slice */ |
| 2086 |
0, /* sq_ass_item */ |
| 2087 |
0, /* sq_ass_slice */ |
| 2088 |
(objobjproc)dictitems_contains, /* sq_contains */ |
| 2089 |
}; |
| 2090 |
|
| 2091 |
static PyObject* dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); |
| 2092 |
|
| 2093 |
PyDoc_STRVAR(reversed_items_doc, |
| 2094 |
"Return a reverse iterator over the dict items."); |
| 2095 |
|
| 2096 |
static PyMethodDef dictitems_methods[] = { |
| 2097 |
{"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O, |
| 2098 |
isdisjoint_doc}, |
| 2099 |
{"__reversed__", (PyCFunction)dictitems_reversed, METH_NOARGS, |
| 2100 |
reversed_items_doc}, |
| 2101 |
{NULL, NULL} /* sentinel */ |
| 2102 |
}; |
| 2103 |
|
| 2104 |
static PyObject * |
| 2105 |
dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
| 2106 |
{ |
| 2107 |
if (dv->dv_dict == NULL) { |
| 2108 |
Py_RETURN_NONE; |
| 2109 |
} |
| 2110 |
return dictiter_new(dv->dv_dict, &PyDictRevIterItem_Type); |
| 2111 |
} |
| 2112 |
|
| 2113 |
/*** dict_values ***/ |
| 2114 |
|
| 2115 |
static PySequenceMethods dictvalues_as_sequence = { |
| 2116 |
(lenfunc)dictview_len, /* sq_length */ |
| 2117 |
0, /* sq_concat */ |
| 2118 |
0, /* sq_repeat */ |
| 2119 |
0, /* sq_item */ |
| 2120 |
0, /* sq_slice */ |
| 2121 |
0, /* sq_ass_item */ |
| 2122 |
0, /* sq_ass_slice */ |
| 2123 |
(objobjproc)0, /* sq_contains */ |
| 2124 |
}; |
| 2125 |
|
| 2126 |
static PyObject* dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); |
| 2127 |
|
| 2128 |
PyDoc_STRVAR(reversed_values_doc, |
| 2129 |
"Return a reverse iterator over the dict values."); |
| 2130 |
|
| 2131 |
static PyMethodDef dictvalues_methods[] = { |
| 2132 |
{"__reversed__", (PyCFunction)dictvalues_reversed, METH_NOARGS, |
| 2133 |
reversed_values_doc}, |
| 2134 |
{NULL, NULL} /* sentinel */ |
| 2135 |
}; |
| 2136 |
|
| 2137 |
static PyObject * |
| 2138 |
dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) |
| 2139 |
{ |
| 2140 |
if (dv->dv_dict == NULL) { |
| 2141 |
Py_RETURN_NONE; |
| 2142 |
} |
| 2143 |
return dictiter_new(dv->dv_dict, &PyDictRevIterValue_Type); |
| 2144 |
} |