red_black_tree.c File Reference

#include "config.h"
#include "red_black_tree.h"
#include "stdio.h"

Include dependency graph for red_black_tree.c:

Go to the source code of this file.

Functions
rb_red_blk_tree *	RBTreeCreate (int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
void	LeftRotate (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	RightRotate (rb_red_blk_tree *tree, rb_red_blk_node *y)
void	TreeInsertHelp (rb_red_blk_tree *tree, rb_red_blk_node *z)
rb_red_blk_node *	RBTreeInsert (rb_red_blk_tree *tree, void *key, void *info)
rb_red_blk_node *	TreeSuccessor (rb_red_blk_tree *tree, rb_red_blk_node *x)
rb_red_blk_node *	TreePredecessor (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	InorderTreePrint (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	TreeDestHelper (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	RBTreeDestroy (rb_red_blk_tree *tree)
void	RBTreePrint (rb_red_blk_tree *tree)
rb_red_blk_node *	RBExactQuery (rb_red_blk_tree *tree, void *q)
void	RBDeleteFixUp (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	RBDelete (rb_red_blk_tree *tree, rb_red_blk_node *z)
stk_stack *	RBEnumerate (rb_red_blk_tree *tree, void *low, void *high)

Function Documentation

void InorderTreePrint	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 385 of file red_black_tree.c.

References rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_tree::PrintInfo, rb_red_blk_tree::PrintKey, rb_red_blk_node::red, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by RBTreePrint().

void LeftRotate	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 86 of file red_black_tree.c.

References Assert(), rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::red, and rb_red_blk_node::right.

Referenced by RBDeleteFixUp(), and RBTreeInsert().

void RBDelete	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	z
	)

Definition at line 601 of file red_black_tree.c.

References Assert(), rb_red_blk_tree::DestroyInfo, rb_red_blk_tree::DestroyKey, if(), rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, RBDeleteFixUp(), rb_red_blk_node::red, rb_red_blk_node::right, rb_red_blk_tree::root, and TreeSuccessor().

Referenced by main().

void RBDeleteFixUp	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 522 of file red_black_tree.c.

References Assert(), rb_red_blk_node::left, LeftRotate(), rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::red, rb_red_blk_node::right, RightRotate(), and rb_red_blk_tree::root.

Referenced by RBDelete().

stk_stack* RBEnumerate	(	rb_red_blk_tree *	tree,
		void *	low,
		void *	high
	)

Definition at line 664 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, NULL, rb_jbuf, rb_red_blk_node::right, rb_red_blk_tree::root, StackCreate(), StackPush(), and TreePredecessor().

Referenced by main().

rb_red_blk_node* RBExactQuery	(	rb_red_blk_tree *	tree,
		void *	q
	)

Definition at line 487 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main().

rb_red_blk_tree* RBTreeCreate	(	int(*)(const void *, const void *)	CompFunc,
		void(*)(void *)	DestFunc,
		void(*)(void *)	InfoDestFunc,
		void(*)(const void *)	PrintFunc,
		void(*)(void *)	PrintInfo
	)

Definition at line 33 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_tree::DestroyInfo, rb_red_blk_tree::DestroyKey, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, NULL, rb_red_blk_node::parent, rb_red_blk_tree::PrintInfo, rb_red_blk_tree::PrintKey, rb_jbuf, rb_red_blk_node::red, rb_red_blk_node::right, rb_red_blk_tree::root, and SafeMalloc().

Referenced by main().

void RBTreeDestroy

(

rb_red_blk_tree *

tree

)

Definition at line 446 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_tree::root, and TreeDestHelper().

Referenced by main().

rb_red_blk_node* RBTreeInsert	(	rb_red_blk_tree *	tree,
		void *	key,
		void *	info
	)

Definition at line 242 of file red_black_tree.c.

References Assert(), rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, LeftRotate(), rb_red_blk_tree::nil, NULL, rb_red_blk_node::parent, rb_jbuf, rb_red_blk_node::red, rb_red_blk_node::right, RightRotate(), rb_red_blk_tree::root, SafeMalloc(), and TreeInsertHelp().

Referenced by main().

void RBTreePrint

(

rb_red_blk_tree *

tree

)

Definition at line 468 of file red_black_tree.c.

References InorderTreePrint(), rb_red_blk_node::left, and rb_red_blk_tree::root.

Referenced by main().

void RightRotate	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	y
	)

Definition at line 141 of file red_black_tree.c.

References Assert(), rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::red, and rb_red_blk_node::right.

Referenced by RBDeleteFixUp(), and RBTreeInsert().

void TreeDestHelper	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 421 of file red_black_tree.c.

References rb_red_blk_tree::DestroyInfo, rb_red_blk_tree::DestroyKey, rb_red_blk_node::info, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, and rb_red_blk_node::right.

Referenced by RBTreeDestroy().

void TreeInsertHelp	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	z
	)

Definition at line 192 of file red_black_tree.c.

References Assert(), rb_red_blk_tree::Compare, rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::red, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by RBTreeInsert().

rb_red_blk_node* TreePredecessor	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 349 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main(), and RBEnumerate().

rb_red_blk_node* TreeSuccessor	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	x
	)

Definition at line 314 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_tree::nil, rb_red_blk_node::parent, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main(), and RBDelete().