#ifndef _atomichashset_hpp
#define _atomichashset_hpp

#include <stddef.h>
#include <atomic>
#include <functional>

template <typename T>
class AtomicHashSet
{
private:
    /*
     * the reserved state is added to reserve a position, before
     * storing the pointer to the given key. after storing is
     * completed the state should be set to occupied.
     */
    enum class State {
        Empty, Occupied, Deleted
    };

    typedef struct entry {
        State state;
        const T* element;
    } entry_t ;

    static const size_t max_size = 128;
    std::atomic<entry_t> elements[max_size];
    std::atomic<size_t> size_counter;

private:
    size_t bound(size_t pos) const {
        return pos % max_size;
    }

    size_t getHash(const T&key) const {
        return bound(std::hash<const T*>()(&key));
    }

    bool isEmpty(entry_t& entry) const {
        return entry.state == State::Empty;
    }

    bool isFree(entry_t& entry) const {
        State state = entry.state;
        return state == State::Empty || state == State::Deleted;
    }

    bool isOccupied(entry_t& entry) const {
        return entry.state == State::Occupied;
    }

    /*
     * sets the state of the given position to deleted, when it
     * was occupied.
     *
     * returns true, when possible,
     * false otherwise.
     */
    bool remove(size_t pos) {
        entry_t given = elements[pos].load();
        entry_t replace = {State::Deleted, nullptr};
        if (!isOccupied(given)) return false;
        return elements[pos].compare_exchange_weak(
                given, replace);
    }

    bool replaceWhenFree(size_t pos, entry_t insertEntry) {
        entry_t expect = elements[pos].load();
        if (!isFree(expect)) return false;
        return elements[pos].compare_exchange_weak(
                expect, insertEntry);
    }

    /*
     * returns true when the element is contained, also stores
     * the position of that element in "position"
     */
    bool contains(const T& key, size_t& position) const {
        size_t pos = getHash(key);
        size_t end = bound(pos-1);

        entry_t entry = elements[pos].load();

        while (pos != end && !isEmpty(entry)
                && !(isOccupied(entry) && entry.element == &key)) {
            pos = bound(pos + 1);
            entry = elements[pos].load();
        }

        position = pos;
        return isOccupied(entry) && entry.element == &key;
    }

    /*
     * searches for a deleted or empty position for the given key.
     * returns the free position. aborts, when the element is already
     * within.
     */
    size_t findFree(const T& key) const {
        size_t pos = getHash(key);
        size_t end = bound(pos-1);

        entry_t entry = elements[pos].load();
        while (pos != end && isOccupied(entry)
            && !(isOccupied(entry) && entry.element == &key)) {
            pos = bound(pos+1);
            entry = elements[pos].load();
        }

        return pos;
    }

public:
    AtomicHashSet() : size_counter{0} {
        for (size_t i = 0; i < max_size; i++) {
            entry_t entry = {State::Empty, nullptr};
            elements[i].store(entry);
        }
    }

    bool contains(const T& key) const {
        size_t pos = 0;
        return contains(key, pos);
    }

    bool insert (const T& key) {
        size_t pos = 0;
        entry_t insertEntry = {State::Occupied, &key};

        bool success = false;

        do {
            // this can only abort too early
            if (size() == max_size) return false;

            // return if the element is already contained
            bool contained = contains(key, pos);
            if (contained) return false;

            // find free place
            pos = findFree(key);

            // try to insert element
            success = replaceWhenFree(pos, insertEntry);
        } while (!success);

        size_counter++;

        return true;
    }

    size_t size() const {
        return size_counter.load();
    }

    bool remove(const T& key) {
        size_t pos = 0;
        bool contained = contains(key, pos);
        if (!contained) return false;
        if (remove(pos)) {
            size_counter--;
            return true;
        }
        return false;
    }
};

#endif