red_black_tree.c File Reference

#include "config.h"
#include <assert.h>
#include <rbtree/red_black_tree.h>
#include <stdio.h>
#include <stdlib.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 *))
static void	LeftRotate (rb_red_blk_tree *tree, rb_red_blk_node *x)
static void	RightRotate (rb_red_blk_tree *tree, rb_red_blk_node *y)
static void	TreeInsertHelp (rb_red_blk_tree *tree, rb_red_blk_node *z)
rb_red_blk_node *	RBTreeInsert (rb_red_blk_tree *tree, void *key)
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)
static void	TreeDestHelper (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	RBTreeDestroy (rb_red_blk_tree *tree)
rb_red_blk_node *	RBExactQuery (rb_red_blk_tree *tree, void *q)
static void	RBDeleteFixUp (rb_red_blk_tree *tree, rb_red_blk_node *x)
void	RBDelete (rb_red_blk_tree *tree, rb_red_blk_node *z)

Function Documentation

LeftRotate()

static void LeftRotate ( rb_red_blk_tree *  tree, rb_red_blk_node *  x  )

static

Definition at line 79 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_node::parent, rb_red_blk_node::right, and tree.

Referenced by RBDeleteFixUp(), and RBTreeInsert().

Here is the caller graph for this function:

RBDelete()

void RBDelete	(	rb_red_blk_tree *	tree,
		rb_red_blk_node *	z
	)

Definition at line 524 of file red_black_tree.c.

References free(), rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_node::parent, RBDeleteFixUp(), rb_red_blk_node::red, rb_red_blk_node::right, tree, TreeSuccessor(), and z.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

RBDeleteFixUp()

static void RBDeleteFixUp ( rb_red_blk_tree *  tree, rb_red_blk_node *  x  )

static

Definition at line 447 of file red_black_tree.c.

References rb_red_blk_node::left, LeftRotate(), rb_red_blk_node::parent, rb_red_blk_node::red, rb_red_blk_node::right, RightRotate(), and tree.

Referenced by RBDelete().

Here is the call graph for this function:

Here is the caller graph for this function:

RBExactQuery()

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

Definition at line 412 of file red_black_tree.c.

References rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_node::right, and tree.

Referenced by main().

Here is the caller graph for this function:

RBTreeCreate()

rb_red_blk_tree * RBTreeCreate	(	int(*)(const void *, const void *)	CompFunc,
		void(*)(void *)	DestFunc
	)

Definition at line 27 of file red_black_tree.c.

References rb_red_blk_tree::Compare, rb_red_blk_tree::DestroyKey, free(), rb_red_blk_node::key, rb_red_blk_node::left, malloc(), rb_red_blk_tree::nil, NULL, rb_red_blk_node::parent, rb_red_blk_node::red, rb_red_blk_node::right, and rb_red_blk_tree::root.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

RBTreeDestroy()

void RBTreeDestroy

(

rb_red_blk_tree *

tree

)

Definition at line 391 of file red_black_tree.c.

References free(), tree, and TreeDestHelper().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

RBTreeInsert()

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

Definition at line 229 of file red_black_tree.c.

References key, rb_red_blk_node::key, rb_red_blk_node::left, LeftRotate(), malloc(), newNode(), NULL, rb_red_blk_node::parent, rb_red_blk_node::red, rb_red_blk_node::right, RightRotate(), tree, and TreeInsertHelp().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

RightRotate()

static void RightRotate ( rb_red_blk_tree *  tree, rb_red_blk_node *  y  )

static

Definition at line 132 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_node::parent, rb_red_blk_node::right, and tree.

Referenced by RBDeleteFixUp(), and RBTreeInsert().

Here is the caller graph for this function:

TreeDestHelper()

static void TreeDestHelper ( rb_red_blk_tree *  tree, rb_red_blk_node *  x  )

static

Definition at line 367 of file red_black_tree.c.

References free(), rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_node::right, tree, and TreeDestHelper().

Referenced by RBTreeDestroy(), and TreeDestHelper().

Here is the call graph for this function:

Here is the caller graph for this function:

TreeInsertHelp()

static void TreeInsertHelp ( rb_red_blk_tree *  tree, rb_red_blk_node *  z  )

static

Definition at line 181 of file red_black_tree.c.

References rb_red_blk_node::key, rb_red_blk_node::left, rb_red_blk_node::parent, rb_red_blk_node::right, tree, and z.

Referenced by RBTreeInsert().

Here is the caller graph for this function:

TreePredecessor()

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

Definition at line 331 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_node::parent, rb_red_blk_node::right, and tree.

Referenced by main().

Here is the caller graph for this function:

TreeSuccessor()

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

Definition at line 296 of file red_black_tree.c.

References rb_red_blk_node::left, rb_red_blk_node::parent, rb_red_blk_node::right, and tree.

Referenced by main(), and RBDelete().

Here is the caller graph for this function: