手工复制dict底层代码中的一个问题:值不能是对象
提问于 2019-10-10 20:01:56
我尝试手动复制 python dict底层代码(它只能实现setitem和getitem)，但我遇到了一个问题:我编写的 hashmap 只有在值类型是基本数据类型(如int、str等)时才能很好地工作--值的类型是object，hashmap只能设置项，python在获取对象类型的值时才会崩溃。
错误消息是“致命错误: GC对象已经跟踪”
我想有几个可能的问题：
definition
- The getitem方法返回的PyObject*中有什么问题，但是python无法解析对象的指针
这是一些我要检查的病例
案例1:键和值类型都是基本的数据类型，运行良好
例2:键的类型是object，但是值类型是基本数据类型，它运行良好
例3:键‘type是基本数据类型，但是值类型是object，python在获取项时崩溃，即使值是空对象
案例4:键类型和值类型都是对象，结果与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
Stack Overflow用户
回答已采纳
发布于 2019-10-11 05:23:37
我相信您已经搞砸了引用计数(尽管很难完全肯定不完整的代码)。
存储值的引用计数应该至少为一个(以表示将引用作为字典的一部分)。但是，在返回它时，应该是两个(一个用于持有的引用，另一个用于对返回值的引用)。
我在PyMap_GetItem中怀疑你应该这样做：
PyObject *ret_val = searchmap(mp, key, hash);
Py_XINCREF(ret_val);
return ret_val;(虽然我似乎没有在PyHashMap_Type中实际设置序列/映射方法，但是谁知道PyMap_GetItem是否真的被使用.)
这似乎适用于ints和string，原因是Python“实习生”小ints和短字符串，本质上保持对它们的持续引用。如果您继续查找，那么它最终会中断(每次您这样做，您失去一个参考)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58334067
复制相关文章
腾讯云开发者
