src/texsourc/libavl/libavl/avl.h

   1 /*
   2  *   Libavl is a library to manage AVL structure to store and organize
   3  *   everykind of data. You just need to implement function to compare,
   4  *   to desallocate and to print your structure.
   5  *
   6  *       DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   7  *                   Version 2, December 2004
   8  *
   9  *   Copyright (C) 2013 Adrien Oliva <adrien.oliva@yapbreak.fr>
  10  *
  11  *   Everyone is permitted to copy and distribute verbatim or modified
  12  *   copies of this license document, and changing it is allowed as long
  13  *   as the name is changed.
  14  *
  15  *           DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
  16  *   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
  17  *
  18  *   0. You just DO WHAT THE FUCK YOU WANT TO.
  19  */
  20
  21 /**
  22  * \file avl.h
  23  * \author Adrien Oliva
  24  * \date May, 24th, 2011
  25  * \brief Generic AVL-tree library.
  26  * \version 1.0.0
  27  *
  28  * Implementation of an AVL tree to store generic data.
  29  * In computer science, an AVL tree is a self-balancing binary search tree,
  30  * and it was the first such data structure to be invented. In an AVL tree,
  31  * the heights of the two child subtrees of any node differ by at most one.
  32  * Lookup, insertion, and deletion all take \f$\mathcal{O}(\log n)\f$
  33  * time in both the average and worst cases, where \e n is the number of
  34  * nodes in the tree prior to the operation. Insertions and deletions may
  35  * require the tree to be rebalanced by one or more tree rotations.
  36  *
  37  * The AVL tree is named after its two Soviet inventors, G.M. Adelson-Velskii
  38  * and E.M. Landis, who published it in their 1962 paper "An algorithm for the
  39  * organization of information."
  40  *
  41  * The balance factor of a node is the height of its left subtree minus the
  42  * height of its right subtree (sometimes opposite) and a node with balance
  43  * factor 1, 0, or -1 is considered balanced. A node with any other balance
  44  * factor is considered unbalanced and requires rebalancing the tree. The
  45  * balance factor is either stored directly at each node or computed from the
  46  * heights of the subtrees.
  47  *
  48  * \section Usage Use of library
  49  *
  50  * Here is an example of code that store structure in AVL tree:
  51  *
  52  * <pre>
  53  *  #include <stdlib.h>
  54  *  #include <stdio.h>
  55  *  #include "avl.h"
  56  *
  57  *  // Structure we want to store
  58  *  // key is used to order data
  59  *  struct data {
  60  *      int key;
  61  *       int value;
  62  *   };
  63  *
  64  *   // Function that compares two struct data
  65  *   int data_cmp(void *a, void *b)
  66  *   {
  67  *       struct data *aa = (struct data *) a;
  68  *       struct data *bb = (struct data *) b;
  69  *
  70  *       // Protect against NULL pointer
  71  *       // It could generally never happened
  72  *       if (!aa || !bb)
  73  *           return 0;
  74  *
  75  *       return aa->key - bb->key;
  76  *   }
  77  *
  78  *   // Function that dumps data structure
  79  *   void data_print(void *d)
  80  *   {
  81  *       struct data *dd = (struct data *) d;
  82  *
  83  *       if (dd)
  84  *           printf("{ %d => %d }\n", dd->key, dd->value);
  85  *   }
  86  *
  87  *   // Function that delete a data structure
  88  *   void data_delete(void *d)
  89  *   {
  90  *       struct data *dd = (struct data *) d;
  91  *
  92  *       if (dd) {
  93  *           // You can put here all additional needed
  94  *           // memory deallocation
  95  *           free(dd);
  96  *       }
  97  *   }
  98  *
  99  *   int main(int argc, char *argv)
 100  *   {
 101  *       tree *avl_tree = NULL;
 102  *       struct data tmp;
 103  *       int result;
 104  *
 105  *       // Initialize a new tree with our three previously defined
 106  *       // functions to store data structure.
 107  *       avl_tree = init_dictionnary(data_cmp, data_print, data_delete);
 108  *
 109  *       tmp.key = 42;
 110  *       tmp.value = 4242;
 111  *
 112  *       // Add element {42, 4242} in our tree.
 113  *       result = insert_elmt(avl_tree, &tmp, sizeof(struct data));
 114  *       // Here result is equal to 1 since there is only 1 element in tree.
 115  *
 116  *       // Dump tree to stdout with data_print function
 117  *       print_tree(avl_tree);
 118  *
 119  *       // For all search function, the only value needed in tmp structure
 120  *       // is key field.
 121  *       tmp.key = 20;
 122  *       tmp.value = 0;
 123  *
 124  *       if (!is_present(avl_tree, &tmp))
 125  *           printf("Key 20 is not found.\n");
 126  *
 127  *       tmp.key = 42;
 128  *       if (is_present(avl_tree, &tmp))
 129  *           printf("Key 42 exist in tree.\n");
 130  *
 131  *       if (get_data(avl_tree, &tmp, sizeof(struct data)))
 132  *           printf("Now, tmp.key is equal to 4242\n");
 133  *
 134  *       delete_node(avl_tree, &tmp);
 135  *       if (!is_present(avl_tree, &tmp))
 136  *           printf("Key 42 does not exist anymore.\n");
 137  *
 138  *       // Free all memory
 139  *       delete_tree(avl_tree);
 140  *
 141  *       return 0;
 142  *   }
 143  *   </pre>
 144  *
 145  * You can find this example in folder \b example.
 146  *
 147  * \subsection Tree initialisation
 148  *
 149  * To start a new tree, you need to init a new one with function
 150  * \b init_tree.
 151  *
 152  * \subsection Manage data
 153  *
 154  * The libavl provide all necessary function to store, retrieve and
 155  * browse your data. The following set gives basic operation:
 156  *  * \b insert_elmt
 157  *  * \b is_present
 158  *  * \b get_data
 159  *  * \b delete_node
 160  *  * \b delete_node_min
 161  *
 162  * Moreover, libavl gives the availability to browse your entire data
 163  * or a subset of your data with:
 164  *  * \b explore_tree
 165  *  * \b explore_restrain_tree
 166  *  * \b print_tree
 167  *
 168  * Finally, libavl take care of your memory and deallocate all memory
 169  * used in a tree when you want to destroy it with \b delete_tree.
 170  *
 171  */
 172 #ifndef __AVL_H__
 173 #define __AVL_H__
 174
 175 #include <stddef.h>
 176
 177
 178
 179 /** \struct _node
 180  * \brief Node of a tree
 181  *
 182  * Structure that contain all data usefull to organize the tree
 183  */
 184 struct _node {
 185         /** Size of subtree */
 186         unsigned height;
 187         /** Left son */
 188         struct _node *left;
 189         /** Right son */
 190         struct _node *right;
 191         /** Pointer to data stored in this node */
 192         void *data;
 193 };
 194
 195 /**
 196  * \brief Pointer to the \c _node structure.
 197  */
 198 typedef struct _node *node;
 199
 200 /**
 201  * \brief Tree structure wich contains all necessary element.
 202  */
 203 typedef struct _tree {
 204         /** Number of element in tree */
 205         unsigned count;
 206         /** Pointer to the first node of tree */
 207         node root;
 208         /** \brief External function to compare data
 209          *
 210          * \param a Pointer to first element to compare
 211          * \param b Pointer to second element to compare
 212          *
 213          * \return 0 if a = b, positive if a > b and negative if a < b.
 214          *
 215          * \note \e You must implement this function. It is necessary for the library
 216          * to work and depends on your data you want to store.
 217          */
 218         int (* data_cmp) (void *, void *);
 219         /** \brief External function to print data.
 220          *
 221          * \param d Pointer to data to print.
 222          *
 223          * This function is usefull for debuging program.
 224          *
 225          * \note \e You must implement this function. It is necessary for the library
 226          * to work and depends on your data you want to store.
 227          */
 228         void (* data_print) (void *d);
 229
 230         /** \brief External function to delete data.
 231          *
 232          * \param d Pointer to data to delete.
 233          *
 234          * This function is usefull for when you want to delete data from tree to prevent
 235          * memory leak.
 236          *
 237          * \note \e You must implement this function. It is necessary for the library
 238          * to work and depends on your data you want to store.
 239          */
 240         void (* data_delete) (void *d);
 241
 242         /** \brief External function to copy data.
 243          *
 244          * \param d Pointer to data to copy.
 245          * \return New data allocation with all its fields filled.
 246          *
 247          * \note \e You must implement this function. It is necessary for the library
 248          * to work and depends on your data you want to store.
 249          */
 250         void (* data_copy) (void *, void *);
 251 } tree;
 252
 253
 254
 255 /* ************************************************************************* *\
 256 |*                      EXTERNAL FUNCTION                                    *|
 257 \* ************************************************************************* */
 258
 259 /** \fn tree *init_dictionnary(int (*data_cmp)(void *, void *),
 260  *                             void (*data_print)(void *),
 261  *                             void (*data_delete)(void *),
 262  *                             void (*data_copy)(void *, void *));
 263  * \brief Initialize dictionnary.
 264  *
 265  * \return Pointer to new tree.
 266  *
 267  * \param data_cmp Function to compare data.
 268  * \param data_print Function to print data.
 269  * \param data_delete Function to delete data.
 270  * \param data_copy Function to copy data.
 271  *
 272  * This function return an initilized tree.
 273  *
 274  * \note By default, if you do not provide function usefull to the tree,
 275  * the LibAVL library uses its own function. As LibAVL does not know exactly
 276  * the structure and the definition of your data, result can not be as good
 277  * as expected. Details on these functions are given in the following.
 278  *
 279  * \section LibAVL internal data function
 280  *
 281  *    - Compare function: by default, the internal \c data_cmp function will
 282  *      return the difference between the two pointer given in arguments
 283  *
 284  *          return (int) ((ptrdiff_t) a - (ptrdiff_t) b);
 285  *
 286  *      The \c data_cmp function is really critical and guarantee efficiency of
 287  *      LibAVL.
 288  *    - Print function: by default, the internal \c data_print function will
 289  *      print the addresse contained in pointer in argument, in hexadecimal
 290  *
 291  *          printf("0x%08x\n", d);
 292  *
 293  *      Since \c data_print is mainly used as debug function to dump a complete
 294  *      tree, it is not the most important data function, but with the correct
 295  *      implementation, it could save lots of time and money when something
 296  *      went wrong.
 297  *    - Delete function: by default, the internal \c data_delete function will
 298  *      call \c free on the argument pointer. If your data is only a static
 299  *      structure or a simple type, this function is enough. But for bigger
 300  *      object like a string array, it is necessary to provide a new
 301  *      \c data_delete function to avoid memory leak.
 302  *    - Copy function: by default, the internal \c data_copy function will
 303  *      memcpy data.
 304  */
 305 tree *init_dictionnary(int (*data_cmp)(void *, void *),
 306                        void (*data_print)(void *),
 307                        void (*data_delete)(void *),
 308                        void (*data_copy)(void *, void *));
 309
 310 /** \fn int insert_elmt(tree *t, void *data, size_t datasize);
 311  * \brief Insert new element in tree.
 312  *
 313  * \return Number of element inserted in tree.
 314  * \param t Pointer to tree.
 315  * \param data Pointer to data to add.
 316  * \param datasize Size of data to add.
 317  *
 318  * This function allocate a new memory space with the given size
 319  * and copy object pointed by \c data to the newly created space.
 320  */
 321 unsigned int insert_elmt(tree *t, void *data, size_t datasize);
 322
 323 /** \fn void verif_tree(tree *t);
 324  * \brief Deffensive check if tree is a real AVL tree.
 325  *
 326  * \param t Pointer to tree.
 327  *
 328  * If tree is not an AVL tree, this function end on an assert.
 329  */
 330 void verif_tree(tree *t);
 331
 332 /** \fn void delete_tree(tree *t);
 333  * \brief Deallocate all memory used by tree.
 334  *
 335  * \param t Pointer to tree to delete.
 336  */
 337 void delete_tree(tree *t);
 338
 339 /** \fn void print_tree(tree *t);
 340  * \brief Use for debug only. Print all element in tree with function
 341  * \c data_print.
 342  *
 343  * \param t Pointer to tree.
 344  */
 345 void print_tree(tree *t);
 346
 347 /** \fn void explore_tree(tree *t, void (*treatement)(void *, void *),
 348  *                              void *param);
 349  * \brief Execute function \c treatement on every node in tree.
 350  *
 351  * \param t Pointer to tree.
 352  * \param treatement Function to apply to each node.
 353  * \param param Pointer to extra data to pass to \c treatement function.
 354  *
 355  * This function goes thought the entire tree and, if \c n is the pointer
 356  * to the current node, call the function:
 357  *
 358  *      treatement(n, param);
 359  *
 360  */
 361 void explore_tree(tree *t, void (*treatement)(void *, void *), void *param);
 362
 363 /** \fn explore_restrain_tree(tree *t, int (*check)(void *, void *),
 364  *                              void *param,
 365  *                              void *data_min, void *data_max);
 366  * \brief Execute function \c check on every node between \c data_min and
 367  * \c data_max.
 368  *
 369  * \return Accumulation of all return value of \c check function.
 370  * \param t Pointer to tree.
 371  * \param check Function apply on every node between \c data_min and
 372  * \c data_max
 373  * \param param Pointer to extra data to pass to \c check function.
 374  * \param data_min Pointer to the minimum element.
 375  * \param data_max Pointer to the maximum element.
 376  *
 377  * This function goes thought a part of tree bounded with \c data_min and
 378  * \c data_max, and if \c n is the pointer to the current node, it calls
 379  * the function:
 380  *
 381  *      accu += check(n, param);
 382  *
 383  * The value of \c accu is returned by \c explore_restrain_tree.
 384  */
 385 int explore_restrain_tree(tree *t, int (*check)(void *, void *), void *param,
 386                                 void *data_min, void *data_max);
 387
 388 /** \fn int is_present(tree *t, void *d);
 389  * \brief Function to check if a given data is present in tree.
 390  *
 391  * \return 1 if data is present, 0 if not.
 392  * \param t Pointer to tree.
 393  * \param d Pointer to data. Only field used in \c avl_data_cmp need
 394  * to be filled in \c d.
 395  */
 396 int is_present(tree *t, void *d);
 397
 398 /** \fn void delete_node_min(tree *t);
 399  * \brief Delete minimum element of a tree.
 400  *
 401  * \param t Tree where minimum element will be deleted.
 402  */
 403 void delete_node_min(tree *t);
 404
 405 /** \fn void delete_node(tree *t, void *data);
 406  * \brief Delete node n of tree.
 407  *
 408  * \param t Pointer to tree.
 409  * \param data Data to delete.
 410  */
 411 void delete_node(tree *t, void *data);
 412
 413 /** \fn int get_data(tree *t, void *data, size_t data_size);
 414  * \brief Fill information pointed by data with the data stored in the tree.
 415  *
 416  * \return True if value pointed by data are relevant, false if not.
 417  *
 418  * \param t Pointer to tree.
 419  * \param data Data to retrieve. At the begining of the function, only
 420  * field used in \c avl_data_cmp must be filled.
 421  * \param data_size Size of data structure pointed by data.
 422  */
 423 int get_data(tree *t, void *data, size_t data_size);
 424
 425 #endif