src/avl.h

   1 /* libavl - manipulates AVL trees.
   2    Copyright (C) 1998-9, 2000 Free Software Foundation, Inc.
   3    Written by Ben Pfaff <blp@gnu.org>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18    02111-1307, USA. */
  19
  20 /* This is file avl.h in libavl, version 1.1.0. */
  21
  22 #if !avl_h
  23 #define avl_h 1
  24
  25 /* This stack size allows for AVL trees for between 5,704,880 and
  26    4,294,967,295 nodes, depending on order of insertion.  If you
  27    increase this it will require recoding some functions that assume
  28    one long is big enough for a bitmap. */
  29 #ifndef AVL_MAX_HEIGHT
  30 #define AVL_MAX_HEIGHT  32
  31 #endif
  32
  33 /* Structure for a node in an AVL tree. */
  34 typedef struct avl_node
  35   {
  36     void *data;                 /* Pointer to data. */
  37     struct avl_node *link[2];   /* Subtrees. */
  38     signed char bal;            /* Balance factor. */
  39     char cache;                 /* Used during insertion. */
  40     signed char pad[2];         /* Unused.  Reserved for threaded trees. */
  41   }
  42 avl_node;
  43
  44 /* Used for traversing an AVL tree. */
  45 typedef struct avl_traverser
  46   {
  47     int init;                   /* Initialized? */
  48     int nstack;                 /* Top of stack. */
  49     const avl_node *p;          /* Used for traversal. */
  50     const avl_node *stack[AVL_MAX_HEIGHT];/* Descended trees. */
  51   }
  52 avl_traverser;
  53
  54 #define avl_traverser_init(TRAVERSER) (TRAVERSER).init = 0
  55
  56 /* Function types. */
  57 #if !AVL_FUNC_TYPES
  58 #define AVL_FUNC_TYPES 1
  59 typedef int (*avl_comparison_func) (const void *a, const void *b, void *param);
  60 typedef void (*avl_node_func) (void *data, void *param);
  61 typedef void *(*avl_copy_func) (void *data, void *param);
  62 #endif
  63
  64 /* Structure which holds information about an AVL tree. */
  65 typedef struct avl_tree
  66   {
  67 #if PSPP
  68     struct pool *pool;          /* Pool to store nodes. */
  69 #endif
  70     avl_node root;              /* Tree root node. */
  71     avl_comparison_func cmp;    /* Used to compare keys. */
  72     int count;                  /* Number of nodes in the tree. */
  73     void *param;                /* Arbitary user data. */
  74   }
  75 avl_tree;
  76
  77 #if PSPP
  78 #define MAYBE_POOL struct pool *pool,
  79 #else
  80 #define MAYBE_POOL /* nothing */
  81 #endif
  82
  83 /* General functions. */
  84 avl_tree *avl_create (MAYBE_POOL avl_comparison_func, void *param);
  85 void avl_destroy (avl_tree *, avl_node_func);
  86 void avl_free (avl_tree *);
  87 int avl_count (const avl_tree *);
  88 avl_tree *avl_copy (MAYBE_POOL const avl_tree *, avl_copy_func);
  89
  90 /* Walk the tree. */
  91 void avl_walk (const avl_tree *, avl_node_func, void *param);
  92 void *avl_traverse (const avl_tree *, avl_traverser *);
  93
  94 /* Search for a given item. */
  95 void **avl_probe (avl_tree *, void *);
  96 void *avl_delete (avl_tree *, const void *);
  97 void *avl_find (const avl_tree *, const void *);
  98
  99 #if __GCC__ >= 2
 100 extern inline void *
 101 avl_insert (avl_tree *tree, void *item)
 102 {
 103   void **p = avl_probe (tree, item);
 104   return (*p == item) ? NULL : *p;
 105 }
 106
 107 extern inline void *
 108 avl_replace (avl_tree *tree, void *item)
 109 {
 110   void **p = avl_probe (tree, item);
 111   if (*p == item)
 112     return NULL;
 113   else
 114     {
 115       void *r = *p;
 116       *p = item;
 117       return r;
 118     }
 119 }
 120 #else /* not gcc */
 121 void *avl_insert (avl_tree *tree, void *item);
 122 void *avl_replace (avl_tree *tree, void *item);
 123 #endif /* not gcc */
 124
 125 /* Easy assertions on insertion & deletion. */
 126 #ifndef NDEBUG
 127 #define avl_force_insert(A, B)                  \
 128         do                                      \
 129           {                                     \
 130             void *r = avl_insert (A, B);        \
 131             assert (r == NULL);                 \
 132           }                                     \
 133         while (0)
 134 void *avl_force_delete (avl_tree *, void *);
 135 #else
 136 #define avl_force_insert(A, B)                  \
 137         avl_insert (A, B)
 138 #define avl_force_delete(A, B)                  \
 139         avl_delete (A, B)
 140 #endif
 141
 142 #endif /* avl_h */