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