#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include "memory.h"
#include "rbtree.h"
#include "tm.h"
#include "lehigh.h"

Include dependency graph for rbtree.c:

Classes
struct	node

struct	rbtree

Macros
#define	LDA(a) *(a)

#define	STA(a, v) *(a) = (v)

#define	LDV(a) (a)

#define	STV(a, v) (a) = (v)

#define	LDF(o, f) ((o)->f)

#define	STF(o, f, v) ((o)->f) = (v)

#define	LDNODE(o, f) ((node_t*)(LDF((o),f)))

#define	TX_LDA(a) TM_SHARED_READ_L(*(a))

#define	TX_STA(a, v) TM_SHARED_WRITE_L(*(a), v)

#define	TX_LDV(a) TM_SHARED_READ_L(a)

#define	TX_STV(a, v) TM_SHARED_WRITE_P(a, v)

#define	TX_LDF(o, f) ((long)TM_SHARED_READ_L((o)->f))

#define	TX_LDF_P(o, f) ((void*)TM_SHARED_READ_P((o)->f))

#define	TX_STF(o, f, v) TM_SHARED_WRITE_L((o)->f, v)

#define	TX_STF_P(o, f, v) TM_SHARED_WRITE_P((o)->f, v)

#define	TX_LDNODE(o, f) ((node_t*)(TX_LDF_P((o),f)))

#define	LOOKUP(set, key) lookup(set, key)

#define	TX_LOOKUP(set, key) TMlookup(TM_ARG set, key)

#define	ROTATE_LEFT(set, node) rotateLeft(set, node)

#define	TX_ROTATE_LEFT(set, node) TMrotateLeft(TM_ARG set, node)

#define	ROTATE_RIGHT(set, node) rotateRight(set, node)

#define	TX_ROTATE_RIGHT(set, node) TMrotateRight(TM_ARG set, node)

#define	PARENT_OF(n) parentOf(n)

#define	TX_PARENT_OF(n) TMparentOf(TM_ARG n)

#define	LEFT_OF(n) leftOf(n)

#define	TX_LEFT_OF(n) TMleftOf(TM_ARG n)

#define	RIGHT_OF(n) rightOf(n)

#define	TX_RIGHT_OF(n) TMrightOf(TM_ARG n)

#define	COLOR_OF(n) colorOf(n)

#define	TX_COLOR_OF(n) TMcolorOf(TM_ARG n)

#define	SET_COLOR(n, c) setColor(n, c)

#define	TX_SET_COLOR(n, c) TMsetColor(TM_ARG n, c)

#define	FIX_AFTER_INSERTION(s, x) fixAfterInsertion(s, x)

#define	TX_FIX_AFTER_INSERTION(s, x) TMfixAfterInsertion(TM_ARG s, x)

#define	INSERT(s, k, v, n) insert(s, k, v, n)

#define	TX_INSERT(s, k, v, n) TMinsert(TM_ARG s, k, v, n)

#define	SUCCESSOR(n) successor(n)

#define	TX_SUCCESSOR(n) TMsuccessor(TM_ARG n)

#define	FIX_AFTER_DELETION(s, n) fixAfterDeletion(s, n)

#define	TX_FIX_AFTER_DELETION(s, n) TMfixAfterDeletion(TM_ARG s, n )

#define	DELETE(s, n) delete_node(s, n)

#define	TX_DELETE(s, n) TMdelete(TM_ARG s, n)

Typedefs
typedef struct node	node_t

Functions
static TM_CALLABLE node_t *	TMlookup (TM_ARGDECL rbtree_t s, void k)

static TM_CALLABLE void	TMrotateLeft (TM_ARGDECL rbtree_t s, node_t x)

static TM_CALLABLE void	TMrotateRight (TM_ARGDECL rbtree_t s, node_t x)

static TM_CALLABLE node_t *	TMparentOf (TM_ARGDECL node_t *n)

static TM_CALLABLE node_t *	TMleftOf (TM_ARGDECL node_t *n)

static TM_CALLABLE node_t *	TMrightOf (TM_ARGDECL node_t *n)

static TM_CALLABLE long	TMcolorOf (TM_ARGDECL node_t *n)

