Lines Matching refs:mp
100 where ix == mp->ma_used. Inserting into other index and deleting item cause
226 static Py_ssize_t lookdict(PyDictObject *mp, PyObject *key,
228 static Py_ssize_t lookdict_unicode(PyDictObject *mp, PyObject *key,
231 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
233 static Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key,
236 static int dictresize(PyDictObject *mp, Py_ssize_t minused);
440 _PyDict_CheckConsistency(PyDictObject *mp)
442 PyDictKeysObject *keys = mp->ma_keys;
443 int splitted = _PyDict_HasSplitTable(mp);
450 assert(0 <= mp->ma_used && mp->ma_used <= usable);
495 for (i=0; i < mp->ma_used; i++) {
496 assert(mp->ma_values[i] != NULL);
575 PyDictObject *mp;
578 mp = free_list[--numfree];
579 assert (mp != NULL);
580 assert (Py_TYPE(mp) == &PyDict_Type);
581 _Py_NewReference((PyObject *)mp);
584 mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
585 if (mp == NULL) {
591 mp->ma_keys = keys;
592 mp->ma_values = values;
593 mp->ma_used = 0;
594 mp->ma_version_tag = DICT_NEXT_VERSION();
595 assert(_PyDict_CheckConsistency(mp));
596 return (PyObject *)mp;
727 lookdict(PyDictObject *mp, PyObject *key,
735 dk = mp->ma_keys;
763 if (dk == mp->ma_keys && ep->me_key == startkey) {
783 lookdict_unicode(PyDictObject *mp, PyObject *key,
786 assert(mp->ma_values == NULL);
792 mp->ma_keys->dk_lookup = lookdict;
793 return lookdict(mp, key, hash, value_addr);
796 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
797 size_t mask = DK_MASK(mp->ma_keys);
802 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
826 lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
829 assert(mp->ma_values == NULL);
835 mp->ma_keys->dk_lookup = lookdict;
836 return lookdict(mp, key, hash, value_addr);
839 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
840 size_t mask = DK_MASK(mp->ma_keys);
845 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
871 lookdict_split(PyDictObject *mp, PyObject *key,
874 /* mp must split table */
875 assert(mp->ma_values != NULL);
877 Py_ssize_t ix = lookdict(mp, key, hash, value_addr);
879 *value_addr = mp->ma_values[ix];
884 PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
885 size_t mask = DK_MASK(mp->ma_keys);
890 Py_ssize_t ix = dk_get_index(mp->ma_keys, i);
901 *value_addr = mp->ma_values[ix];
925 #define MAINTAIN_TRACKING(mp, key, value) \
927 if (!_PyObject_GC_IS_TRACKED(mp)) { \
930 _PyObject_GC_TRACK(mp); \
938 PyDictObject *mp;
946 mp = (PyDictObject *) op;
947 ep0 = DK_ENTRIES(mp->ma_keys);
948 numentries = mp->ma_keys->dk_nentries;
949 if (_PyDict_HasSplitTable(mp)) {
951 if ((value = mp->ma_values[i]) == NULL)
992 insertion_resize(PyDictObject *mp)
994 return dictresize(mp, GROWTH_RATE(mp));
1003 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1010 if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
1011 if (insertion_resize(mp) < 0)
1015 Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
1019 assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
1020 MAINTAIN_TRACKING(mp, key, value);
1025 if (_PyDict_HasSplitTable(mp) &&
1026 ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
1027 (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
1028 if (insertion_resize(mp) < 0)
1036 if (mp->ma_keys->dk_usable <= 0) {
1038 if (insertion_resize(mp) < 0)
1041 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
1042 ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
1043 dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
1046 if (mp->ma_values) {
1047 assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
1048 mp->ma_values[mp->ma_keys->dk_nentries] = value;
1053 mp->ma_used++;
1054 mp->ma_version_tag = DICT_NEXT_VERSION();
1055 mp->ma_keys->dk_usable--;
1056 mp->ma_keys->dk_nentries++;
1057 assert(mp->ma_keys->dk_usable >= 0);
1058 assert(_PyDict_CheckConsistency(mp));
1062 if (_PyDict_HasSplitTable(mp)) {
1063 mp->ma_values[ix] = value;
1066 assert(ix == mp->ma_used);
1067 mp->ma_used++;
1072 DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1075 mp->ma_version_tag = DICT_NEXT_VERSION();
1077 assert(_PyDict_CheckConsistency(mp));
1116 dictresize(PyDictObject *mp, Py_ssize_t minsize)
1133 oldkeys = mp->ma_keys;
1135 /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
1141 mp->ma_keys = new_keys_object(newsize);
1142 if (mp->ma_keys == NULL) {
1143 mp->ma_keys = oldkeys;
1147 assert(mp->ma_keys->dk_usable >= mp->ma_used);
1149 mp->ma_keys->dk_lookup = lookdict;
1151 numentries = mp->ma_used;
1153 newentries = DK_ENTRIES(mp->ma_keys);
1154 oldvalues = mp->ma_values;
1171 mp->ma_values = NULL;
1200 build_indices(mp->ma_keys, newentries, numentries);
1201 mp->ma_keys->dk_usable -= numentries;
1202 mp->ma_keys->dk_nentries = numentries;
1213 PyDictObject *mp = (PyDictObject *)op;
1217 if (!_PyDict_HasSplitTable(mp)) {
1220 assert(mp->ma_keys->dk_refcnt == 1);
1221 if (mp->ma_keys->dk_lookup == lookdict) {
1224 else if (mp->ma_keys->dk_lookup == lookdict_unicode) {
1226 if (dictresize(mp, DK_SIZE(mp->ma_keys)))
1229 assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);
1231 ep0 = DK_ENTRIES(mp->ma_keys);
1232 size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
1243 mp->ma_keys->dk_lookup = lookdict_split;
1244 mp->ma_values = values;
1246 DK_INCREF(mp->ma_keys);
1247 return mp->ma_keys;
1294 PyDictObject *mp = (PyDictObject *)op;
1320 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1327 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1344 PyDictObject *mp = (PyDictObject *)op;
1352 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1368 PyDictObject*mp = (PyDictObject *)op;
1384 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
1445 PyDictObject *mp;
1453 mp = (PyDictObject *)op;
1463 return insertdict(mp, key, hash, value);
1470 PyDictObject *mp;
1479 mp = (PyDictObject *)op;
1482 return insertdict(mp, key, hash, value);
1486 delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
1492 Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
1495 mp->ma_used--;
1496 mp->ma_version_tag = DICT_NEXT_VERSION();
1497 ep = &DK_ENTRIES(mp->ma_keys)[ix];
1498 dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1499 ENSURE_ALLOWS_DELETIONS(mp);
1506 assert(_PyDict_CheckConsistency(mp));
1529 PyDictObject *mp;
1538 mp = (PyDictObject *)op;
1539 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1548 if (_PyDict_HasSplitTable(mp)) {
1549 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1552 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1556 return delitem_common(mp, hash, ix, old_value);
1568 PyDictObject *mp;
1581 mp = (PyDictObject *)op;
1582 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1591 if (_PyDict_HasSplitTable(mp)) {
1592 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1595 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1603 hashpos = lookdict_index(mp->ma_keys, hash, ix);
1607 return delitem_common(mp, hashpos, ix, old_value);
1616 PyDictObject *mp;
1623 mp = ((PyDictObject *)op);
1624 oldkeys = mp->ma_keys;
1625 oldvalues = mp->ma_values;
1630 mp->ma_keys = Py_EMPTY_KEYS;
1631 mp->ma_values = empty_values;
1632 mp->ma_used = 0;
1633 mp->ma_version_tag = DICT_NEXT_VERSION();
1646 assert(_PyDict_CheckConsistency(mp));
1659 PyDictObject *mp;
1665 mp = (PyDictObject *)op;
1667 if (mp->ma_values) {
1668 if (i < 0 || i >= mp->ma_used)
1671 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1672 value = mp->ma_values[i];
1676 Py_ssize_t n = mp->ma_keys->dk_nentries;
1679 entry_ptr = &DK_ENTRIES(mp->ma_keys)[i];
1729 PyDictObject *mp;
1732 mp = (PyDictObject *)dict;
1734 if (mp->ma_used == 0) {
1742 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1755 if (_PyDict_HasSplitTable(mp)) {
1756 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
1759 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
1763 hashpos = lookdict_index(mp->ma_keys, hash, ix);
1766 mp->ma_used--;
1767 mp->ma_version_tag = DICT_NEXT_VERSION();
1768 dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
1769 ep = &DK_ENTRIES(mp->ma_keys)[ix];
1770 ENSURE_ALLOWS_DELETIONS(mp);
1776 assert(_PyDict_CheckConsistency(mp));
1817 PyDictObject *mp = (PyDictObject *)d;
1823 if (dictresize(mp, ESTIMATE_SIZE(PyDict_GET_SIZE(iterable)))) {
1829 if (insertdict(mp, key, hash, value)) {
1837 PyDictObject *mp = (PyDictObject *)d;
1842 if (dictresize(mp, ESTIMATE_SIZE(PySet_GET_SIZE(iterable)))) {
1848 if (insertdict(mp, key, hash, value)) {
1893 dict_dealloc(PyDictObject *mp)
1895 PyObject **values = mp->ma_values;
1896 PyDictKeysObject *keys = mp->ma_keys;
1900 PyObject_GC_UnTrack(mp);
1901 Py_TRASHCAN_SAFE_BEGIN(mp)
1904 for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
1915 if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
1916 free_list[numfree++] = mp;
1918 Py_TYPE(mp)->tp_free((PyObject *)mp);
1919 Py_TRASHCAN_SAFE_END(mp)
1924 dict_repr(PyDictObject *mp)
1931 i = Py_ReprEnter((PyObject *)mp);
1936 if (mp->ma_used == 0) {
1937 Py_ReprLeave((PyObject *)mp);
1944 writer.min_length = 1 + 4 + (2 + 4) * (mp->ma_used - 1) + 1;
1953 while (PyDict_Next((PyObject *)mp, &i, &key, &value)) {
1994 Py_ReprLeave((PyObject *)mp);
1999 Py_ReprLeave((PyObject *)mp);
2007 dict_length(PyDictObject *mp)
2009 return mp->ma_used;
2013 dict_subscript(PyDictObject *mp, PyObject *key)
2025 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2029 if (!PyDict_CheckExact(mp)) {
2033 missing = _PyObject_LookupSpecial((PyObject *)mp, &PyId___missing__);
2051 dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
2054 return PyDict_DelItem((PyObject *)mp, v);
2056 return PyDict_SetItem((PyObject *)mp, v, w);
2066 dict_keys(PyDictObject *mp)
2075 n = mp->ma_used;
2079 if (n != mp->ma_used) {
2086 ep = DK_ENTRIES(mp->ma_keys);
2087 size = mp->ma_keys->dk_nentries;
2088 if (mp->ma_values) {
2089 value_ptr = mp->ma_values;
2110 dict_values(PyDictObject *mp)
2119 n = mp->ma_used;
2123 if (n != mp->ma_used) {
2130 ep = DK_ENTRIES(mp->ma_keys);
2131 size = mp->ma_keys->dk_nentries;
2132 if (mp->ma_values) {
2133 value_ptr = mp->ma_values;
2154 dict_items(PyDictObject *mp)
2168 n = mp->ma_used;
2180 if (n != mp->ma_used) {
2188 ep = DK_ENTRIES(mp->ma_keys);
2189 size = mp->ma_keys->dk_nentries;
2190 if (mp->ma_values) {
2191 value_ptr = mp->ma_values;
2368 PyDictObject *mp, *other;
2383 mp = (PyDictObject*)a;
2386 if (other == mp || other->ma_used == 0)
2389 if (mp->ma_used == 0)
2399 if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
2400 if (dictresize(mp, ESTIMATE_SIZE(mp->ma_used + other->ma_used))) {
2421 err = insertdict(mp, key, hash, value);
2428 err = insertdict(mp, key, hash, value);
2523 dict_copy(PyDictObject *mp)
2525 return PyDict_Copy((PyObject*)mp);
2532 PyDictObject *mp;
2540 mp = (PyDictObject *)o;
2541 if (mp->ma_used == 0) {
2546 if (_PyDict_HasSplitTable(mp)) {
2548 Py_ssize_t size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
2559 split_copy->ma_keys = mp->ma_keys;
2560 split_copy->ma_used = mp->ma_used;
2562 DK_INCREF(mp->ma_keys);
2564 PyObject *value = mp->ma_values[i];
2568 if (_PyObject_GC_IS_TRACKED(mp))
2573 if (PyDict_CheckExact(mp) && mp->ma_values == NULL &&
2574 (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3))
2578 (1) 'mp' is an instance of a subclassed dict; and
2580 (2) 'mp' is not a split-dict; and
2582 (3) if 'mp' is non-compact ('del' operation does not resize dicts),
2590 return clone_combined_dict(mp);
2603 PyDict_Size(PyObject *mp)
2605 if (mp == NULL || !PyDict_Check(mp)) {
2609 return ((PyDictObject *)mp)->ma_used;
2613 PyDict_Keys(PyObject *mp)
2615 if (mp == NULL || !PyDict_Check(mp)) {
2619 return dict_keys((PyDictObject *)mp);
2623 PyDict_Values(PyObject *mp)
2625 if (mp == NULL || !PyDict_Check(mp)) {
2629 return dict_values((PyDictObject *)mp);
2633 PyDict_Items(PyObject *mp)
2635 if (mp == NULL || !PyDict_Check(mp)) {
2639 return dict_items((PyDictObject *)mp);
2726 register PyDictObject *mp = self;
2737 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2782 PyDictObject *mp = (PyDictObject *)d;
2798 if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
2799 if (insertion_resize(mp) < 0)
2803 Py_ssize_t ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
2807 if (_PyDict_HasSplitTable(mp) &&
2808 ((ix >= 0 && value == NULL && mp->ma_used != ix) ||
2809 (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
2810 if (insertion_resize(mp) < 0) {
2819 if (mp->ma_keys->dk_usable <= 0) {
2820 if (insertion_resize(mp) < 0) {
2824 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
2825 ep0 = DK_ENTRIES(mp->ma_keys);
2826 ep = &ep0[mp->ma_keys->dk_nentries];
2827 dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
2830 MAINTAIN_TRACKING(mp, key, value);
2833 if (_PyDict_HasSplitTable(mp)) {
2834 assert(mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
2835 mp->ma_values[mp->ma_keys->dk_nentries] = value;
2840 mp->ma_used++;
2841 mp->ma_version_tag = DICT_NEXT_VERSION();
2842 mp->ma_keys->dk_usable--;
2843 mp->ma_keys->dk_nentries++;
2844 assert(mp->ma_keys->dk_usable >= 0);
2848 assert(_PyDict_HasSplitTable(mp));
2849 assert(ix == mp->ma_used);
2851 MAINTAIN_TRACKING(mp, key, value);
2852 mp->ma_values[ix] = value;
2853 mp->ma_used++;
2854 mp->ma_version_tag = DICT_NEXT_VERSION();
2857 assert(_PyDict_CheckConsistency(mp));
2886 dict_clear(PyDictObject *mp)
2888 PyDict_Clear((PyObject *)mp);
2893 dict_pop(PyDictObject *mp, PyObject *args)
2900 return _PyDict_Pop((PyObject*)mp, key, deflt);
2904 dict_popitem(PyDictObject *mp)
2922 if (mp->ma_used == 0) {
2929 if (mp->ma_keys->dk_lookup == lookdict_split) {
2930 if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
2935 ENSURE_ALLOWS_DELETIONS(mp);
2938 ep0 = DK_ENTRIES(mp->ma_keys);
2939 i = mp->ma_keys->dk_nentries - 1;
2946 j = lookdict_index(mp->ma_keys, ep->me_hash, i);
2948 assert(dk_get_index(mp->ma_keys, j) == i);
2949 dk_set_index(mp->ma_keys, j, DKIX_DUMMY);
2956 mp->ma_keys->dk_nentries = i;
2957 mp->ma_used--;
2958 mp->ma_version_tag = DICT_NEXT_VERSION();
2959 assert(_PyDict_CheckConsistency(mp));
2966 PyDictObject *mp = (PyDictObject *)op;
2967 PyDictKeysObject *keys = mp->ma_keys;
2980 if (mp->ma_values != NULL) {
2982 Py_VISIT(mp->ma_values[i]);
3004 _PyDict_SizeOf(PyDictObject *mp)
3008 size = DK_SIZE(mp->ma_keys);
3011 res = _PyObject_SIZE(Py_TYPE(mp));
3012 if (mp->ma_values)
3016 if (mp->ma_keys->dk_refcnt == 1)
3018 + DK_IXSIZE(mp->ma_keys) * size
3032 dict_sizeof(PyDictObject *mp)
3034 return PyLong_FromSsize_t(_PyDict_SizeOf(mp));
3108 PyDictObject *mp = (PyDictObject *)op;
3117 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
3127 PyDictObject *mp = (PyDictObject *)op;
3131 ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
