rbtree.h

Go to the documentation of this file.

 
#pragma once
 
#ifndef RBTREE_ITER_MAX_HEIGHT
#define RBTREE_ITER_MAX_HEIGHT 64
#endif
 
// ============================================================================
// Opaque types.
 
typedef struct rbtree_node_t rbtree_node_t;
typedef struct rbtree_t rbtree_t;
typedef struct rbtree_iter_t rbtree_iter_t;
 
// ============================================================================
// Comparison functions.
typedef int (*rbtree_tree_cmp_f)(rbtree_t *tree, rbtree_node_t *a, void *arg);
typedef int (*rbtree_tree_node_cmp_f)(rbtree_t *tree, rbtree_node_t *a, rbtree_node_t *b);
typedef void (*rbtree_tree_node_f)(rbtree_t *tree, rbtree_node_t *node);
 
// ============================================================================
// Node management functions.
 
rbtree_node_t *rbtree_node_alloc(void);
 
rbtree_node_t *rbtree_node_create(void *value);
 
rbtree_node_t *rbtree_node_init(rbtree_node_t *node, void *value);
 
void *rbtree_node_get_value(rbtree_node_t *node);
 
void rbtree_node_dealloc(rbtree_node_t *node);
 
// ============================================================================
// Tree management functions.
 
rbtree_t *rbtree_tree_alloc(void);
 
rbtree_t *rbtree_tree_create(rbtree_tree_node_cmp_f cmp);
 
rbtree_t *rbtree_tree_init(rbtree_t *tree, rbtree_tree_node_cmp_f cmp);
 
void rbtree_tree_dealloc(rbtree_t *tree, rbtree_tree_node_f node_cb);
 
void *rbtree_tree_find(rbtree_t *tree, void *value);
 
void *rbtree_tree_find_by_value(rbtree_t *tree, rbtree_tree_cmp_f cmp_fun, void *value);
 
int rbtree_tree_insert(rbtree_t *tree, void *value);
 
int rbtree_tree_remove(rbtree_t *tree, void *value);
 
unsigned int rbtree_tree_size(rbtree_t *tree);
 
int rbtree_tree_insert_node(rbtree_t *tree, rbtree_node_t *node);
 
int rbtree_tree_remove_with_cb(rbtree_t *tree, void *value, rbtree_tree_node_f node_cb);
 
// ============================================================================
// Iterators.
 
rbtree_iter_t *rbtree_iter_alloc(void);
 
rbtree_iter_t *rbtree_iter_init(rbtree_iter_t *iter);
 
rbtree_iter_t *rbtree_iter_create(void);
 
void rbtree_iter_dealloc(rbtree_iter_t *iter);
 
void *rbtree_iter_first(rbtree_iter_t *iter, rbtree_t *tree);
 
void *rbtree_iter_last(rbtree_iter_t *iter, rbtree_t *tree);
 
void *rbtree_iter_next(rbtree_iter_t *iter);
 
void *rbtree_iter_prev(rbtree_iter_t *iter);
 
// ============================================================================
// Tree debugging functions.
 
int rbtree_tree_test(rbtree_t *tree, rbtree_node_t *root);
 
void rbtree_tree_print(rbtree_t *tree, rbtree_tree_node_f fun);