Lines Matching refs:mp
235 static int dictresize(PyDictObject *mp, uint8_t log_newsize, int unicode);
477 get_index_from_order(PyDictObject *mp, Py_ssize_t i)
479 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
480 assert(i < (((char *)mp->ma_values)[-2]));
481 return ((char *)mp->ma_values)[-3-i];
509 PyDictObject *mp = (PyDictObject *)op;
511 PyDictKeysObject *keys = mp->ma_keys;
512 int splitted = _PyDict_HasSplitTable(mp);
515 CHECK(0 <= mp->ma_used && mp->ma_used <= usable);
527 CHECK(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
576 CHECK(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
579 for (Py_ssize_t i=0; i < mp->ma_used; i++) {
580 int index = get_index_from_order(mp, i);
583 CHECK(mp->ma_values->values[index] != NULL);
719 PyDictObject *mp;
728 mp = state->free_list[--state->numfree];
729 assert (mp != NULL);
730 assert (Py_IS_TYPE(mp, &PyDict_Type));
732 _Py_NewReference((PyObject *)mp);
737 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
738 if (mp == NULL) {
746 mp->ma_keys = keys;
747 mp->ma_values = values;
748 mp->ma_used = used;
749 mp->ma_version_tag = DICT_NEXT_VERSION();
750 ASSERT_CONSISTENT(mp);
751 return (PyObject *)mp;
868 unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
892 if (dk == mp->ma_keys && ep->me_key == startkey) {
958 dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
981 if (dk == mp->ma_keys && ep->me_key == startkey) {
1041 _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
1048 dk = mp->ma_keys;
1056 ix = unicodekeys_lookup_generic(mp, dk, key, hash);
1064 *value_addr = mp->ma_values->values[ix];
1075 ix = dictkeys_generic_lookup(mp, dk, key, hash);
1105 #define MAINTAIN_TRACKING(mp, key, value) \
1107 if (!_PyObject_GC_IS_TRACKED(mp)) { \
1110 _PyObject_GC_TRACK(mp); \
1118 PyDictObject *mp;
1125 mp = (PyDictObject *) op;
1126 numentries = mp->ma_keys->dk_nentries;
1127 if (_PyDict_HasSplitTable(mp)) {
1129 if ((value = mp->ma_values->values[i]) == NULL)
1137 if (DK_IS_UNICODE(mp->ma_keys)) {
1138 PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(mp->ma_keys);
1147 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
1181 insertion_resize(PyDictObject *mp, int unicode)
1183 return dictresize(mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
1226 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1230 if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) {
1231 if (insertion_resize(mp, 0) < 0)
1233 assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
1236 Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
1240 MAINTAIN_TRACKING(mp, key, value);
1244 mp->ma_keys->dk_version = 0;
1246 if (mp->ma_keys->dk_usable <= 0) {
1248 if (insertion_resize(mp, 1) < 0)
1252 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
1253 dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
1255 if (DK_IS_UNICODE(mp->ma_keys)) {
1257 ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1259 if (mp->ma_values) {
1260 Py_ssize_t index = mp->ma_keys->dk_nentries;
1261 _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
1262 assert (mp->ma_values->values[index] == NULL);
1263 mp->ma_values->values[index] = value;
1271 ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1276 mp->ma_used++;
1277 mp->ma_version_tag = DICT_NEXT_VERSION();
1278 mp->ma_keys->dk_usable--;
1279 mp->ma_keys->dk_nentries++;
1280 assert(mp->ma_keys->dk_usable >= 0);
1281 ASSERT_CONSISTENT(mp);
1286 if (_PyDict_HasSplitTable(mp)) {
1287 mp->ma_values->values[ix] = value;
1289 _PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
1290 mp->ma_used++;
1295 if (DK_IS_UNICODE(mp->ma_keys)) {
1296 DK_UNICODE_ENTRIES(mp->ma_keys)[ix].me_value = value;
1299 DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1302 mp->ma_version_tag = DICT_NEXT_VERSION();
1305 ASSERT_CONSISTENT(mp);
1318 insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
1321 assert(mp->ma_keys == Py_EMPTY_KEYS);
1331 mp->ma_keys = newkeys;
1332 mp->ma_values = NULL;
1334 MAINTAIN_TRACKING(mp, key, value);
1337 dictkeys_set_index(mp->ma_keys, hashpos, 0);
1339 PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys);
1344 PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys);
1349 mp->ma_used++;
1350 mp->ma_version_tag = DICT_NEXT_VERSION();
1351 mp->ma_keys->dk_usable--;
1352 mp->ma_keys->dk_nentries++;
1405 dictresize(PyDictObject *mp, uint8_t log2_newsize, int unicode)
1416 oldkeys = mp->ma_keys;
1417 oldvalues = mp->ma_values;
1423 /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
1429 mp->ma_keys = new_keys_object(log2_newsize, unicode);
1430 if (mp->ma_keys == NULL) {
1431 mp->ma_keys = oldkeys;
1435 assert(mp->ma_keys->dk_usable >= mp->ma_used);
1437 Py_ssize_t numentries = mp->ma_used;
1444 if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) {
1446 PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1449 int index = get_index_from_order(mp, i);
1457 build_indices_generic(mp->ma_keys, newentries, numentries);
1460 PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
1463 int index = get_index_from_order(mp, i);
1470 build_indices_unicode(mp->ma_keys, newentries, numentries);
1473 mp->ma_values = NULL;
1479 assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
1481 PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1493 build_indices_generic(mp->ma_keys, newentries, numentries);
1498 PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
1499 if (oldkeys->dk_nentries == numentries && mp->ma_keys->dk_kind == DICT_KEYS_UNICODE) {
1510 build_indices_unicode(mp->ma_keys, newentries, numentries);
1513 PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
1523 build_indices_generic(mp->ma_keys, newentries, numentries);
1560 mp->ma_keys->dk_usable -= numentries;
1561 mp->ma_keys->dk_nentries = numentries;
1562 ASSERT_CONSISTENT(mp);
1654 PyDictObject *mp = (PyDictObject *)op;
1678 ix = _Py_dict_lookup(mp, key, hash, &value);
1689 _PyDict_GetItemHint(PyDictObject *mp, PyObject *key,
1693 assert(PyDict_CheckExact((PyObject*)mp));
1696 if (hint >= 0 && hint < mp->ma_keys->dk_nentries) {
1699 if (DK_IS_UNICODE(mp->ma_keys)) {
1700 PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys) + (size_t)hint;
1702 if (mp->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
1703 assert(mp->ma_values != NULL);
1704 res = mp->ma_values->values[(size_t)hint];
1716 PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys) + (size_t)hint;
1718 if (mp->ma_keys->dk_kind == DICT_KEYS_SPLIT) {
1719 assert(mp->ma_values != NULL);
1720 res = mp->ma_values->values[(size_t)hint];
1741 return _Py_dict_lookup(mp, key, hash, value);
1752 PyDictObject *mp = (PyDictObject *)op;
1760 ix = _Py_dict_lookup(mp, key, hash, &value);
1774 PyDictObject*mp = (PyDictObject *)op;
1789 ix = _Py_dict_lookup(mp, key, hash, &value);
1868 _PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
1872 assert(PyDict_Check(mp));
1882 if (mp->ma_keys == Py_EMPTY_KEYS) {
1883 return insert_to_emptydict(mp, key, hash, value);
1886 return insertdict(mp, key, hash, value);
1913 PyDictObject *mp;
1922 mp = (PyDictObject *)op;
1926 if (mp->ma_keys == Py_EMPTY_KEYS) {
1927 return insert_to_emptydict(mp, key, hash, value);
1930 return insertdict(mp, key, hash, value);
1950 delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
1955 Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
1958 mp->ma_used--;
1959 mp->ma_version_tag = DICT_NEXT_VERSION();
1960 if (mp->ma_values) {
1961 assert(old_value == mp->ma_values->values[ix]);
1962 mp->ma_values->values[ix] = NULL;
1965 delete_index_from_values(mp->ma_values, ix);
1966 ASSERT_CONSISTENT(mp);
1969 mp->ma_keys->dk_version = 0;
1970 dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1971 if (DK_IS_UNICODE(mp->ma_keys)) {
1972 PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
1978 PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
1988 ASSERT_CONSISTENT(mp);
2010 PyDictObject *mp;
2019 mp = (PyDictObject *)op;
2020 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2028 return delitem_common(mp, hash, ix, old_value);
2040 PyDictObject *mp;
2053 mp = (PyDictObject *)op;
2054 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2066 hashpos = lookdict_index(mp->ma_keys, hash, ix);
2070 return delitem_common(mp, hashpos, ix, old_value);
2079 PyDictObject *mp;
2086 mp = ((PyDictObject *)op);
2087 oldkeys = mp->ma_keys;
2088 oldvalues = mp->ma_values;
2094 mp->ma_keys = Py_EMPTY_KEYS;
2095 mp->ma_values = NULL;
2096 mp->ma_used = 0;
2097 mp->ma_version_tag = DICT_NEXT_VERSION();
2110 ASSERT_CONSISTENT(mp);
2123 PyDictObject *mp;
2129 mp = (PyDictObject *)op;
2131 if (mp->ma_values) {
2132 assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE);
2133 if (i < 0 || i >= mp->ma_used)
2135 int index = get_index_from_order(mp, i);
2136 value = mp->ma_values->values[index];
2138 key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key;
2143 Py_ssize_t n = mp->ma_keys->dk_nentries;
2146 if (DK_IS_UNICODE(mp->ma_keys)) {
2147 PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(mp->ma_keys)[i];
2159 PyDictKeyEntry *entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
2211 PyDictObject *mp;
2214 mp = (PyDictObject *)dict;
2216 if (mp->ma_used == 0) {
2224 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2237 delitem_common(mp, hash, ix, old_value);
2239 ASSERT_CONSISTENT(mp);
2279 PyDictObject *mp = (PyDictObject *)d;
2286 if (dictresize(mp, estimate_log2_keysize(PyDict_GET_SIZE(iterable)), unicode)) {
2294 if (insertdict(mp, key, hash, value)) {
2302 PyDictObject *mp = (PyDictObject *)d;
2307 if (dictresize(mp, estimate_log2_keysize(PySet_GET_SIZE(iterable)), 0)) {
2315 if (insertdict(mp, key, hash, value)) {
2360 dict_dealloc(PyDictObject *mp)
2362 PyDictValues *values = mp->ma_values;
2363 PyDictKeysObject *keys = mp->ma_keys;
2367 PyObject_GC_UnTrack(mp);
2368 Py_TRASHCAN_BEGIN(mp, dict_dealloc)
2370 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
2386 if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
2387 state->free_list[state->numfree++] = mp;
2393 Py_TYPE(mp)->tp_free((PyObject *)mp);
2400 dict_repr(PyDictObject *mp)
2407 i = Py_ReprEnter((PyObject *)mp);
2412 if (mp->ma_used == 0) {
2413 Py_ReprLeave((PyObject *)mp);
2420 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
2429 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
2470 Py_ReprLeave((PyObject *)mp);
2475 Py_ReprLeave((PyObject *)mp);
2483 dict_length(PyDictObject *mp)
2485 return mp->ma_used;
2489 dict_subscript(PyDictObject *mp, PyObject *key)
2500 ix = _Py_dict_lookup(mp, key, hash, &value);
2504 if (!PyDict_CheckExact(mp)) {
2508 (PyObject *)mp, &_Py_ID(__missing__));
2525 dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
2528 return PyDict_DelItem((PyObject *)mp, v);
2530 return PyDict_SetItem((PyObject *)mp, v, w);
2540 dict_keys(PyDictObject *mp)
2546 n = mp->ma_used;
2550 if (n != mp->ma_used) {
2561 while (_PyDict_Next((PyObject*)mp, &pos, &key, NULL, NULL)) {
2572 dict_values(PyDictObject *mp)
2578 n = mp->ma_used;
2582 if (n != mp->ma_used) {
2593 while (_PyDict_Next((PyObject*)mp, &pos, NULL, &value, NULL)) {
2604 dict_items(PyDictObject *mp)
2615 n = mp->ma_used;
2627 if (n != mp->ma_used) {
2638 while (_PyDict_Next((PyObject*)mp, &pos, &key, &value, NULL)) {
2818 PyDictObject *mp, *other;
2831 mp = (PyDictObject*)a;
2834 if (other == mp || other->ma_used == 0)
2837 if (mp->ma_used == 0) {
2855 dictkeys_decref(mp->ma_keys);
2856 mp->ma_keys = keys;
2857 if (mp->ma_values != NULL) {
2858 free_values(mp->ma_values);
2859 mp->ma_values = NULL;
2862 mp->ma_used = other->ma_used;
2863 mp->ma_version_tag = DICT_NEXT_VERSION();
2864 ASSERT_CONSISTENT(mp);
2866 if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) {
2868 _PyObject_GC_TRACK(mp);
2878 if (USABLE_FRACTION(DK_SIZE(mp->ma_keys)) < other->ma_used) {
2880 if (dictresize(mp, estimate_log2_keysize(mp->ma_used + other->ma_used), unicode)) {
2897 err = insertdict(mp, key, hash, value);
2904 err = insertdict(mp, key, hash, value);
3007 dict_copy(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3009 return PyDict_Copy((PyObject*)mp);
3016 PyDictObject *mp;
3024 mp = (PyDictObject *)o;
3025 if (mp->ma_used == 0) {
3030 if (_PyDict_HasSplitTable(mp)) {
3032 Py_ssize_t size = shared_keys_usable_size(mp->ma_keys);
3043 memcpy(((char *)newvalues)-prefix_size, ((char *)mp->ma_values)-prefix_size, prefix_size-1);
3045 split_copy->ma_keys = mp->ma_keys;
3046 split_copy->ma_used = mp->ma_used;
3048 dictkeys_incref(mp->ma_keys);
3050 PyObject *value = mp->ma_values->values[i];
3054 if (_PyObject_GC_IS_TRACKED(mp))
3059 if (Py_TYPE(mp)->tp_iter == (getiterfunc)dict_iter &&
3060 mp->ma_values == NULL &&
3061 (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3))
3065 (1) type(mp) doesn't override tp_iter; and
3067 (2) 'mp' is not a split-dict; and
3069 (3) if 'mp' is non-compact ('del' operation does not resize dicts),
3077 PyDictKeysObject *keys = clone_combined_dict_keys(mp);
3088 new->ma_used = mp->ma_used;
3090 if (_PyObject_GC_IS_TRACKED(mp)) {
3108 PyDict_Size(PyObject *mp)
3110 if (mp == NULL || !PyDict_Check(mp)) {
3114 return ((PyDictObject *)mp)->ma_used;
3118 PyDict_Keys(PyObject *mp)
3120 if (mp == NULL || !PyDict_Check(mp)) {
3124 return dict_keys((PyDictObject *)mp);
3128 PyDict_Values(PyObject *mp)
3130 if (mp == NULL || !PyDict_Check(mp)) {
3134 return dict_values((PyDictObject *)mp);
3138 PyDict_Items(PyObject *mp)
3140 if (mp == NULL || !PyDict_Check(mp)) {
3144 return dict_items((PyDictObject *)mp);
3246 register PyDictObject *mp = self;
3256 ix = _Py_dict_lookup(mp, key, hash, &value);
3300 PyDictObject *mp = (PyDictObject *)d;
3315 if (mp->ma_keys == Py_EMPTY_KEYS) {
3318 if (insert_to_emptydict(mp, key, hash, defaultobj) < 0) {
3324 if (!PyUnicode_CheckExact(key) && DK_IS_UNICODE(mp->ma_keys)) {
3325 if (insertion_resize(mp, 0) < 0) {
3330 Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
3335 mp->ma_keys->dk_version = 0;
3337 if (mp->ma_keys->dk_usable <= 0) {
3338 if (insertion_resize(mp, 1) < 0) {
3342 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
3343 dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
3344 if (DK_IS_UNICODE(mp->ma_keys)) {
3346 PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
3348 if (_PyDict_HasSplitTable(mp)) {
3349 Py_ssize_t index = (int)mp->ma_keys->dk_nentries;
3351 assert(mp->ma_values->values[index] == NULL);
3352 mp->ma_values->values[index] = value;
3353 _PyDictValues_AddToInsertionOrder(mp->ma_values, index);
3360 PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
3367 MAINTAIN_TRACKING(mp, key, value);
3368 mp->ma_used++;
3369 mp->ma_version_tag = DICT_NEXT_VERSION();
3370 mp->ma_keys->dk_usable--;
3371 mp->ma_keys->dk_nentries++;
3372 assert(mp->ma_keys->dk_usable >= 0);
3376 assert(_PyDict_HasSplitTable(mp));
3377 assert(mp->ma_values->values[ix] == NULL);
3379 MAINTAIN_TRACKING(mp, key, value);
3380 mp->ma_values->values[ix] = value;
3381 _PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
3382 mp->ma_used++;
3383 mp->ma_version_tag = DICT_NEXT_VERSION();
3386 ASSERT_CONSISTENT(mp);
3415 dict_clear(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3417 PyDict_Clear((PyObject *)mp);
3534 PyDictObject *mp = (PyDictObject *)op;
3535 PyDictKeysObject *keys = mp->ma_keys;
3539 if (mp->ma_values != NULL) {
3541 Py_VISIT(mp->ma_values->values[i]);
3573 _PyDict_SizeOf(PyDictObject *mp)
3577 res = _PyObject_SIZE(Py_TYPE(mp));
3578 if (mp->ma_values) {
3579 res += shared_keys_usable_size(mp->ma_keys) * sizeof(PyObject*);
3583 if (mp->ma_keys->dk_refcnt == 1) {
3584 res += _PyDict_KeysSize(mp->ma_keys);
3600 dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
3602 return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
3695 PyDictObject *mp = (PyDictObject *)op;
3703 ix = _Py_dict_lookup(mp, key, hash, &value);
3713 PyDictObject *mp = (PyDictObject *)op;
3717 ix = _Py_dict_lookup(mp, key, hash, &value);