最新网站开发需求文档,顺德乐从网站建设,东莞建站模板搭建,网站建设 千佳网络Dict的类型的查找使用的是lookdict函数 static PyDictKeyEntry *
lookdict(PyDictObject *mp, PyObject *key,Py_hash_t hash, PyObject ***value_addr) 函数的参数中#xff0c;*value_addr是指向匹配slot中值的指针。 这个函数在正确的情况下一定会返回一个指向slot的指针*value_addr是指向匹配slot中值的指针。 这个函数在正确的情况下一定会返回一个指向slot的指针出错则会返回NULL。 如果成功找到了匹配的slot则返回对应的slot 如果没有匹配的slot则返回查找链上第一个未被使用的slot。 该slot可以是unused状态也可以是dummy状态。 mask DK_MASK(mp-ma_keys);ep0 mp-ma_keys-dk_entries[0];i (size_t)hash mask; 计算了slot的初始位置把hash值映射到slot table的下标范围内。 初始位置hashmaskmaskdk_size-1 if (ep-me_key NULL || ep-me_key key) {*value_addr ep-me_value;return ep;} 如果找到了匹配的key或unused slot返回该结果即可。 if (ep-me_key dummy)freeslot ep;else {if (ep-me_hash hash) {startkey ep-me_key;Py_INCREF(startkey);cmp PyObject_RichCompareBool(startkey, key, Py_EQ);Py_DECREF(startkey);if (cmp 0)return NULL;if (ep0 mp-ma_keys-dk_entries ep-me_key startkey) {if (cmp 0) {*value_addr ep-me_value;return ep;}}else {/* The dict was mutated, restart */goto top;}}freeslot NULL;} 进一步的比较。 若该slot状态为dummy则用freeslot记录该slot并继续搜索 如果该slot的hash值与待搜索key的hash相同那么对两个key进行比较。 这里的PyObject_RichCompareBool是一个比较函数其第三个参数为比较的操作。 如果操作结果为true返回1为false返回0比较出错返回-1。 比较出错的情况下会返回NULL比较成功在这里为相等返回该slot比较不成功则继续进行搜索。 这一部分进行了第一次的搜索在dict容量不太满时一般在这里就可以找到合适的结果。 i (i 2) i perturb 1;ep ep0[i mask];if (ep-me_key NULL) {if (freeslot NULL) {*value_addr ep-me_value;return ep;} else {*value_addr freeslot-me_value;return freeslot;}} 找到了unused slot的情况。 如果freeslot是NULL那么返回该slot即可若freeslot不是NULL那么返回freeslot。 if (ep-me_key key) {*value_addr ep-me_value;return ep;} 找到了匹配的key。此情况返回对应slot即可。 if (ep-me_hash hash ep-me_key ! dummy) {startkey ep-me_key;Py_INCREF(startkey);cmp PyObject_RichCompareBool(startkey, key, Py_EQ);Py_DECREF(startkey);if (cmp 0) {*value_addr NULL;return NULL;}if (ep0 mp-ma_keys-dk_entries ep-me_key startkey) {if (cmp 0) {*value_addr ep-me_value;return ep;}}else {/* The dict was mutated, restart */goto top;}} 该slot hash值与给定hash值相同时进一步比较的情况。 else if (ep-me_key dummy freeslot NULL)freeslot ep; 在dummy情况下设置freeslot。 在搜索过程中原则是找到和key相等的对象即可。 那么什么是和key相等呢 一种情况是它们的引用相等自然的值也相等。 这类比较只需要直接比较对应指针是否相等呢该即可。 而另一种情况是引用不相等但值还相等。 如果没有对这种情况的处理那么对于非共享的对象来说搜索几乎不会得到正确的结果。 搜索中的进一步比较就是对这种情况的处理。 进一步比较发生的前提是hash值相等因为值相等必然有hash相等 但hash相等值却可能不等因此不能直接比较hash值还需要更进一步的比较值才可以。转载于:https://www.cnblogs.com/ruizhang3/p/6888006.html
