Ticket #13394: deldict_exact.2.pyx

File deldict_exact.2.pyx, 1.9 KB (added by nbruin, 5 years ago)

proof of concept delete-by-id for python dicts

Line 
1from cpython cimport Py_XINCREF, Py_XDECREF
2
3cdef extern from "Python.h":
4    ctypedef struct PyDictEntry:
5        Py_ssize_t me_hash
6        PyObject* me_key
7        PyObject* me_value
8    ctypedef struct PyDictObject:
9        Py_ssize_t ma_fill
10        Py_ssize_t ma_used
11        Py_ssize_t ma_mask
12        PyDictEntry* ma_table
13    cdef PyObject* _PyDict_Dummy()
14
15cdef PyObject *dummy = NULL
16
17def init_dummy():
18    cdef dict D = dict()
19    cdef PyDictObject* mp = <PyDictObject *><void *>D
20    cdef size_t mask
21    cdef PyDictEntry* ep0 = mp.ma_table
22    cdef PyDictEntry* ep
23    cdef size_t i
24    global dummy
25
26    if dummy !=NULL:
27        return       
28    D[1]=1; del D[1] #ensure that there is a "deleted" entry in the dict
29    mask = mp.ma_mask
30    for i in range(mask+1):
31        ep = &(ep0[i])
32        if ep.me_key != NULL:
33            Py_XINCREF(ep.me_key)
34            dummy = ep.me_key
35            return
36    raise RuntimeError("Problem initializing dummy")
37           
38def del_dictitem_exact(dict D, object key, long hash):
39    cdef PyDictObject *mp = <PyDictObject *><void *>D
40    cdef size_t i
41    cdef size_t perturb
42    cdef size_t mask = <size_t> mp.ma_mask
43    cdef PyDictEntry* ep0 = mp.ma_table
44    cdef PyDictEntry* ep
45    i = hash & mask
46    ep = &(ep0[i])
47
48    if ep.me_key == NULL:
49        raise KeyError("key not found")
50
51    perturb = hash
52    while (<void *>(ep.me_key) != <void *>key):
53        i = (i << 2) + i + perturb +1
54        ep = &ep0[i & mask]
55        if ep.me_key == NULL:
56            raise KeyError("key not found")
57        perturb = perturb >> 5 #this is the value of PERTURB_SHIFT
58
59    old_key= ep.me_key
60    if dummy == NULL:
61        raise RuntimeError("dummy needs to be initialized")
62    Py_XINCREF(dummy)
63    ep.me_key = dummy
64    old_value = ep.me_value
65    ep.me_value = NULL
66    mp.ma_used -= 1
67    Py_XDECREF(old_key)
68    Py_XDECREF(old_value)
69