GRASS Programmer's Manual
6.4.3(2013)-r
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
Pages
tavl.c
Go to the documentation of this file.
1
/* Produced by texiweb from libavl.w on 2002/02/09 at 01:45. */
2
3
/* libavl - library for manipulation of binary trees.
4
Copyright (C) 1998-2002 Free Software Foundation, Inc.
5
6
This program is free software; you can redistribute it and/or
7
modify it under the terms of the GNU General Public License as
8
published by the Free Software Foundation; either version 2 of the
9
License, or (at your option) any later version.
10
11
This program is distributed in the hope that it will be useful, but
12
WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14
See the GNU General Public License for more details.
15
16
You should have received a copy of the GNU General Public License
17
along with this program; if not, write to the Free Software
18
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19
20
The author may be contacted at <blp@gnu.org> on the Internet, or
21
as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through more
22
mundane means.
23
*/
24
25
#include <assert.h>
26
#include <stdio.h>
27
#include <stdlib.h>
28
#include "
tavl.h
"
29
30
/* Creates and returns a new table
31
with comparison function |compare| using parameter |param|
32
and memory allocator |allocator|.
33
Returns |NULL| if memory allocation failed. */
34
struct
tavl_table
*
tavl_create
(
tavl_comparison_func
* compare,
void
*param,
35
struct
libavl_allocator
*allocator)
36
{
37
struct
tavl_table
*tree;
38
39
assert(compare !=
NULL
);
40
41
if
(allocator ==
NULL
)
42
allocator = &
tavl_allocator_default
;
43
44
tree = allocator->
libavl_malloc
(allocator,
sizeof
*tree);
45
if
(tree ==
NULL
)
46
return
NULL
;
47
48
tree->
tavl_root
=
NULL
;
49
tree->
tavl_compare
= compare;
50
tree->
tavl_param
= param;
51
tree->
tavl_alloc
= allocator;
52
tree->
tavl_count
= 0;
53
54
return
tree;
55
}
56
57
/* Search |tree| for an item matching |item|, and return it if found.
58
Otherwise return |NULL|. */
59
void
*
tavl_find
(
const
struct
tavl_table
*tree,
const
void
*item)
60
{
61
const
struct
tavl_node
*p;
62
63
assert(tree !=
NULL
&& item !=
NULL
);
64
65
p = tree->
tavl_root
;
66
if
(p ==
NULL
)
67
return
NULL
;
68
69
for
(;;) {
70
int
cmp, dir;
71
72
cmp = tree->
tavl_compare
(item, p->
tavl_data
, tree->
tavl_param
);
73
if
(cmp == 0)
74
return
p->
tavl_data
;
75
76
dir = cmp > 0;
77
if
(p->
tavl_tag
[dir] ==
TAVL_CHILD
)
78
p = p->
tavl_link
[dir];
79
else
80
return
NULL
;
81
}
82
}
83
84
/* Inserts |item| into |tree| and returns a pointer to |item|'s address.
85
If a duplicate item is found in the tree,
86
returns a pointer to the duplicate without inserting |item|.
87
Returns |NULL| in case of memory allocation failure. */
88
void
**
tavl_probe
(
struct
tavl_table
*tree,
void
*item)
89
{
90
struct
tavl_node
*
y
, *z;
/* Top node to update balance factor, and parent. */
91
struct
tavl_node
*p, *
q
;
/* Iterator, and parent. */
92
struct
tavl_node
*n;
/* Newly inserted node. */
93
struct
tavl_node
*
w
;
/* New root of rebalanced subtree. */
94
int
dir;
/* Direction to descend. */
95
96
unsigned
char
da[
TAVL_MAX_HEIGHT
];
/* Cached comparison results. */
97
int
k = 0;
/* Number of cached results. */
98
99
assert(tree !=
NULL
&& item !=
NULL
);
100
101
z = (
struct
tavl_node
*)&tree->
tavl_root
;
102
y = tree->
tavl_root
;
103
if
(y !=
NULL
) {
104
for
(q = z, p = y;; q = p, p = p->
tavl_link
[dir]) {
105
int
cmp =
106
tree->
tavl_compare
(item, p->tavl_data, tree->
tavl_param
);
107
if
(cmp == 0)
108
return
&p->tavl_data;
109
110
if
(p->tavl_balance != 0)
111
z =
q
, y = p, k = 0;
112
da[k++] = dir = cmp > 0;
113
114
if
(p->tavl_tag[dir] ==
TAVL_THREAD
)
115
break
;
116
}
117
}
118
else
{
119
p = z;
120
dir = 0;
121
}
122
123
n = tree->
tavl_alloc
->
libavl_malloc
(tree->
tavl_alloc
,
sizeof
*n);
124
if
(n ==
NULL
)
125
return
NULL
;
126
127
tree->
tavl_count
++;
128
n->
tavl_data
= item;
129
n->
tavl_tag
[0] = n->
tavl_tag
[1] =
TAVL_THREAD
;
130
n->
tavl_link
[dir] = p->
tavl_link
[dir];
131
if
(tree->
tavl_root
!=
NULL
) {
132
p->
tavl_tag
[dir] =
TAVL_CHILD
;
133
n->
tavl_link
[!dir] = p;
134
}
135
else
136
n->
tavl_link
[1] =
NULL
;
137
p->
tavl_link
[dir] = n;
138
n->
tavl_balance
= 0;
139
if
(tree->
tavl_root
== n)
140
return
&n->
tavl_data
;
141
142
for
(p = y, k = 0; p != n; p = p->
tavl_link
[da[k]], k++)
143
if
(da[k] == 0)
144
p->
tavl_balance
--;
145
else
146
p->
tavl_balance
++;
147
148
if
(y->
tavl_balance
== -2) {
149
struct
tavl_node
*x = y->
tavl_link
[0];
150
151
if
(x->
tavl_balance
== -1) {
152
w = x;
153
if
(x->
tavl_tag
[1] ==
TAVL_THREAD
) {
154
x->
tavl_tag
[1] =
TAVL_CHILD
;
155
y->
tavl_tag
[0] =
TAVL_THREAD
;
156
y->
tavl_link
[0] = x;
157
}
158
else
159
y->
tavl_link
[0] = x->
tavl_link
[1];
160
x->
tavl_link
[1] =
y
;
161
x->
tavl_balance
= y->
tavl_balance
= 0;
162
}
163
else
{
164
assert(x->
tavl_balance
== +1);
165
w = x->
tavl_link
[1];
166
x->
tavl_link
[1] = w->
tavl_link
[0];
167
w->
tavl_link
[0] = x;
168
y->
tavl_link
[0] = w->
tavl_link
[1];
169
w->
tavl_link
[1] =
y
;
170
if
(w->
tavl_balance
== -1)
171
x->
tavl_balance
= 0, y->
tavl_balance
= +1;
172
else
if
(w->
tavl_balance
== 0)
173
x->
tavl_balance
= y->
tavl_balance
= 0;
174
else
/* |w->tavl_balance == +1| */
175
x->
tavl_balance
= -1, y->
tavl_balance
= 0;
176
w->
tavl_balance
= 0;
177
if
(w->
tavl_tag
[0] ==
TAVL_THREAD
) {
178
x->
tavl_tag
[1] =
TAVL_THREAD
;
179
x->
tavl_link
[1] =
w
;
180
w->
tavl_tag
[0] =
TAVL_CHILD
;
181
}
182
if
(w->
tavl_tag
[1] ==
TAVL_THREAD
) {
183
y->
tavl_tag
[0] =
TAVL_THREAD
;
184
y->
tavl_link
[0] =
w
;
185
w->
tavl_tag
[1] =
TAVL_CHILD
;
186
}
187
}
188
}
189
else
if
(y->
tavl_balance
== +2) {
190
struct
tavl_node
*x = y->
tavl_link
[1];
191
192
if
(x->
tavl_balance
== +1) {
193
w = x;
194
if
(x->
tavl_tag
[0] ==
TAVL_THREAD
) {
195
x->
tavl_tag
[0] =
TAVL_CHILD
;
196
y->
tavl_tag
[1] =
TAVL_THREAD
;
197
y->
tavl_link
[1] = x;
198
}
199
else
200
y->
tavl_link
[1] = x->
tavl_link
[0];
201
x->
tavl_link
[0] =
y
;
202
x->
tavl_balance
= y->
tavl_balance
= 0;
203
}
204
else
{
205
assert(x->
tavl_balance
== -1);
206
w = x->
tavl_link
[0];
207
x->
tavl_link
[0] = w->
tavl_link
[1];
208
w->
tavl_link
[1] = x;
209
y->
tavl_link
[1] = w->
tavl_link
[0];
210
w->
tavl_link
[0] =
y
;
211
if
(w->
tavl_balance
== +1)
212
x->
tavl_balance
= 0, y->
tavl_balance
= -1;
213
else
if
(w->
tavl_balance
== 0)
214
x->
tavl_balance
= y->
tavl_balance
= 0;
215
else
/* |w->tavl_balance == -1| */
216
x->
tavl_balance
= +1, y->
tavl_balance
= 0;
217
w->
tavl_balance
= 0;
218
if
(w->
tavl_tag
[0] ==
TAVL_THREAD
) {
219
y->
tavl_tag
[1] =
TAVL_THREAD
;
220
y->
tavl_link
[1] =
w
;
221
w->
tavl_tag
[0] =
TAVL_CHILD
;
222
}
223
if
(w->
tavl_tag
[1] ==
TAVL_THREAD
) {
224
x->
tavl_tag
[0] =
TAVL_THREAD
;
225
x->
tavl_link
[0] =
w
;
226
w->
tavl_tag
[1] =
TAVL_CHILD
;
227
}
228
}
229
}
230
else
231
return
&n->
tavl_data
;
232
z->
tavl_link
[y != z->
tavl_link
[0]] =
w
;
233
234
return
&n->
tavl_data
;
235
}
236
237
/* Inserts |item| into |table|.
238
Returns |NULL| if |item| was successfully inserted
239
or if a memory allocation error occurred.
240
Otherwise, returns the duplicate item. */
241
void
*
tavl_insert
(
struct
tavl_table
*table,
void
*item)
242
{
243
void
**p =
tavl_probe
(table, item);
244
245
return
p ==
NULL
|| *p == item ?
NULL
: *p;
246
}
247
248
/* Inserts |item| into |table|, replacing any duplicate item.
249
Returns |NULL| if |item| was inserted without replacing a duplicate,
250
or if a memory allocation error occurred.
251
Otherwise, returns the item that was replaced. */
252
void
*
tavl_replace
(
struct
tavl_table
*table,
void
*item)
253
{
254
void
**p =
tavl_probe
(table, item);
255
256
if
(p ==
NULL
|| *p == item)
257
return
NULL
;
258
else
{
259
void
*
r
= *p;
260
261
*p = item;
262
return
r
;
263
}
264
}
265
266
/* Returns the parent of |node| within |tree|,
267
or a pointer to |tavl_root| if |s| is the root of the tree. */
268
static
struct
tavl_node
*find_parent(
struct
tavl_table
*tree,
269
struct
tavl_node
*node)
270
{
271
if
(node != tree->
tavl_root
) {
272
struct
tavl_node
*x, *
y
;
273
274
for
(x = y = node;; x = x->
tavl_link
[0], y = y->
tavl_link
[1])
275
if
(y->
tavl_tag
[1] ==
TAVL_THREAD
) {
276
struct
tavl_node
*p = y->
tavl_link
[1];
277
278
if
(p ==
NULL
|| p->
tavl_link
[0] != node) {
279
while
(x->
tavl_tag
[0] ==
TAVL_CHILD
)
280
x = x->
tavl_link
[0];
281
p = x->
tavl_link
[0];
282
}
283
return
p;
284
}
285
else
if
(x->
tavl_tag
[0] ==
TAVL_THREAD
) {
286
struct
tavl_node
*p = x->
tavl_link
[0];
287
288
if
(p ==
NULL
|| p->
tavl_link
[1] != node) {
289
while
(y->
tavl_tag
[1] ==
TAVL_CHILD
)
290
y = y->
tavl_link
[1];
291
p = y->
tavl_link
[1];
292
}
293
return
p;
294
}
295
}
296
else
297
return
(
struct
tavl_node
*)&tree->
tavl_root
;
298
}
299
300
/* Deletes from |tree| and returns an item matching |item|.
301
Returns a null pointer if no matching item found. */
302
void
*
tavl_delete
(
struct
tavl_table
*tree,
const
void
*item)
303
{
304
struct
tavl_node
*p;
/* Traverses tree to find node to delete. */
305
struct
tavl_node
*
q
;
/* Parent of |p|. */
306
int
dir;
/* Index into |q->tavl_link[]| to get |p|. */
307
int
cmp;
/* Result of comparison between |item| and |p|. */
308
309
assert(tree !=
NULL
&& item !=
NULL
);
310
311
if
(tree->
tavl_root
==
NULL
)
312
return
NULL
;
313
314
p = (
struct
tavl_node
*)&tree->
tavl_root
;
315
for (cmp = -1; cmp != 0;
316
cmp = tree->
tavl_compare
(item, p->
tavl_data
, tree->
tavl_param
)) {
317
dir = cmp > 0;
318
319
q = p;
320
if
(p->
tavl_tag
[dir] ==
TAVL_THREAD
)
321
return
NULL
;
322
p = p->
tavl_link
[dir];
323
}
324
item = p->
tavl_data
;
325
326
if
(p->
tavl_tag
[1] ==
TAVL_THREAD
) {
327
if
(p->
tavl_tag
[0] ==
TAVL_CHILD
) {
328
struct
tavl_node
*t = p->
tavl_link
[0];
329
330
while
(t->
tavl_tag
[1] ==
TAVL_CHILD
)
331
t = t->
tavl_link
[1];
332
t->
tavl_link
[1] = p->
tavl_link
[1];
333
q->
tavl_link
[dir] = p->
tavl_link
[0];
334
}
335
else
{
336
q->
tavl_link
[dir] = p->
tavl_link
[dir];
337
if
(q != (
struct
tavl_node
*)&tree->
tavl_root
)
338
q->
tavl_tag
[dir] =
TAVL_THREAD
;
339
}
340
}
341
else
{
342
struct
tavl_node
*
r
= p->
tavl_link
[1];
343
344
if
(r->
tavl_tag
[0] ==
TAVL_THREAD
) {
345
r->
tavl_link
[0] = p->
tavl_link
[0];
346
r->
tavl_tag
[0] = p->
tavl_tag
[0];
347
if
(r->
tavl_tag
[0] ==
TAVL_CHILD
) {
348
struct
tavl_node
*t = r->
tavl_link
[0];
349
350
while
(t->
tavl_tag
[1] ==
TAVL_CHILD
)
351
t = t->
tavl_link
[1];
352
t->
tavl_link
[1] =
r
;
353
}
354
q->
tavl_link
[dir] =
r
;
355
r->
tavl_balance
= p->
tavl_balance
;
356
q =
r
;
357
dir = 1;
358
}
359
else
{
360
struct
tavl_node
*
s
;
361
362
for
(;;) {
363
s = r->
tavl_link
[0];
364
if
(s->
tavl_tag
[0] ==
TAVL_THREAD
)
365
break
;
366
367
r =
s
;
368
}
369
370
if
(s->
tavl_tag
[1] ==
TAVL_CHILD
)
371
r->
tavl_link
[0] = s->
tavl_link
[1];
372
else
{
373
r->
tavl_link
[0] =
s
;
374
r->
tavl_tag
[0] =
TAVL_THREAD
;
375
}
376
377
s->
tavl_link
[0] = p->
tavl_link
[0];
378
if
(p->
tavl_tag
[0] ==
TAVL_CHILD
) {
379
struct
tavl_node
*t = p->
tavl_link
[0];
380
381
while
(t->
tavl_tag
[1] ==
TAVL_CHILD
)
382
t = t->
tavl_link
[1];
383
t->
tavl_link
[1] =
s
;
384
385
s->
tavl_tag
[0] =
TAVL_CHILD
;
386
}
387
388
s->
tavl_link
[1] = p->
tavl_link
[1];
389
s->
tavl_tag
[1] =
TAVL_CHILD
;
390
391
q->
tavl_link
[dir] =
s
;
392
s->
tavl_balance
= p->
tavl_balance
;
393
q =
r
;
394
dir = 0;
395
}
396
}
397
398
tree->
tavl_alloc
->
libavl_free
(tree->
tavl_alloc
, p);
399
400
while
(q != (
struct
tavl_node
*)&tree->
tavl_root
) {
401
struct
tavl_node
*y =
q
;
402
403
q = find_parent(tree, y);
404
405
if
(dir == 0) {
406
dir = q->
tavl_link
[0] !=
y
;
407
y->
tavl_balance
++;
408
if
(y->
tavl_balance
== +1)
409
break
;
410
else
if
(y->
tavl_balance
== +2) {
411
struct
tavl_node
*x = y->
tavl_link
[1];
412
413
assert(x !=
NULL
);
414
if
(x->
tavl_balance
== -1) {
415
struct
tavl_node
*
w
;
416
417
assert(x->
tavl_balance
== -1);
418
w = x->
tavl_link
[0];
419
x->
tavl_link
[0] = w->
tavl_link
[1];
420
w->
tavl_link
[1] = x;
421
y->
tavl_link
[1] = w->
tavl_link
[0];
422
w->
tavl_link
[0] =
y
;
423
if
(w->
tavl_balance
== +1)
424
x->
tavl_balance
= 0, y->
tavl_balance
= -1;
425
else
if
(w->
tavl_balance
== 0)
426
x->
tavl_balance
= y->
tavl_balance
= 0;
427
else
/* |w->tavl_balance == -1| */
428
x->
tavl_balance
= +1, y->
tavl_balance
= 0;
429
w->
tavl_balance
= 0;
430
if
(w->
tavl_tag
[0] ==
TAVL_THREAD
) {
431
y->
tavl_tag
[1] =
TAVL_THREAD
;
432
y->
tavl_link
[1] =
w
;
433
w->
tavl_tag
[0] =
TAVL_CHILD
;
434
}
435
if
(w->
tavl_tag
[1] ==
TAVL_THREAD
) {
436
x->
tavl_tag
[0] =
TAVL_THREAD
;
437
x->
tavl_link
[0] =
w
;
438
w->
tavl_tag
[1] =
TAVL_CHILD
;
439
}
440
q->
tavl_link
[dir] =
w
;
441
}
442
else
{
443
q->
tavl_link
[dir] = x;
444
445
if
(x->
tavl_balance
== 0) {
446
y->
tavl_link
[1] = x->
tavl_link
[0];
447
x->
tavl_link
[0] =
y
;
448
x->
tavl_balance
= -1;
449
y->
tavl_balance
= +1;
450
break
;
451
}
452
else
{
/* |x->tavl_balance == +1| */
453
454
if
(x->
tavl_tag
[0] ==
TAVL_CHILD
)
455
y->
tavl_link
[1] = x->
tavl_link
[0];
456
else
{
457
y->
tavl_tag
[1] =
TAVL_THREAD
;
458
x->
tavl_tag
[0] =
TAVL_CHILD
;
459
}
460
x->
tavl_link
[0] =
y
;
461
y->
tavl_balance
= x->
tavl_balance
= 0;
462
}
463
}
464
}
465
}
466
else
{
467
dir = q->
tavl_link
[0] !=
y
;
468
y->
tavl_balance
--;
469
if
(y->
tavl_balance
== -1)
470
break
;
471
else
if
(y->
tavl_balance
== -2) {
472
struct
tavl_node
*x = y->
tavl_link
[0];
473
474
assert(x !=
NULL
);
475
if
(x->
tavl_balance
== +1) {
476
struct
tavl_node
*
w
;
477
478
assert(x->
tavl_balance
== +1);
479
w = x->
tavl_link
[1];
480
x->
tavl_link
[1] = w->
tavl_link
[0];
481
w->
tavl_link
[0] = x;
482
y->
tavl_link
[0] = w->
tavl_link
[1];
483
w->
tavl_link
[1] =
y
;
484
if
(w->
tavl_balance
== -1)
485
x->
tavl_balance
= 0, y->
tavl_balance
= +1;
486
else
if
(w->
tavl_balance
== 0)
487
x->
tavl_balance
= y->
tavl_balance
= 0;
488
else
/* |w->tavl_balance == +1| */
489
x->
tavl_balance
= -1, y->
tavl_balance
= 0;
490
w->
tavl_balance
= 0;
491
if
(w->
tavl_tag
[0] ==
TAVL_THREAD
) {
492
x->
tavl_tag
[1] =
TAVL_THREAD
;
493
x->
tavl_link
[1] =
w
;
494
w->
tavl_tag
[0] =
TAVL_CHILD
;
495
}
496
if
(w->
tavl_tag
[1] ==
TAVL_THREAD
) {
497
y->
tavl_tag
[0] =
TAVL_THREAD
;
498
y->
tavl_link
[0] =
w
;
499
w->
tavl_tag
[1] =
TAVL_CHILD
;
500
}
501
q->
tavl_link
[dir] =
w
;
502
}
503
else
{
504
q->
tavl_link
[dir] = x;
505
506
if
(x->
tavl_balance
== 0) {
507
y->
tavl_link
[0] = x->
tavl_link
[1];
508
x->
tavl_link
[1] =
y
;
509
x->
tavl_balance
= +1;
510
y->
tavl_balance
= -1;
511
break
;
512
}
513
else
{
/* |x->tavl_balance == -1| */
514
515
if
(x->
tavl_tag
[1] ==
TAVL_CHILD
)
516
y->
tavl_link
[0] = x->
tavl_link
[1];
517
else
{
518
y->
tavl_tag
[0] =
TAVL_THREAD
;
519
x->
tavl_tag
[1] =
TAVL_CHILD
;
520
}
521
x->
tavl_link
[1] =
y
;
522
y->
tavl_balance
= x->
tavl_balance
= 0;
523
}
524
}
525
}
526
}
527
}
528
529
tree->
tavl_count
--;
530
return
(
void
*)item;
531
}
532
533
/* Initializes |trav| for use with |tree|
534
and selects the null node. */
535
void
tavl_t_init
(
struct
tavl_traverser
*trav,
struct
tavl_table
*tree)
536
{
537
trav->
tavl_table
= tree;
538
trav->
tavl_node
=
NULL
;
539
}
540
541
/* Initializes |trav| for |tree|.
542
Returns data item in |tree| with the least value,
543
or |NULL| if |tree| is empty. */
544
void
*
tavl_t_first
(
struct
tavl_traverser
*trav,
struct
tavl_table
*tree)
545
{
546
assert(tree !=
NULL
&& trav !=
NULL
);
547
548
trav->
tavl_table
= tree;
549
trav->
tavl_node
= tree->
tavl_root
;
550
if
(trav->
tavl_node
!=
NULL
) {
551
while
(trav->
tavl_node
->
tavl_tag
[0] ==
TAVL_CHILD
)
552
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[0];
553
return
trav->
tavl_node
->
tavl_data
;
554
}
555
else
556
return
NULL
;
557
}
558
559
/* Initializes |trav| for |tree|.
560
Returns data item in |tree| with the greatest value,
561
or |NULL| if |tree| is empty. */
562
void
*
tavl_t_last
(
struct
tavl_traverser
*trav,
struct
tavl_table
*tree)
563
{
564
assert(tree !=
NULL
&& trav !=
NULL
);
565
566
trav->
tavl_table
= tree;
567
trav->
tavl_node
= tree->
tavl_root
;
568
if
(trav->
tavl_node
!=
NULL
) {
569
while
(trav->
tavl_node
->
tavl_tag
[1] ==
TAVL_CHILD
)
570
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[1];
571
return
trav->
tavl_node
->
tavl_data
;
572
}
573
else
574
return
NULL
;
575
}
576
577
/* Searches for |item| in |tree|.
578
If found, initializes |trav| to the item found and returns the item
579
as well.
580
If there is no matching item, initializes |trav| to the null item
581
and returns |NULL|. */
582
void
*
tavl_t_find
(
struct
tavl_traverser
*trav,
struct
tavl_table
*tree,
583
void
*item)
584
{
585
struct
tavl_node
*p;
586
587
assert(trav !=
NULL
&& tree !=
NULL
&& item !=
NULL
);
588
589
trav->
tavl_table
= tree;
590
trav->
tavl_node
=
NULL
;
591
592
p = tree->
tavl_root
;
593
if
(p ==
NULL
)
594
return
NULL
;
595
596
for
(;;) {
597
int
cmp, dir;
598
599
cmp = tree->
tavl_compare
(item, p->
tavl_data
, tree->
tavl_param
);
600
if
(cmp == 0) {
601
trav->
tavl_node
= p;
602
return
p->
tavl_data
;
603
}
604
605
dir = cmp > 0;
606
if
(p->
tavl_tag
[dir] ==
TAVL_CHILD
)
607
p = p->
tavl_link
[dir];
608
else
609
return
NULL
;
610
}
611
}
612
613
/* Attempts to insert |item| into |tree|.
614
If |item| is inserted successfully, it is returned and |trav| is
615
initialized to its location.
616
If a duplicate is found, it is returned and |trav| is initialized to
617
its location. No replacement of the item occurs.
618
If a memory allocation failure occurs, |NULL| is returned and |trav|
619
is initialized to the null item. */
620
void
*
tavl_t_insert
(
struct
tavl_traverser
*trav,
621
struct
tavl_table
*tree,
void
*item)
622
{
623
void
**p;
624
625
assert(trav !=
NULL
&& tree !=
NULL
&& item !=
NULL
);
626
627
p =
tavl_probe
(tree, item);
628
if
(p !=
NULL
) {
629
trav->
tavl_table
= tree;
630
trav->
tavl_node
= ((
struct
tavl_node
*)
631
((
char
*)p -
632
offsetof(
struct
tavl_node
,
tavl_data
)));
633
return
*p;
634
}
635
else
{
636
tavl_t_init
(trav, tree);
637
return
NULL
;
638
}
639
}
640
641
/* Initializes |trav| to have the same current node as |src|. */
642
void
*
tavl_t_copy
(
struct
tavl_traverser
*trav,
643
const
struct
tavl_traverser
*src)
644
{
645
assert(trav !=
NULL
&& src !=
NULL
);
646
647
trav->
tavl_table
= src->
tavl_table
;
648
trav->
tavl_node
= src->
tavl_node
;
649
650
return
trav->
tavl_node
!=
NULL
? trav->
tavl_node
->
tavl_data
:
NULL
;
651
}
652
653
/* Returns the next data item in inorder
654
within the tree being traversed with |trav|,
655
or if there are no more data items returns |NULL|. */
656
void
*
tavl_t_next
(
struct
tavl_traverser
*trav)
657
{
658
assert(trav !=
NULL
);
659
660
if
(trav->
tavl_node
==
NULL
)
661
return
tavl_t_first
(trav, trav->
tavl_table
);
662
else
if
(trav->
tavl_node
->
tavl_tag
[1] ==
TAVL_THREAD
) {
663
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[1];
664
return
trav->
tavl_node
!=
NULL
? trav->
tavl_node
->
tavl_data
:
NULL
;
665
}
666
else
{
667
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[1];
668
while
(trav->
tavl_node
->
tavl_tag
[0] ==
TAVL_CHILD
)
669
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[0];
670
return
trav->
tavl_node
->
tavl_data
;
671
}
672
}
673
674
/* Returns the previous data item in inorder
675
within the tree being traversed with |trav|,
676
or if there are no more data items returns |NULL|. */
677
void
*
tavl_t_prev
(
struct
tavl_traverser
*trav)
678
{
679
assert(trav !=
NULL
);
680
681
if
(trav->
tavl_node
==
NULL
)
682
return
tavl_t_last
(trav, trav->
tavl_table
);
683
else
if
(trav->
tavl_node
->
tavl_tag
[0] ==
TAVL_THREAD
) {
684
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[0];
685
return
trav->
tavl_node
!=
NULL
? trav->
tavl_node
->
tavl_data
:
NULL
;
686
}
687
else
{
688
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[0];
689
while
(trav->
tavl_node
->
tavl_tag
[1] ==
TAVL_CHILD
)
690
trav->
tavl_node
= trav->
tavl_node
->
tavl_link
[1];
691
return
trav->
tavl_node
->
tavl_data
;
692
}
693
}
694
695
/* Returns |trav|'s current item. */
696
void
*
tavl_t_cur
(
struct
tavl_traverser
*trav)
697
{
698
assert(trav !=
NULL
);
699
700
return
trav->
tavl_node
!=
NULL
? trav->
tavl_node
->
tavl_data
:
NULL
;
701
}
702
703
/* Replaces the current item in |trav| by |new| and returns the item replaced.
704
|trav| must not have the null item selected.
705
The new item must not upset the ordering of the tree. */
706
void
*
tavl_t_replace
(
struct
tavl_traverser
*trav,
void
*
new
)
707
{
708
struct
tavl_node
*old;
709
710
assert(trav !=
NULL
&& trav->
tavl_node
!=
NULL
&&
new
!=
NULL
);
711
old = trav->
tavl_node
->
tavl_data
;
712
trav->
tavl_node
->
tavl_data
=
new
;
713
return
old;
714
}
715
716
/* Creates a new node as a child of |dst| on side |dir|.
717
Copies data and |tavl_balance| from |src| into the new node,
718
applying |copy()|, if non-null.
719
Returns nonzero only if fully successful.
720
Regardless of success, integrity of the tree structure is assured,
721
though failure may leave a null pointer in a |tavl_data| member. */
722
static
int
723
copy_node(
struct
tavl_table
*tree,
724
struct
tavl_node
*dst,
int
dir,
725
const
struct
tavl_node
*src,
tavl_copy_func
* copy)
726
{
727
struct
tavl_node
*
new
=
728
tree->
tavl_alloc
->
libavl_malloc
(tree->
tavl_alloc
,
sizeof
*
new
);
729
if
(
new
==
NULL
)
730
return
0;
731
732
new
->tavl_link[dir] = dst->
tavl_link
[dir];
733
new
->
tavl_tag
[dir] =
TAVL_THREAD
;
734
new
->tavl_link[!dir] = dst;
735
new
->
tavl_tag
[!dir] =
TAVL_THREAD
;
736
dst->
tavl_link
[dir] =
new
;
737
dst->
tavl_tag
[dir] =
TAVL_CHILD
;
738
739
new
->tavl_balance = src->
tavl_balance
;
740
if
(copy ==
NULL
)
741
new
->tavl_data = src->
tavl_data
;
742
else
{
743
new
->tavl_data = copy(src->
tavl_data
, tree->
tavl_param
);
744
if
(new->tavl_data ==
NULL
)
745
return
0;
746
}
747
748
return
1;
749
}
750
751
static
void
752
copy_error_recovery(
struct
tavl_node
*p,
753
struct
tavl_table
*
new
,
tavl_item_func
* destroy)
754
{
755
new
->tavl_root = p;
756
if
(p !=
NULL
) {
757
while
(p->
tavl_tag
[1] ==
TAVL_CHILD
)
758
p = p->
tavl_link
[1];
759
p->
tavl_link
[1] =
NULL
;
760
}
761
tavl_destroy
(
new
, destroy);
762
}
763
764
/* Copies |org| to a newly created tree, which is returned.
765
If |copy != NULL|, each data item in |org| is first passed to |copy|,
766
and the return values are inserted into the tree,
767
with |NULL| return values taken as indications of failure.
768
On failure, destroys the partially created new tree,
769
applying |destroy|, if non-null, to each item in the new tree so far,
770
and returns |NULL|.
771
If |allocator != NULL|, it is used for allocation in the new tree.
772
Otherwise, the same allocator used for |org| is used. */
773
struct
tavl_table
*
tavl_copy
(
const
struct
tavl_table
*org,
774
tavl_copy_func
* copy,
tavl_item_func
* destroy,
775
struct
libavl_allocator
*allocator)
776
{
777
struct
tavl_table
*
new
;
778
779
const
struct
tavl_node
*p;
780
struct
tavl_node
*
q
;
781
struct
tavl_node
rp, rq;
782
783
assert(org !=
NULL
);
784
new
=
tavl_create
(org->
tavl_compare
, org->
tavl_param
,
785
allocator !=
NULL
? allocator : org->
tavl_alloc
);
786
if
(
new
==
NULL
)
787
return
NULL
;
788
789
new
->tavl_count = org->
tavl_count
;
790
if
(new->tavl_count == 0)
791
return
new
;
792
793
p = &rp;
794
rp.
tavl_link
[0] = org->
tavl_root
;
795
rp.
tavl_tag
[0] =
TAVL_CHILD
;
796
797
q = &rq;
798
rq.
tavl_link
[0] =
NULL
;
799
rq.
tavl_tag
[0] =
TAVL_THREAD
;
800
801
for
(;;) {
802
if
(p->
tavl_tag
[0] ==
TAVL_CHILD
) {
803
if
(!copy_node(
new
, q, 0, p->
tavl_link
[0], copy)) {
804
copy_error_recovery(rq.
tavl_link
[0],
new
, destroy);
805
return
NULL
;
806
}
807
808
p = p->
tavl_link
[0];
809
q = q->
tavl_link
[0];
810
}
811
else
{
812
while
(p->
tavl_tag
[1] ==
TAVL_THREAD
) {
813
p = p->
tavl_link
[1];
814
if
(p ==
NULL
) {
815
q->
tavl_link
[1] =
NULL
;
816
new
->tavl_root = rq.
tavl_link
[0];
817
return
new
;
818
}
819
820
q = q->
tavl_link
[1];
821
}
822
823
p = p->
tavl_link
[1];
824
q = q->
tavl_link
[1];
825
}
826
827
if
(p->
tavl_tag
[1] ==
TAVL_CHILD
)
828
if
(!copy_node(
new
, q, 1, p->
tavl_link
[1], copy)) {
829
copy_error_recovery(rq.
tavl_link
[0],
new
, destroy);
830
return
NULL
;
831
}
832
}
833
}
834
835
/* Frees storage allocated for |tree|.
836
If |destroy != NULL|, applies it to each data item in inorder. */
837
void
tavl_destroy
(
struct
tavl_table
*tree,
tavl_item_func
* destroy)
838
{
839
struct
tavl_node
*p;
/* Current node. */
840
struct
tavl_node
*n;
/* Next node. */
841
842
p = tree->
tavl_root
;
843
if
(p !=
NULL
)
844
while
(p->
tavl_tag
[0] ==
TAVL_CHILD
)
845
p = p->
tavl_link
[0];
846
847
while
(p !=
NULL
) {
848
n = p->
tavl_link
[1];
849
if
(p->
tavl_tag
[1] ==
TAVL_CHILD
)
850
while
(n->
tavl_tag
[0] ==
TAVL_CHILD
)
851
n = n->
tavl_link
[0];
852
853
if
(destroy !=
NULL
&& p->
tavl_data
!=
NULL
)
854
destroy(p->
tavl_data
, tree->
tavl_param
);
855
tree->
tavl_alloc
->
libavl_free
(tree->
tavl_alloc
, p);
856
857
p = n;
858
}
859
860
tree->
tavl_alloc
->
libavl_free
(tree->
tavl_alloc
, tree);
861
}
862
863
/* Allocates |size| bytes of space using |malloc()|.
864
Returns a null pointer if allocation fails. */
865
void
*
tavl_malloc
(
struct
libavl_allocator
*allocator,
size_t
size
)
866
{
867
assert(allocator !=
NULL
&& size > 0);
868
return
malloc(size);
869
}
870
871
/* Frees |block|. */
872
void
tavl_free
(
struct
libavl_allocator
*allocator,
void
*block)
873
{
874
assert(allocator !=
NULL
&& block !=
NULL
);
875
free(block);
876
}
877
878
/* Default memory allocator that uses |malloc()| and |free()|. */
879
struct
libavl_allocator
tavl_allocator_default
= {
880
tavl_malloc
,
881
tavl_free
882
};
883
884
/* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
885
void (
tavl_assert_insert
) (
struct
tavl_table
* table,
void
*item)
886
{
887
void
**p =
tavl_probe
(table, item);
888
889
assert(p !=
NULL
&& *p == item);
890
}
891
892
/* Asserts that |tavl_delete()| really removes |item| from |table|,
893
and returns the removed item. */
894
void
*(
tavl_assert_delete
) (
struct
tavl_table
* table,
void
*item)
895
{
896
void
*p =
tavl_delete
(table, item);
897
898
assert(p !=
NULL
);
899
return
p;
900
}
lib
vector
dglib
tavl.c
Generated on Thu Sep 26 2013 09:48:07 for GRASS Programmer's Manual by
1.8.4