le_redBlackTree.h

Go to the documentation of this file.

#ifndef LEGATO_RED_BLACK_TREE_INCLUDE_GUARD
#define LEGATO_RED_BLACK_TREE_INCLUDE_GUARD

typedef enum
{
    LE_RBTREE_NO_COLOR,
    LE_RBTREE_BLACK,
    LE_RBTREE_RED
}
le_rbtree_Color_t;

typedef struct le_rbtree_Node
{
    void *key;                      
    struct le_rbtree_Node *parent;  
    struct le_rbtree_Node *left;    
    struct le_rbtree_Node *right;   
    le_rbtree_Color_t color;        
}
le_rbtree_Node_t;

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
typedef int (*le_rbtree_CompareFunc_t)
(
    const void *key1Ptr,   
    const void *key2Ptr    
);


//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
typedef struct le_rbtree_Tree
{
    le_rbtree_Node_t *root;         
    size_t size;                    
    le_rbtree_CompareFunc_t compFn; 
}
le_rbtree_Tree_t;


//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
void le_rbtree_InitTree
(
    le_rbtree_Tree_t *treePtr,      
    le_rbtree_CompareFunc_t compFn  
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
void le_rbtree_InitNode
(
    le_rbtree_Node_t *linkPtr,      
    void *keyPtr                    
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_Insert
(
    le_rbtree_Tree_t *treePtr,            
    le_rbtree_Node_t *newLinkPtr          
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_Find
(
    le_rbtree_Tree_t *treePtr,    
    void *keyPtr                  
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_Remove
(
    le_rbtree_Tree_t *treePtr,    
    le_rbtree_Node_t *linkPtr     
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_RemoveByKey
(
    le_rbtree_Tree_t *treePtr,    
    void *keyPtr                  
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_GetFirst
(
    const le_rbtree_Tree_t *treePtr    
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_GetLast
(
    const le_rbtree_Tree_t *treePtr    
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_GetNext
(
    const le_rbtree_Tree_t *treePtr,   
    le_rbtree_Node_t *currentLinkPtr   
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
le_rbtree_Node_t* le_rbtree_GetPrev
(
    const le_rbtree_Tree_t *treePtr,        
    le_rbtree_Node_t *currentLinkPtr        
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
bool le_rbtree_IsEmpty
(
    const le_rbtree_Tree_t *treePtr         
);

//--------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------
size_t le_rbtree_Size
(
    const le_rbtree_Tree_t *treePtr         
);

#endif  // LEGATO_RED_BLACK_TREE_INCLUDE_GUARD