BTreeList.h

Go to the documentation of this file.

/*
 * Copyright (c) 2018 https://www.thecoderscorner.com (Dave Cherry)
 * This product is licensed under an Apache license, see the LICENSE file in the top-level directory.
 */

 
#ifndef TASKMANAGER_IO_COLLECTIONS_H
#define TASKMANAGER_IO_COLLECTIONS_H
 
#include <string.h>
#include <inttypes.h>
#include "TaskPlatformDeps.h"
 
namespace tccollection {
 
    enum GrowByMode : unsigned char {
        GROW_NEVER,
        GROW_BY_5,
        GROW_BY_DOUBLE
    };
 
}
 
#ifdef __AVR_ATmega2560__
# define DEFAULT_LIST_SIZE 10
# define DEFAULT_GROW_MODE GROW_BY_5
typedef uint8_t bsize_t;
#elif defined(__AVR__)
# define DEFAULT_LIST_SIZE 5
# define DEFAULT_GROW_MODE GROW_BY_5
typedef uint8_t bsize_t;
#else
# define DEFAULT_LIST_SIZE 10
# define DEFAULT_GROW_MODE GROW_BY_DOUBLE
typedef size_t bsize_t;
#endif
 
 
namespace ioaTreeInternal {
 
    typedef uint32_t (*KeyAccessor)(const void *item);
 
    typedef void (*CopyOperator)(void *dest, const void *src);

    class BtreeStorage {
    private:
        void *binTree;
        void *swapperSpace;
        KeyAccessor keyAccessor;
        CopyOperator copier;
        bsize_t currentCapacity;
        bsize_t currentSize;
        bsize_t sizeOfAnItem;
        tccollection::GrowByMode growByMode;
    public:
        BtreeStorage(bsize_t size, tccollection::GrowByMode howToGrow, bsize_t eachItemSize, KeyAccessor compareOperator,
                     CopyOperator copyOperator);
 
        ~BtreeStorage();
 
        bool add(const void *newItem);
 
        bool removeByKey(uint32_t key);
 
        void removeIndex(bsize_t index);
 
        bsize_t nearestLocation(uint32_t key) const;
 
        void *getByKey(uint32_t key) const;
 
        void clear() { currentSize = 0; }
 
        void *underlyingData() const { return binTree; }
 
        bsize_t getCapacity() const { return currentCapacity; }
 
        bsize_t getCurrentSize() const { return currentSize; }
 
    private:
        bool checkCapacity();
        void *memoryOf(void *baseMem, bsize_t item) const { return static_cast<uint8_t*>(baseMem) + (item * sizeOfAnItem); }
    };
}
 
namespace tccollection {

    template<class T>
    class BtreeIterator {
    private:
        bsize_t currentPosition;
        const ioaTreeInternal::BtreeStorage &storage;
    public:
        BtreeIterator(bsize_t position, const ioaTreeInternal::BtreeStorage &storage) : currentPosition(position),
                                                                                  storage(storage) {}
 
        void operator++() { ++currentPosition; }
 
        bool operator!=(const BtreeIterator &other) const { return currentPosition != other.currentPosition; }
 
        T &operator*() { return ((T *) storage.underlyingData())[currentPosition]; }
    };

    template<class K, class V>
    class BtreeList {
    private:
        ioaTreeInternal::BtreeStorage treeStorage;
    public:
        explicit BtreeList(bsize_t size = DEFAULT_LIST_SIZE, GrowByMode howToGrow = DEFAULT_GROW_MODE)
                : treeStorage(size, howToGrow, sizeof(V), keyAccessor, copyInternal) {}

        explicit BtreeList(ioaTreeInternal::KeyAccessor customAccessor, bsize_t size = DEFAULT_LIST_SIZE, GrowByMode howToGrow = DEFAULT_GROW_MODE)
                : treeStorage(size, howToGrow, sizeof(V), customAccessor, copyInternal) {}
 
        static uint32_t keyAccessor(const void *itm) {
            return reinterpret_cast<const V *>(itm)->getKey();
        }
 
        static void copyInternal(void *dest, const void *src) {
            auto *itemDest = reinterpret_cast<V *>(dest);
            auto *itemSrc = reinterpret_cast<const V *>(src);
            *itemDest = *itemSrc;
        }

        bool add(const V &item) { return treeStorage.add(&item); }

        V *getByKey(K key) const { return reinterpret_cast<V *>(treeStorage.getByKey(key)); };

        bool removeByKey(K key) { return treeStorage.removeByKey(key); }

        void removeIndex(bsize_t index) { treeStorage.removeIndex(index); }

        bsize_t nearestLocation(const K &key) const { return treeStorage.nearestLocation(key); }

        const V *items() const { return reinterpret_cast<V *>(treeStorage.underlyingData()); };

        V *itemAtIndex(bsize_t idx) const {
            auto *binTree = reinterpret_cast<V *>(treeStorage.underlyingData());
            return (idx < treeStorage.getCurrentSize()) ? &binTree[idx] : NULL;
        }

        bsize_t count() const {
            return treeStorage.getCurrentSize();
        }

        bsize_t capacity() const { return treeStorage.getCapacity(); }

        void clear() { treeStorage.clear(); }

        BtreeIterator<V> begin() const { return BtreeIterator<V>(0, treeStorage); }

        BtreeIterator<V> end() const { return BtreeIterator<V>(treeStorage.getCurrentSize(), treeStorage); }

        void forEachItem(void(*paramFn)(V *)) {
            for (bsize_t i = 0; i < count(); ++i) {
                paramFn(itemAtIndex(i));
            }
        }
    };
}
 
#ifndef TC_COLLECTION_MANUAL_NAMESPACE
using namespace tccollection;
#endif
 
#endif