rbtree.64.c File Reference

rbltree interface implementation. More...

#include <rbtree.h>
#include <cpu/sync.h>
#include <list.h>

Classes
struct	rbtree_node_t
struct	rbtree_t
struct	rbtree_iterator_t

Typedefs
typedef enum rbtree_color_t	rbtree_color_t
typedef struct rbtree_node_t	rbtree_node_t
typedef struct rbtree_t	rbtree_t
typedef struct rbtree_iterator_t	rbtree_iterator_t

Enumerations
enum	rbtree_color_t { RBTREE_COLOR_RED , RBTREE_COLOR_BLACK }

Functions
	MODULE ("turnstone.lib")
boolean_t	rbtree_node_is_on_left (rbtree_node_t *rbn)
boolean_t	rbtree_node_has_red_child (rbtree_node_t *rbn)
rbtree_node_t *	rbtree_node_uncle (rbtree_node_t *rbn)
rbtree_node_t *	rbtree_node_sibling (rbtree_node_t *rbn)
void	rbtree_node_move_down (rbtree_node_t *rbn, rbtree_node_t *new_parent)
rbtree_node_t *	rbtree_node_new (memory_heap_t *heap, const void *key, const void *data)
void	rbtree_node_swap_colors (rbtree_node_t *rbn1, rbtree_node_t *rbn2)
void	rbtree_node_swap_values (rbtree_node_t *rbn1, rbtree_node_t *rbn2)
rbtree_node_t *	rbtree_node_successor (rbtree_node_t *x)
rbtree_node_t *	rbtree_node_bst_replace (rbtree_node_t *x)
void	rbtree_left_rotate (rbtree_t *rbt, rbtree_node_t *rbn)
void	rbtree_right_rotate (rbtree_t *rbt, rbtree_node_t *rbn)
void	rbtree_fix_redred (rbtree_t *rbt, rbtree_node_t *rbn)
void	rbtree_fix_blackblack (rbtree_t *rbt, rbtree_node_t *rbn)
void	rbtree_delete_node (rbtree_t *rbt, rbtree_node_t *v)
boolean_t	rbtree_search_node (rbtree_t *rbt, const void *key, index_key_comparator_f cmp, rbtree_node_t **res)
uint64_t	rbtree_size (index_t *idx)
int8_t	rbtree_insert (index_t *idx, const void *key, const void *data, void **removed_data)
int8_t	rbtree_delete (index_t *idx, const void *key, void **removed_data)
const void *	rbtree_find (index_t *idx, const void *key)
iterator_t *	rbtree_search (index_t *idx, const void *key1, const void *key2, const index_key_search_criteria_t criteria)
iterator_t *	rbtree_create_iterator (index_t *idx)
boolean_t	rbtree_contains (index_t *idx, const void *key)
list_t *	rbtree_inorder (index_t *idx, const void *key1, const void *key2, index_key_search_criteria_t criteria)
index_t *	rbtree_create_index_with_heap (memory_heap_t *heap, index_key_comparator_f comparator)
	create rbtree index More...
int8_t	rbtree_destroy_index (index_t *idx)
	destroy rbtree index More...
int8_t	rbtree_iterator_destroy (iterator_t *iterator)
int8_t	rbtree_iterator_end_of_index (iterator_t *iterator)
iterator_t *	rbtree_iterator_next (iterator_t *iterator)
const void *	rbtree_iterator_get_key (iterator_t *iterator)
const void *	rbtree_iterator_get_data (iterator_t *iterator)

Detailed Description

rbltree interface implementation.

This work is licensed under TURNSTONE OS Public License. Please read and understand latest version of Licence.

Function Documentation

rbtree_create_index_with_heap()

index_t * rbtree_create_index_with_heap	(	memory_heap_t *	heap,
		index_key_comparator_f	comparator
	)

create rbtree index

Parameters

[in]	heap	memory heap to use
[in]	comparator	index key comparator

Returns

index or null

rbtree_destroy_index()

int8_t rbtree_destroy_index

(

index_t *

idx

)

destroy rbtree index

Parameters

[in]

idx

index to destroy

Returns

0 if success