AVL Trees

AVL Trees — AVL Trees

Synopsis

typedef             raptor_avltree;
enum                raptor_avltree_bitflags;
raptor_avltree *    raptor_new_avltree                  (raptor_data_compare_handler compare_handler,
                                                         raptor_data_free_handler free_handler,
                                                         unsigned int flags);
void                raptor_free_avltree                 (raptor_avltree *tree);
int                 raptor_avltree_add                  (raptor_avltree *tree,
                                                         void *p_data);
int                 raptor_avltree_delete               (raptor_avltree *tree,
                                                         void *p_data);
int                 raptor_avltree_print                (raptor_avltree *tree,
                                                         FILE *stream);
void *              raptor_avltree_remove               (raptor_avltree *tree,
                                                         void *p_data);
void *              raptor_avltree_search               (raptor_avltree *tree,
                                                         const void *p_data);
void                raptor_avltree_set_print_handler    (raptor_avltree *tree,
                                                         raptor_data_print_handler print_handler);
int                 raptor_avltree_size                 (raptor_avltree *tree);
int                 raptor_avltree_visit                (raptor_avltree *tree,
                                                         raptor_avltree_visit_handler visit_handler,
                                                         void *user_data);
typedef             raptor_avltree_iterator;
raptor_avltree_iterator * raptor_new_avltree_iterator   (raptor_avltree *tree,
                                                         void *range,
                                                         raptor_data_free_handler range_free_handler,
                                                         int direction);
void                raptor_free_avltree_iterator        (raptor_avltree_iterator *iterator);
void *              raptor_avltree_iterator_get         (raptor_avltree_iterator *iterator);
int                 raptor_avltree_iterator_is_end      (raptor_avltree_iterator *iterator);
int                 raptor_avltree_iterator_next        (raptor_avltree_iterator *iterator);
int                 (*raptor_avltree_visit_handler)     (int depth,
                                                         void *data,
                                                         void *user_data);

Description

AVL Trees

Details

raptor_avltree

typedef struct raptor_avltree_s raptor_avltree;

AVL Tree

enum raptor_avltree_bitflags

typedef enum {
 RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES = 1
} raptor_avltree_bitflags;

Bit flags for AVL Tree class constructor raptor_new_avltree()

RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES

 If set raptor_avltree_add() will replace any duplicate items. If not set, raptor_avltree_add() will not replace them and will return status >0 when adding a duplicate. (Default is not set)

raptor_new_avltree ()

raptor_avltree *    raptor_new_avltree                  (raptor_data_compare_handler compare_handler,
                                                         raptor_data_free_handler free_handler,
                                                         unsigned int flags);

AVL Tree Constructor

compare_handler :

 item comparison handler for ordering

free_handler :

 item free handler (or NULL)

flags :

 AVLTree flags - bitmask of raptor_avltree_bitflags flags.

Returns :

 new AVL Tree or NULL on failure

raptor_free_avltree ()

void                raptor_free_avltree                 (raptor_avltree *tree);

AVL Tree destructor

tree :

 AVLTree object

raptor_avltree_add ()

int                 raptor_avltree_add                  (raptor_avltree *tree,
                                                         void *p_data);

add an item to an AVL Tree

The item added becomes owned by the AVL Tree, and will be freed by the free_handler argument given to raptor_new_avltree().

tree :

 AVL Tree object

p_data :

 pointer to data item

Returns :

 0 on success, >0 if equivalent item exists (and the old element remains in the tree), <0 on failure

raptor_avltree_delete ()

int                 raptor_avltree_delete               (raptor_avltree *tree,
                                                         void *p_data);

Remove an item from an AVL Tree and free it

tree :

 AVL Tree object

p_data :

 pointer to data item

Returns :

 non-0 on failure

raptor_avltree_print ()

int                 raptor_avltree_print                (raptor_avltree *tree,
                                                         FILE *stream);

Print the items in the tree in order to a stream (for debugging)

tree :

 AVL Tree