static TM_CALLABLE void	TMsetColor (TM_ARGDECL node_t *n, long c)

static TM_CALLABLE void	TMfixAfterInsertion (TM_ARGDECL rbtree_t s, node_t x)

static TM_CALLABLE node_t *	TMsuccessor (TM_ARGDECL node_t *t)

static TM_CALLABLE void	TMfixAfterDeletion (TM_ARGDECL rbtree_t s, node_t x)

static TM_CALLABLE node_t *	TMinsert (TM_ARGDECL rbtree_t s, void k, void v, node_t n)

static TM_CALLABLE node_t *	TMgetNode (TM_ARGDECL_ALONE)

static TM_CALLABLE node_t *	TMdelete (TM_ARGDECL rbtree_t s, node_t p)

static node_t *	lookup (rbtree_t s, void k)

static void	rotateLeft (rbtree_t s, node_t x)

static void	rotateRight (rbtree_t s, node_t x)

static node_t *	parentOf (node_t *n)

static node_t *	leftOf (node_t *n)

static node_t *	rightOf (node_t *n)

static long	colorOf (node_t *n)

static void	setColor (node_t *n, long c)

static void	fixAfterInsertion (rbtree_t s, node_t x)

static node_t *	insert (rbtree_t s, void k, void v, node_t n)

static node_t *	successor (node_t *t)

static void	fixAfterDeletion (rbtree_t s, node_t x)

static node_t *	delete_node (rbtree_t s, node_t p)

static node_t *	firstEntry (rbtree_t *s)

static long	verifyRedBlack (node_t *root, long depth)

long	rbtree_verify (rbtree_t *s, long verbose)

static long	compareKeysDefault (const void a, const void b)

static TM_CALLABLE long	TMcompareKeysDefault (TM_ARGDECL const void a, const void b)

rbtree_t *	rbtree_alloc (comparator_t *compare)

rbtree_t *	TMrbtree_alloc (TM_ARGDECL comparator_t *compare)

static void	releaseNode (node_t *n)

static TM_CALLABLE void	TMreleaseNode (TM_ARGDECL node_t *n)

static void	freeNode (node_t *n)

static void	TMfreeNode (TM_ARGDECL node_t *n)

void	rbtree_free (rbtree_t *r)

void	TMrbtree_free (TM_ARGDECL rbtree_t *r)

static node_t *	getNode ()

bool_t	rbtree_insert (rbtree_t r, void key, void *val)

bool_t	TMrbtree_insert (TM_ARGDECL rbtree_t r, void key, void *val)

bool_t	rbtree_delete (rbtree_t r, void key)

bool_t	TMrbtree_delete (TM_ARGDECL rbtree_t r, void key)

bool_t	rbtree_update (rbtree_t r, void key, void *val)

bool_t	TMrbtree_update (TM_ARGDECL rbtree_t r, void key, void *val)

void *	rbtree_get (rbtree_t r, void key)

void *	TMrbtree_get (TM_ARGDECL rbtree_t r, void key)

long	rbtree_contains (rbtree_t r, void key)

long	TMrbtree_contains (TM_ARGDECL rbtree_t r, void key)

Variables
static long	RED = 0

static long	BLACK = 1

comparator_t rbtree_comparekeysdefault &	compareKeysDefault

Macro Definition Documentation

#define COLOR_OF ( n ) colorOf(n)

#define DELETE	(	s,
		n
	)	delete_node(s, n)

#define FIX_AFTER_DELETION	(	s,
		n
	)	fixAfterDeletion(s, n)

#define FIX_AFTER_INSERTION	(	s,
		x
	)	fixAfterInsertion(s, x)

#define INSERT	(	s,
		k,
		v,
		n
	)	insert(s, k, v, n)

#define LDA ( a ) *(a)

#define LDF	(	o,
		f
	)	((o)->f)

#define LDNODE	(	o,
		f
	)	((node_t*)(LDF((o),f)))

#define LDV ( a ) (a)

#define LEFT_OF ( n ) leftOf(n)

#define LOOKUP	(	set,
		key
	)	lookup(set, key)

#define PARENT_OF ( n ) parentOf(n)

