Leptonica  1.54
Файл src/rbtree.c
#include "allheaders.h"

Макросы

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

Определения типов

typedef L_RBTREE_NODE node

Перечисления

enum  { L_RED_NODE = 1, L_BLACK_NODE = 2 }

Функции

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 nodegrandparent (node *n)
static nodesibling (node *n)
static nodeuncle (node *n)
static void verify_properties (L_RBTREE *t)
static void verify_property_1 (node *root)
static void verify_property_2 (node *root)
static l_int32 node_color (node *n)
static void verify_property_4 (node *root)
static void verify_property_5 (node *root)
static void verify_property_5_helper (node *n, int black_count, int *black_count_path)
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)
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)
l_int32 l_compareKeys (l_int32 keytype, RB_TYPE left, RB_TYPE right)

Макросы

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

Типы


Перечисления

anonymous enum
Элементы перечислений:
L_RED_NODE 
L_BLACK_NODE 

Функции

static void count_helper ( node n,
l_int32 pcount 
) [static]
static void delete_case1 ( L_RBTREE t,
node n 
) [static]
static void delete_case2 ( L_RBTREE t,
node n 
) [static]
static void delete_case3 ( L_RBTREE t,
node n 
) [static]
static void delete_case4 ( L_RBTREE t,
node n 
) [static]
static void delete_case5 ( L_RBTREE t,
node n 
) [static]
static void delete_case6 ( L_RBTREE t,
node n 
) [static]
static void destroy_helper ( node n) [static]
static node * grandparent ( node n) [static]
static void insert_case1 ( L_RBTREE t,
node n 
) [static]
static void insert_case2 ( L_RBTREE t,
node n 
) [static]
static void insert_case3 ( L_RBTREE t,
node n 
) [static]
static void insert_case4 ( L_RBTREE t,
node n 
) [static]
static void insert_case5 ( L_RBTREE t,
node n 
) [static]
l_int32 l_compareKeys ( l_int32  keytype,
RB_TYPE  left,
RB_TYPE  right 
)
void l_rbtreeDelete ( L_RBTREE t,
RB_TYPE  key 
)
void l_rbtreeDestroy ( L_RBTREE **  pt)
void l_rbtreeInsert ( L_RBTREE t,
RB_TYPE  key,
RB_TYPE  value 
)
RB_TYPE* l_rbtreeLookup ( L_RBTREE t,
RB_TYPE  key 
)
void l_rbtreePrint ( FILE *  fp,
L_RBTREE t 
)
static node * lookup_node ( L_RBTREE t,
RB_TYPE  key 
) [static]
static node * maximum_node ( node root) [static]
static node * new_node ( RB_TYPE  key,
RB_TYPE  value,
l_int32  node_color,
node left,
node right 
) [static]
static l_int32 node_color ( node n) [static]
static void print_tree_helper ( FILE *  fp,
node n,
l_int32  keytype,
l_int32  indent 
) [static]
static void replace_node ( L_RBTREE t,
node oldn,
node newn 
) [static]
static void rotate_left ( L_RBTREE t,
node n 
) [static]
static void rotate_right ( L_RBTREE t,
node n 
) [static]
static node * sibling ( node n) [static]
static node * uncle ( node n) [static]
static void verify_properties ( L_RBTREE t) [static]
static void verify_property_1 ( node root) [static]
static void verify_property_2 ( node root) [static]
static void verify_property_4 ( node root) [static]
static void verify_property_5 ( node root) [static]
static void verify_property_5_helper ( node n,
int  black_count,
int *  black_count_path 
) [static]