src/tree.c

   1 /*--- tree.c -------------------------------------------------------------------
   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    Have a look at tree.h for a more detailed description. */
  26
  27 /*----------------------------------------------------------------------------*/
  28 #include "tree.h"               /* Tree header */
  29
  30 /*----------------------------------------------------------------------------*/
  31 void *
  32 default_content_free(void* content)
  33 {
  34   TRY_RESET; TRY(free(content));
  35   return (TRY_SUCCESS)?NULL:content;
  36 }
  37
  38 /*----------------------------------------------------------------------------*/
  39 tree *
  40 tree_init(void)
  41 {
  42   tree * mytree;
  43   if ((mytree=(tree*)malloc(sizeof(tree)))) {
  44     if ((mytree->children=vector_init())) {
  45       mytree->parent=NULL;
  46       mytree->content=NULL;
  47       mytree->children->vector_free_item=tree_vector_free_item;
  48       mytree->tree_free_content=default_content_free;
  49     } else TRY_CATCH(free(mytree));
  50   }
  51   return mytree;
  52 }
  53
  54 /*----------------------------------------------------------------------------*/
  55 int
  56 tree_push(tree* mytree, void * elem)
  57 {
  58   int result = 0;
  59   tree * item;
  60   if (mytree && elem)
  61     if ((item = malloc(sizeof(tree)))) {
  62       item->content=elem;
  63       item->parent=mytree;
  64       item->tree_free_content=mytree->tree_free_content;
  65       if ((item->children=vector_init()) &&
  66           vector_push(mytree->children,item)) {
  67         item->children->vector_free_item=tree_vector_free_item;
  68         result=1;
  69       }
  70       else free(item);
  71     }
  72   return result;
  73 }
  74
  75 /*----------------------------------------------------------------------------*/
  76 int
  77 tree_pop(tree* mytree)
  78 {
  79   return mytree && vector_pop(mytree->children);
  80 }
  81
  82 /*----------------------------------------------------------------------------*/
  83 int
  84 tree_inner_iterator(tree * mytree, uint depth, uint pos,
  85                     tree_callback_func tree_callback, void * params,
  86                     tree_iter_type iter_type)
  87 {
  88   int i;
  89   int result=1;
  90 #define TREE_INNER_ITERATOR_CALL \
  91 result&=tree_inner_iterator(mytree->children->content[i],depth+1,i,\
  92                             tree_callback,params,iter_type)
  93
  94   if (iter_type==TREE_TOP_DOWN) result&=tree_callback(mytree,depth,pos,params);
  95   if(iter_type!=TREE_DESTROY)
  96     for(i=0;i<mytree->children->pos;++i)
  97       TREE_INNER_ITERATOR_CALL;
  98   else {
  99     for(i=mytree->children->pos-1;result&&i>-1;--i,--mytree->children->pos)
 100       TREE_INNER_ITERATOR_CALL;
 101     /* Now, this is ugly. Have a look at tree_free_callback for explanation */
 102     if(!result) {
 103       mytree->children->content[--mytree->children->pos]=NULL;
 104       debug("Tree_inner_iterator: memory leak: %d, %d\n",depth,pos);
 105     }
 106   }
 107
 108   if (iter_type!=TREE_TOP_DOWN) result&=tree_callback(mytree,depth,pos,params);
 109   return result;
 110 }
 111
 112 /*----------------------------------------------------------------------------*/
 113 int
 114 tree_iterate(tree* mytree,tree_callback_func tree_callback,void * params,
 115               tree_iter_type iter_type)
 116 {
 117   return mytree &&
 118     tree_inner_iterator(mytree,0,0,tree_callback,params, iter_type);
 119 }
 120
 121 /*----------------------------------------------------------------------------*/
 122 /* This function is called only on a terminal leaf, hence its direct use
 123    of free() instead of vector_free().
 124
 125    NOTE: if error reporting is correctly implemented, no attempt is made at
 126          correcting them: for now, an error leads to discarding the leaf
 127          (hence a memory leak: I know, its ugly, but at least the global
 128          state is preserved!)
 129 */
 130 int
 131 tree_free_callback(tree* mytree,uint depth, uint pos, void *params)
 132 {
 133   int result=0;
 134   /* Whenever this is executed, we are in a terminal
 135      leaf: direct freeing is preferable to vector_free. */
 136   TRY_RESET;
 137   TRY(free(mytree->children->content));
 138   if (TRY_SUCCESS) {
 139     TRY(free(mytree->children));
 140     if(TRY_SUCCESS) {
 141       if (mytree->content)
 142         mytree->content=mytree->tree_free_content(mytree->content);
 143       TRY(free(mytree));
 144     }
 145     result=TRY_SUCCESS;
 146   }
 147 #ifdef DEBUG
 148   if(!result)
 149     debug("Ouch! Memory leak with tree at 0x%x\n",(uint)mytree);
 150 #endif
 151   return result;
 152 }
 153
 154 /*----------------------------------------------------------------------------*/
 155 tree *
 156 tree_free(tree * mytree)
 157 {
 158   return (tree_iterate(mytree,tree_free_callback,NULL,TREE_DESTROY))?
 159     NULL:mytree;
 160 }
 161
 162 /*----------------------------------------------------------------------------*/
 163 void *
 164 tree_vector_free_item(void * mytree)
 165 {
 166   return tree_free((tree*)mytree);
 167 }
 168
 169 /*----------------------------------------------------------------------------*/