PiggyList.h

Go to the documentation of this file.

#pragma once
 
#include "souffle/utility/ParallelUtil.h"
#include <array>
#include <atomic>
#include <cassert>
#include <cstring>
#include <iostream>
#include <iterator>
 
#ifdef _WIN32
/**
 * Some versions of MSVC do not provide a builtin for counting leading zeroes
 * like gcc, so we have to implement it ourselves.
 */
#if defined(_MSC_VER)
unsigned long __inline __builtin_clzll(unsigned long long value) {
    unsigned long msb = 0;
 
    if (_BitScanReverse64(&msb, value))
        return 63 - msb;
    else
        return 64;
}
#endif  // _MSC_VER
#endif  // _WIN32
 
using std::size_t;
namespace souffle {
 
/**
 * A PiggyList that allows insertAt functionality.
 * This means we can't append, as we don't know the next available element.
 * insertAt is dangerous. You must be careful not to call it for the same index twice!
 */
template <class T>
class RandomInsertPiggyList {
public:
    RandomInsertPiggyList() = default;
    // an instance where the initial size is not 65k, and instead is user settable (to a power of
    // initialbitsize)
    RandomInsertPiggyList(size_t initialbitsize) : BLOCKBITS(initialbitsize) {}
 
    /** copy constructor */
    RandomInsertPiggyList(const RandomInsertPiggyList& other) : BLOCKBITS(other.BLOCKBITS) {
        this->numElements.store(other.numElements.load());
 
        // copy blocks from the old lookup table to this one
        for (size_t i = 0; i < maxContainers; ++i) {
            if (other.blockLookupTable[i].load() != nullptr) {
                // calculate the size of that block
                const size_t blockSize = INITIALBLOCKSIZE << i;
 
                // allocate that in the new container
                this->blockLookupTable[i].store(new T[blockSize]);
 
                // then copy the stuff over
                std::memcpy(this->blockLookupTable[i].load(), other.blockLookupTable[i].load(),
                        blockSize * sizeof(T));
            }
        }
    }
 
    // move ctr
    RandomInsertPiggyList(RandomInsertPiggyList&& other) = delete;
    // copy assign ctor
    RandomInsertPiggyList& operator=(RandomInsertPiggyList& other) = delete;
    // move assign ctor
    RandomInsertPiggyList& operator=(RandomInsertPiggyList&& other) = delete;
 
    ~RandomInsertPiggyList() {
        freeList();
    }
 
    inline size_t size() const {
        return numElements.load();
    }
 
    inline T* getBlock(size_t blockNum) const {
        return blockLookupTable[blockNum];
    }
 
    inline T& get(size_t index) const {
        size_t nindex = index + INITIALBLOCKSIZE;
        size_t blockNum = (63 - __builtin_clzll(nindex));
        size_t blockInd = (nindex) & ((1 << blockNum) - 1);
        return this->getBlock(blockNum - BLOCKBITS)[blockInd];
    }
 
    void insertAt(size_t index, T value) {
        // starting with an initial blocksize requires some shifting to transform into a nice powers of two
        // series
        size_t blockNum = (63 - __builtin_clzll(index + INITIALBLOCKSIZE)) - BLOCKBITS;
 
        // allocate the block if not allocated
        if (blockLookupTable[blockNum].load() == nullptr) {
            slock.lock();
            if (blockLookupTable[blockNum].load() == nullptr) {
                blockLookupTable[blockNum].store(new T[INITIALBLOCKSIZE << blockNum]);
            }
            slock.unlock();
        }
 
        this->get(index) = value;
        // we ALWAYS increment size, even if there was something there before (its impossible to tell!)
        // the onus is up to the user to not call this for an index twice
        ++numElements;
    }
 
    void clear() {
        freeList();
        numElements.store(0);
    }
    const size_t BLOCKBITS = 16ul;
    const size_t INITIALBLOCKSIZE = (1ul << BLOCKBITS);
 
    // number of elements currently stored within
    std::atomic<size_t> numElements{0};
 
    // 2^64 - 1 elements can be stored (default initialised to nullptrs)
    static constexpr size_t maxContainers = 64;
    std::array<std::atomic<T*>, maxContainers> blockLookupTable = {};
 
    // for parallel node insertions
    mutable SpinLock slock;
 
    /**
     * Free the arrays allocated within the linked list nodes
     */
    void freeList() {
        slock.lock();
        // delete all - deleting a nullptr is a no-op
        for (size_t i = 0; i < maxContainers; ++i) {
            delete[] blockLookupTable[i].load();
            // reset the container within to be empty.
            blockLookupTable[i].store(nullptr);
        }
        slock.unlock();
    }
};
 
template <class T>
class PiggyList {
public:
    PiggyList() : num_containers(0), container_size(0), m_size(0) {}
    PiggyList(size_t initialbitsize)
            : BLOCKBITS(initialbitsize), num_containers(0), container_size(0), m_size(0) {}
 
