1112 return -1; |
1112 return -1; |
1113 } |
1113 } |
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) { |
1120 if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) { |
1172 if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) { |
1121 PyErr_SetString(PyExc_ValueError, "overflow in index_init_nt"); |
1173 PyErr_SetString(PyExc_ValueError, "overflow in index_init_nt"); |
1262 return -1; |
1314 return -1; |
1263 } |
1315 } |
1264 self->ntrev = -1; |
1316 self->ntrev = -1; |
1265 } |
1317 } |
1266 return 0; |
1318 return 0; |
1267 } |
|
1268 |
|
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 } |
1319 } |
1320 |
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; |