AVL Trees

AVL Trees — AVL Trees

Types and Values

Description

AVL Trees

Functions

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

Parameters

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

Parameters

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().

Parameters

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

Parameters

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)

Parameters

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.

Parameters

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

Parameters

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

Parameters

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

Parameters

tree

AVL Tree object

 

Returns

number of items in tree


raptor_avltree_trim ()

void
raptor_avltree_trim (raptor_avltree *tree);

Delete all nodes from an AVL tree but keep the shell.

Parameters

tree

AVLTree object

 

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

Parameters

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_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.

Parameters

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

Parameters

iterator

AVL Tree iterator object

 

raptor_avltree_iterator_get ()

void *
raptor_avltree_iterator_get (raptor_avltree_iterator *iterator);

Get current iteration object

Parameters

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

Parameters

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

Parameters

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()

Parameters

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.

Types and Values

raptor_avltree

typedef struct raptor_avltree_s raptor_avltree;

AVL Tree


enum raptor_avltree_bitflags

Bit flags for AVL Tree class constructor raptor_new_avltree()

Members

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_avltree_iterator

typedef struct raptor_avltree_iterator_s raptor_avltree_iterator;

AVL Tree Iterator as created by raptor_new_avltree_iterator()



Navigation: Redland Home Page

Copyright 2000-2023 Dave Beckett