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
| 457 | * compressed node characters are needed to represent the key, just all |
| 458 | * its parents nodes). */ |
| 459 | static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts) { |
| 460 | raxNode *h = rax->head; |
| 461 | raxNode **parentlink = &rax->head; |
| 462 | |
| 463 | size_t i = 0; /* Position in the string. */ |
| 464 | size_t j = 0; /* Position in the node children (or bytes if compressed).*/ |
| 465 | while(h->size && i < len) { |
| 466 | debugnode("Lookup current node",h); |
| 467 | unsigned char *v = h->data; |
| 468 | |
| 469 | if (h->iscompr) { |
| 470 | for (j = 0; j < h->size && i < len; j++, i++) { |
| 471 | if (v[j] != s[i]) break; |
| 472 | } |
| 473 | if (j != h->size) break; |
| 474 | } else { |
| 475 | /* Even when h->size is large, linear scan provides good |
| 476 | * performances compared to other approaches that are in theory |
| 477 | * more sounding, like performing a binary search. */ |
| 478 | for (j = 0; j < h->size; j++) { |
| 479 | if (v[j] == s[i]) break; |
| 480 | } |
| 481 | if (j == h->size) break; |
| 482 | i++; |
| 483 | } |
| 484 | |
| 485 | if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */ |
| 486 | raxNode **children = raxNodeFirstChildPtr(h); |
| 487 | if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */ |
| 488 | memcpy(&h,children+j,sizeof(h)); |
| 489 | parentlink = children+j; |
| 490 | j = 0; /* If the new node is non compressed and we do not |
| 491 | iterate again (since i == len) set the split |
| 492 | position to 0 to signal this node represents |
| 493 | the searched key. */ |
| 494 | } |
| 495 | debugnode("Lookup stop node is",h); |
| 496 | if (stopnode) *stopnode = h; |
| 497 | if (plink) *plink = parentlink; |
| 498 | if (splitpos && h->iscompr) *splitpos = j; |
| 499 | return i; |
| 500 | } |
| 501 | |
| 502 | /* Insert the element 's' of size 'len', setting as auxiliary data |
| 503 | * the pointer 'data'. If the element is already present, the associated |
no test coverage detected