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

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010 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,
  31    assuming that NODE is embedded as the given MEMBER name in
  32    data type STRUCT. */
  33 #define bt_data(NODE, STRUCT, MEMBER)                           \
  34         (CHECK_POINTER_HAS_TYPE (NODE, struct bt_node *),       \
  35          UP_CAST (NODE, STRUCT, MEMBER))
  36
  37 /* Node in a balanced binary tree. */
  38 struct bt_node
  39   {
  40     struct bt_node *up;        /* Parent (NULL for root). */
  41     struct bt_node *down[2];   /* Left child, right child. */
  42   };
  43
  44 /* Compares nodes A and B, with the tree's AUX.
  45    Returns a strcmp-like result. */
  46 typedef int bt_compare_func (const struct bt_node *a,
  47                              const struct bt_node *b,
  48                              const void *aux);
  49
  50 /* A balanced binary tree. */
  51 struct bt
  52   {
  53     struct bt_node *root;       /* Tree's root, NULL if empty. */
  54     bt_compare_func *compare;   /* To compare nodes. */
  55     const void *aux;            /* Auxiliary data. */
  56     size_t size;                /* Current node count. */
  57     size_t max_size;            /* Max size since last complete rebalance. */
  58   };
  59
  60 void bt_init (struct bt *, bt_compare_func *, const void *aux);
  61
  62 struct bt_node *bt_insert (struct bt *, struct bt_node *);
  63 void bt_delete (struct bt *, struct bt_node *);
  64
  65 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  66 struct bt_node *bt_find_ge (const struct bt *, const struct bt_node *);
  67 struct bt_node *bt_find_le (const struct bt *, const struct bt_node *);
  68
  69 struct bt_node *bt_first (const struct bt *);
  70 struct bt_node *bt_last (const struct bt *);
  71 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  72 struct bt_node *bt_next (const struct bt *, const struct bt_node *);
  73 struct bt_node *bt_prev (const struct bt *, const struct bt_node *);
  74
  75 struct bt_node *bt_changed (struct bt *, struct bt_node *);
  76 void bt_moved (struct bt *, struct bt_node *);
  77
  78 /* Returns the number of nodes currently in BT. */
  79 static inline size_t bt_count (const struct bt *bt)
  80 {
  81   return bt->size;
  82 }
  83
  84 /* Return true if BT contains no nodes,
  85    false if BT contains at least one node. */
  86 static inline bool bt_is_empty (const struct bt *bt)
  87 {
  88   return bt->size == 0;
  89 }
  90
  91 #endif /* libpspp/bt.h */