Show More
@@ -1114,6 +1114,58 b' static int nt_init(nodetree *self, index' | |||||
1114 | return 0; |
|
1114 | return 0; | |
1115 | } |
|
1115 | } | |
1116 |
|
1116 | |||
|
1117 | static int nt_partialmatch(nodetree *self, const char *node, | |||
|
1118 | Py_ssize_t nodelen) | |||
|
1119 | { | |||
|
1120 | return nt_find(self, node, nodelen, 1); | |||
|
1121 | } | |||
|
1122 | ||||
|
1123 | /* | |||
|
1124 | * Find the length of the shortest unique prefix of node. | |||
|
1125 | * | |||
|
1126 | * Return values: | |||
|
1127 | * | |||
|
1128 | * -3: error (exception set) | |||
|
1129 | * -2: not found (no exception set) | |||
|
1130 | * rest: length of shortest prefix | |||
|
1131 | */ | |||
|
1132 | static int nt_shortest(nodetree *self, const char *node) | |||
|
1133 | { | |||
|
1134 | int level, off; | |||
|
1135 | ||||
|
1136 | for (level = off = 0; level < 40; level++) { | |||
|
1137 | int k, v; | |||
|
1138 | nodetreenode *n = &self->nodes[off]; | |||
|
1139 | k = nt_level(node, level); | |||
|
1140 | v = n->children[k]; | |||
|
1141 | if (v < 0) { | |||
|
1142 | const char *n; | |||
|
1143 | v = -(v + 2); | |||
|
1144 | n = index_node_existing(self->index, v); | |||
|
1145 | if (n == NULL) | |||
|
1146 | return -3; | |||
|
1147 | if (memcmp(node, n, 20) != 0) | |||
|
1148 | /* | |||
|
1149 | * Found a unique prefix, but it wasn't for the | |||
|
1150 | * requested node (i.e the requested node does | |||
|
1151 | * not exist). | |||
|
1152 | */ | |||
|
1153 | return -2; | |||
|
1154 | return level + 1; | |||
|
1155 | } | |||
|
1156 | if (v == 0) | |||
|
1157 | return -2; | |||
|
1158 | off = v; | |||
|
1159 | } | |||
|
1160 | /* | |||
|
1161 | * The node was still not unique after 40 hex digits, so this won't | |||
|
1162 | * happen. Also, if we get here, then there's a programming error in | |||
|
1163 | * this file that made us insert a node longer than 40 hex digits. | |||
|
1164 | */ | |||
|
1165 | PyErr_SetString(PyExc_Exception, "broken node tree"); | |||
|
1166 | return -3; | |||
|
1167 | } | |||
|
1168 | ||||
1117 | static int index_init_nt(indexObject *self) |
|
1169 | static int index_init_nt(indexObject *self) | |
1118 | { |
|
1170 | { | |
1119 | if (self->nt == NULL) { |
|
1171 | if (self->nt == NULL) { | |
@@ -1266,58 +1318,6 b' static int index_populate_nt(indexObject' | |||||
1266 | return 0; |
|
1318 | return 0; | |
1267 | } |
|
1319 | } | |
1268 |
|
1320 | |||
1269 | static int nt_partialmatch(nodetree *self, const char *node, |
|
|||
1270 | Py_ssize_t nodelen) |
|
|||
1271 | { |
|
|||
1272 | return nt_find(self, node, nodelen, 1); |
|
|||
1273 | } |
|
|||
1274 |
|
||||
1275 | /* |
|
|||
1276 | * Find the length of the shortest unique prefix of node. |
|
|||
1277 | * |
|
|||
1278 | * Return values: |
|
|||
1279 | * |
|
|||
1280 | * -3: error (exception set) |
|
|||
1281 | * -2: not found (no exception set) |
|
|||
1282 | * rest: length of shortest prefix |
|
|||
1283 | */ |
|
|||
1284 | static int nt_shortest(nodetree *self, const char *node) |
|
|||
1285 | { |
|
|||
1286 | int level, off; |
|
|||
1287 |
|
||||
1288 | for (level = off = 0; level < 40; level++) { |
|
|||
1289 | int k, v; |
|
|||
1290 | nodetreenode *n = &self->nodes[off]; |
|
|||
1291 | k = nt_level(node, level); |
|
|||
1292 | v = n->children[k]; |
|
|||
1293 | if (v < 0) { |
|
|||
1294 | const char *n; |
|
|||
1295 | v = -(v + 2); |
|
|||
1296 | n = index_node_existing(self->index, v); |
|
|||
1297 | if (n == NULL) |
|
|||
1298 | return -3; |
|
|||
1299 | if (memcmp(node, n, 20) != 0) |
|
|||
1300 | /* |
|
|||
1301 | * Found a unique prefix, but it wasn't for the |
|
|||
1302 | * requested node (i.e the requested node does |
|
|||
1303 | * not exist). |
|
|||
1304 | */ |
|
|||
1305 | return -2; |
|
|||
1306 | return level + 1; |
|
|||
1307 | } |
|
|||
1308 | if (v == 0) |
|
|||
1309 | return -2; |
|
|||
1310 | off = v; |
|
|||
1311 | } |
|
|||
1312 | /* |
|
|||
1313 | * The node was still not unique after 40 hex digits, so this won't |
|
|||
1314 | * happen. Also, if we get here, then there's a programming error in |
|
|||
1315 | * this file that made us insert a node longer than 40 hex digits. |
|
|||
1316 | */ |
|
|||
1317 | PyErr_SetString(PyExc_Exception, "broken node tree"); |
|
|||
1318 | return -3; |
|
|||
1319 | } |
|
|||
1320 |
|
||||
1321 | static PyObject *index_partialmatch(indexObject *self, PyObject *args) |
|
1321 | static PyObject *index_partialmatch(indexObject *self, PyObject *args) | |
1322 | { |
|
1322 | { | |
1323 | const char *fullnode; |
|
1323 | const char *fullnode; |
General Comments 0
You need to be logged in to leave comments.
Login now