multi_clock.hpp

Go to the documentation of this file.

#ifndef __MULTI_CLOCK_HPP
#define __MULTI_CLOCK_HPP

#include "multi_clock_exceptions.hpp"

#include <cstdint>
#include <cstring>
#include <vector>
#include <array>

namespace zero::multi_clock {

    typedef uint32_t ClockIndex;

    template<class key_type,
             class value_type, uint32_t clock_count, key_type invalid_index, key_type invalid_clock_index = clock_count>
    class MultiHandedClock {
    public:
        MultiHandedClock(key_type entryCount) :
                _entryCount(entryCount),
                _values(_entryCount),
                _clocks(_entryCount),
                _clockMembership(_entryCount, invalid_clock_index) {
            _hands.fill(invalid_index);
            _sizes.fill(0);
        };

        ~MultiHandedClock() {};

        template<ClockIndex clock>
        void getHead(value_type& head) const {
            static_assert(clock < clock_count);
            if (!isEmpty<clock>()) {
                w_assert1(_clockMembership[_hands[clock]] == clock);
                head = _values[_hands[clock]];
            } else {
                w_assert1(_hands[clock] == invalid_index);
                throw MultiHandedClockEmptyException<key_type, value_type, clock_count, invalid_index,
                                                     invalid_clock_index>(this, clock);
            }
        };

        template<ClockIndex clock>
        void setHead(const value_type newValue) {
            static_assert(clock < clock_count);
            if (!isEmpty<clock>()) {
                _values[_hands[clock]] = newValue;
            } else {
                throw MultiHandedClockEmptyException<key_type, value_type, clock_count, invalid_index,
                                                     invalid_clock_index>(this, clock);
            }
        };

        template<ClockIndex clock>
        void getHeadIndex(key_type& headIndex) const {
            static_assert(clock < clock_count);
            if (!isEmpty<clock>()) {
                w_assert1(_clockMembership[_hands[clock]] == clock);
                headIndex = _hands[clock];
            } else {
                throw MultiHandedClockEmptyException<key_type, value_type, clock_count, invalid_index,
                                                     invalid_clock_index>(this, clock);
            }
        };

        template<ClockIndex clock>
        void moveHead() {
            static_assert(clock < clock_count);
            if (!isEmpty<clock>()) {
                _hands[clock] = _clocks[_hands[clock]]._after;
                w_assert1(_clockMembership[_hands[clock]] == clock);
            } else {
                throw MultiHandedClockEmptyException<key_type, value_type, clock_count, invalid_index,
                                                     invalid_clock_index>(this, clock);
            }
        };

