1 /* libavl - manipulates AVL trees.
2 Copyright (C) 1998-9, 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
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.
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.
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
20 /* This is file avl.h in libavl, version 1.1.0. */
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
33 /* Structure for a node in an AVL tree. */
34 typedef struct avl_node
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. */
44 /* Used for traversing an AVL tree. */
45 typedef struct avl_traverser
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. */
54 #define avl_traverser_init(TRAVERSER) (TRAVERSER).init = 0
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);
64 /* Structure which holds information about an AVL tree. */
65 typedef struct avl_tree
68 struct pool *pool; /* Pool to store nodes. */
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. */
78 #define MAYBE_POOL struct pool *pool,
80 #define MAYBE_POOL /* nothing */
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);
91 void avl_walk (const avl_tree *, avl_node_func, void *param);
92 void *avl_traverse (const avl_tree *, avl_traverser *);
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 *);
101 avl_insert (avl_tree *tree, void *item)
103 void **p = avl_probe (tree, item);
104 return (*p == item) ? NULL : *p;
108 avl_replace (avl_tree *tree, void *item)
110 void **p = avl_probe (tree, item);
121 void *avl_insert (avl_tree *tree, void *item);
122 void *avl_replace (avl_tree *tree, void *item);
125 /* Easy assertions on insertion & deletion. */
127 #define avl_force_insert(A, B) \
130 void *r = avl_insert (A, B); \
131 assert (r == NULL); \
134 void *avl_force_delete (avl_tree *, void *);
136 #define avl_force_insert(A, B) \
138 #define avl_force_delete(A, B) \