src/tree.h

   1 /*--- tree.h -------------------------------------------------------------------
   2 Copyright (C) 2004, 2005, 2006 Sylvain Fourmanoit <syfou@users.sourceforge.net>
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to
   6 deal in the Software without restriction, including without limitation the
   7 rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8 sell copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies of the Software and its documentation and acknowledgment shall be
  13 given in the documentation and software packages that this Software was
  14 used.
  15
  16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  19 THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  20 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22 ------------------------------------------------------------------------------*/
  23 /* This implements a minimalistic tree API with error checking.
  24 */
  25
  26 /*----------------------------------------------------------------------------*/
  27 #ifndef HAVE_TREE_H
  28 #define HAVE_TREE_H
  29
  30 #ifndef HAVE_CONFIG_H
  31 #error Autogenerated config.h should be used.
  32 #endif
  33
  34 /*----------------------------------------------------------------------------*/
  35 #include "config.h"                     /* Autoconf header */
  36
  37 #ifdef HAVE_STDLIB_H
  38 #include <stdlib.h>                     /* C includes: malloc, free, realloc */
  39 #endif
  40
  41 #include "types.h"                      /* Various typedef */
  42 #include "error.h"                      /* Error wrapper */
  43 #include "vector.h"                     /* Vector API */
  44
  45 /*----------------------------------------------------------------------------*/
  46 typedef void * (*tree_free_content_func) (void*);
  47
  48 typedef struct s_tree {
  49   struct s_tree * parent;               /* Reference to parent */
  50   vector        * children;             /* Ref. to vector of children  */
  51   void          * content;              /* Ref. to dynamic, unspecified data */
  52   tree_free_content_func                /* The content freeing function */
  53      tree_free_content;
  54 } tree;
  55
  56 typedef int (*tree_callback_func) (tree*,uint,uint,void*);
  57
  58 typedef enum e_tree_iter_type {
  59   TREE_TOP_DOWN,
  60   TREE_BOTTOM_UP,
  61   TREE_DESTROY} tree_iter_type;
  62
  63 /*----------------------------------------------------------------------------*/
  64 /* Create a tree.
  65    A default wrapping of free() is put in place as the tree_free_content
  66    function reference. Users needing different desallocation should
  67    overwrite it. Return the tree address, or NULL in case of failure.
  68 */
  69 tree * tree_init(void);
  70
  71 /* Push a reference to an untyped element into a tree.
  72    Return 1 if successful, 0 otherwise.
  73 */
  74 int tree_push(tree*, void*);
  75
  76 /* Pop the last reference out of a tree (including all its children)
  77    Return 1 if successful, 0 otherwise.
  78 */
  79 int tree_pop(tree*);
  80
  81 /* Iterate through a tree. The iteration process goes:
  82    - from the top node to the bottom leaves if  last argument
  83      has `TREE_TOP_DOWN' value
  84    - from the bottom leaves to the top if it has `TREE_BOTTOM_UP'
  85      value
  86    - like `THREE_BOTTOM_UP', but stopping as soon as something goes wrong
  87      on the way up with the `TREE_DESTROY' value, and iterating through
  88      children in reverse order.
  89    Return 1 if all calls to tree_callback_func
  90    were successfull, 0 if not.
  91 */
  92 int tree_iterate(tree*,tree_callback_func,void*,tree_iter_type);
  93
  94 /* Destruct a tree.
  95    Return NULL if successful, original tree otherwise, minus what
  96    could have been removed: the most is made to preserve a consistent tree
  97    (bottom-up iteration stopping as soon as something goes wrong),
  98    by `nullifiying' dead branches...
  99 */
 100 tree * tree_free(tree*);
 101
 102 /* This function is a wrapper to make possible recursive memory free
 103    in leaves: it is the default vector_free_item function for the children
 104    vector: it is nothing more than a wrapper around the tree_free() function.
 105    Note: We export it here because it can be usefull to create more complex
 106    structures such as vectors of trees.
 107 */
 108 void * tree_vector_free_item(void *);
 109
 110 /*----------------------------------------------------------------------------*/
 111 #endif