| General Info | |
|
Interface: AVLTree_In Files: avltree_in.h Last change: 24/06/2005 Author: Luiz Henrique Shigunov |
Description
Structures |
| Functions | |
|
0x00 - Add - Add an element 0x01 - Count - Get the number of elements 0x02 - Find - Find an element 0x03 - FindAdd - Try to find an element and if not found add it 0x04 - FindClose - Try to find an element and if not found get a near one |
0x05 - Free - Free all elements 0x06 - IsEmpty - Check if the tree is empty 0x07 - Remove - Remove an element 0x08 - Walk - Walk through the tree |
This page describes the AVLTree_In interface which provides access to a particular AVL tree that uses an exposed structure to allow a better use of the structure, quickness and memory economy.
All functions in this interface that add elements use int (*cmpAddFunc)(const AVLTree_In_Node *addNode, const AVLTree_In_Node *node) as compare function.
This function compares node addNode, which is going to be added, with node node that is already in the tree.
All other functions use int (*cmpFunc)(const void *info, const AVLTree_In_Node *node) as compare function. It compares an information info with node node.
These two functions must return:
This was done this way because data is inside the node, just after node data, for instance:
typedef struct {
AVLTree_In_Node node;
char *name;
unsigned int ID;
} MyData;
So, functions that add elements in the tree, must use a different compare function than the one used to look for a node in the tree. For instance, look for name in MyData.
A Tree structure must have these members initialized when it is created: root (initialized with NULL), cmpFunc and cmpAddFunc.
A node must be initialized too, it must be initialized with it's own data (name and ID for MyData).
This interface use this data structure for the tree's root:
typedef struct {
AVLTree_In_Node *root;
int (*cmpFunc)(const void*,const AVLTree_In_Node*);
int (*cmpAddFunc)(const AVLTree_In_Node*,const AVLTree_In_Node*);
unsigned int count;
} AVLTree_In_Tree;
And this data structure for a node:
typedef struct AVLTree_In_Type_Node {
struct AVLTree_In_Type_Node *left;
struct AVLTree_In_Type_Node *right;
signed char bal;
char cache;
char pad[2];
} AVLTree_In_Node;
int AVLTree_In_Add(AVLTree_In_Tree *tree, AVLTree_In_Node *node);
This function adds node in tree.
unsigned int AVLTree_In_Count(const AVLTree_In_Tree *tree);
This function gets the number of elements in tree.
AVLTree_In_Node *AVLTree_In_Find(const AVLTree_In_Tree *tree, const void *info);
This function looks for info in tree.
Use the macros IS_PTR_ERROR and PTR_TO_ERROR to know whether an error occurred and to get the error.
AVLTree_In_Node *AVLTree_In_FindAdd(AVLTree_In_Tree *tree, AVLTree_In_Node *node);
This function looks for node in tree and if it cannot find, adds it.
Use the macros IS_PTR_ERROR and PTR_TO_ERROR to know whether an error occurred and to get the error.
AVLTree_In_Node *AVLTree_In_FindClose(const AVLTree_In_Tree *tree, const void *info);
This function looks for info in tree and if it cannot find it returns a near one.
This function only fails if tree is empty.
Use the macros IS_PTR_ERROR and PTR_TO_ERROR to know whether an error occurred and to get the error.
int AVLTree_In_Free(AVLTree_In_Tree *tree, void (*freeFunc)(AVLTree_In_Node *node));
This function walks through tree and, for each element, calls freeFunc to free node.
int AVLTree_In_IsEmpty(const AVLTree_In_Tree *tree);
This function checks if tree is empty.
AVLTree_In_Node *AVLTree_In_Remove(AVLTree_In_Tree *tree, const void *info);
This function removes info from tree.
It only removes element from tree, it doesn't free it's memory.
Use the macros IS_PTR_ERROR and PTR_TO_ERROR to know whether an error occurred and to get the error.
int AVLTree_In_Walk(const AVLTree_In_Tree *tree, void (*walkFunc)(AVLTree_In_Node *info, void *param1, void *param2), void *param1, void *param2);
This function walks through tree and, for each element, calls walkFunc passing node info and param1 and param2.