Q: `radix_tree_prev` iterates through all nodes with a lexicographic order less than `path`

[haoyang1994]

Functionradix_tree_prev in easy_rax.c iterates through all nodes with a lexicographic order less than path. May I know why?This caused a time complexity of O(N). When there are a lot of routes and can't hit exactly, it performs poor.

[haoyang1994]

---

int
radix_tree_prev(void *it, const unsigned char *buf, size_t len)
{
    raxIterator    *iter = it;
    int             res;

    while (1) {
        res = raxPrev(iter);
        if (!res) {
            return -1;
        }

        if (iter->key_len > len ||
            memcmp(buf, iter->key, iter->key_len) != 0) {
            continue;
        }

        break;
    }

    return (int)iter->data;
}

This function is called by:

    local it = radix.radix_tree_search(self.tree, self.tree_it, path, #path)
    if not it then
        return nil, "failed to match"
    end

    while true do
        local idx = radix.radix_tree_prev(it, path, #path)
        if idx <= 0 then
            break
        end

        routes = self.match_data[idx]
        if routes then
            local route = _match_from_routes(routes, path, opts, args)
            if route then
                return route
            end
        end
    end

It seems that what we need is the stack of raxSeek result. Please let me know what I am missing. Thank you.

[spacewander]

The raxPrev travels through the radix tree so it's not an O(n) operation.

The code will find the longest rule which matches the given path (exact match or prefix match), therefore it iterates the radix tree reversely (from leaf to root).

[haoyang1994]

@spacewander Much appreicate for reply. But raxPrev doesn't work as travelling through. It iterates all nodes with keys that smaller than the node what was found by raxSeek one by one. Just to be clear, I put my test code.

   rax *t = raxNew();
    char *toadd[] = {"alligator","alien","baloon","chromodynamic","romane","romanus","romulus","rubens","ruber","rubicon","rubicundus","all","rub","ba",NULL};

    long items = 0;
    while(toadd[items] != NULL) items++;

    for (long i = 0; i < items; i++)
        raxInsert(t,(unsigned char*)toadd[i],strlen(toadd[i]),(void*)i,NULL);

    raxIterator *iter = malloc(sizeof(raxIterator));
    raxStart(iter,t);
    raxSeek(iter,"<=","hello",5);

    int             res;

    while (1) {
        res = raxPrev(iter);
        if (!res) {
            break;
        }
        printf("cur key found by raxPrev: %s,key_len: %d\n",iter->key,iter->key_len);
        continue;
    }
    raxStop(iter);
    raxFree(t);

OutPut:

cur key found by raxPrev: chromodynamic,key_len: 13
cur key found by raxPrev: baloondynamic,key_len: 6
cur key found by raxPrev: baloondynamic,key_len: 2
cur key found by raxPrev: alligatoramic,key_len: 9
cur key found by raxPrev: alligatoramic,key_len: 3
cur key found by raxPrev: alienatoramic,key_len: 5
OK! \o/

The iteration path of raxPrev is chromodynamic -> baloon -> ba -> alligator -> all -> alien. But what we really need here is that chromodynamic -> Root of the radix tree , then over. It's meanless to search other branches of the tree but the one from the node returned by raxSeek to the Root.

[spacewander]

Interesting. Look like we can add a quit break here. Would you like to try it?

[haoyang1994]

With pleasure.