Function raxRandomWalk

rax.c:2152–2215

Perform a random walk starting in the current position of the iterator. * Return 0 if the tree is empty or on out of memory. Otherwise 1 is returned * and the iterator is set to the node reached after doing a random walk * of 'steps' steps. If the 'steps' argument is 0, the random walk is performed * using a random number of steps between 1 and two times the logarithm of * the number of eleme

 * tree certain keys will be reported much more often than others. At least
 * this function should be able to expore every possible element eventually. */
int raxRandomWalk(raxIterator *it, size_t steps) {
    if (it->rt->numele == 0) {
        it->flags |= RAX_ITER_EOF;
        return 0;
    }

    if (steps == 0) {
        size_t fle = 1+floor(log(it->rt->numele));
        fle *= 2;
        steps = 1 + rand() % fle;
    }

    raxNode *n = it->node;
    int inline_leaf = raxIteratorIsInlineLeaf(it);
    int node_child = it->node_child;
    while(steps > 0 || !(inline_leaf || n->iskey)) {
        if (inline_leaf) {
            inline_leaf = 0;
            int todel = n->iscompr ? n->size : 1;
            raxIteratorDelChars(it,todel);
            if (n->iskey) steps--;
            continue;
        }

        int numchildren = n->iscompr ? 1 : n->size;
        int r = rand() % (numchildren+(n != it->rt->head));

        if (r == numchildren) {
            /* Go up to parent. */
            n = raxStackPop(&it->stack);
            node_child = -1;
            int todel = n->iscompr ? n->size : 1;
            raxIteratorDelChars(it,todel);
        } else {
            /* Select a random child. */
            raxNode **cp = raxNodeFirstChildPtr(n)+r;
            int cidx = n->iscompr ? 0 : r;
            if (n->iscompr) {
                if (!raxIteratorAddChars(it,n->data,n->size)) return 0;
            } else {
                if (!raxIteratorAddChars(it,n->data+r,1)) return 0;
            }
            if (raxIsInlineLeaf(n,cidx)) {
                memcpy(&it->data,cp,sizeof(it->data));
                inline_leaf = 1;
                node_child = cidx;
            } else {
                if (!raxStackPush(&it->stack,n)) return 0;
                memcpy(&n,cp,sizeof(n));
                node_child = cidx;
            }
        }
        if (inline_leaf || n->iskey) steps--;
    }
    it->node = n;
    it->node_child = node_child;
    if (inline_leaf) {
        it->flags |= RAX_ITER_INLINE_LEAF;