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

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010, 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_BT_H
  18 #define LIBPSPP_BT_H 1
  19
  20 /* Balanced tree (BT) data structure.
  21
  22    The client should not need to be aware of the form of
  23    balancing applied to the balanced tree, as its operation is
  24    fully encapsulated. */
  25
  26 #include <stdbool.h>
  27 #include <stddef.h>
  28 #include "libpspp/cast.h"
  29
  30 /* Returns the data structure corresponding to the given NODE, assuming that
  31    NODE is embedded as the given MEMBER name in data type STRUCT.  NODE must
  32    not be a null pointer. */
  33 #define BT_DATA(NODE, STRUCT, MEMBER)                   \
  34   (CHECK_POINTER_HAS_TYPE (NODE, struct bt_node *),     \
  35    UP_CAST (NODE, STRUCT, MEMBER))
  36
  37 /* Like BT_DATA, except that a null NODE yields a null pointer result. */
  38 #define BT_NULLABLE_DATA(NODE, STRUCT, MEMBER) \
  39   ((STRUCT *) bt_nullable_data__ (NODE, offsetof (STRUCT, MEMBER)))
  40
  41 /* Node in a balanced binary tree. */
  42 struct bt_node
  43   {
  44     struct bt_node *up;        /* Parent (NULL for root). */
  45     struct bt_node *down[2];   /* Left child, right child. */
  46   };
  47
  48 /* Compares nodes A and B, with the tree's AUX.
  49    Returns a strcmp-like result. */
  50 typedef int bt_compare_func (const struct bt_node *a,
  51                              const struct bt_node *b,
  52                              const void *aux);
  53
  54 /* A balanced binary tree. */
  55 struct bt
  56   {
  57     struct bt_node *root;       /* Tree's root, NULL if empty. */
  58     bt_compare_func *compare;   /* To compare nodes. */
  59     const void *aux;            /* Auxiliary data. */
  60     size_t size;                /* Current node count. */
  61     size_t max_size;            /* Max size since last complete rebalance. */
  62   };
  63 #define BT_INITIALIZER(COMPARE, AUX) { .compare = COMPARE, .aux = AUX }
  64
  65 void bt_init (struct bt *, bt_compare_func *, const void *aux);
  66
  67 struct bt_node *bt_insert (struct bt *, struct bt_node *);
  68 void bt_delete (struct bt *, struct bt_node *);
  69
  70 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  71 struct bt_node *bt_find_ge (const struct bt *, const struct bt_node *);
  72 struct bt_node *bt_find_le (const struct bt *, const struct bt_node *);
  73
  74 struct bt_node *bt_first (const struct bt *);
  75 struct bt_node *bt_last (const struct bt *);
  76 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  77 struct bt_node *bt_next (const struct bt *, const struct bt_node *);
  78 struct bt_node *bt_prev (const struct bt *, const struct bt_node *);
  79
  80 struct bt_node *bt_changed (struct bt *, struct bt_node *);
  81 void bt_moved (struct bt *, struct bt_node *);
  82
  83 /* Convenience macros for iteration.
  84
  85    These macros automatically use BT_DATA to obtain the data elements that
  86    encapsulate bt nodes, which often saves typing and can make code easier to
  87    read.  Refer to the large comment near the top of this file for an example.
  88
  89    These macros evaluate their arguments many times. */
  90 #define BT_FIRST(STRUCT, MEMBER, BT)                        \
  91   BT_NULLABLE_DATA (bt_first (BT), STRUCT, MEMBER)
  92 #define BT_NEXT(DATA, STRUCT, MEMBER, BT)                           \
  93   BT_NULLABLE_DATA (bt_next (BT, &(DATA)->MEMBER), STRUCT, MEMBER)
  94 #define BT_FOR_EACH(DATA, STRUCT, MEMBER, BT)       \
  95   for ((DATA) = BT_FIRST (STRUCT, MEMBER, BT);      \
  96        (DATA) != NULL;                                  \
  97        (DATA) = BT_NEXT (DATA, STRUCT, MEMBER, BT))
  98 #define BT_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, BT)    \
  99   for ((DATA) = BT_FIRST (STRUCT, MEMBER, BT);              \
 100        ((DATA) != NULL                                          \
 101         ? ((NEXT) = BT_NEXT (DATA, STRUCT, MEMBER, BT), 1)  \
 102         : 0);                                                   \
 103        (DATA) = (NEXT))
 104
 105 /* Returns the number of nodes currently in BT. */
 106 static inline size_t bt_count (const struct bt *bt)
 107 {
 108   return bt->size;
 109 }
 110
 111 /* Return true if BT contains no nodes,
 112    false if BT contains at least one node. */
 113 static inline bool bt_is_empty (const struct bt *bt)
 114 {
 115   return bt->size == 0;
 116 }
 117
 118 /* Helper for BT_NULLABLE_DATA (to avoid evaluating its NODE argument more than
 119    once).  */
 120 static inline void *
 121 bt_nullable_data__ (struct bt_node *node, size_t member_offset)
 122 {
 123   return node != NULL ? (char *) node - member_offset : NULL;
 124 }
 125
 126 #endif /* libpspp/bt.h */