#define RIGHT_OF ( n ) rightOf(n)

#define ROTATE_LEFT	(	set,
		node
	)	rotateLeft(set, node)

#define ROTATE_RIGHT	(	set,
		node
	)	rotateRight(set, node)

#define SET_COLOR	(	n,
		c
	)	setColor(n, c)

#define STA	(	a,
		v
	)	*(a) = (v)

#define STF	(	o,
		f,
		v
	)	((o)->f) = (v)

#define STV	(	a,
		v
	)	(a) = (v)

#define SUCCESSOR ( n ) successor(n)

#define TX_COLOR_OF ( n ) TMcolorOf(TM_ARG n)

#define TX_DELETE	(	s,
		n
	)	TMdelete(TM_ARG s, n)

#define TX_FIX_AFTER_DELETION	(	s,
		n
	)	TMfixAfterDeletion(TM_ARG s, n )

#define TX_FIX_AFTER_INSERTION	(	s,
		x
	)	TMfixAfterInsertion(TM_ARG s, x)

#define TX_INSERT	(	s,
		k,
		v,
		n
	)	TMinsert(TM_ARG s, k, v, n)

#define TX_LDA ( a ) TM_SHARED_READ_L(*(a))

#define TX_LDF	(	o,
		f
	)	((long)TM_SHARED_READ_L((o)->f))

#define TX_LDF_P	(	o,
		f
	)	((void*)TM_SHARED_READ_P((o)->f))

#define TX_LDNODE	(	o,
		f
	)	((node_t*)(TX_LDF_P((o),f)))

#define TX_LDV ( a ) TM_SHARED_READ_L(a)

#define TX_LEFT_OF ( n ) TMleftOf(TM_ARG n)

#define TX_LOOKUP	(	set,
		key
	)	TMlookup(TM_ARG set, key)

#define TX_PARENT_OF ( n ) TMparentOf(TM_ARG n)

#define TX_RIGHT_OF ( n ) TMrightOf(TM_ARG n)

#define TX_ROTATE_LEFT	(	set,
		node
	)	TMrotateLeft(TM_ARG set, node)

#define TX_ROTATE_RIGHT	(	set,
		node
	)	TMrotateRight(TM_ARG set, node)

#define TX_SET_COLOR	(	n,
		c
	)	TMsetColor(TM_ARG n, c)

#define TX_STA	(	a,
		v
	)	TM_SHARED_WRITE_L(*(a), v)

#define TX_STF	(	o,
		f,
		v
	)	TM_SHARED_WRITE_L((o)->f, v)

#define TX_STF_P	(	o,
		f,
		v
	)	TM_SHARED_WRITE_P((o)->f, v)

#define TX_STV	(	a,
		v
	)	TM_SHARED_WRITE_P(a, v)

#define TX_SUCCESSOR ( n ) TMsuccessor(TM_ARG n)

Typedef Documentation

typedef struct node node_t

Function Documentation

static long colorOf ( node_t * n )

inlinestatic

static long compareKeysDefault	(	const void *	a,
		const void *	b
	)

static

static node_t* delete_node	(	rbtree_t *	s,
		node_t *	p
	)

static

static node_t* firstEntry ( rbtree_t * s )

static

Here is the caller graph for this function:

static void fixAfterDeletion	(	rbtree_t *	s,
		node_t *	x
	)

static

static void fixAfterInsertion	(	rbtree_t *	s,
		node_t *	x
	)

static

static void freeNode ( node_t * n )

static

Here is the call graph for this function:

Here is the caller graph for this function:

static node_t* getNode ( )

static

Here is the caller graph for this function:

static node_t* insert	(	rbtree_t *	s,
		void *	k,
		void *	v,
		node_t *	n
	)

static

Here is the call graph for this function:

static node_t* leftOf ( node_t * n )

inlinestatic

static node_t* lookup	(	rbtree_t *	s,
		void *	k
	)

static

static node_t* parentOf ( node_t * n )

inlinestatic

rbtree_t* rbtree_alloc ( comparator_t * compare )

long rbtree_contains	(	rbtree_t *	r,
		void *	key
	)

bool_t rbtree_delete	(	rbtree_t *	r,
		void *	key
	)

