GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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, *z; /* Top node to update balance factor, and parent. */
93  struct tavl_node *p, *q; /* Iterator, and parent. */
94  struct tavl_node *n; /* Newly inserted node. */
95  struct tavl_node *w; /* New root of rebalanced subtree. */
96  int dir; /* Direction to descend. */
97 
98  unsigned char da[TAVL_MAX_HEIGHT]; /* Cached comparison results. */
99  int k = 0; /* Number of cached results. */
100 
101  assert(tree != NULL && item != NULL);
102 
103  z = (struct tavl_node *)&tree->tavl_root;
104  y = tree->tavl_root;
105  dir = 0;
106  q = z, p = y;
107  while (p != NULL) {
108  int cmp =
109  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,
634  struct tavl_table *tree, 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 = ((struct tavl_node *)
644  ((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,
657  const struct tavl_traverser *src)
658 {
659  assert(trav != NULL && src != NULL);
660 
661  trav->tavl_table = src->tavl_table;
662  trav->tavl_node = src->tavl_node;
663 
664  return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
665 }
666 
667 /* Returns the next data item in inorder
668  within the tree being traversed with |trav|,
669  or if there are no more data items returns |NULL|. */
670 void *tavl_t_next(struct tavl_traverser *trav)
671 {
672  assert(trav != NULL);
673 
674  if (trav->tavl_node == NULL)
675  return tavl_t_first(trav, trav->tavl_table);
676  else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD) {
677  trav->tavl_node = trav->tavl_node->tavl_link[1];
678  return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
679  }
680  else {
681  trav->tavl_node = trav->tavl_node->tavl_link[1];
682  while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
683  trav->tavl_node = trav->tavl_node->tavl_link[0];
684  return trav->tavl_node->tavl_data;
685  }
686 }
687 
688 /* Returns the previous data item in inorder
689  within the tree being traversed with |trav|,
690  or if there are no more data items returns |NULL|. */
691 void *tavl_t_prev(struct tavl_traverser *trav)
692 {
693  assert(trav != NULL);
694 
695  if (trav->tavl_node == NULL)
696  return tavl_t_last(trav, trav->tavl_table);
697  else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD) {
698  trav->tavl_node = trav->tavl_node->tavl_link[0];
699  return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
700  }
701  else {
702  trav->tavl_node = trav->tavl_node->tavl_link[0];
703  while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
704  trav->tavl_node = trav->tavl_node->tavl_link[1];
705  return trav->tavl_node->tavl_data;
706  }
707 }
708 
709 /* Returns |trav|'s current item. */
710 void *tavl_t_cur(struct tavl_traverser *trav)
711 {
712  assert(trav != NULL);
713 
714  return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
715 }
716 
717 /* Replaces the current item in |trav| by |new| and returns the item replaced.
718  |trav| must not have the null item selected.
719  The new item must not upset the ordering of the tree. */
720 void *tavl_t_replace(struct tavl_traverser *trav, void *new)
721 {
722  void *old;
723 
724  assert(trav != NULL && trav->tavl_node != NULL && new != NULL);
725  old = trav->tavl_node->tavl_data;
726  trav->tavl_node->tavl_data = new;
727 
728  return old;
729 }
730 
731 /* Creates a new node as a child of |dst| on side |dir|.
732  Copies data and |tavl_balance| from |src| into the new node,
733  applying |copy()|, if non-null.
734  Returns nonzero only if fully successful.
735  Regardless of success, integrity of the tree structure is assured,
736  though failure may leave a null pointer in a |tavl_data| member. */
737 static int
738 copy_node(struct tavl_table *tree,
739  struct tavl_node *dst, int dir,
740  const struct tavl_node *src, tavl_copy_func * copy)
741 {
742  struct tavl_node *new =
743  tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *new);
744  if (new == NULL)
745  return 0;
746 
747  new->tavl_link[dir] = dst->tavl_link[dir];
748  new->tavl_tag[dir] = TAVL_THREAD;
749  new->tavl_link[!dir] = dst;
750  new->tavl_tag[!dir] = TAVL_THREAD;
751  dst->tavl_link[dir] = new;
752  dst->tavl_tag[dir] = TAVL_CHILD;
753 
754  new->tavl_balance = src->tavl_balance;
755  if (copy == NULL)
756  new->tavl_data = src->tavl_data;
757  else {
758  new->tavl_data = copy(src->tavl_data, tree->tavl_param);
759  if (new->tavl_data == NULL)
760  return 0;
761  }
762 
763  return 1;
764 }
765 
766 /* Destroys |new| with |tavl_destroy (new, destroy)|,
767  first initializing the right link in |new| that has
768  not yet been initialized. */
769 static void
770 copy_error_recovery(struct tavl_node *p,
771  struct tavl_table *new, tavl_item_func * destroy)
772 {
773  new->tavl_root = p;
774  if (p != NULL) {
775  while (p->tavl_tag[1] == TAVL_CHILD)
776  p = p->tavl_link[1];
777  p->tavl_link[1] = NULL;
778  }
779  tavl_destroy(new, destroy);
780 }
781 
782 /* Copies |org| to a newly created tree, which is returned.
783  If |copy != NULL|, each data item in |org| is first passed to |copy|,
784  and the return values are inserted into the tree,
785  with |NULL| return values taken as indications of failure.
786  On failure, destroys the partially created new tree,
787  applying |destroy|, if non-null, to each item in the new tree so far,
788  and returns |NULL|.
789  If |allocator != NULL|, it is used for allocation in the new tree.
790  Otherwise, the same allocator used for |org| is used. */
791 struct tavl_table *tavl_copy(const struct tavl_table *org,
792  tavl_copy_func * copy, tavl_item_func * destroy,
793  struct libavl_allocator *allocator)
794 {
795  struct tavl_table *new;
796 
797  const struct tavl_node *p;
798  struct tavl_node *q;
799  struct tavl_node rp, rq;
800 
801  assert(org != NULL);
802  new = tavl_create(org->tavl_compare, org->tavl_param,
803  allocator != NULL ? allocator : org->tavl_alloc);
804  if (new == NULL)
805  return NULL;
806 
807  new->tavl_count = org->tavl_count;
808  if (new->tavl_count == 0)
809  return new;
810 
811  p = &rp;
812  rp.tavl_link[0] = org->tavl_root;
813  rp.tavl_tag[0] = TAVL_CHILD;
814 
815  q = &rq;
816  rq.tavl_link[0] = NULL;
817  rq.tavl_tag[0] = TAVL_THREAD;
818 
819  while (p != NULL) {
820  if (p->tavl_tag[0] == TAVL_CHILD) {
821  if (!copy_node(new, q, 0, p->tavl_link[0], copy)) {
822  copy_error_recovery(rq.tavl_link[0], new, destroy);
823  return NULL;
824  }
825 
826  p = p->tavl_link[0];
827  q = q->tavl_link[0];
828  }
829  else {
830  while (p->tavl_tag[1] == TAVL_THREAD) {
831  p = p->tavl_link[1];
832  if (p == NULL) {
833  q->tavl_link[1] = NULL;
834  new->tavl_root = rq.tavl_link[0];
835  return new;
836  }
837 
838  q = q->tavl_link[1];
839  }
840 
841  p = p->tavl_link[1];
842  q = q->tavl_link[1];
843  }
844 
845  if (p->tavl_tag[1] == TAVL_CHILD)
846  if (!copy_node(new, q, 1, p->tavl_link[1], copy)) {
847  copy_error_recovery(rq.tavl_link[0], new, destroy);
848  return NULL;
849  }
850  }
851 
852  return new;
853 }
854 
855 /* Frees storage allocated for |tree|.
856  If |destroy != NULL|, applies it to each data item in inorder. */
857 void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy)
858 {
859  struct tavl_node *p; /* Current node. */
860  struct tavl_node *n; /* Next node. */
861 
862  p = tree->tavl_root;
863  if (p != NULL) {
864  while (p->tavl_tag[0] == TAVL_CHILD)
865  p = p->tavl_link[0];
866  }
867 
868  while (p != NULL) {
869  n = p->tavl_link[1];
870  if (p->tavl_tag[1] == TAVL_CHILD)
871  while (n->tavl_tag[0] == TAVL_CHILD)
872  n = n->tavl_link[0];
873 
874  if (destroy != NULL && p->tavl_data != NULL)
875  destroy(p->tavl_data, tree->tavl_param);
876  tree->tavl_alloc->libavl_free(tree->tavl_alloc, p);
877 
878  p = n;
879  }
880 
881  tree->tavl_alloc->libavl_free(tree->tavl_alloc, tree);
882 }
883 
884 /* Allocates |size| bytes of space using |malloc()|.
885  Returns a null pointer if allocation fails. */
886 void *tavl_malloc(struct libavl_allocator *allocator, size_t size)
887 {
888  assert(allocator != NULL && size > 0);
889  return malloc(size);
890 }
891 
892 /* Frees |block|. */
893 void tavl_free(struct libavl_allocator *allocator, void *block)
894 {
895  assert(allocator != NULL && block != NULL);
896  free(block);
897 }
898 
899 /* Default memory allocator that uses |malloc()| and |free()|. */
901  tavl_malloc,
902  tavl_free
903 };
904 
905 #undef NDEBUG
906 #include <assert.h>
907 
908 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */
909 void (tavl_assert_insert) (struct tavl_table * table, void *item)
910 {
911  void **p = tavl_probe(table, item);
912 
913  assert(p != NULL && *p == item);
914 }
915 
916 /* Asserts that |tavl_delete()| really removes |item| from |table|,
917  and returns the removed item. */
918 void *(tavl_assert_delete) (struct tavl_table * table, void *item)
919 {
920  void *p = tavl_delete(table, item);
921 
922  assert(p != NULL);
923 
924  return p;
925 }
struct tavl_node * tavl_node
Definition: tavl.h:84
size_t tavl_count
Definition: tavl.h:61
void * tavl_replace(struct tavl_table *table, void *item)
Definition: tavl.c:254
void tavl_item_func(void *tavl_item, void *tavl_param)
Definition: tavl.h:31
void * tavl_t_next(struct tavl_traverser *trav)
Definition: tavl.c:670
Definition: tavl.h:72
void *(* libavl_malloc)(struct libavl_allocator *, size_t libavl_size)
Definition: avl.h:39
void * tavl_t_prev(struct tavl_traverser *trav)
Definition: tavl.c:691
void * tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:573
void * tavl_t_copy(struct tavl_traverser *trav, const struct tavl_traverser *src)
Definition: tavl.c:656
void * tavl_copy_func(void *tavl_item, void *tavl_param)
Definition: tavl.h:32
void ** tavl_probe(struct tavl_table *tree, void *item)
Definition: tavl.c:90
char * dst
Definition: lz4.h:599
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:791
void(* libavl_free)(struct libavl_allocator *, void *libavl_block)
Definition: avl.h:40
void * tavl_data
Definition: tavl.h:75
void * tavl_delete(struct tavl_table *tree, const void *item)
Definition: tavl.c:305
void free(void *)
void * tavl_t_cur(struct tavl_traverser *trav)
Definition: tavl.c:710
#define NULL
Definition: ccmath.h:32
#define x
void * tavl_malloc(struct libavl_allocator *allocator, size_t size)
Definition: tavl.c:886
struct tavl_table * tavl_create(tavl_comparison_func *compare, void *param, struct libavl_allocator *allocator)
Definition: tavl.c:37
void * malloc(YYSIZE_T)
struct tavl_node * tavl_link[2]
Definition: tavl.h:74
double t
Definition: r_raster.c:39
void * tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:555
void * tavl_param
Definition: tavl.h:59
void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree)
Definition: tavl.c:546
void * tavl_insert(struct tavl_table *table, void *item)
Definition: tavl.c:243
int tavl_comparison_func(const void *tavl_a, const void *tavl_b, void *tavl_param)
Definition: tavl.h:29
#define assert(condition)
Definition: lz4.c:324
void tavl_free(struct libavl_allocator *allocator, void *block)
Definition: tavl.c:893
void * tavl_find(const struct tavl_table *tree, const void *item)
Definition: tavl.c:62
struct tavl_node * tavl_root
Definition: tavl.h:57
void * tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree, void *item)
Definition: tavl.c:593
#define TAVL_MAX_HEIGHT
Definition: tavl.h:51
struct libavl_allocator tavl_allocator_default
Definition: tavl.c:900
void * tavl_t_replace(struct tavl_traverser *trav, void *new)
Definition: tavl.c:720
void * tavl_t_insert(struct tavl_traverser *trav, struct tavl_table *tree, void *item)
Definition: tavl.c:633
tavl_comparison_func * tavl_compare
Definition: tavl.h:58
void() tavl_assert_insert(struct tavl_table *table, void *item)
Definition: tavl.c:909
void *() tavl_assert_delete(struct tavl_table *table, void *item)
Definition: tavl.c:918
struct tavl_table * tavl_table
Definition: tavl.h:83
int compare(const void *a, const void *b)
Definition: dgraph.c:177
void tavl_destroy(struct tavl_table *tree, tavl_item_func *destroy)
Definition: tavl.c:857
struct libavl_allocator * tavl_alloc
Definition: tavl.h:60
unsigned char tavl_tag[2]
Definition: tavl.h:76
double r
Definition: r_raster.c:39
signed char tavl_balance
Definition: tavl.h:77