source: subversion/applications/utils/coastcheck/rb.c @ 30195

Last change on this file since 30195 was 6729, checked in by martinvoosterhout, 12 years ago

Initial commit of the coastline checker. It's been used for a while now
successfully.

File size: 24.4 KB
Line 
1/* Produced by texiweb from libavl.w. */
2
3/* libavl - library for manipulation of binary trees.
4   Copyright (C) 1998-2002, 2004 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., 59 Temple Place - Suite 330, Boston, MA
19   02111-1307, USA.
20
21   The author may be contacted at <blp@gnu.org> on the Internet, or
22   write to Ben Pfaff, Stanford University, Computer Science Dept., 353
23   Serra Mall, Stanford CA 94305, USA.
24*/
25
26#include <assert.h>
27#include <stdio.h>
28#include <stdlib.h>
29#include <string.h>
30#include "rb.h"
31
32/* Creates and returns a new table
33   with comparison function |compare| using parameter |param|
34   and memory allocator |allocator|.
35   Returns |NULL| if memory allocation failed. */
36struct rb_table *
37rb_create (rb_comparison_func *compare, void *param,
38            struct libavl_allocator *allocator)
39{
40  struct rb_table *tree;
41
42  assert (compare != NULL);
43
44  if (allocator == NULL)
45    allocator = &rb_allocator_default;
46
47  tree = allocator->libavl_malloc (allocator, sizeof *tree);
48  if (tree == NULL)
49    return NULL;
50
51  tree->rb_root = NULL;
52  tree->rb_compare = compare;
53  tree->rb_param = param;
54  tree->rb_alloc = allocator;
55  tree->rb_count = 0;
56  tree->rb_generation = 0;
57
58  return tree;
59}
60
61/* Search |tree| for an item matching |item|, and return it if found.
62   Otherwise return |NULL|. */
63void *
64rb_find (const struct rb_table *tree, const void *item)
65{
66  const struct rb_node *p;
67
68  assert (tree != NULL && item != NULL);
69  for (p = tree->rb_root; p != NULL; )
70    {
71      int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param);
72
73      if (cmp < 0)
74        p = p->rb_link[0];
75      else if (cmp > 0)
76        p = p->rb_link[1];
77      else /* |cmp == 0| */
78        return p->rb_data;
79    }
80
81  return NULL;
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. */
88void **
89rb_probe (struct rb_table *tree, void *item)
90{
91  struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */
92  unsigned char da[RB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
93  int k;                             /* Stack height. */
94
95  struct rb_node *p; /* Traverses tree looking for insertion point. */
96  struct rb_node *n; /* Newly inserted node. */
97
98  assert (tree != NULL && item != NULL);
99
100  pa[0] = (struct rb_node *) &tree->rb_root;
101  da[0] = 0;
102  k = 1;
103  for (p = tree->rb_root; p != NULL; p = p->rb_link[da[k - 1]])
104    {
105      int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param);
106      if (cmp == 0)
107        return &p->rb_data;
108
109      pa[k] = p;
110      da[k++] = cmp > 0;
111    }
112
113  n = pa[k - 1]->rb_link[da[k - 1]] =
114    tree->rb_alloc->libavl_malloc (tree->rb_alloc, sizeof *n);
115  if (n == NULL)
116    return NULL;
117
118  n->rb_data = item;
119  n->rb_link[0] = n->rb_link[1] = NULL;
120  n->rb_color = RB_RED;
121  tree->rb_count++;
122  tree->rb_generation++;
123
124  while (k >= 3 && pa[k - 1]->rb_color == RB_RED)
125    {
126      if (da[k - 2] == 0)
127        {
128          struct rb_node *y = pa[k - 2]->rb_link[1];
129          if (y != NULL && y->rb_color == RB_RED)
130            {
131              pa[k - 1]->rb_color = y->rb_color = RB_BLACK;
132              pa[k - 2]->rb_color = RB_RED;
133              k -= 2;
134            }
135          else
136            {
137              struct rb_node *x;
138
139              if (da[k - 1] == 0)
140                y = pa[k - 1];
141              else
142                {
143                  x = pa[k - 1];
144                  y = x->rb_link[1];
145                  x->rb_link[1] = y->rb_link[0];
146                  y->rb_link[0] = x;
147                  pa[k - 2]->rb_link[0] = y;
148                }
149
150              x = pa[k - 2];
151              x->rb_color = RB_RED;
152              y->rb_color = RB_BLACK;
153
154              x->rb_link[0] = y->rb_link[1];
155              y->rb_link[1] = x;
156              pa[k - 3]->rb_link[da[k - 3]] = y;
157              break;
158            }
159        }
160      else
161        {
162          struct rb_node *y = pa[k - 2]->rb_link[0];
163          if (y != NULL && y->rb_color == RB_RED)
164            {
165              pa[k - 1]->rb_color = y->rb_color = RB_BLACK;
166              pa[k - 2]->rb_color = RB_RED;
167              k -= 2;
168            }
169          else
170            {
171              struct rb_node *x;
172
173              if (da[k - 1] == 1)
174                y = pa[k - 1];
175              else
176                {
177                  x = pa[k - 1];
178                  y = x->rb_link[0];
179                  x->rb_link[0] = y->rb_link[1];
180                  y->rb_link[1] = x;
181                  pa[k - 2]->rb_link[1] = y;
182                }
183
184              x = pa[k - 2];
185              x->rb_color = RB_RED;
186              y->rb_color = RB_BLACK;
187
188              x->rb_link[1] = y->rb_link[0];
189              y->rb_link[0] = x;
190              pa[k - 3]->rb_link[da[k - 3]] = y;
191              break;
192            }
193        }
194    }
195  tree->rb_root->rb_color = RB_BLACK;
196
197
198  return &n->rb_data;
199}
200
201/* Inserts |item| into |table|.
202   Returns |NULL| if |item| was successfully inserted
203   or if a memory allocation error occurred.
204   Otherwise, returns the duplicate item. */
205void *
206rb_insert (struct rb_table *table, void *item)
207{
208  void **p = rb_probe (table, item);
209  return p == NULL || *p == item ? NULL : *p;
210}
211
212/* Inserts |item| into |table|, replacing any duplicate item.
213   Returns |NULL| if |item| was inserted without replacing a duplicate,
214   or if a memory allocation error occurred.
215   Otherwise, returns the item that was replaced. */
216void *
217rb_replace (struct rb_table *table, void *item)
218{
219  void **p = rb_probe (table, item);
220  if (p == NULL || *p == item)
221    return NULL;
222  else
223    {
224      void *r = *p;
225      *p = item;
226      return r;
227    }
228}
229
230/* Deletes from |tree| and returns an item matching |item|.
231   Returns a null pointer if no matching item found. */
232void *
233rb_delete (struct rb_table *tree, const void *item)
234{
235  struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */
236  unsigned char da[RB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
237  int k;                             /* Stack height. */
238
239  struct rb_node *p;    /* The node to delete, or a node part way to it. */
240  int cmp;              /* Result of comparison between |item| and |p|. */
241
242  assert (tree != NULL && item != NULL);
243
244  k = 0;
245  p = (struct rb_node *) &tree->rb_root;
246  for (cmp = -1; cmp != 0;
247       cmp = tree->rb_compare (item, p->rb_data, tree->rb_param))
248    {
249      int dir = cmp > 0;
250
251      pa[k] = p;
252      da[k++] = dir;
253
254      p = p->rb_link[dir];
255      if (p == NULL)
256        return NULL;
257    }
258  item = p->rb_data;
259
260  if (p->rb_link[1] == NULL)
261    pa[k - 1]->rb_link[da[k - 1]] = p->rb_link[0];
262  else
263    {
264      enum rb_color t;
265      struct rb_node *r = p->rb_link[1];
266
267      if (r->rb_link[0] == NULL)
268        {
269          r->rb_link[0] = p->rb_link[0];
270          t = r->rb_color;
271          r->rb_color = p->rb_color;
272          p->rb_color = t;
273          pa[k - 1]->rb_link[da[k - 1]] = r;
274          da[k] = 1;
275          pa[k++] = r;
276        }
277      else
278        {
279          struct rb_node *s;
280          int j = k++;
281
282          for (;;)
283            {
284              da[k] = 0;
285              pa[k++] = r;
286              s = r->rb_link[0];
287              if (s->rb_link[0] == NULL)
288                break;
289
290              r = s;
291            }
292
293          da[j] = 1;
294          pa[j] = s;
295          pa[j - 1]->rb_link[da[j - 1]] = s;
296
297          s->rb_link[0] = p->rb_link[0];
298          r->rb_link[0] = s->rb_link[1];
299          s->rb_link[1] = p->rb_link[1];
300
301          t = s->rb_color;
302          s->rb_color = p->rb_color;
303          p->rb_color = t;
304        }
305    }
306
307  if (p->rb_color == RB_BLACK)
308    {
309      for (;;)
310        {
311          struct rb_node *x = pa[k - 1]->rb_link[da[k - 1]];
312          if (x != NULL && x->rb_color == RB_RED)
313            {
314              x->rb_color = RB_BLACK;
315              break;
316            }
317          if (k < 2)
318            break;
319
320          if (da[k - 1] == 0)
321            {
322              struct rb_node *w = pa[k - 1]->rb_link[1];
323
324              if (w->rb_color == RB_RED)
325                {
326                  w->rb_color = RB_BLACK;
327                  pa[k - 1]->rb_color = RB_RED;
328
329                  pa[k - 1]->rb_link[1] = w->rb_link[0];
330                  w->rb_link[0] = pa[k - 1];
331                  pa[k - 2]->rb_link[da[k - 2]] = w;
332
333                  pa[k] = pa[k - 1];
334                  da[k] = 0;
335                  pa[k - 1] = w;
336                  k++;
337
338                  w = pa[k - 1]->rb_link[1];
339                }
340
341              if ((w->rb_link[0] == NULL
342                   || w->rb_link[0]->rb_color == RB_BLACK)
343                  && (w->rb_link[1] == NULL
344                      || w->rb_link[1]->rb_color == RB_BLACK))
345                w->rb_color = RB_RED;
346              else
347                {
348                  if (w->rb_link[1] == NULL
349                      || w->rb_link[1]->rb_color == RB_BLACK)
350                    {
351                      struct rb_node *y = w->rb_link[0];
352                      y->rb_color = RB_BLACK;
353                      w->rb_color = RB_RED;
354                      w->rb_link[0] = y->rb_link[1];
355                      y->rb_link[1] = w;
356                      w = pa[k - 1]->rb_link[1] = y;
357                    }
358
359                  w->rb_color = pa[k - 1]->rb_color;
360                  pa[k - 1]->rb_color = RB_BLACK;
361                  w->rb_link[1]->rb_color = RB_BLACK;
362
363                  pa[k - 1]->rb_link[1] = w->rb_link[0];
364                  w->rb_link[0] = pa[k - 1];
365                  pa[k - 2]->rb_link[da[k - 2]] = w;
366                  break;
367                }
368            }
369          else
370            {
371              struct rb_node *w = pa[k - 1]->rb_link[0];
372
373              if (w->rb_color == RB_RED)
374                {
375                  w->rb_color = RB_BLACK;
376                  pa[k - 1]->rb_color = RB_RED;
377
378                  pa[k - 1]->rb_link[0] = w->rb_link[1];
379                  w->rb_link[1] = pa[k - 1];
380                  pa[k - 2]->rb_link[da[k - 2]] = w;
381
382                  pa[k] = pa[k - 1];
383                  da[k] = 1;
384                  pa[k - 1] = w;
385                  k++;
386
387                  w = pa[k - 1]->rb_link[0];
388                }
389
390              if ((w->rb_link[0] == NULL
391                   || w->rb_link[0]->rb_color == RB_BLACK)
392                  && (w->rb_link[1] == NULL
393                      || w->rb_link[1]->rb_color == RB_BLACK))
394                w->rb_color = RB_RED;
395              else
396                {
397                  if (w->rb_link[0] == NULL
398                      || w->rb_link[0]->rb_color == RB_BLACK)
399                    {
400                      struct rb_node *y = w->rb_link[1];
401                      y->rb_color = RB_BLACK;
402                      w->rb_color = RB_RED;
403                      w->rb_link[1] = y->rb_link[0];
404                      y->rb_link[0] = w;
405                      w = pa[k - 1]->rb_link[0] = y;
406                    }
407
408                  w->rb_color = pa[k - 1]->rb_color;
409                  pa[k - 1]->rb_color = RB_BLACK;
410                  w->rb_link[0]->rb_color = RB_BLACK;
411
412                  pa[k - 1]->rb_link[0] = w->rb_link[1];
413                  w->rb_link[1] = pa[k - 1];
414                  pa[k - 2]->rb_link[da[k - 2]] = w;
415                  break;
416                }
417            }
418
419          k--;
420        }
421
422    }
423
424  tree->rb_alloc->libavl_free (tree->rb_alloc, p);
425  tree->rb_count--;
426  tree->rb_generation++;
427  return (void *) item;
428}
429
430/* Refreshes the stack of parent pointers in |trav|
431   and updates its generation number. */
432static void
433trav_refresh (struct rb_traverser *trav)
434{
435  assert (trav != NULL);
436
437  trav->rb_generation = trav->rb_table->rb_generation;
438
439  if (trav->rb_node != NULL)
440    {
441      rb_comparison_func *cmp = trav->rb_table->rb_compare;
442      void *param = trav->rb_table->rb_param;
443      struct rb_node *node = trav->rb_node;
444      struct rb_node *i;
445
446      trav->rb_height = 0;
447      for (i = trav->rb_table->rb_root; i != node; )
448        {
449          assert (trav->rb_height < RB_MAX_HEIGHT);
450          assert (i != NULL);
451
452          trav->rb_stack[trav->rb_height++] = i;
453          i = i->rb_link[cmp (node->rb_data, i->rb_data, param) > 0];
454        }
455    }
456}
457
458/* Initializes |trav| for use with |tree|
459   and selects the null node. */
460void
461rb_t_init (struct rb_traverser *trav, struct rb_table *tree)
462{
463  trav->rb_table = tree;
464  trav->rb_node = NULL;
465  trav->rb_height = 0;
466  trav->rb_generation = tree->rb_generation;
467}
468
469/* Initializes |trav| for |tree|
470   and selects and returns a pointer to its least-valued item.
471   Returns |NULL| if |tree| contains no nodes. */
472void *
473rb_t_first (struct rb_traverser *trav, struct rb_table *tree)
474{
475  struct rb_node *x;
476
477  assert (tree != NULL && trav != NULL);
478
479  trav->rb_table = tree;
480  trav->rb_height = 0;
481  trav->rb_generation = tree->rb_generation;
482
483  x = tree->rb_root;
484  if (x != NULL)
485    while (x->rb_link[0] != NULL)
486      {
487        assert (trav->rb_height < RB_MAX_HEIGHT);
488        trav->rb_stack[trav->rb_height++] = x;
489        x = x->rb_link[0];
490      }
491  trav->rb_node = x;
492
493  return x != NULL ? x->rb_data : NULL;
494}
495
496/* Initializes |trav| for |tree|
497   and selects and returns a pointer to its greatest-valued item.
498   Returns |NULL| if |tree| contains no nodes. */
499void *
500rb_t_last (struct rb_traverser *trav, struct rb_table *tree)
501{
502  struct rb_node *x;
503
504  assert (tree != NULL && trav != NULL);
505
506  trav->rb_table = tree;
507  trav->rb_height = 0;
508  trav->rb_generation = tree->rb_generation;
509
510  x = tree->rb_root;
511  if (x != NULL)
512    while (x->rb_link[1] != NULL)
513      {
514        assert (trav->rb_height < RB_MAX_HEIGHT);
515        trav->rb_stack[trav->rb_height++] = x;
516        x = x->rb_link[1];
517      }
518  trav->rb_node = x;
519
520  return x != NULL ? x->rb_data : NULL;
521}
522
523/* Searches for |item| in |tree|.
524   If found, initializes |trav| to the item found and returns the item
525   as well.
526   If there is no matching item, initializes |trav| to the null item
527   and returns |NULL|. */
528void *
529rb_t_find (struct rb_traverser *trav, struct rb_table *tree, void *item)
530{
531  struct rb_node *p, *q;
532
533  assert (trav != NULL && tree != NULL && item != NULL);
534  trav->rb_table = tree;
535  trav->rb_height = 0;
536  trav->rb_generation = tree->rb_generation;
537  for (p = tree->rb_root; p != NULL; p = q)
538    {
539      int cmp = tree->rb_compare (item, p->rb_data, tree->rb_param);
540
541      if (cmp < 0)
542        q = p->rb_link[0];
543      else if (cmp > 0)
544        q = p->rb_link[1];
545      else /* |cmp == 0| */
546        {
547          trav->rb_node = p;
548          return p->rb_data;
549        }
550
551      assert (trav->rb_height < RB_MAX_HEIGHT);
552      trav->rb_stack[trav->rb_height++] = p;
553    }
554
555  trav->rb_height = 0;
556  trav->rb_node = NULL;
557  return NULL;
558}
559
560/* Attempts to insert |item| into |tree|.
561   If |item| is inserted successfully, it is returned and |trav| is
562   initialized to its location.
563   If a duplicate is found, it is returned and |trav| is initialized to
564   its location.  No replacement of the item occurs.
565   If a memory allocation failure occurs, |NULL| is returned and |trav|
566   is initialized to the null item. */
567void *
568rb_t_insert (struct rb_traverser *trav, struct rb_table *tree, void *item)
569{
570  void **p;
571
572  assert (trav != NULL && tree != NULL && item != NULL);
573
574  p = rb_probe (tree, item);
575  if (p != NULL)
576    {
577      trav->rb_table = tree;
578      trav->rb_node =
579        ((struct rb_node *)
580         ((char *) p - offsetof (struct rb_node, rb_data)));
581      trav->rb_generation = tree->rb_generation - 1;
582      return *p;
583    }
584  else
585    {
586      rb_t_init (trav, tree);
587      return NULL;
588    }
589}
590
591/* Initializes |trav| to have the same current node as |src|. */
592void *
593rb_t_copy (struct rb_traverser *trav, const struct rb_traverser *src)
594{
595  assert (trav != NULL && src != NULL);
596
597  if (trav != src)
598    {
599      trav->rb_table = src->rb_table;
600      trav->rb_node = src->rb_node;
601      trav->rb_generation = src->rb_generation;
602      if (trav->rb_generation == trav->rb_table->rb_generation)
603        {
604          trav->rb_height = src->rb_height;
605          memcpy (trav->rb_stack, (const void *) src->rb_stack,
606                  sizeof *trav->rb_stack * trav->rb_height);
607        }
608    }
609
610  return trav->rb_node != NULL ? trav->rb_node->rb_data : NULL;
611}
612
613/* Returns the next data item in inorder
614   within the tree being traversed with |trav|,
615   or if there are no more data items returns |NULL|. */
616void *
617rb_t_next (struct rb_traverser *trav)
618{
619  struct rb_node *x;
620
621  assert (trav != NULL);
622
623  if (trav->rb_generation != trav->rb_table->rb_generation)
624    trav_refresh (trav);
625
626  x = trav->rb_node;
627  if (x == NULL)
628    {
629      return rb_t_first (trav, trav->rb_table);
630    }
631  else if (x->rb_link[1] != NULL)
632    {
633      assert (trav->rb_height < RB_MAX_HEIGHT);
634      trav->rb_stack[trav->rb_height++] = x;
635      x = x->rb_link[1];
636
637      while (x->rb_link[0] != NULL)
638        {
639          assert (trav->rb_height < RB_MAX_HEIGHT);
640          trav->rb_stack[trav->rb_height++] = x;
641          x = x->rb_link[0];
642        }
643    }
644  else
645    {
646      struct rb_node *y;
647
648      do
649        {
650          if (trav->rb_height == 0)
651            {
652              trav->rb_node = NULL;
653              return NULL;
654            }
655
656          y = x;
657          x = trav->rb_stack[--trav->rb_height];
658        }
659      while (y == x->rb_link[1]);
660    }
661  trav->rb_node = x;
662
663  return x->rb_data;
664}
665
666/* Returns the previous data item in inorder
667   within the tree being traversed with |trav|,
668   or if there are no more data items returns |NULL|. */
669void *
670rb_t_prev (struct rb_traverser *trav)
671{
672  struct rb_node *x;
673
674  assert (trav != NULL);
675
676  if (trav->rb_generation != trav->rb_table->rb_generation)
677    trav_refresh (trav);
678
679  x = trav->rb_node;
680  if (x == NULL)
681    {
682      return rb_t_last (trav, trav->rb_table);
683    }
684  else if (x->rb_link[0] != NULL)
685    {
686      assert (trav->rb_height < RB_MAX_HEIGHT);
687      trav->rb_stack[trav->rb_height++] = x;
688      x = x->rb_link[0];
689
690      while (x->rb_link[1] != NULL)
691        {
692          assert (trav->rb_height < RB_MAX_HEIGHT);
693          trav->rb_stack[trav->rb_height++] = x;
694          x = x->rb_link[1];
695        }
696    }
697  else
698    {
699      struct rb_node *y;
700
701      do
702        {
703          if (trav->rb_height == 0)
704            {
705              trav->rb_node = NULL;
706              return NULL;
707            }
708
709          y = x;
710          x = trav->rb_stack[--trav->rb_height];
711        }
712      while (y == x->rb_link[0]);
713    }
714  trav->rb_node = x;
715
716  return x->rb_data;
717}
718
719/* Returns |trav|'s current item. */
720void *
721rb_t_cur (struct rb_traverser *trav)
722{
723  assert (trav != NULL);
724
725  return trav->rb_node != NULL ? trav->rb_node->rb_data : NULL;
726}
727
728/* Replaces the current item in |trav| by |new| and returns the item replaced.
729   |trav| must not have the null item selected.
730   The new item must not upset the ordering of the tree. */
731void *
732rb_t_replace (struct rb_traverser *trav, void *new)
733{
734  void *old;
735
736  assert (trav != NULL && trav->rb_node != NULL && new != NULL);
737  old = trav->rb_node->rb_data;
738  trav->rb_node->rb_data = new;
739  return old;
740}
741
742/* Destroys |new| with |rb_destroy (new, destroy)|,
743   first setting right links of nodes in |stack| within |new|
744   to null pointers to avoid touching uninitialized data. */
745static void
746copy_error_recovery (struct rb_node **stack, int height,
747                     struct rb_table *new, rb_item_func *destroy)
748{
749  assert (stack != NULL && height >= 0 && new != NULL);
750
751  for (; height > 2; height -= 2)
752    stack[height - 1]->rb_link[1] = NULL;
753  rb_destroy (new, destroy);
754}
755
756/* Copies |org| to a newly created tree, which is returned.
757   If |copy != NULL|, each data item in |org| is first passed to |copy|,
758   and the return values are inserted into the tree,
759   with |NULL| return values taken as indications of failure.
760   On failure, destroys the partially created new tree,
761   applying |destroy|, if non-null, to each item in the new tree so far,
762   and returns |NULL|.
763   If |allocator != NULL|, it is used for allocation in the new tree.
764   Otherwise, the same allocator used for |org| is used. */
765struct rb_table *
766rb_copy (const struct rb_table *org, rb_copy_func *copy,
767          rb_item_func *destroy, struct libavl_allocator *allocator)
768{
769  struct rb_node *stack[2 * (RB_MAX_HEIGHT + 1)];
770  int height = 0;
771
772  struct rb_table *new;
773  const struct rb_node *x;
774  struct rb_node *y;
775
776  assert (org != NULL);
777  new = rb_create (org->rb_compare, org->rb_param,
778                    allocator != NULL ? allocator : org->rb_alloc);
779  if (new == NULL)
780    return NULL;
781  new->rb_count = org->rb_count;
782  if (new->rb_count == 0)
783    return new;
784
785  x = (const struct rb_node *) &org->rb_root;
786  y = (struct rb_node *) &new->rb_root;
787  for (;;)
788    {
789      while (x->rb_link[0] != NULL)
790        {
791          assert (height < 2 * (RB_MAX_HEIGHT + 1));
792
793          y->rb_link[0] =
794            new->rb_alloc->libavl_malloc (new->rb_alloc,
795                                           sizeof *y->rb_link[0]);
796          if (y->rb_link[0] == NULL)
797            {
798              if (y != (struct rb_node *) &new->rb_root)
799                {
800                  y->rb_data = NULL;
801                  y->rb_link[1] = NULL;
802                }
803
804              copy_error_recovery (stack, height, new, destroy);
805              return NULL;
806            }
807
808          stack[height++] = (struct rb_node *) x;
809          stack[height++] = y;
810          x = x->rb_link[0];
811          y = y->rb_link[0];
812        }
813      y->rb_link[0] = NULL;
814
815      for (;;)
816        {
817          y->rb_color = x->rb_color;
818          if (copy == NULL)
819            y->rb_data = x->rb_data;
820          else
821            {
822              y->rb_data = copy (x->rb_data, org->rb_param);
823              if (y->rb_data == NULL)
824                {
825                  y->rb_link[1] = NULL;
826                  copy_error_recovery (stack, height, new, destroy);
827                  return NULL;
828                }
829            }
830
831          if (x->rb_link[1] != NULL)
832            {
833              y->rb_link[1] =
834                new->rb_alloc->libavl_malloc (new->rb_alloc,
835                                               sizeof *y->rb_link[1]);
836              if (y->rb_link[1] == NULL)
837                {
838                  copy_error_recovery (stack, height, new, destroy);
839                  return NULL;
840                }
841
842              x = x->rb_link[1];
843              y = y->rb_link[1];
844              break;
845            }
846          else
847            y->rb_link[1] = NULL;
848
849          if (height <= 2)
850            return new;
851
852          y = stack[--height];
853          x = stack[--height];
854        }
855    }
856}
857
858/* Frees storage allocated for |tree|.
859   If |destroy != NULL|, applies it to each data item in inorder. */
860void
861rb_destroy (struct rb_table *tree, rb_item_func *destroy)
862{
863  struct rb_node *p, *q;
864
865  assert (tree != NULL);
866
867  for (p = tree->rb_root; p != NULL; p = q)
868    if (p->rb_link[0] == NULL)
869      {
870        q = p->rb_link[1];
871        if (destroy != NULL && p->rb_data != NULL)
872          destroy (p->rb_data, tree->rb_param);
873        tree->rb_alloc->libavl_free (tree->rb_alloc, p);
874      }
875    else
876      {
877        q = p->rb_link[0];
878        p->rb_link[0] = q->rb_link[1];
879        q->rb_link[1] = p;
880      }
881
882  tree->rb_alloc->libavl_free (tree->rb_alloc, tree);
883}
884
885/* Allocates |size| bytes of space using |malloc()|.
886   Returns a null pointer if allocation fails. */
887void *
888rb_malloc (struct libavl_allocator *allocator, size_t size)
889{
890  assert (allocator != NULL && size > 0);
891  return malloc (size);
892}
893
894/* Frees |block|. */
895void
896rb_free (struct libavl_allocator *allocator, void *block)
897{
898  assert (allocator != NULL && block != NULL);
899  free (block);
900}
901
902/* Default memory allocator that uses |malloc()| and |free()|. */
903struct libavl_allocator rb_allocator_default =
904  {
905    rb_malloc,
906    rb_free
907  };
908
909#undef NDEBUG
910#include <assert.h>
911
912/* Asserts that |rb_insert()| succeeds at inserting |item| into |table|. */
913void
914(rb_assert_insert) (struct rb_table *table, void *item)
915{
916  void **p = rb_probe (table, item);
917  assert (p != NULL && *p == item);
918}
919
920/* Asserts that |rb_delete()| really removes |item| from |table|,
921   and returns the removed item. */
922void *
923(rb_assert_delete) (struct rb_table *table, void *item)
924{
925  void *p = rb_delete (table, item);
926  assert (p != NULL);
927  return p;
928}
929
Note: See TracBrowser for help on using the repository browser.