rbt.hh

/*
 * rbt.hh - Set of methods and structures used to create and manage red black trees
 *
 * This file only declares and documents the methods that can be used publicly to manage RBTs
 * For helper methods used internally, please refer to rbt.cc
 *
 * Romain Gaillard - Adapted from the Red Black Tree implementation of Emin Martinian.
 */
 
#ifndef MIDDLEBOX_RBT_HH
#define MIDDLEBOX_RBT_HH
 
 
#include <clicknet/tcp.h>
#include "memorypool.hh"
 
CLICK_DECLS
 
class RBTManager;
 
typedef struct rb_red_blk_node {
    void* key;
    void* info;
    int red; /* if red=0 then the node is black */
    struct rb_red_blk_node* left;
    struct rb_red_blk_node* right;
    struct rb_red_blk_node* parent;
} rb_red_blk_node;
 
typedef struct rb_red_blk_tree {
    RBTManager* manager; // Pointer to the RBTManager used to compare keys and allocate memory
    /*  A sentinel is used for root and for nil.  These sentinels are */
    /*  created when RBTreeCreate is called.  root->left should always */
    /*  point to the node which is the root of the tree.  nil points to a */
    /*  node which should always be black but has aribtrary children and */
    /*  parent and no key or info.  The point of using these sentinels is so */
    /*  that the root and nil nodes do not require special cases in the code */
    rb_red_blk_node* root;
    rb_red_blk_node* nil;
} rb_red_blk_tree;
 
rb_red_blk_tree* RBTreeCreate(RBTManager* manager);
 
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key, void* info);
 
void RBTreePrint(rb_red_blk_tree* tree);
 
void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* node);
 
void RBTreeDestroy(rb_red_blk_tree* tree);
 
rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* node);
 
rb_red_blk_node* TreeSuccessor(rb_red_blk_tree*, rb_red_blk_node*);
 
rb_red_blk_node* RBExactQuery(rb_red_blk_tree* tree, void* key);
 
rb_red_blk_node* RBFindElementGreatestBelow(rb_red_blk_tree* tree, void* key);
 
rb_red_blk_node* RBMin(rb_red_blk_tree* tree);
 
rb_red_blk_node* RBMax(rb_red_blk_tree* tree);
 
void RBPrune(rb_red_blk_tree* tree, void* key);
 
#define BS_TREE_POOL_SIZE 10
#define BS_POOL_SIZE 5000
#define BS_PRUNE_THRESHOLD 10
 
 
class RBTManager
{
public:
    RBTManager() : poolNodes(BS_POOL_SIZE),
        poolKeys(BS_POOL_SIZE),
        poolInfos(BS_POOL_SIZE),
        poolTrees(BS_TREE_POOL_SIZE)
    {
 
    }
 
    inline int compareKeys(const void* first, const void* second)
    {
        if(SEQ_GT(*(uint32_t*)first, *(uint32_t*)second))
            return 1;
        if(SEQ_LT(*(uint32_t*)first, *(uint32_t*)second))
            return -1;
 
        return 0;
    }
 
    void printKey(const void* first)
    {
        click_chatter("%u", *(uint32_t*)first);
    }
 
    void printInfo(void* first)
    {
        click_chatter("%d", *(int*)first);
    }
 
    rb_red_blk_node* allocateNode(void)
    {
        return poolNodes.getMemory();
    }
 
    rb_red_blk_tree* allocateTree(void)
    {
        return poolTrees.getMemory();
    }
 
    void freeNode(rb_red_blk_node* node)
    {
        poolNodes.releaseMemory(node);
    }
 
    void freeKey(void* key)
    {
        poolKeys.releaseMemory((uint32_t*)key);
    }
 
    void freeInfo(void* info)
    {
        poolInfos.releaseMemory((int*)info);
    }
 
    void freeTree(rb_red_blk_tree* tree)
    {
        poolTrees.releaseMemory(tree);
    }
 
    uint32_t* allocateKey(void)
    {
        return poolKeys.getMemory();
    }
 
    int* allocateInfo(void)
    {
        return poolInfos.getMemory();
    }
 
private:
    MemoryPool<rb_red_blk_tree> poolTrees;
    MemoryPool<rb_red_blk_node> poolNodes;
    MemoryPool<uint32_t> poolKeys;
    MemoryPool<int> poolInfos;
};
 
 
CLICK_ENDDECLS
 
#endif