手动复制字典底层代码的问题：该值不能是对象

Question

我试图手动复制python dict基础代码（它只能实现setitem和getitem），但是我遇到了一个问题：我写的hashmap仅能工作当值类型是基本数据类型（例如int，str等）时，效果很好。如果值的类型是object，则hashmap只能设置item，获取对象类型的值时python将崩溃。

错误消息是“致命错误：GC对象已被跟踪“

我想可能有几个问题：

1. [PyTypeObject）PyHashMap_Type定义中出现问题
2. getitem方法返回的PyObject *，但是python无法解析对象的指针

这是我测试过的一些情况

case1：键和值类型都是基本数据类型，效果很好

case2：键的类型为object，但值的类型为基本数据类型，效果很好

case3：key'type是基本数据类型，而value类型是object，即使值是an，获取项目时python崩溃空对象

case4：键和值的类型都是对象，结果相同视情况3

// 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;
}

我希望值类型可以是对象

Answer 1

我相信您已经弄乱了引用计数（尽管很难[[绝对确定不完整的代码）。

您对存储值的引用计数应至少为一个（以表示您在字典中拥有对该引用的引用这一事实）。但是，在返回该点时，它应该是两个（一个用于您所持有的引用，另一个用于对返回值的引用）。

我怀疑您应该在PyMap_GetItem中这样做：

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

（（尽管我您似乎并没有在PyHashMap_Type中实际设置顺序/映射方法，所以谁知道PyMap_GetItem是否真正在使用...）

之所以看起来适用于int和string，是因为Python“实习生”小int和short字符串，本质上保持对它们的恒定引用。如果您一直在查找它们，那么它最终还是会中断（每次您执行操作都会丢失参考）。