Here is the call graph for this function:

void rbtree_free ( rbtree_t * r )

Here is the call graph for this function:

void* rbtree_get	(	rbtree_t *	r,
		void *	key
	)

bool_t rbtree_insert	(	rbtree_t *	r,
		void *	key,
		void *	val
	)

Here is the call graph for this function:

bool_t rbtree_update	(	rbtree_t *	r,
		void *	key,
		void *	val
	)

Here is the call graph for this function:

long rbtree_verify	(	rbtree_t *	s,
		long	verbose
	)

Here is the call graph for this function:

static void releaseNode ( node_t * n )

static

Here is the caller graph for this function:

static node_t* rightOf ( node_t * n )

inlinestatic

static void rotateLeft	(	rbtree_t *	s,
		node_t *	x
	)

static

static void rotateRight	(	rbtree_t *	s,
		node_t *	x
	)

static

static void setColor	(	node_t *	n,
		long	c
	)

inlinestatic

static node_t* successor ( node_t * t )

static

Here is the caller graph for this function:

static long TMcolorOf ( TM_ARGDECL node_t * n )

inlinestatic

static TM_CALLABLE long TMcompareKeysDefault	(	TM_ARGDECL const void *	a,
		const void *	b
	)

static

static node_t * TMdelete	(	TM_ARGDECL rbtree_t *	s,
		node_t *	p
	)

static

static void TMfixAfterDeletion	(	TM_ARGDECL rbtree_t *	s,
		node_t *	x
	)

static

static void TMfixAfterInsertion	(	TM_ARGDECL rbtree_t *	s,
		node_t *	x
	)

static

static void TMfreeNode ( TM_ARGDECL node_t * n )

static

Here is the call graph for this function:

Here is the caller graph for this function:

static node_t * TMgetNode ( TM_ARGDECL_ALONE )

static

Here is the caller graph for this function:

static node_t * TMinsert	(	TM_ARGDECL rbtree_t *	s,
		void *	k,
		void *	v,
		node_t *	n
	)

static

Here is the call graph for this function:

static node_t * TMleftOf ( TM_ARGDECL node_t * n )

inlinestatic

static node_t * TMlookup	(	TM_ARGDECL rbtree_t *	s,
		void *	k
	)

static

static node_t * TMparentOf ( TM_ARGDECL node_t * n )

inlinestatic

rbtree_t* TMrbtree_alloc ( TM_ARGDECL comparator_t * compare )

long TMrbtree_contains	(	TM_ARGDECL rbtree_t *	r,
		void *	key
	)

bool_t TMrbtree_delete	(	TM_ARGDECL rbtree_t *	r,
		void *	key
	)

Here is the call graph for this function:

void TMrbtree_free ( TM_ARGDECL rbtree_t * r )

Here is the call graph for this function:

void* TMrbtree_get	(	TM_ARGDECL rbtree_t *	r,
		void *	key
	)

bool_t TMrbtree_insert	(	TM_ARGDECL rbtree_t *	r,
		void *	key,
		void *	val
	)

Here is the call graph for this function:

bool_t TMrbtree_update	(	TM_ARGDECL rbtree_t *	r,
		void *	key,
		void *	val
	)

Here is the call graph for this function:

static TM_CALLABLE void TMreleaseNode ( TM_ARGDECL node_t * n )

static

Here is the caller graph for this function:

static node_t * TMrightOf ( TM_ARGDECL node_t * n )

inlinestatic

static void TMrotateLeft	(	TM_ARGDECL rbtree_t *	s,
		node_t *	x
	)

static

static void TMrotateRight	(	TM_ARGDECL rbtree_t *	s,
		node_t *	x
	)

static

static void TMsetColor	(	TM_ARGDECL node_t *	n,
		long	c
	)

inlinestatic

static node_t * TMsuccessor ( TM_ARGDECL node_t * t )

static

static long verifyRedBlack	(	node_t *	root,
		long	depth
	)

static

Here is the caller graph for this function:

Variable Documentation

long BLACK = 1

static

comparator_t rbtree_comparekeysdefault& compareKeysDefault

long RED = 0

static

Classes

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation