Skiplist Implementation

skiplist.hpp

/*

The MIT License (MIT) Copyright (c) 2016 UAA Software

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
associated documentation files (the "Software"), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge, publish, distribute,
sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial
portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES
OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

*/

#include <cassert>
#include <cstdint>
#include <cstdlib>

#include "plf_colony.hpp"

#define UAALIB_DEBUG_PRINT

// ref: A Skip List Cookbook
//      http://drum.lib.umd.edu/bitstream/handle/1903/544/CS-TR-2286.1.pdf;sequence=2

namespace uaa {

#define UAA_IMPLICIT_SKIPLIST_MAXLEVELS 16

template <typename T>
class implicit_skiplist {

    // Disallow copy and move operators and constructors.
    implicit_skiplist(implicit_skiplist&& other) = delete;
    implicit_skiplist(const implicit_skiplist& other) = delete;
    implicit_skiplist& operator=(const implicit_skiplist& other) = delete;
    implicit_skiplist& operator=(implicit_skiplist&& other) = delete;

    // Linked list node.
    struct Node {
        Node* next[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];
        uint32_t skipWidth[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];
        uint16_t height = 0;
        T data;
    };

    // Header pointing to linked list.
    Node m_header;
    Node m_footer;
    T defaultData;

    // Actual storage for the nodes.
    plf::colony< Node >& m_storage;

private:

    // Find a node such that node->index == index for index > 0 if found, or NULL otherwise.
    inline Node* find_node(uint32_t index)
    {
        auto maxlvl = m_header.height;
        assert(maxlvl < UAA_IMPLICIT_SKIPLIST_MAXLEVELS);
        index++;

        // Go down the skiplist until we have hit lower_bound(index).
        uint64_t cindex = 0;
        Node* c = &m_header;
        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &m_footer && cindex + (uint64_t) c->skipWidth[i] < (uint64_t) index) {
                assert(c->skipWidth[i] > 0);
                cindex += c->skipWidth[i];
                c = c->next[i];
            }
        }

        assert(c && c->next[0]);
        assert(c->skipWidth[0] == 1);
        if (c && c->next[0] && (cindex + (uint64_t) c->skipWidth[0] == (uint64_t) index)) {
            return c->next[0];
        } else {
            return nullptr;
        }
    }

    // Generate a continual coin-toss level, where each level should statstically have a
    // link every 2^n nodes.
    inline uint32_t random_level(void)
    {
        uint32_t lvl = 1;
        while (rand() % 2 && lvl < UAA_IMPLICIT_SKIPLIST_MAXLEVELS - 1) {
            lvl++;
        }
        return lvl;
    }

public:

    // Minimal iterator class.
    class iterator {
        Node* m_node = nullptr;
        friend class implicit_skiplist;

    public:
        inline void operator ++ (int) { m_node = m_node->next[0]; }
        inline T& operator * (void) { return m_node->data; }
        inline bool operator == (const iterator& other) const { return m_node == other.m_node; }
        inline bool operator != (const iterator& other) const { return m_node != other.m_node; }
        inline T* operator -> (void) { return &m_node->data; }
    };

    typedef plf::colony< Node > storage;

private:
    inline iterator make_itr(Node* node) {
        iterator itr;
        itr.m_node = node;
        return itr;
    }

public:
    explicit implicit_skiplist(storage& s)
        : m_storage(s)
    {
        for (int i = 0; i < UAA_IMPLICIT_SKIPLIST_MAXLEVELS; i++) {
            m_header.skipWidth[i] = 1;
            m_header.next[i] = &m_footer;
        }
    }

    virtual ~implicit_skiplist() {
        this->clear();
    }

    // Clear all data, release storage and reset state to initial state. O(n).
    void clear(bool releaseNodes = true)
    {
        if (releaseNodes) {
            for (auto itr = this->begin(); itr != this->end();) {
                auto nextItr = itr; nextItr++;
                m_storage.erase(m_storage.get_iterator_from_pointer(itr.m_node));
                itr = nextItr;
            }
        }
        for (int i = 0; i < UAA_IMPLICIT_SKIPLIST_MAXLEVELS; i++) {
            m_header.skipWidth[i] = 1;
            m_header.next[i] = &m_footer;
        }
        m_header.height = 0;
    }

    // Returns n-th element of the skiplist.
    // Expected time complexity is O(log n).
    T& get(uint32_t index)
    {
        auto c = this->find_node(index);
        if (c) {
            return c->data;
        } else {
            return defaultData;
        }
    }

    // Returns n-th element of the skiplist.
    // Expected time complexity is O(log n).
    const T& get(uint32_t index) const
    {
        auto c = this->find_node(index);
        if (c) {
            return c->data;
        } else {
            return defaultData;
        }
    }

    iterator begin(void)
    {
        return make_itr(m_header.next[0]);
    }

    iterator end(void)
    {
        return make_itr(&m_footer);
    }

    void append(T data)
    {
        uint32_t cidx[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];
        Node* update[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];

        // Find the end of each list.
        uint64_t cindex = 0;
        auto maxlvl = m_header.height;
        Node* c = &m_header;

        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &m_footer) {
                cindex += c->skipWidth[i];
                c = c->next[i];
            }
            update[i] = c;
            cidx[i] = cindex;
        }

        // Advance to the insertion target.
        assert(c && c->next[0]);
        if (!c || !c->next[0]) {
            return;
        }
        c = c->next[0];

        // Append a new value.
        auto nlevel = this->random_level();
        if (nlevel > maxlvl) {
            for (int32_t lvl = maxlvl + 1; lvl < nlevel; lvl++) {
                update[lvl] = &m_header;
                cidx[lvl] = 0;
            }
            m_header.height = maxlvl = nlevel;
        }

        // Allocate new node.
        Node *node;
        {
            Node nodeStorage;
            nodeStorage.height = nlevel;
            nodeStorage.data = data;
            auto itr = m_storage.insert(nodeStorage);
            node = &(*itr);
        }
        assert(node);

        // Insert new node into all linked list levels.
        for (int i = 0; i < node->height; i++) {
            // Update skip width.
            assert(cidx[i] <= cindex);
            auto skips = cindex - cidx[i];
            node->skipWidth[i] = 1;
            update[i]->skipWidth[i] = skips + 1;
            assert(node->skipWidth[i] >= 1);
            assert(update[i]->skipWidth[i] >= 1);

            // Update next pointer.
            node->next[i] = update[i]->next[i];
            update[i]->next[i] = node;
        }
    }

    void erase(uint32_t index)
    {
        uint32_t cidx[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];
        Node* update[UAA_IMPLICIT_SKIPLIST_MAXLEVELS];
        index++;

        // Find the update vector for given index.
        uint64_t cindex = 0;
        auto maxlvl = m_header.height;
        Node* c = &m_header;

        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &m_footer && cindex + (uint64_t) c->skipWidth[i] < (uint64_t) index) {
                cindex += c->skipWidth[i];
                c = c->next[i];
            }
            update[i] = c;
            cidx[i] = cindex;
        }

        // Advance to the deletion target.
        assert(c && c->next[0]);
        if (!c || !c->next[0]) {
            return;
        }
        if (cindex + (uint64_t) c->skipWidth[0] != (uint64_t) index) {
            return;
        }
        c = c->next[0];

        // Delete the node from all levels.
        for (int i = 0; i <= maxlvl; i++) {
            if (update[i]->next[i] != c) {
                if (update[i]->next[i] != &m_footer) {
                    update[i]->skipWidth[i]--;
                    assert(update[i]->skipWidth[i] >= 1);
                }
                continue;
            }
            update[i]->next[i] = c->next[i];
            update[i]->skipWidth[i] += c->skipWidth[i];
            update[i]->skipWidth[i]--;
            assert(update[i]->skipWidth[i] >= 1);
        }
        m_storage.erase(m_storage.get_iterator_from_pointer(c));
        while (m_header.height > 0 && m_header.next[m_header.height] == &m_footer) {
            m_header.height--;
        }
    }

    static void split(uint32_t index, implicit_skiplist<T>& list, implicit_skiplist<T>& dest)
    {
        dest.clear();
        uint64_t cindex = 0;
        auto maxlvl = dest.m_header.height = list.m_header.height;
        Node* c = &list.m_header;

        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &list.m_footer && cindex + (uint64_t) c->skipWidth[i] < (uint64_t) index) {
                cindex += c->skipWidth[i];
                c = c->next[i];
            }
            dest.m_header.skipWidth[i] = 1 + (cindex + c->skipWidth[i]) - index;
            dest.m_header.next[i] = c->next[i];
            c->next[i] = &list.m_footer;
            c->skipWidth[i] = 1;
        }

        c = &dest.m_header;
        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &list.m_footer) {
                c = c->next[i];
            }
            c->next[i] = &dest.m_footer;
        }

        while (list.m_header.height > 0 && list.m_header.next[list.m_header.height] == &list.m_footer) {
            list.m_header.height--;
        }
        while (dest.m_header.height > 0 && dest.m_header.next[dest.m_header.height] == &dest.m_footer) {
            dest.m_header.height--;
        }
    }

    void split(uint32_t index, implicit_skiplist<T>& dest)
    {
        split(index, *this, dest);
    }

    static void concatenate(implicit_skiplist<T>& list, implicit_skiplist<T>& src)
    {
        // If maxlvl is too low in our destination, then we need to increase it.
        if (list.m_header.height < src.m_header.height) {
            for (uint32_t i = list.m_header.height + 1; i <= src.m_header.height; i++) {
                list.m_header.next[i] = &list.m_footer;
                list.m_header.skipWidth[i] = 1;
            }
            list.m_header.height = src.m_header.height;
        }

        auto maxlvl = list.m_header.height;
        uint64_t endindex = 0;
        Node* c = &list.m_header;
        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &list.m_footer) {
                endindex += c->skipWidth[i];
                c = c->next[i];
            }
        }

        // Change all the next pointers to point to the start of src lists.
        uint64_t cindex = 0;
        c = &list.m_header;
        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &list.m_footer) {
                cindex += c->skipWidth[i];
                c = c->next[i];
            }
            if (i <= src.m_header.height) {
                c->next[i] = src.m_header.next[i];
                c->skipWidth[i] = (endindex + src.m_header.skipWidth[i]) - cindex;
            }
        }

        c = &src.m_header;
        for (int32_t i = maxlvl; i >= 0; i--) {
            while (c->next[i] != &src.m_footer) {
                c = c->next[i];
            }
            c->next[i] = &list.m_footer;
            c->skipWidth[i] = 1;
        }

        src.clear(false);
    }

    void concatenate(implicit_skiplist<T>& src)
    {
        concatenate(*this, src);
    }

    void debugPrint(void)
    {
    #ifdef UAALIB_DEBUG_PRINT
        printf("===== debug print =====\n");
        for (int i = 0; i < m_header.height; i++) {
            Node *node = &m_header;
            while (node != &m_footer) {
                if (node == &m_header) {
                    printf("Hdr ");
                } else {
                    printf("[%*d]", 2, (int) node->data);
                }
                assert(node->skipWidth[i] >= 1);
                if (node->next[i] != &m_footer) {
                    for (int j = 0; j < (int) node->skipWidth[i] - 1; j++) {
                        printf("--->");
                    }
                }
                node = node->next[i];
            }
            printf("\n");
        }
    #endif
    }

};
 
} // namespace uaa