Leptonica  1.82.0
Image processing and image analysis suite
rbtree.c File Reference
#include "allheaders.h"

Go to the source code of this file.

Macros

#define VERIFY_RBTREE   0 /* only for debugging */
 
#define INDENT_STEP   4
 

Typedefs

typedef L_RBTREE_NODE node
 

Enumerations

enum  { L_RED_NODE = 1, L_BLACK_NODE = 2 }
 

Functions

static void destroy_helper (node *n)
 
static void count_helper (node *n, l_int32 *pcount)
 
static void print_tree_helper (FILE *fp, node *n, l_int32 keytype, l_int32 indent)
 
static l_int32 compareKeys (l_int32 keytype, RB_TYPE left, RB_TYPE right)
 
static nodegrandparent (node *n)
 
static nodesibling (node *n)
 
static nodeuncle (node *n)
 
static l_int32 node_color (node *n)
 
static nodenew_node (RB_TYPE key, RB_TYPE value, l_int32 node_color, node *left, node *right)
 
static nodelookup_node (L_RBTREE *t, RB_TYPE key)
 
static void rotate_left (L_RBTREE *t, node *n)
 
static void rotate_right (L_RBTREE *t, node *n)
 
static void replace_node (L_RBTREE *t, node *oldn, node *newn)
 
static void insert_case1 (L_RBTREE *t, node *n)
 
static void insert_case2 (L_RBTREE *t, node *n)
 
static void insert_case3 (L_RBTREE *t, node *n)
 
static void insert_case4 (L_RBTREE *t, node *n)
 
static void insert_case5 (L_RBTREE *t, node *n)
 
static nodemaximum_node (node *root)
 
static void delete_case1 (L_RBTREE *t, node *n)
 
static void delete_case2 (L_RBTREE *t, node *n)
 
static void delete_case3 (L_RBTREE *t, node *n)
 
static void delete_case4 (L_RBTREE *t, node *n)
 
static void delete_case5 (L_RBTREE *t, node *n)
 
static void delete_case6 (L_RBTREE *t, node *n)
 
static void verify_properties (L_RBTREE *t)
 
L_RBTREEl_rbtreeCreate (l_int32 keytype)
 
RB_TYPEl_rbtreeLookup (L_RBTREE *t, RB_TYPE key)
 
void l_rbtreeInsert (L_RBTREE *t, RB_TYPE key, RB_TYPE value)
 
void l_rbtreeDelete (L_RBTREE *t, RB_TYPE key)
 
void l_rbtreeDestroy (L_RBTREE **pt)
 
L_RBTREE_NODEl_rbtreeGetFirst (L_RBTREE *t)
 
L_RBTREE_NODEl_rbtreeGetNext (L_RBTREE_NODE *n)
 
L_RBTREE_NODEl_rbtreeGetLast (L_RBTREE *t)
 
L_RBTREE_NODEl_rbtreeGetPrev (L_RBTREE_NODE *n)
 
l_int32 l_rbtreeGetCount (L_RBTREE *t)
 
void l_rbtreePrint (FILE *fp, L_RBTREE *t)
 

Detailed Description

 Basic functions for using red-black trees.  These are "nearly" balanced
 sorted trees with ordering by key that allows insertion, lookup and
 deletion of key/value pairs in log(n) time.
 We use red-black trees to implement our version of:
   * a map: a function that maps keys to values (e.g., int64 --> int64).
   * a set: a collection that is sorted by unique keys (without
     associated values)
 There are 5 invariant properties of RB trees:
 (1) Each node is either red or black.
 (2) The root node is black.
 (3) All leaves are black and contain no data (null).
 (4) Every red node has two children and both are black.  This is
     equivalent to requiring the parent of every red node to be black.
 (5) All paths from any given node to its leaf nodes contain the
     same number of black nodes.
 Interface to red-black tree
          L_RBTREE       *l_rbtreeCreate()
          RB_TYPE        *l_rbtreeLookup()
          void            l_rbtreeInsert()
          void            l_rbtreeDelete()
          void            l_rbtreeDestroy()
          L_RBTREE_NODE  *l_rbtreeGetFirst()
          L_RBTREE_NODE  *l_rbtreeGetNext()
          L_RBTREE_NODE  *l_rbtreeGetLast()
          L_RBTREE_NODE  *l_rbtreeGetPrev()
          l_int32         l_rbtreeGetCount()
          void            l_rbtreePrint()
 General comparison function
          static l_int32  compareKeys()

