pintos-os.org Git - pspp/blob - src/libpspp/abt.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program 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
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #ifndef LIBPSPP_ABT_H
  18 #define LIBPSPP_ABT_H 1
  19
  20 /* Augmented binary tree (ABT) data structure.
  21
  22    A data structure can be "augmented" by defining new
  23    information for it to maintain.  One commonly useful way to
  24    augment a binary search tree-based data structure is to define
  25    part of its data as a function of its immediate children's
  26    data.  Furthermore, augmented data defined in this way can be
  27    efficiently maintained as the tree changes over time.
  28
  29    For example, suppose we define the "size" of a node as the sum
  30    of the "size" of its immediate children, plus 1.  In such an
  31    annotated BST with height H, we can find the node that would
  32    be Kth in in-order traversal in O(H) time, instead of O(K)
  33    time, which is a significant saving for balanced trees.
  34
  35    The ABT data structure partially abstracts augmentation.  The
  36    client passes in a "reaugmentation" function that accepts a
  37    node.  This function must recalculate the node's augmentation
  38    data based on its own contents and the contents of its
  39    children, and store the new augmentation data in the node.
  40
  41    The ABT automatically calls the reaugmentation function
  42    whenever it can tell that a node's augmentation data might
  43    need to be updated: when the node is inserted or when a node's
  44    descendants change due to insertion or deletion.  The ABT does
  45    not know to call the reaugmentation function if a node's data
  46    is updated while it is in the ABT.  In such a case, call the
  47    abt_reaugmented or abt_changed function to update the
  48    augmentation.
  49
  50    Augmentation is only partially abstracted: we do not provide
  51    any way to search an ABT based on its augmentations.  The
  52    tree structure is thus exposed to the client to allow it to
  53    implement search.
  54
  55    To allow for optimization, the ABT implementation assumes that
  56    the augmentation function in use is unaffected by the shape of
  57    a binary search tree.  That is, if a given subtree within a
  58    larger tree is rearranged, e.g. via a series of rotations,
  59    then the implementation will not call the reaugmentation
  60    function outside of the subtree, because the overall
  61    augmentation data for the subtree is assumed not to change.
  62    This optimization is valid for the forms of augmentation
  63    described in CLR and Knuth (see below), and it is possible
  64    that it is valid for every efficient binary search tree
  65    augmentation.
  66
  67    The client should not need to be aware of the form of
  68    balancing applied to the ABT, as its operation should be fully
  69    encapsulated by the reaugmentation function.  The current
  70    implementation uses an AA (Arne Andersson) tree, but this is
  71    subject to change.
  72
  73    The following example illustrates how to use an ABT to build a
  74    tree that can be searched either by a data value or in-order
  75    position:
  76
  77      // Test data element.
  78      struct element
  79        {
  80          struct abt_node node;       // Embedded binary tree element.
  81          int data;                   // Primary value.
  82          int count;                  // Number of nodes in subtree,
  83                                      // including this node.
  84        };
  85
  86      // Returns the `struct element' that NODE is embedded within.
  87      static struct element *
  88      node_to_element (const struct abt_node *node)
  89      {
  90        return ABT_DATA (node, struct element, node);
  91      }
  92
  93      // Compares the DATA values in A and B and returns a
  94      // strcmp-type return value.
  95      static int
  96      compare_elements (const struct abt_node *a_, const struct abt_node *b_,
  97                        const void *aux)
  98      {
  99        const struct element *a = node_to_element (a_);
 100        const struct element *b = node_to_element (b_);
 101
 102        return a->data < b->data ? -1 : a->data > b->data;
 103      }
 104
 105      // Recalculates the count for NODE's subtree by adding up the
 106      // counts for its left and right child subtrees.
 107      static void
 108      reaugment_elements (struct abt_node *node_, const void *aux)
 109      {
 110        struct element *node = node_to_element (node_);
 111        node->count = 1;
 112        if (node->node.down[0] != NULL)
 113          node->count += node_to_element (node->node.down[0])->count;
 114        if (node->node.down[1] != NULL)
 115          node->count += node_to_element (node->node.down[1])->count;
 116      }
 117
 118      // Finds and returns the element in ABT that is in the given
 119      // 0-based POSITION in in-order.
 120      static struct element *
 121      find_by_position (struct abt *abt, int position)
 122      {
 123        struct abt_node *p;
 124        for (p = abt->root; p != NULL;)
 125          {
 126            int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
 127            if (position == p_pos)
 128              return node_to_element (p);
 129            else if (position < p_pos)
 130              p = p->down[0];
 131            else
 132              {
 133                p = p->down[1];
 134                position -= p_pos + 1;
 135              }
 136          }
 137        return NULL;
 138      }
 139
 140    For more information on augmenting binary search tree-based
 141    data structures, see Cormen-Leiserson-Rivest, chapter 15, or
 142    Knuth vol. 3, section 6.2.3, under "Linear list
 143    representation."  For more information on AA trees, see
 144    <http://en.wikipedia.org/wiki/AA_tree>, which includes source
 145    code and links to other resources, such as the original AA
 146    tree paper.  */
 147
 148 #include <stdbool.h>
 149 #include <stddef.h>
 150 #include "libpspp/cast.h"
 151
 152 /* Returns the data structure corresponding to the given NODE, assuming that
 153    NODE is embedded as the given MEMBER name in data type STRUCT.  NODE must
 154    not be a null pointer. */
 155 #define ABT_DATA(NODE, STRUCT, MEMBER)                   \
 156   (CHECK_POINTER_HAS_TYPE (NODE, struct abt_node *),     \
 157    UP_CAST (NODE, STRUCT, MEMBER))
 158
 159 /* Like ABT_DATA, except that a null NODE yields a null pointer result. */
 160 #define ABT_NULLABLE_DATA(NODE, STRUCT, MEMBER) \
 161   ((STRUCT *) abt_nullable_data__ (NODE, offsetof (STRUCT, MEMBER)))
 162
 163 /* Node in an augmented binary tree. */
 164 struct abt_node
 165   {
 166     struct abt_node *up;        /* Parent (NULL for root). */
 167     struct abt_node *down[2];   /* Left child, right child. */
 168     int level;                  /* AA tree level (not ordinary BST level). */
 169   };
 170
 171 /* Compares nodes A and B, with the tree's AUX.
 172    Returns a strcmp-like result. */
 173 typedef int abt_compare_func (const struct abt_node *a,
 174                               const struct abt_node *b,
 175                               const void *aux);
 176
 177 /* Recalculates NODE's augmentation based on NODE's data and that of its left
 178    and right children NODE->down[0] and NODE[1], respectively, with the tree's
 179    AUX. */
 180 typedef void abt_reaugment_func (struct abt_node *node, const void *aux);
 181
 182 /* An augmented binary tree. */
 183 struct abt
 184   {
 185     struct abt_node *root;         /* Tree's root, NULL if empty. */
 186     abt_compare_func *compare;     /* To compare nodes. */
 187     abt_reaugment_func *reaugment; /* To augment a node using its children. */
 188     const void *aux;               /* Auxiliary data. */
 189   };
 190 #define ABT_INITIALIZER(COMPARE, REAUGMENT, AUX) \
 191   { .compare = COMPARE, .reaugment = REAUGMENT, .aux = AUX }
 192
 193 void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *,
 194                const void *aux);
 195
 196 static inline bool abt_is_empty (const struct abt *);
 197
 198 struct abt_node *abt_insert (struct abt *, struct abt_node *);
 199 void abt_insert_after (struct abt *,
 200                        const struct abt_node *, struct abt_node *);
 201 void abt_insert_before (struct abt *,
 202                         const struct abt_node *, struct abt_node *);
 203 void abt_delete (struct abt *, struct abt_node *);
 204
 205 struct abt_node *abt_first (const struct abt *);
 206 struct abt_node *abt_last (const struct abt *);
 207 struct abt_node *abt_find (const struct abt *, const struct abt_node *);
 208 struct abt_node *abt_next (const struct abt *, const struct abt_node *);
 209 struct abt_node *abt_prev (const struct abt *, const struct abt_node *);
 210
 211 void abt_reaugmented (const struct abt *, struct abt_node *);
 212 struct abt_node *abt_changed (struct abt *, struct abt_node *);
 213 void abt_moved (struct abt *, struct abt_node *);
 214
 215 /* Convenience macros for iteration.
 216
 217    These macros automatically use ABT_DATA to obtain the data elements that
 218    encapsulate abt nodes, which often saves typing and can make code easier to
 219    read.  Refer to the large comment near the top of this file for an example.
 220
 221    These macros evaluate their arguments many times. */
 222 #define ABT_FIRST(STRUCT, MEMBER, ABT)                        \
 223   ABT_NULLABLE_DATA (abt_first (ABT), STRUCT, MEMBER)
 224 #define ABT_NEXT(DATA, STRUCT, MEMBER, ABT)                           \
 225   ABT_NULLABLE_DATA (abt_next (ABT, &(DATA)->MEMBER), STRUCT, MEMBER)
 226 #define ABT_FOR_EACH(DATA, STRUCT, MEMBER, ABT)       \
 227   for ((DATA) = ABT_FIRST (STRUCT, MEMBER, ABT);      \
 228        (DATA) != NULL;                                  \
 229        (DATA) = ABT_NEXT (DATA, STRUCT, MEMBER, ABT))
 230 #define ABT_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, ABT)    \
 231   for ((DATA) = ABT_FIRST (STRUCT, MEMBER, ABT);              \
 232        ((DATA) != NULL                                          \
 233         ? ((NEXT) = ABT_NEXT (DATA, STRUCT, MEMBER, ABT), 1)  \
 234         : 0);                                                   \
 235        (DATA) = (NEXT))
 236
 237 /* Returns true if ABT contains no nodes, false if ABT contains at least one
 238    node. */
 239 static inline bool
 240 abt_is_empty (const struct abt *abt)
 241 {
 242   return abt->root == NULL;
 243 }
 244
 245 /* Helper for ABT_NULLABLE_DATA (to avoid evaluating its NODE argument more
 246    than once).  */
 247 static inline void *
 248 abt_nullable_data__ (struct abt_node *node, size_t member_offset)
 249 {
 250   return node != NULL ? (char *) node - member_offset : NULL;
 251 }
 252
 253 #endif /* libpspp/abt.h */