        template<ClockIndex clock>
        void addTail(const key_type& index) {
            static_assert(clock < clock_count);
            if (!isValidIndex(index)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, index);
            } else if (isContainedIndex(index)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, index);
            } else {
                if (isEmpty<clock>()) {
                    _hands[clock] = index;
                    _clocks[index]._before = index;
                    _clocks[index]._after = index;
                } else {
                    _clocks[index]._before = _clocks[_hands[clock]]._before;
                    _clocks[index]._after = _hands[clock];
                    _clocks[_clocks[_hands[clock]]._before]._after = index;
                    _clocks[_hands[clock]]._before = index;
                }
                _sizes[clock]++;
                _clockMembership[index] = clock;
            }
        };

        template<ClockIndex clock>
        void addTail(key_type&& index) {
            static_assert(clock < clock_count);
            if (!isValidIndex(index)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, index);
            } else if (isContainedIndex(index)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, index);
            } else {
                if (isEmpty<clock>()) {
                    _hands[clock] = index;
                    _clocks[index]._before = index;
                    _clocks[index]._after = index;
                } else {
                    _clocks[index]._before = _clocks[_hands[clock]]._before;
                    _clocks[index]._after = _hands[clock];
                    _clocks[_clocks[_hands[clock]]._before]._after = index;
                    _clocks[_hands[clock]]._before = index;
                }
                _sizes[clock]++;
                _clockMembership[index] = clock;
            }
        };

        void addBefore(const key_type& inside, const key_type& newEntry) {
            if (isValidIndex(newEntry)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, newEntry);
            } else if (isValidIndex(inside)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, inside);
            } else if (isContainedIndex(newEntry)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, newEntry);
            } else if (!isContainedIndex(inside)) {
                MultiHandedClockNotContainedException<key_type, value_type, clock_count, invalid_index,
                                                      invalid_clock_index>(this, inside);
            } else {
                w_assert1(_sizes[_clockMembership[inside]] >= 1);
                _clocks[newEntry]._before = _clocks[inside]._before;
                _clocks[newEntry]._after = inside;
                _clocks[inside]._before = newEntry;
                _clockMembership[newEntry] = _clockMembership[inside];
                _sizes[_clockMembership[inside]]++;
            }
        };

        void addBefore(const key_type& inside, key_type&& newEntry) {
            if (isValidIndex(newEntry)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, newEntry);
            } else if (isValidIndex(inside)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, inside);
            } else if (isContainedIndex(newEntry)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, newEntry);
            } else if (!isContainedIndex(inside)) {
                MultiHandedClockNotContainedException<key_type, value_type, clock_count, invalid_index,
                                                      invalid_clock_index>(this, inside);
            } else {
                w_assert1(_sizes[_clockMembership[inside]] >= 1);
                _clocks[newEntry]._before = _clocks[inside]._before;
                _clocks[newEntry]._after = inside;
                _clocks[inside]._before = newEntry;
                _clockMembership[newEntry] = _clockMembership[inside];
                _sizes[_clockMembership[inside]]++;
            }
        };

        void addAfter(const key_type& inside, const key_type& newEntry) {
            if (isValidIndex(newEntry)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, newEntry);
            } else if (isValidIndex(inside)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, inside);
            } else if (isContainedIndex(newEntry)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, newEntry);
            } else if (!isContainedIndex(inside)) {
                MultiHandedClockNotContainedException<key_type, value_type, clock_count, invalid_index,
                                                      invalid_clock_index>(this, inside);
            } else {
                w_assert1(_sizes[_clockMembership[inside]] >= 1);
                _clocks[newEntry]._after = _clocks[inside]._after;
                _clocks[newEntry]._before = inside;
                _clocks[inside]._after = newEntry;
                _clockMembership[newEntry] = _clockMembership[inside];
                _sizes[_clockMembership[inside]]++;
            }
        };

        void addAfter(const key_type& inside, const key_type&& newEntry) {
            if (isValidIndex(newEntry)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, newEntry);
            } else if (isValidIndex(inside)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, inside);
            } else if (isContainedIndex(newEntry)) {
                throw MultiHandedClockAlreadyContainedException<key_type, value_type, clock_count, invalid_index,
                                                                invalid_clock_index>(this, newEntry);
            } else if (!isContainedIndex(inside)) {
                MultiHandedClockNotContainedException<key_type, value_type, clock_count, invalid_index,
                                                      invalid_clock_index>(this, inside);
            } else {
                w_assert1(_sizes[_clockMembership[inside]] >= 1);
                _clocks[newEntry]._after = _clocks[inside]._after;
                _clocks[newEntry]._before = inside;
                _clocks[inside]._after = newEntry;
                _clockMembership[newEntry] = _clockMembership[inside];
                _sizes[_clockMembership[inside]]++;
            }
        };

        template<ClockIndex clock>
        void removeHead(key_type& removedIndex) {
            static_assert(clock < clock_count);
            if (!isEmpty<clock>()) {
                removedIndex = _hands[clock];
                remove(removedIndex);
            } else {
                w_assert1(_hands[clock] == invalid_index);
                throw MultiHandedClockEmptyException<key_type, value_type, clock_count, invalid_index,
                                                     invalid_clock_index>(this, clock);
            }
        };

        void remove(const key_type& index) {
            if (!isValidIndex(index)) {
                throw MultiHandedClockInvalidIndexException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, index);
            } else if (!isContainedIndex(index)) {
                throw MultiHandedClockNotContainedException<key_type, value_type, clock_count, invalid_index,
                                                            invalid_clock_index>(this, index);
            } else {
                ClockIndex clock = _clockMembership[index];
                if (_sizes[clock] == 1) {
                    w_assert1(_hands[clock] >= 0 && _hands[clock] <= _entryCount - 1 && _hands[clock] != invalid_index);
                    w_assert1(_clocks[_hands[clock]]._before == _hands[clock]);
                    w_assert1(_clocks[_hands[clock]]._after == _hands[clock]);

                    _clocks[index]._before = invalid_index;
                    _clocks[index]._after = invalid_index;
                    _hands[clock] = invalid_index;
                    _clockMembership[index] = invalid_clock_index;
                    _sizes[clock]--;
                } else {
                    _clocks[_clocks[index]._before]._after = _clocks[index]._after;
                    _clocks[_clocks[index]._after]._before = _clocks[index]._before;
                    _hands[clock] = _clocks[index]._after;
                    _clocks[index]._before = invalid_index;
                    _clocks[index]._after = invalid_index;
                    _clockMembership[index] = invalid_clock_index;
                    _sizes[clock]--;

                    w_assert1(_hands[clock] != invalid_index);
                }
            }
        };

        template<ClockIndex source, ClockIndex destination>
        void switchHeadToTail(key_type& movedIndex) {
            static_assert(source < clock_count);
            static_assert(destination < clock_count);
            movedIndex = invalid_index;
            removeHead<source>(movedIndex);

            w_assert1(movedIndex != invalid_index);

            addTail<destination>(movedIndex);
        };

        template<ClockIndex clock>
        inline key_type sizeOf() const noexcept {
            static_assert(clock < clock_count);
            return _sizes[clock];
        }

        template<ClockIndex clock>
        inline bool isEmpty() const noexcept {
            static_assert(clock < clock_count);
            return sizeOf<clock>() == 0;
        }

        inline bool isValidIndex(const key_type& index) const noexcept {
            return index != invalid_index && index >= 0 && index <= _entryCount - 1;
        }

        inline bool isContainedIndex(const key_type& index) const noexcept {
            return isValidIndex(index) && _clockMembership[index] != invalid_clock_index;
        }

        inline value_type& get(const key_type& index) noexcept {
            if (isValidIndex(index)) {
                return _values[index];
            } else {
                return _values[invalid_index];
            }
        }

        inline const value_type& get(const key_type& index) const noexcept {
            if (isValidIndex(index)) {
                return _values[index];
            } else {
                return _values[invalid_index];
            }
        }

        inline void set(const key_type& index, const value_type& newValue) noexcept {
            if (isValidIndex(index)) {
                _values[index] = newValue;
            }
        }

        inline void set(const key_type& index, value_type&& newValue) noexcept {
            if (isValidIndex(index)) {
                _values[index] = newValue;
            }
        }

        inline value_type& operator[](const key_type& index) noexcept {
            if (isValidIndex(index)) {
                return _values[index];
            } else {
                return _values[invalid_index];
            }
        }

        inline const value_type& operator[](const key_type& index) const noexcept {
            if (isValidIndex(index)) {
                return _values[index];
            } else {
                return _values[invalid_index];
            }
        }

        inline ClockIndex& getClockIndex(const key_type& index) noexcept {
            if (isValidIndex(index)) {
                return _clockMembership[index];
            } else {
                return invalid_clock_index;
            }
        }

        inline const ClockIndex& getClockIndex(const key_type& index) const noexcept {
            if (isValidIndex(index)) {
                return _clockMembership[index];
            } else {
                return invalid_clock_index;
            }
        }

    private:
        class IndexPair {
        public:
            IndexPair() {};

            IndexPair(const key_type& before, const key_type& after) :
                    _before(before),
                    _after(after) {};

            key_type _before;

            key_type _after;
        };

        key_type _entryCount;

        std::vector<value_type> _values;

        std::vector<IndexPair> _clocks;

        std::vector<ClockIndex> _clockMembership;

        std::array<key_type, clock_count> _hands;

        std::array<key_type, clock_count> _sizes;
    };
} // zero::multi_clock

#endif // __MULTI_CLOCK_HPP