Do an iteration step towards the next element. At the end of the step the * iterator key will represent the (new) current key. If it is not possible * to step in the specified direction since there are no longer elements, the * iterator is flagged with RAX_ITER_EOF. * * If 'noup' is true the function starts directly scanning for the next * lexicographically smaller children, and the current
| 1311 | * |
| 1312 | * The function returns 1 on success or 0 on out of memory. */ |
| 1313 | int raxIteratorNextStep(raxIterator *it, int noup) { |
| 1314 | if (it->flags & RAX_ITER_EOF) { |
| 1315 | return 1; |
| 1316 | } else if (it->flags & RAX_ITER_JUST_SEEKED) { |
| 1317 | it->flags &= ~RAX_ITER_JUST_SEEKED; |
| 1318 | return 1; |
| 1319 | } |
| 1320 | |
| 1321 | /* Save key len, stack items and the node where we are currently |
| 1322 | * so that on iterator EOF we can restore the current key and state. */ |
| 1323 | size_t orig_key_len = it->key_len; |
| 1324 | size_t orig_stack_items = it->stack.items; |
| 1325 | raxNode *orig_node = it->node; |
| 1326 | |
| 1327 | while(1) { |
| 1328 | int children = it->node->iscompr ? 1 : it->node->size; |
| 1329 | if (!noup && children) { |
| 1330 | debugf("GO DEEPER\n"); |
| 1331 | /* Seek the lexicographically smaller key in this subtree, which |
| 1332 | * is the first one found always going towards the first child |
| 1333 | * of every successive node. */ |
| 1334 | if (!raxStackPush(&it->stack,it->node)) return 0; |
| 1335 | raxNode **cp = raxNodeFirstChildPtr(it->node); |
| 1336 | if (!raxIteratorAddChars(it,it->node->data, |
| 1337 | it->node->iscompr ? it->node->size : 1)) return 0; |
| 1338 | memcpy(&it->node,cp,sizeof(it->node)); |
| 1339 | /* Call the node callback if any, and replace the node pointer |
| 1340 | * if the callback returns true. */ |
| 1341 | if (it->node_cb && it->node_cb(&it->node)) |
| 1342 | memcpy(cp,&it->node,sizeof(it->node)); |
| 1343 | /* For "next" step, stop every time we find a key along the |
| 1344 | * way, since the key is lexicograhically smaller compared to |
| 1345 | * what follows in the sub-children. */ |
| 1346 | if (it->node->iskey) { |
| 1347 | it->data = raxGetData(it->node); |
| 1348 | return 1; |
| 1349 | } |
| 1350 | } else { |
| 1351 | /* If we finished exploring the previous sub-tree, switch to the |
| 1352 | * new one: go upper until a node is found where there are |
| 1353 | * children representing keys lexicographically greater than the |
| 1354 | * current key. */ |
| 1355 | while(1) { |
| 1356 | int old_noup = noup; |
| 1357 | |
| 1358 | /* Already on head? Can't go up, iteration finished. */ |
| 1359 | if (!noup && it->node == it->rt->head) { |
| 1360 | it->flags |= RAX_ITER_EOF; |
| 1361 | it->stack.items = orig_stack_items; |
| 1362 | it->key_len = orig_key_len; |
| 1363 | it->node = orig_node; |
| 1364 | return 1; |
| 1365 | } |
| 1366 | /* If there are no children at the current node, try parent's |
| 1367 | * next child. */ |
| 1368 | unsigned char prevchild = it->key[it->key_len-1]; |
| 1369 | if (!noup) { |
| 1370 | it->node = raxStackPop(&it->stack); |
no test coverage detected