src/libpspp/bt.h

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    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, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #ifndef LIBPSPP_BT_H
  20 #define LIBPSPP_BT_H 1
  21
  22 /* Balanced tree (BT) data structure.
  23
  24    The client should not need to be aware of the form of
  25    balancing applied to the balanced tree, as its operation is
  26    fully encapsulated. */
  27
  28 #include <stddef.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         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
  35
  36 /* Node in a balanced binary tree. */
  37 struct bt_node
  38   {
  39     struct bt_node *up;        /* Parent (NULL for root). */
  40     struct bt_node *down[2];   /* Left child, right child. */
  41   };
  42
  43 /* Compares nodes A and B, with the tree's AUX.
  44    Returns a strcmp-like result. */
  45 typedef int bt_compare_func (const struct bt_node *a,
  46                              const struct bt_node *b,
  47                              const void *aux);
  48
  49 /* A balanced binary tree. */
  50 struct bt
  51   {
  52     struct bt_node *root;       /* Tree's root, NULL if empty. */
  53     bt_compare_func *compare;   /* To compare nodes. */
  54     const void *aux;            /* Auxiliary data. */
  55     size_t size;                /* Current node count. */
  56     size_t max_size;            /* Max size since last complete rebalance. */
  57   };
  58
  59 void bt_init (struct bt *, bt_compare_func *, const void *aux);
  60
  61 struct bt_node *bt_insert (struct bt *, struct bt_node *);
  62 void bt_delete (struct bt *, struct bt_node *);
  63
  64 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  65 struct bt_node *bt_find_ge (const struct bt *, const struct bt_node *);
  66 struct bt_node *bt_find_le (const struct bt *, const struct bt_node *);
  67
  68 struct bt_node *bt_first (const struct bt *);
  69 struct bt_node *bt_last (const struct bt *);
  70 struct bt_node *bt_find (const struct bt *, const struct bt_node *);
  71 struct bt_node *bt_next (const struct bt *, const struct bt_node *);
  72 struct bt_node *bt_prev (const struct bt *, const struct bt_node *);
  73
  74 struct bt_node *bt_changed (struct bt *, struct bt_node *);
  75 void bt_moved (struct bt *, struct bt_node *);
  76
  77 /* Returns the number of nodes currently in BT. */
  78 static inline size_t bt_count (const struct bt *bt)
  79 {
  80   return bt->size;
  81 }
  82
  83 #endif /* libpspp/bt.h */