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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
|
/* Plzip - A parallel version of the lzip data compressor
Copyright (C) 2009 Laszlo Ersek.
Copyright (C) 2009 Antonio Diaz Diaz.
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 3 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, see <http://www.gnu.org/licenses/>.
*/
#ifdef __cplusplus
extern "C" {
#endif
struct lacos_rbtree_node;
/*
Opaque data type for red-black binary tree nodes. To get its data pointer,
cast a (struct lacos_rbtree_node *) object to (void **) and derefer it once.
Empty trees equal to (struct lacos_rbtree_node *)0.
This group of functions is generally not thread-safe (although it doesn't use
any static data), because the non-read-only operations must exclude all
operations on the same tree via external locking in a multi-threaded
environment.
If you want to alter the (your own) "key" field in an element, you mustn't do
that in one step. It must involve one delete and one insert operation, in the
order of your choice. Delete-insert is probably faster than insert-delete.
*/
/*
The functions below all return and mainly take pointers to nodes, not
elements (pointers to void). However, for simplicity of language, they are
described as if they operated on pointers to void (elements).
*/
lacos_rbtree_node *
lacos_rbtree_find( lacos_rbtree_node *root, const void *key,
int (*cmp)(const void *cmp_key, const void *cmp_data));
/*
USAGE:
Find an element in the tree.
ARGUMENTS:
root:
Root of the tree.
key:
This specifies which element should be found. This doesn't need to be an
element, it can be a standalone key too, if you write the "cmp" function
accordingly.
cmp:
A function which should return an integer less than, equal to, or greater
than zero if the "key" argument compares less than, equal to, or greater
than the currently inspected element in the tree.
RETURN VALUE:
If the key is found, this function returns the element (actually the
address of the containing node). If it is not found, 0 is returned.
READ-ONLY OPERATION:
Yes.
*/
lacos_rbtree_node *
lacos_rbtree_min( lacos_rbtree_node *root);
/*
USAGE:
Get the smallest element in the tree.
ARGUMENTS:
root:
Root of the tree.
RETURN VALUE:
If the tree is empty ("root" is null), 0 is returned. Otherwise, the
smallest element is returned.
READ-ONLY OPERATION:
Yes.
*/
lacos_rbtree_node *
lacos_rbtree_max( lacos_rbtree_node *root);
/*
USAGE:
Get the greatest element in the tree.
ARGUMENTS:
root:
Root of the tree.
RETURN VALUE:
If the tree is empty ("root" is null), 0 is returned. Otherwise, the
greatest element is returned.
READ-ONLY OPERATION:
Yes.
*/
lacos_rbtree_node *
lacos_rbtree_next( lacos_rbtree_node *current);
/*
USAGE:
Get the smallest element greater than "current".
ARGUMENTS:
current:
An element.
RETURN VALUE:
If "current" is null or the last element in the tree, 0 is returned.
Otherwise, the smallest element greater than "current" is returned.
READ-ONLY OPERATION:
Yes.
*/
lacos_rbtree_node *
lacos_rbtree_prev( lacos_rbtree_node *current);
/*
USAGE:
Get the greatest element smaller than "current".
ARGUMENTS:
current:
An element.
RETURN VALUE:
If "current" is null or the first element in the tree, 0 is returned.
Otherwise, the greatest element smaller than "current" is returned.
READ-ONLY OPERATION:
Yes.
*/
int
lacos_rbtree_insert( lacos_rbtree_node **new_root,
lacos_rbtree_node **new_node, void *new_data,
int (*cmp)(const void *cmp_new_data, const void *cmp_data),
void *(*alloc)(size_t size, void *alloc_ctl), void *alloc_ctl);
/*
USAGE:
Insert an element into the tree.
ARGUMENTS:
new_root:
Address of the tree's root; "*new_root" is the root of the tree. Both
input and output.
new_node:
Output only.
new_data:
The data to insert. This must not be a standalone key, this must be a
full element. It will only be linked in, not copied.
cmp:
A function which should return an integer less than, equal to, or greater
than zero if the "new_data" argument compares less than, equal to, or
greater than the currently inspected element in the tree.
alloc:
A memory allocator function whose externally observable behavior is
consistent with that of "malloc". It must work together with the
"dealloc" function passed to "lacos_rbtree_delete".
alloc_ctl:
A pointer to a custom data type to supply the "alloc" function with
optional auxiliary control information (arena etc).
RETURN VALUE:
If the insertion succeeds, 0 is returned, the new element is stored into
"*new_node", and "*new_root" is updated to the new root of the tree.
Otherwise, "*new_root" is not modified, and -1 is returned because of one
of the following errors:
- An element with a colliding key was found in the tree. In this case, the
colliding element is stored into "*new_node".
- There was not enough memory to allocate a new node object. In this case,
0 is stored into "*new_node".
Existing node pointers remain valid in any case.
READ-ONLY OPERATION:
No.
*/
void
lacos_rbtree_delete( lacos_rbtree_node **new_root,
lacos_rbtree_node *old_node, void **old_data,
void (*dealloc)(void *ptr, void *alloc_ctl), void *alloc_ctl);
/*
USAGE:
Remove an element from the tree.
ARGUMENTS:
new_root:
Address of the tree's root; "*new_root" is the root of the tree. Both
input and output.
old_node:
The element to remove. This must be a valid node pointer into the tree.
old_data:
The deleted element (the data of the deleted node, which was specified by
the "new_data" argument of the corresponding "lacos_rbtree_insert" call).
You could get the data also through "*(void **)old_node" before calling
this function. The data pointer of the node to delete is only accessed
and stored into "*old_data" if "old_data" is not 0.
dealloc:
A memory deallocator function whose externally observable behavior is
consistent with that of "free". It must work together with the "alloc"
function passed to "lacos_rbtree_insert".
alloc_ctl:
A pointer to a custom data type to supply the "dealloc" function with
optional auxiliary control information (arena etc).
Existing node pointers different from "old_node" remain valid.
READ-ONLY OPERATION:
No.
*/
#ifdef __cplusplus
}
#endif
|
