Low level function that walks the tree looking for the string * 's' of 'len' bytes. The function returns the number of characters * of the key that was possible to process: if the returned integer * is the same as 'len', then it means that the node corresponding to the * string was found (however it may not be a key in case the node->iskey is * zero or if simply we stopped in the middle of a
| 557 | * compressed node characters are needed to represent the key, just all |
| 558 | * its parents nodes). */ |
| 559 | static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts, int *inline_leaf) { |
| 560 | raxNode *h = rax->head; |
| 561 | raxNode **parentlink = &rax->head; |
| 562 | |
| 563 | if (inline_leaf) *inline_leaf = 0; |
| 564 | size_t i = 0; /* Position in the string. */ |
| 565 | size_t j = 0; /* Position in the node children (or bytes if compressed).*/ |
| 566 | while(h->size && i < len) { |
| 567 | debugnode("Lookup current node",h); |
| 568 | unsigned char *v = h->data; |
| 569 | |
| 570 | if (h->iscompr) { |
| 571 | for (j = 0; j < h->size && i < len; j++, i++) { |
| 572 | if (v[j] != s[i]) break; |
| 573 | } |
| 574 | if (j != h->size) break; |
| 575 | } else { |
| 576 | /* Even when h->size is large, linear scan provides good |
| 577 | * performances compared to other approaches that are in theory |
| 578 | * more sounding, like performing a binary search. However |
| 579 | * for nodes with many children, using memchr() is faster |
| 580 | * since it is SIMD-accelerated on modern architectures. */ |
| 581 | if (h->size > 16) { |
| 582 | unsigned char *found = memchr(v,s[i],h->size); |
| 583 | if (found == NULL) break; |
| 584 | j = found - v; |
| 585 | } else { |
| 586 | for (j = 0; j < h->size; j++) { |
| 587 | if (v[j] == s[i]) break; |
| 588 | } |
| 589 | if (j == h->size) break; |
| 590 | } |
| 591 | i++; |
| 592 | } |
| 593 | |
| 594 | raxNode **children = raxNodeFirstChildPtr(h); |
| 595 | if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */ |
| 596 | |
| 597 | /* If the child we are about to follow is an inline leaf (a value |
| 598 | * stored directly in the child pointer slot), we can't descend |
| 599 | * further. Stop the walk here: h remains as the parent, and |
| 600 | * parentlink will point to the slot containing the inline value. |
| 601 | * We do NOT push h onto the stack since we're not descending. */ |
| 602 | if (raxIsInlineLeaf(h,j)) { |
| 603 | if (inline_leaf) *inline_leaf = 1; |
| 604 | parentlink = children+j; |
| 605 | break; |
| 606 | } |
| 607 | if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */ |
| 608 | memcpy(&h,children+j,sizeof(h)); |
| 609 | parentlink = children+j; |
| 610 | j = 0; /* If the new node is compressed and we do not |
| 611 | iterate again (since i == l) set the split |
| 612 | position to 0 to signal this node represents |
| 613 | the searched key. */ |
| 614 | } |
| 615 | debugnode("Lookup stop node is",h); |
| 616 | if (stopnode) *stopnode = h; |
no test coverage detected