avl_tree.c File Reference

#include "avl_tree.h"
#include <math.h>
#include <assert.h>
#include "ross-kernel-inline.h"

Go to the source code of this file.

Functions
void	avlDestroy (AvlTree t)
int	avlGetHeight (AvlTree t)
int	avlSearch (AvlTree t, tw_event *key)
void	avlSanityCheck (AvlTree root)
static void	avlFixHeight (AvlTree t)
static void	avlRotate (AvlTree *root, int d)
static void	avlRebalance (AvlTree *t)
void	avlInsert (AvlTree *t, tw_event *key)
void	avlPrintKeys (AvlTree t)
tw_event *	avlDeleteMin (AvlTree *t)
tw_event *	avlDelete (AvlTree *t, tw_event *key)
AvlTree	avl_alloc (void)
void	avl_free (AvlTree t)

Variables
tw_pe *	pe

Function Documentation

avl_alloc()

AvlTree avl_alloc

(

void

)

Definition at line 330 of file avl_tree.c.

References g_tw_avl_node_count, g_tw_pe, avlNode::next, tw_error(), and TW_LOC.

Referenced by avlInsert().

avl_free()

void avl_free

(

AvlTree

t

)

Definition at line 346 of file avl_tree.c.

References AVL_EMPTY, and g_tw_pe.

Referenced by avlDelete(), avlDeleteMin(), and avlDestroy().

avlDelete()

tw_event * avlDelete	(	AvlTree *	t,
		tw_event *	key )

Definition at line 270 of file avl_tree.c.

References AVL_EMPTY, avl_free(), avlDelete(), avlDeleteMin(), avlRebalance(), avlNode::child, tw_event::event_id, tw_event_sig::event_tiebreaker, tw_event::recv_ts, tw_event::send_pe, tw_event::sig, tw_error(), TW_LOC, and TW_STIME_CMP.

Referenced by avlDelete(), and tw_hash_remove().

avlDeleteMin()

tw_event * avlDeleteMin

(

AvlTree *

t

)

Definition at line 245 of file avl_tree.c.

References AVL_EMPTY, avl_free(), avlDeleteMin(), avlRebalance(), avlNode::child, and avlNode::key.

Referenced by avlDelete(), and avlDeleteMin().

avlDestroy()

void avlDestroy

(

AvlTree

t

)

Definition at line 14 of file avl_tree.c.

References AVL_EMPTY, avl_free(), avlDestroy(), and avlNode::child.

Referenced by avlDestroy().

avlFixHeight()

void avlFixHeight ( AvlTree t )

static

Definition at line 96 of file avl_tree.c.

References AVL_EMPTY, avlGetHeight(), avlNode::child, avlNode::height, and ROSS_MAX.

Referenced by avlRebalance(), and avlRotate().

avlGetHeight()

int avlGetHeight

(

AvlTree

t

)

Definition at line 27 of file avl_tree.c.

References AVL_EMPTY, and avlNode::height.

Referenced by avlFixHeight(), avlRebalance(), and avlSanityCheck().

avlInsert()

void avlInsert	(	AvlTree *	t,
		tw_event *	key )

Definition at line 172 of file avl_tree.c.

References avl_alloc(), AVL_EMPTY, avlInsert(), avlRebalance(), tw_event::event_id, tw_event_sig::event_tiebreaker, g_tw_avl_node_count, tw_event::recv_ts, tw_event::send_pe, tw_event::sig, tw_error(), TW_LOC, tw_printf(), and TW_STIME_CMP.

Referenced by avlInsert(), and tw_hash_insert().

avlPrintKeys()

void avlPrintKeys

(

AvlTree

t

)

Definition at line 233 of file avl_tree.c.

References AVL_EMPTY, avlPrintKeys(), and avlNode::child.

Referenced by avlPrintKeys().

avlRebalance()

void avlRebalance ( AvlTree * t )

static

Definition at line 138 of file avl_tree.c.

References AVL_EMPTY, avlFixHeight(), avlGetHeight(), and avlRotate().

Referenced by avlDelete(), avlDeleteMin(), and avlInsert().

avlRotate()

void avlRotate ( AvlTree * root, int d )

static

Definition at line 115 of file avl_tree.c.

References avlFixHeight(), and avlNode::child.

Referenced by avlRebalance().

avlSanityCheck()

void avlSanityCheck

(

AvlTree

root

)

Definition at line 81 of file avl_tree.c.

References AVL_EMPTY, avlGetHeight(), avlSanityCheck(), avlNode::child, avlNode::height, and ROSS_MAX.

Referenced by avlSanityCheck().

avlSearch()

int avlSearch	(	AvlTree	t,
		tw_event *	key )

Definition at line 39 of file avl_tree.c.

References AVL_EMPTY, avlSearch(), avlNode::child, tw_event::event_id, tw_event_sig::event_tiebreaker, avlNode::key, tw_event::recv_ts, tw_event::send_pe, tw_event::sig, and TW_STIME_CMP.

Referenced by avlSearch().

Variable Documentation

pe

tw_pe* pe

Definition at line 10 of file avl_tree.c.

Referenced by collect_sim_engine_data(), dummy_pe_f(), gvt_hook(), io_event_grab(), map_round_robin(), setup_pes(), st_collect_engine_data(), st_collect_engine_data_kps(), st_collect_engine_data_pes(), st_collect_model_data(), tw_delta_alloc(), tw_event_free(), tw_event_grab(), tw_eventq_fossil_collect(), tw_eventq_push_list(), tw_get_stats(), tw_gvt_inprogress(), tw_gvt_inprogress(), tw_gvt_set(), tw_hash_insert(), tw_hash_remove(), tw_kp_next_onpe(), tw_kp_onpe(), tw_kp_rollback_event(), tw_kp_rollback_to_sig(), tw_lp_next_onpe(), tw_lp_onpe(), and tw_scheduler_rollback_and_cancel_events_pe().