    /** copy constructor */
    PiggyList(const PiggyList& other) : BLOCKBITS(other.BLOCKBITS) {
        num_containers.store(other.num_containers.load());
        container_size.store(other.container_size.load());
        m_size.store(other.m_size.load());
        // copy each chunk from other into this
        // the size of the next container to allocate
        size_t cSize = BLOCKSIZE;
        for (size_t i = 0; i < other.num_containers; ++i) {
            this->blockLookupTable[i] = new T[cSize];
            std::memcpy(this->blockLookupTable[i], other.blockLookupTable[i], cSize * sizeof(T));
            cSize <<= 1;
        }
        // if this isn't the case, uhh
        assert((cSize >> 1) == container_size.load());
    }
 
    /** move constructor */
    PiggyList(PiggyList&& other) = delete;
    /** copy assign ctor **/
    PiggyList& operator=(const PiggyList& other) = delete;
 
    ~PiggyList() {
        freeList();
    }
 
    /**
     * Well, returns the number of nodes exist within the list + number of nodes queued to be inserted
     *  The reason for this, is that there may be many nodes queued up
     *  that haven't had time to had containers created and updated
     * @return the number of nodes exist within the list + number of nodes queued to be inserted
     */
    inline size_t size() const {
        return m_size.load();
    };
 
    inline T* getBlock(size_t blocknum) const {
        return this->blockLookupTable[blocknum];
    }
 
    size_t append(T element) {
        size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
 
        // will this not fit?
        if (container_size < new_index + 1) {
            sl.lock();
            // check and add as many containers as required
            while (container_size < new_index + 1) {
                blockLookupTable[num_containers] = new T[allocsize];
                num_containers += 1;
                container_size += allocsize;
                // double the number elements that will be allocated next time
                allocsize <<= 1;
            }
            sl.unlock();
        }
 
        this->get(new_index) = element;
        return new_index;
    }
 
    size_t createNode() {
        size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
 
        // will this not fit?
        if (container_size < new_index + 1) {
            sl.lock();
            // check and add as many containers as required
            while (container_size < new_index + 1) {
                blockLookupTable[num_containers] = new T[allocsize];
                num_containers += 1;
                container_size += allocsize;
                // double the number elements that will be allocated next time
                allocsize <<= 1;
            }
            sl.unlock();
        }
 
        return new_index;
    }
 
    /**
     * Retrieve a reference to the stored value at index
     * @param index position to search
     * @return the value at index
     */
    inline T& get(size_t index) const {
        // supa fast 2^16 size first block
        size_t nindex = index + BLOCKSIZE;
        size_t blockNum = (63 - __builtin_clzll(nindex));
        size_t blockInd = (nindex) & ((1 << blockNum) - 1);
        return this->getBlock(blockNum - BLOCKBITS)[blockInd];
    }
 
    /**
     * Clear all elements from the PiggyList
     */
    void clear() {
        freeList();
        m_size = 0;
        num_containers = 0;
 
        allocsize = BLOCKSIZE;
        container_size = 0;
    }
 
    class iterator : std::iterator<std::forward_iterator_tag, T> {
        size_t cIndex = 0;
        PiggyList* bl;
 
    public:
        // default ctor, to silence
        iterator() = default;
 
        /* begin iterator for iterating over all elements */
        iterator(PiggyList* bl) : bl(bl){};
        /* ender iterator for marking the end of the iteration */
        iterator(PiggyList* bl, size_t beginInd) : cIndex(beginInd), bl(bl){};
 
        T operator*() {
            return bl->get(cIndex);
        };
        const T operator*() const {
            return bl->get(cIndex);
        };
 
        iterator& operator++(int) {
            ++cIndex;
            return *this;
        };
 
        iterator operator++() {
            iterator ret(*this);
            ++cIndex;
            return ret;
        };
 
        bool operator==(const iterator& x) const {
            return x.cIndex == this->cIndex && x.bl == this->bl;
        };
 
        bool operator!=(const iterator& x) const {
            return !(x == *this);
        };
    };
 
    iterator begin() {
        return iterator(this);
    }
    iterator end() {
        return iterator(this, size());
    }
    const size_t BLOCKBITS = 16ul;
    const size_t BLOCKSIZE = (1ul << BLOCKBITS);
 
    // number of inserted
    std::atomic<size_t> num_containers = 0;
    size_t allocsize = BLOCKSIZE;
    std::atomic<size_t> container_size = 0;
    std::atomic<size_t> m_size = 0;
 
    // > 2^64 elements can be stored (default initialise to nullptrs)
    static constexpr size_t max_conts = 64;
    std::array<T*, max_conts> blockLookupTable = {};
 
    // for parallel node insertions
    mutable SpinLock sl;
 
    /**
     * Free the arrays allocated within the linked list nodes
     */
    void freeList() {
        sl.lock();
        // we don't know which ones are taken up!
        for (size_t i = 0; i < num_containers; ++i) {
            delete[] blockLookupTable[i];
        }
        sl.unlock();
    }
};
 
}  // namespace souffle