stream :

 stream to print to

Returns :

 non-0 on failure

raptor_avltree_remove ()

void *              raptor_avltree_remove               (raptor_avltree *tree,
                                                         void *p_data);

Remove an item from an AVL Tree and return it

The item removed is no longer owned by the AVL Tree and is owned by the caller.

tree :

 AVL Tree object

p_data :

 pointer to data item

Returns :

 object or NULL on failure or if not found

raptor_avltree_search ()

void *              raptor_avltree_search               (raptor_avltree *tree,
                                                         const void *p_data);

Find an item in an AVL Tree

tree :

 AVL Tree object

p_data :

 pointer to data item

Returns :

 shared pointer to item (still owned by AVL Tree) or NULL on failure or if not found

raptor_avltree_set_print_handler ()

void                raptor_avltree_set_print_handler    (raptor_avltree *tree,
                                                         raptor_data_print_handler print_handler);

Set the handler for printing an item in a tree

tree :

 AVL Tree object

print_handler :

 print function

raptor_avltree_size ()

int                 raptor_avltree_size                 (raptor_avltree *tree);

Get the number of items in the AVL Tree

tree :

 AVL Tree object

Returns :

 number of items in tree

raptor_avltree_visit ()

int                 raptor_avltree_visit                (raptor_avltree *tree,
                                                         raptor_avltree_visit_handler visit_handler,
                                                         void *user_data);

Perform an in-order visit of the items in the AVL Tree

tree :

 AVL Tree object

visit_handler :

 visit function to call at each item

user_data :

 user data pointer fo visit function

Returns :

 non-0 if traversal was terminated early by visit_handler

raptor_avltree_iterator

typedef struct raptor_avltree_iterator_s raptor_avltree_iterator;

AVL Tree Iterator as created by raptor_new_avltree_iterator()

raptor_new_avltree_iterator ()

raptor_avltree_iterator * raptor_new_avltree_iterator   (raptor_avltree *tree,
                                                         void *range,
                                                         raptor_data_free_handler range_free_handler,
                                                         int direction);

Get an in-order iterator for the start of a range, or the entire contents

If range is NULL, the entire tree is walked in order. If range specifies a range (i.e. the tree comparison function will 'match' (return 0 for) range and /several/ nodes), the iterator will be placed at the leftmost child matching range, and raptor_avltree_iterator_next will iterate over all nodes (and only nodes) that match range.

tree :

 raptor_avltree object

range :

 range

range_free_handler :

 function to free range object

direction :

 <0 to go 'backwards' otherwise 'forwards'

Returns :

 a new raptor_avltree_iterator object or NULL on failure

raptor_free_avltree_iterator ()

void                raptor_free_avltree_iterator        (raptor_avltree_iterator *iterator);

AVL Tree Iterator destructor

iterator :

 AVL Tree iterator object

raptor_avltree_iterator_get ()

void *              raptor_avltree_iterator_get         (raptor_avltree_iterator *iterator);

Get current iteration object

iterator :

 AVL Tree iterator object

Returns :

 object or NULL if iteration is finished

raptor_avltree_iterator_is_end ()

int                 raptor_avltree_iterator_is_end      (raptor_avltree_iterator *iterator);

Test if an iteration is finished

iterator :

 AVL Tree iterator object

Returns :

 non-0 if iteration is finished

raptor_avltree_iterator_next ()

int                 raptor_avltree_iterator_next        (raptor_avltree_iterator *iterator);

Move iteration to next/prev object

iterator :

 AVL Tree iterator object

Returns :

 non-0 if iteration is finished

raptor_avltree_visit_handler ()

int                 (*raptor_avltree_visit_handler)     (int depth,
                                                         void *data,
                                                         void *user_data);

AVL Tree visitor function as given to raptor_avltree_visit()

depth :

 depth of object in tree

data :

 data object being visited

user_data :

 user data arg to raptor_avltree_visit()

Returns :

 non-0 to terminate visit early.
Generated by GTK-Doc V1.18