1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
/* libavl - manipulates AVL trees.
Copyright (C) 1998, 1999 Free Software Foundation, Inc.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
The author may be contacted at <pfaffben@pilot.msu.edu> on the
Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
through more mundane means. */
/* This is file avltr.h in libavl. */
#if !avltr_h
#define avltr_h 1
/* The default maximum height of 32 allows for AVL trees having
between 5,704,880 and 4,294,967,295 nodes, depending on order of
insertion. You may change this compile-time constant as you
wish. */
#ifndef AVL_MAX_HEIGHT
#define AVL_MAX_HEIGHT 32
#endif
/* Structure for a node in a right-threaded AVL tree. */
typedef struct avltr_node
{
void *data; /* Pointer to data. */
struct avltr_node *link[2]; /* Subtrees or threads. */
signed char bal; /* Balance factor. */
char cache; /* Used during insertion. */
char pad; /* Reserved for fully threaded trees. */
signed char rtag; /* Right thread tag. */
}
avltr_node;
/* Used for traversing a right-threaded AVL tree. */
typedef struct avltr_traverser
{
int init; /* Initialized? */
const avltr_node *p; /* Last node returned. */
}
avltr_traverser;
/* Initializer for avltr_traverser. */
#define AVLTR_TRAVERSER_INIT {0}
/* Function types. */
#if !AVL_FUNC_TYPES
#define AVL_FUNC_TYPES 1
typedef int (*avl_comparison_func) (const void *a, const void *b, void *param);
typedef void (*avl_node_func) (void *data, void *param);
typedef void *(*avl_copy_func) (void *data, void *param);
#endif
/* Structure which holds information about a threaded AVL tree. */
typedef struct avltr_tree
{
avltr_node root; /* Tree root node. */
avl_comparison_func cmp; /* Used to compare keys. */
int count; /* Number of nodes in the tree. */
void *param; /* Arbitary user data. */
}
avltr_tree;
/* General functions. */
avltr_tree *avltr_create (avl_comparison_func, void *param);
void avltr_destroy (avltr_tree *, avl_node_func);
void avltr_free (avltr_tree *);
int avltr_count (const avltr_tree *);
avltr_tree *avltr_copy (const avltr_tree *, avl_copy_func);
struct avl_tree;
avltr_tree *avltr_thread (struct avl_tree *);
struct avl_tree *avltr_unthread (avltr_tree *);
/* Walk the tree. */
void avltr_walk (const avltr_tree *, avl_node_func, void *param);
void *avltr_traverse (const avltr_tree *, avltr_traverser *);
#define avlt_init_traverser(TRAVERSER) ((TRAVERSER)->init = 0)
void **avltr_next (const avltr_tree *tree, void **item);
/* Search for a given item. */
void **avltr_probe (avltr_tree *, void *);
void *avltr_delete (avltr_tree *, const void *);
void **avltr_find (const avltr_tree *, const void *);
void **avltr_find_close (const avltr_tree *, const void *);
#if __GCC__ >= 2
extern inline void *
avltr_insert (avltr_tree *tree, void *item)
{
void **p = avltr_probe (tree, item);
return (*p == item) ? NULL : *p;
}
extern inline void *
avltr_replace (avltr_tree *tree, void *item)
{
void **p = avltr_probe (tree, item);
if (*p == item)
return NULL;
else
{
void *r = *p;
*p = item;
return r;
}
}
#else /* not gcc */
void *avltr_insert (avltr_tree *tree, void *item);
void *avltr_replace (avltr_tree *tree, void *item);
#endif /* not gcc */
/* Easy assertions on insertion & deletion. */
#ifndef NDEBUG
#define avltr_force_insert(A, B) \
do \
{ \
void *r = avltr_insert (A, B); \
assert (r == NULL); \
} \
while (0)
void *avltr_force_delete (avltr_tree *, void *);
#else
#define avltr_force_insert(A, B) \
avltr_insert (A, B)
#define avltr_force_delete(A, B) \
avltr_delete (A, B)
#endif
#endif /* avltr_h */
|
