tree.h

   1 /* A tree class.
   2  * By Richard W.M. Jones <rich@annexia.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the Free
  16  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  * $Id: tree.h,v 1.1 2002/09/15 15:08:52 rich Exp $
  19  */
  20
  21 #ifndef TREE_H
  22 #define TREE_H
  23
  24 #include <pool.h>
  25 #include <vector.h>
  26
  27 struct tree
  28 {
  29   struct vector v;              /* Vector of subnodes. */
  30   size_t size;                  /* Size of the data. */
  31   char data[0];                 /* Opaque data (used by the application). */
  32 };
  33
  34 typedef struct tree *tree;
  35
  36 /* Function: new_tree - allocate a new tree, node or leaf
  37  * Function: _tree_new
  38  *
  39  * Allocate a new tree / node / leaf.
  40  *
  41  * A node in the tree is defined as a list of pointers to subnodes
  42  * and some data stored in the node itself. Because of the recursive
  43  * definition of trees, a tree is just a node, the special 'root'
  44  * node. A leaf is just a node which happens to have no subnodes. You
  45  * can add subnodes to a leaf later if you want.
  46  *
  47  * The @code{new_vector} macro is used to allocate a node in the
  48  * tree storing data @code{type} in the node. It just evaluates the
  49  * size of @code{type} and calls @code{_tree_new} which actually
  50  * allocates the node.
  51  *
  52  * Unless you are very careful with types, you should always make
  53  * sure that each node in your tree has the same @code{type}.
  54  *
  55  * Returns: The tree / node (of type @code{tree}).
  56  */
  57 #define new_tree(pool,type) _tree_new ((pool), sizeof (type))
  58 extern tree _tree_new (pool, size_t size);
  59
  60 /* Function: tree_get_data - access the data stored in a node
  61  * Function: _tree_get_data
  62  * Function: tree_set_data
  63  * Function: _tree_set_data
  64  *
  65  * These functions allow you to access the data stored in the node.
  66  *
  67  * @code{tree_get_data} copies the data out of the node into the
  68  * local variable.
  69  *
  70  * @code{tree_set_data} copies the data from the local variable into
  71  * the node.
  72  */
  73 #define tree_get_data(t,obj) _tree_get_data ((t), &(obj))
  74 extern void _tree_get_data (tree t, void *ptr);
  75 #define tree_set_data(t,obj) _tree_set_data ((t), &(obj))
  76 extern void _tree_set_data (tree t, const void *ptr);
  77
  78 /* Function: copy_tree - make a deep copy of a tree
  79  *
  80  * Make a deep copy of tree @code{t} into pool @code{pool}. This
  81  * copies all of the nodes and the data in those nodes recursively
  82  * Note however that if the data in a node is a / contains a pointer
  83  * then the pointed-to data will not be copied.
  84  *
  85  * Returns: The copied tree (of type @code{tree}).
  86  */
  87 extern tree copy_tree (pool, tree t);
  88
  89 /* Function: tree_push_back - add or remove subnodes to or from a node
  90  * Function: tree_pop_back
  91  * Function: tree_push_front
  92  * Function: tree_pop_front
  93  *
  94  * The @code{*_push_*} functions push subnodes into nodes.
  95  *
  96  * The @code{*_pop_*} functions pop subnodes off nodes into local variables.
  97  *
  98  * The @code{*_front} functions push and pop subnodes off the front
  99  * of a node.
 100  *
 101  * The @code{*_back} functions push and pop subnodes
 102  * off the end of the node.
 103  *
 104  * Array indexes are checked. You cannot pop a node which has
 105  * no subnodes.
 106  */
 107 #define tree_push_back(t,subnode) (vector_push_back ((vector)(t), (subnode)))
 108 #define tree_pop_back(t,subnode) (vector_pop_back ((vector)(t), (subnode)))
 109 #define tree_push_front(t,subnode) (vector_push_front ((vector)(t), (subnode)))
 110 #define tree_pop_front(t,subnode) (vector_pop_front ((vector)(t), (subnode)))
 111
 112 /* Function: tree_get_subnode - get a particular subnode of a node
 113  * Function: tree_get
 114  *
 115  * @code{tree_get_subnode} returns the @code{i}th subnode of a node. The
 116  * node is unaffected.
 117  *
 118  * @code{tree_get} is identical.
 119  */
 120 #define tree_get_subnode(t,i,subnode) tree_get((t), (i), (subnode))
 121 #define tree_get(t,i,subnode) (vector_get ((vector)(t), (i), (subnode)))
 122
 123 /* Function: tree_insert - insert subnodes into a tree
 124  * Function: tree_insert_array
 125  *
 126  * @code{tree_insert} inserts a single subnode @code{subnode} before subnode
 127  * @code{i}. All other subnodes are moved up to make space.
 128  *
 129  * @code{tree_insert_array} inserts an array of @code{n} subnodes
 130  * starting at address @code{ptr} into the node before index
 131  * @code{i}.
 132  *
 133  * Array indexes are checked.
 134  */
 135 #define tree_insert(t,i,subnode) (vector_insert ((vector)(t), (i), (subnode)))
 136 #define tree_insert_array(t,i,ptr,n) (vector_insert_array ((vector)(t), (i), (ptr), (n)))
 137
 138 /* Function: tree_replace - replace subnodes of a node
 139  * Function: tree_replace_array
 140  *
 141  * @code{tree_replace} replaces the single subnode at
 142  * @code{v[i]} with @code{subnode}.
 143  *
 144  * @code{tree_replace_array} replaces the @code{n} subnodes
 145  * in the node starting at index @code{i} with the @code{n}
 146  * subnodes from the array @code{ptr}.
 147  *
 148  * Array indexes are checked.
 149  */
 150 #define tree_replace(t,i,subnode) (vector_replace ((vector)(t), (i), (subnode)))
 151 #define tree_replace_array(t,i,ptr,n) (vector_replace_array ((vector)(t), (i), (ptr), (n)))
 152
 153 /* Function: tree_erase - erase subnodes of a node
 154  * Function: tree_erase_range
 155  * Function: tree_clear
 156  *
 157  * @code{tree_erase} removes the subnode index @code{i}, shuffling
 158  * the later subnodes down by one place to fill the space.
 159  *
 160  * @code{tree_erase_range} removes a range of subnodes @code{i}
 161  * to @code{j-1} (@code{i <= j}), shuffling later subnodes down
 162  * to fill the space.
 163  *
 164  * @code{tree_clear} removes all subnodes from the node, setting
 165  * its size to @code{0}, and effectively making the node into a leaf.
 166  *
 167  * Array indexes are checked.
 168  */
 169 #define tree_erase(t,i) (vector_erase ((vector)(t), (i)))
 170 #define tree_erase_range(t,i,j) (vector_erase_range ((vector)(t), (i), (j)))
 171 #define tree_clear(t) (vector_clear ((vector)(t)))
 172
 173 /* Function: tree_size - return the number of subnodes of a node
 174  * Function: tree_nr_subnodes
 175  *
 176  * Return the size (ie. number of subnodes) in the node. The
 177  * @code{tree_nr_subnodes} macro is identical.
 178  */
 179 #define tree_size(t) (vector_size ((vector)(t)))
 180 #define tree_nr_subnodes(t) tree_size(t)
 181
 182 /* Function: tree_swap - swap the order of two subnodes of a node
 183  *
 184  * Swap subnodes @code{i} and @code{j} of tree @code{t}.
 185  */
 186 #define tree_swap(t,i,j) (vector_swap ((vector)(t), (i), (j)))
 187
 188 #endif /* TREE_H */