RBTree.hxx

Go to the documentation of this file.

 
#ifndef _UTILS_RBTREE_HXX_
#define _UTILS_RBTREE_HXX_
 
extern "C"
{
#include <sys/tree.hxx>
};
 
#include "utils/macros.h"
 
template <typename Key, typename Value> class RBTree
{
public:
    RBTree()
        : freeList(NULL)
    {
        RB_INIT(&head);
    }
 
    RBTree(size_t nodes)
        : freeList(NULL)
    {
        RB_INIT(&head);
        Node *first = new Node[nodes];
        first->entry.rbe_left = (Node*)this;
        
        for (size_t i = 1; i < nodes; i++)
        {
            first[i].entry.rbe_left = freeList;
            freeList = first + i;
        }
    }
 
    struct Node
    {
    public:
        RB_ENTRY(Node) entry;
        Key key; 
        Value value; 
        Node()
        {
        }
        
        Node(Key key, Value value)
            : key(key),
              value(value)
        {
        }
    };
 
    Node *insert(Key key, Value value)
    {
        Node *node = find(key);
        if (node)
        {
            node->value = value;
        }
        else
        {
            node = alloc();
            if (node)
            {
                node->key = key;
                node->value = value;
                insert(node);
            }
        }
        return node;
    }
 
    void insert(Node *node)
    {
        RB_INSERT(tree, &head, node);
    }
 
    void remove(Node *node)
    {
        RB_REMOVE(tree, &head, node);
        free(node);
    }
    
    Node *remove(Key key)
    {
        Node *node = find(key);
        if (node)
        {
            remove(node);
            free(node);
        }
        return node;
    }
    
    Node *find(Key key)
    {
        Node lookup;
        
        lookup.key = key;
        
        return RB_FIND(tree, &head, &lookup);
    };
    
    Node *first()
    {
        return RB_MIN(tree, &head);
    }
    
    Node *last()
    {
        return RB_MAX(tree, &head);
    }
 
    Node *next(Node *node)
    {
        return RB_NEXT(tree, &head, node);
    }
    
    Node *next(Key key)
    {
        Node *node = find(key);
        return node ? RB_NEXT(tree, &head, node) : node;
    }
    
    Node *previous(Node *node)
    {
        return RB_PREV(tree, &head, node);
    }
    
    ~RBTree()
    {
    }
    
private:
    Node *alloc()
    {
        if (freeList && freeList != (Node*)this)
        {
            Node *node = freeList;
            freeList = freeList->entry.rbe_left;
            return node;
        }
        return NULL;
    }
    
    void free(Node *node)
    {
        if (freeList || freeList == (Node*)this)
        {
            node->entry.rbe_left = freeList;
            freeList = node;
        }
    }
 
    Key compare(Node *a, Node *b)
    {
        return a->key - b->key;
    }
 
    Node *freeList;
 
    RB_HEAD(tree, Node);
 
    RB_GENERATE(tree, Node, entry, compare);
    
    struct tree head;
    
    DISALLOW_COPY_AND_ASSIGN(RBTree);
};
 
#endif /* _UTILS_RBTREE_HXX_ */