SysMap.hxx

Go to the documentation of this file.

 
#ifndef _UTILS_SYSMAP_HXX_
#define _UTILS_SYSMAP_HXX_
 
#include <sys/tree.hxx>
#include <cstdint>
 
#include "utils/macros.h"
 
template <typename Key, typename Value> class SysMap
{
public:
    SysMap()
        : entries(0),
          used(0),
          freeList(NULL),
          nodes(NULL)
 
    {
        clear();
    }
 
    SysMap(size_t entries)
        : entries(entries),
          used(0),
          freeList(NULL),
          nodes(NULL)
    {
        if (entries) {
            nodes = new Node[entries];
        }
        clear();
    }
 
    ~SysMap()
    {
        delete nodes;
    }
    
    struct Pair
    {
        Key first; 
        Value second; 
    };
 
private:
    struct Node
    {
    public:
        RB_ENTRY(Node) entry;
        union
        {
            Pair p; 
            struct
            {
                Key key; 
                Value value; 
            };
        };
 
        Node() = default;
    };
 
public:
    class Iterator
    {
    public:
        Iterator()
            : node(NULL),
              m(NULL)
        {
        }
        
        Iterator(const Iterator &it)
            : node(it.node),
              m(it.m)
        {
        }
        
        Iterator(SysMap* context, Node *node)
            : node(node),
              m(context)
            
        {
        }
 
        ~Iterator()
        {
        }
        
        Pair &operator*() const
        {
            return node->p;
        }
 
        Pair *operator->() const
        {
            return &node->p;
        }
 
        Iterator &operator ++ ()
        {
            if (node)
            {
                node = RB_NEXT(m->tree, &(m->head), node);
            }
            return *this;
        }
 
        bool operator != (const Iterator &it)
        {
            return node != it.node;
        }
 
        bool operator == (const Iterator &it)
        {
            return node == it.node;
        }
 
    private:
        Node *node;
        
        SysMap *m;
 
        friend class SysMap;
    };
    
    Value &operator[](const Key &key)
    {
        Iterator it = find(key);
        if (it == end())
        {
            Node *node = alloc();
            HASSERT(node);
            node->key = key;
            node->value = (Value)0;
            HASSERT(RB_INSERT(tree, &head, node) == NULL);
            it = Iterator(this, node);
        }
        return (*it).second;
    }
 
    size_t size()
    {
        return used;
    }
 
    size_t max_size()
    {
        return entries ? entries : UINTPTR_MAX / sizeof(Pair);
    }
 
    void clear()
    {
        RB_INIT(&head);
        used = 0;
        if (entries)
        {
            nodes->entry.rbe_left = NULL;
 
            for (size_t i = 1; i < entries; ++i)
            {
                nodes[i].entry.rbe_left = nodes + (i - 1);
            }
            freeList = nodes + (entries - 1);
        }
    }
 
    Iterator find(const Key &key)
    {
        Node lookup;
        lookup.key = key;
        Node *node = RB_FIND(tree, &head, &lookup);
        
        return node ? Iterator(this, node) : Iterator();
    }
    
    Iterator end()
    {
        return Iterator();
    }
 
    Iterator begin()
    {
        Node *node = RB_MIN(tree, &head);
        
        return node ? Iterator(this, node) : Iterator();
    }
 
    size_t erase(Key key)
    {
        Node lookup;
        lookup.key = key;
        Node *node = RB_FIND(tree, &head, &lookup);
 
        if (node)
        {
            RB_REMOVE(tree, &head, node);
            free(node);
            return 1;
        }
        return 0;
    }
    
    void erase(Iterator it)
    {
        Node *node = it.node;
        if (node)
        {
            RB_REMOVE(tree, &head, node);
            free(node);
        }
    }
 
private:
    Node *alloc()
    {
        if (nodes)
        {
            if (freeList != NULL)
            {
                Node *node = freeList;
                freeList = freeList->entry.rbe_left;
                memset(node, 0, sizeof(Node));
                ++used;
                return node;
            }
            return NULL;
        }
        else
        {
            Node *node = new Node;
            memset(node, 0, sizeof(Node));
            ++used;
            return node;
        }
 
    }
    
    void free(Node *node)
    {
        if (nodes)
        {
            node->entry.rbe_left = freeList;
            freeList = node;
            --used;
        }
        else
        {
            --used;
            delete node;
        }
    }
 
    int64_t compare(Node *a, Node *b)
    {
        union comp
        {
            int64_t s;
            Key     k;
        };
        
        comp ca, cb;
        ca.s = 0;
        cb.s = 0;
        ca.k = a->key;
        cb.k = b->key;
        
        return ca.s - cb.s;
    }
 
    size_t entries;
 
    size_t used;
 
    Node *freeList;
    
    Node *nodes;
 
    RB_HEAD(tree, Node);
 
    RB_GENERATE(tree, Node, entry, compare);
    
    struct tree head;
 
    DISALLOW_COPY_AND_ASSIGN(SysMap);
};
 
#endif /* _UTILS_SYSMAP_HXX_ */