Файл 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 node *	grandparent (node *n)
static node *	sibling (node *n)
static node *	uncle (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 node *	new_node (RB_TYPE key, RB_TYPE value, l_int32 node_color, node *left, node *right)
static node *	lookup_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 node *	maximum_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_RBTREE *	l_rbtreeCreate (l_int32 keytype)
RB_TYPE *	l_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_NODE *	l_rbtreeGetFirst (L_RBTREE *t)
L_RBTREE_NODE *	l_rbtreeGetNext (L_RBTREE_NODE *n)
L_RBTREE_NODE *	l_rbtreeGetLast (L_RBTREE *t)
L_RBTREE_NODE *	l_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)

Макросы

INDENT_STEP

#define INDENT_STEP   4

VERIFY_RBTREE

#define VERIFY_RBTREE   0 /* only for debugging */

Типы

node

typedef L_RBTREE_NODE node

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

anonymous enum

anonymous enum

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

Функции

count_helper()

static void count_helper ( node *  n, l_int32 *  pcount  )

static

delete_case1()

static void delete_case1 ( L_RBTREE *  t, node *  n  )

static

delete_case2()

static void delete_case2 ( L_RBTREE *  t, node *  n  )

static

delete_case3()

static void delete_case3 ( L_RBTREE *  t, node *  n  )

static

delete_case4()

static void delete_case4 ( L_RBTREE *  t, node *  n  )

static

delete_case5()

static void delete_case5 ( L_RBTREE *  t, node *  n  )

static

delete_case6()

static void delete_case6 ( L_RBTREE *  t, node *  n  )

static

destroy_helper()

static void destroy_helper ( node *  n )

static

grandparent()

static node * grandparent ( node *  n )

static

insert_case1()

static void insert_case1 ( L_RBTREE *  t, node *  n  )

static

insert_case2()

static void insert_case2 ( L_RBTREE *  t, node *  n  )

static

insert_case3()

static void insert_case3 ( L_RBTREE *  t, node *  n  )

static

insert_case4()

static void insert_case4 ( L_RBTREE *  t, node *  n  )

static

insert_case5()

static void insert_case5 ( L_RBTREE *  t, node *  n  )

static

l_compareKeys()

l_int32 l_compareKeys	(	l_int32	keytype,
		RB_TYPE	left,
		RB_TYPE	right
	)

l_rbtreeCreate()

L_RBTREE* l_rbtreeCreate

(

l_int32

keytype

)

l_rbtreeDelete()

void l_rbtreeDelete	(	L_RBTREE *	t,
		RB_TYPE	key
	)

l_rbtreeDestroy()

void l_rbtreeDestroy

(

L_RBTREE **

pt

)

l_rbtreeGetCount()

l_int32 l_rbtreeGetCount

(

L_RBTREE *

t

)

l_rbtreeGetFirst()

L_RBTREE_NODE* l_rbtreeGetFirst

(

L_RBTREE *

t

)

l_rbtreeGetLast()

L_RBTREE_NODE* l_rbtreeGetLast

(

L_RBTREE *

t

)

l_rbtreeGetNext()

L_RBTREE_NODE* l_rbtreeGetNext

(

L_RBTREE_NODE *

n

)

l_rbtreeGetPrev()

L_RBTREE_NODE* l_rbtreeGetPrev

(

L_RBTREE_NODE *

n

)

l_rbtreeInsert()

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

l_rbtreeLookup()

RB_TYPE* l_rbtreeLookup	(	L_RBTREE *	t,
		RB_TYPE	key
	)

l_rbtreePrint()

void l_rbtreePrint	(	FILE *	fp,
		L_RBTREE *	t
	)

lookup_node()

static node * lookup_node ( L_RBTREE *  t, RB_TYPE  key  )

static

maximum_node()

static node * maximum_node ( node *  root )

static

new_node()

static node * new_node ( RB_TYPE  key, RB_TYPE  value, l_int32  node_color, node *  left, node *  right  )

static

node_color()

static l_int32 node_color ( node *  n )

static

print_tree_helper()

static void print_tree_helper ( FILE *  fp, node *  n, l_int32  keytype, l_int32  indent  )

static

replace_node()

static void replace_node ( L_RBTREE *  t, node *  oldn, node *  newn  )

static

rotate_left()

static void rotate_left ( L_RBTREE *  t, node *  n  )

static

rotate_right()

static void rotate_right ( L_RBTREE *  t, node *  n  )

static

sibling()

static node * sibling ( node *  n )

static

uncle()

static node * uncle ( node *  n )

static

verify_properties()

static void verify_properties ( L_RBTREE *  t )

static

verify_property_1()

static void verify_property_1 ( node *  root )

static

verify_property_2()

static void verify_property_2 ( node *  root )

static

verify_property_4()

static void verify_property_4 ( node *  root )

static

verify_property_5()

static void verify_property_5 ( node *  root )

static

verify_property_5_helper()

static void verify_property_5_helper ( node *  n, int  black_count, int *  black_count_path  )

static