Definition in file rbtree.c.

Function Documentation

◆ l_rbtreeCreate()

L_RBTREE* l_rbtreeCreate ( l_int32  keytype)

l_rbtreeCreate()

Parameters
[in]keytypedefined by an enum for an RB_TYPE union
Returns
rbtree container with empty ptr to the root

Definition at line 135 of file rbtree.c.

◆ l_rbtreeDelete()

void l_rbtreeDelete ( L_RBTREE t,
RB_TYPE  key 
)

l_rbtreeDelete()

Parameters
[in]trbtree, including root node
[in]keydelete the node with this key
Returns
void

Definition at line 242 of file rbtree.c.

◆ l_rbtreeDestroy()

void l_rbtreeDestroy ( L_RBTREE **  pt)

l_rbtreeDestroy()

Parameters
[in]ptpointer to tree; will be wet to null before returning
Returns
void
Notes:
     (1) Destroys the tree and nulls the input tree ptr.

Definition at line 290 of file rbtree.c.

◆ l_rbtreeGetCount()

l_int32 l_rbtreeGetCount ( L_RBTREE t)

l_rbtreeGetCount()

Parameters
[in]trbtree
Returns
count the number of nodes in the tree, or 0 on error

Definition at line 459 of file rbtree.c.

◆ l_rbtreeGetFirst()

L_RBTREE_NODE* l_rbtreeGetFirst ( L_RBTREE t)

l_rbtreeGetFirst()

Parameters
[in]trbtree, including root node
Returns
first node, or NULL on error or if the tree is empty
Notes:
     (1) This is the first node in an in-order traversal.

Definition at line 324 of file rbtree.c.

◆ l_rbtreeGetLast()

L_RBTREE_NODE* l_rbtreeGetLast ( L_RBTREE t)

l_rbtreeGetLast()

Parameters
[in]trbtree, including root node
Returns
last node, or NULL on error or if the tree is empty
Notes:
     (1) This is the last node in an in-order traversal.

Definition at line 394 of file rbtree.c.

◆ l_rbtreeGetNext()

L_RBTREE_NODE* l_rbtreeGetNext ( L_RBTREE_NODE n)

l_rbtreeGetNext()

Parameters
[in]ncurrent node
Returns
next node, or NULL if it's the last node
Notes:
     (1) This finds the next node, in an in-order traversal, from
         the current node.
     (2) It is useful as an iterator for a map.
     (3) Call l_rbtreeGetFirst() to get the first node.

Definition at line 359 of file rbtree.c.

◆ l_rbtreeGetPrev()

L_RBTREE_NODE* l_rbtreeGetPrev ( L_RBTREE_NODE n)

l_rbtreeGetPrev()

Parameters
[in]ncurrent node
Returns
next node, or NULL if it's the first node
Notes:
     (1) This finds the previous node, in an in-order traversal, from
         the current node.
     (2) It is useful as an iterator for a map.
     (3) Call l_rbtreeGetLast() to get the last node.

Definition at line 429 of file rbtree.c.

◆ l_rbtreeInsert()

void l_rbtreeInsert ( L_RBTREE t,
RB_TYPE  key,
RB_TYPE  value 
)

l_rbtreeInsert()

Parameters
[in]trbtree, including root node
[in]keyinsert a node with this key, if the key does not already exist in the tree
[in]valuetypically an int, used for an index
Returns
void
Notes:
     (1) If a node with the key already exists, this just updates the value.

Definition at line 188 of file rbtree.c.

◆ l_rbtreeLookup()

RB_TYPE* l_rbtreeLookup ( L_RBTREE t,
RB_TYPE  key 
)

l_rbtreeLookup()

Parameters
[in]trbtree, including root node
[in]keyfind a node with this key
Returns
&value a pointer to a union, if the node exists; else NULL

Definition at line 159 of file rbtree.c.

◆ l_rbtreePrint()

void l_rbtreePrint ( FILE *  fp,
L_RBTREE t 
)

l_rbtreePrint()

Parameters
[in]fpfile stream
[in]trbtree
Returns
void

Definition at line 492 of file rbtree.c.