skiplistsReverseIteration.cpp

// Reverse iteration implementation for skip lists, that are not implemented as doubly-linked lists nodes.
//
// Based on idea from http://blog.memsql.com/the-story-behind-memsqls-skiplist-indexes/ 
// You can use e.g [from, upto) ranges to limit the breadth; the idea is that keep track of the last node within the range
// for each subsequent layer you walk down, and then, for each segment, you push into a stack and iterate it in reverse
// This saves memory (no need for prev pointer, and according to @NikitaShamgunov:
// https://twitter.com/NikitaShamgunov/status/596167839796449281 " It is quite performant "
void Skiplist::foreach_reverse(std::function<void(const KVT k)> l)
{
        const node *ckpt[MAX_DEPTH + 1], *it = head;
        uint8_t cnt{1};
        Vector<const node *> stack;

        ckpt[0] = head->next[0];
        for (int8_t i = height - 1; i >= 0; --i)
        {
                if (const auto *n = it->next[i])
                {
                        ckpt[cnt++] = n;
                        do
                        {
                                it = n;
                        } while ((n = it->next[i]));
                }
        }
        ckpt[cnt] = nullptr;

        do
        {
                const auto *const end   = ckpt[cnt--];
                const auto *it          = ckpt[cnt];

                for (stack.SetToEmpty(); it != end; it = it->next[0])
                        stack.Append(it);

                while (stack.Any())
                      l(stack.Pop()));

        } while (cnt);
}