Проблема в ручном воспроизведении dict базового кода: значение не может быть объектом - PullRequest
Новая
       34

Проблема в ручном воспроизведении dict базового кода: значение не может быть объектом

0 голосов
/ 11 октября 2019

Я пытался вручную воспроизвести python dict базовый код (он может реализовывать только setitem и getitem), но я столкнулся с проблемой: hashmap Я написал, что может работать хорошо только тогда, когда типом значения являются базовые типы данных (например, int, str и т. Д.). Если типом значения является object, hashmap может только устанавливать элемент, то при получении значения типа объекта происходит сбой питона.

Сообщение об ошибке «Неустранимая ошибка: объект GC уже отслежен»

Я полагаю, есть несколько возможных проблем:

  1. что-то не так в (PyTypeObject) определении PyHashMap_Type
  2. Метод getitem возвращает PyObject *, но питон не может разрешить указатель объекта

В некоторых случаях у меня есть тест

case1: все типы ключей и значений являются базовыми типами данных, он хорошо работает

case2: тип ключа является объектным, но тип значения является базовым типом данных, он работает хорошо

case3: тип ключа - базовыйic тип данных, но тип значения - объект, сбой питона при получении элемента, даже если значением является пустой объект

case4: все типы ключей и значений являются объектами, результат такой же, какcase3 

// the PyTypeObject
static PyTypeObject PyHashMap_Type = {
    PyVarObject_HEAD_INIT(NULL, 0)
    "hashmap",
    sizeof(PyMapObject),
    0,
    (destructor)PyHashMap_dealloc,              /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    (reprfunc)repr_func,                        /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
        Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS,         /* tp_flags */
    0,                              /* tp_doc */
    0,                              /* tp_traverse */
    0,                              /* tp_clear */
    0,                              /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    0,                               /* tp_methods */
    0,                                          /* tp_members */
    0,                                          /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                  /* tp_init */
    PyType_GenericAlloc,                        /* tp_alloc */
    _HashMap_New,                                   /* tp_new */
    PyObject_GC_Del,                            /* tp_free */
};

// the hashmap struct
typedef struct _mapkeysobject PyMapKeysObject;

typedef struct {
    Py_hash_t me_hash;                          
    PyObject *me_key;                           
    PyObject *me_value;                         
} PyMapKeyEntry;

struct _mapkeysobject {
    Py_ssize_t dk_size;                         
    Py_ssize_t dk_usable;
    PyMapKeyEntry dk_entries[1];                
};

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    PyMapKeysObject *ma_keys;
    PyObject **ma_values;
} PyMapObject;

// get item methods, the python call GET_ITEM_WRAPPER
static PyObject* GET_ITEM_WRAPPER(PyObject* self, PyObject* args){
    PyObject * o = NULL;
    PyObject * key = NULL;
    if (!PyArg_ParseTuple(args, "OO",&o,&key)) {
        printf("error: arg list error");
        Py_RETURN_NONE;
    }
    PyObject* value = PyMap_GetItem(o, key);
    if (value == NULL) Py_RETURN_NONE;
    return value;
}

static PyObject* PyMap_GetItem(PyObject* o, PyObject* key){
    PyMapObject *mp;
    Py_hash_t hash;
    mp = (PyMapObject *)o;

    hash = PyObject_Hash(key);  
    if (hash == -1)
        return NULL;
    return searchmap(mp, key, hash);
}

static PyObject* searchmap(PyMapObject* mp, PyObject* key, Py_hash_t hash){
    PyObject **value_addr;  
    PyMapKeyEntry *ep;

    ep = lookup_function(mp, key, hash, &value_addr);

    if (ep == NULL) return NULL;
    return ep->me_value;
}

PyMapKeyEntry* lookup_function(PyMapObject* mp, PyObject* key, Py_hash_t hash, PyObject ***value_addr){
    size_t i;
    size_t perturb;
    size_t mask = DK_MASK(mp->ma_keys);                                
    PyMapKeyEntry *ep0 = &mp->ma_keys->dk_entries[0];                 
    PyMapKeyEntry *ep;

    i = (size_t)hash & mask;                                           
    ep = &ep0[i];
    if (ep->me_key == NULL || ep->me_key == key) {                     
        *value_addr = &ep->me_value;                                    
        return ep;                                                      
    }
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {                    
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
        if (ep->me_key == NULL || ep->me_key == key) {                  
            *value_addr = &ep->me_value;                                
            return ep;                                                  
        }
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

Я ожидаю, что типом значения может быть объект

1 Ответ

0 голосов
/ 11 октября 2019

Я полагаю, что вы испортили счетчик ссылок (хотя трудно быть абсолютно уверен с неполным кодом).

Ваш счетчик ссылок для сохраненных значений должен быть хотя бы один(представлять тот факт, что вы держите ссылку на него как часть вашего словаря). Однако в тот момент, когда вы его возвращаете, должно быть два (один для ссылки, которую вы держите, а другой для ссылки на возвращаемое значение).

Я подозреваю, что в PyMap_GetItem вы должны сделать: 

PyObject *ret_val = searchmap(mp, key, hash);
Py_XINCREF(ret_val);
return ret_val;

(хотя вы, кажется, фактически не устанавливаете методы последовательности / отображения в PyHashMap_Type, поэтому кто знает, действительно ли используется PyMap_GetItem ...)

Причинаэто будет работать для целочисленных значений, а строка - это то, что Python «интернирует» небольшие целые и короткие строки, по сути, сохраняя постоянную ссылку на них. Если вы продолжаете искать их, то в конце концов они будут ломаться (каждый раз, когда вы делаете это, вы теряете ссылку).

...