Ticket #13394: deldict_exact.pyx

from cpython cimport Py_XINCREF, Py_XDECREF

cdef extern from "Python.h":
    ctypedef struct PyDictEntry:
        Py_ssize_t me_hash
        PyObject* me_key
        PyObject* me_value
    ctypedef struct PyDictObject:
        Py_ssize_t ma_fill
        Py_ssize_t ma_used
        Py_ssize_t ma_mask
        PyDictEntry* ma_table
    cdef PyObject* _PyDict_Dummy()

cdef PyObject *dummy = NULL

def init_dummy():
    cdef dict D = dict()
    cdef PyDictObject* mp = <PyDictObject *><void *>D
    cdef size_t mask
    cdef PyDictEntry* ep0 = mp.ma_table
    cdef PyDictEntry* ep
    cdef size_t i
    global dummy

    if dummy !=NULL:
        return        
    D[1]=1; del D[1] #ensure that there is a "deleted" entry in the dict
    mask = mp.ma_mask
    for i in range(mask+1):
        ep = &(ep0[i])
        if ep.me_key != NULL:
            Py_XINCREF(ep.me_key)
            dummy = ep.me_key
            return
    raise RuntimeError("Problem initializing dummy")
            
def del_dictitem_exact(dict D, object key, long hash):
    cdef PyDictObject *mp = <PyDictObject *><void *>D
    cdef size_t i
    cdef size_t perturb
    cdef size_t mask = <size_t> mp.ma_mask
    cdef PyDictEntry* ep0 = mp.ma_table
    cdef PyDictEntry* ep
    i = hash & mask
    ep = &(ep0[i])

    if ep.me_key == NULL:
        raise KeyError("key not found")

    perturb = hash
    while (<void *>(ep.me_key) != <void *>key):
        i = (i << 2) + i + perturb +1
        ep = &ep0[i & mask]
        if ep.me_key == NULL:
            raise KeyError("key not found")
        perturb = perturb >> 5 #this is the value of PERTURB_SHIFT

    old_key= ep.me_key
    if dummy == NULL:
        raise RuntimeError("dummy needs to be initialized")
    Py_XINCREF(dummy)
    ep.me_key = dummy
    old_value = ep.me_value
    ep.me_value = NULL
    mp.ma_used -= 1
    Py_XDECREF(old_key)
    Py_XDECREF(old_value)