← Back to branch summary

~ubuntu-branches/ubuntu/utopic/binutils-arm64-cross/utopic

« back to all changes in this revision

Viewing changes to binutils-2.23.52.20130611/libiberty/splay-tree.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-06-20 17:38:09 UTC
  • Revision ID: package-import@ubuntu.com-20130620173809-app8lzgvymy5fg6c
Tags: 0.7
Build-depend on binutils-source (>= 2.23.52.20130620-1~).

Show diffs side-by-side

added added

removed removed

Lines of Context:
binutils-2.23.52.20130611/libiberty/splay-tree.c
 
1
/* A splay-tree datatype.  
 
2
   Copyright (C) 1998, 1999, 2000, 2001, 2009,
 
3
   2010, 2011 Free Software Foundation, Inc.
 
4
   Contributed by Mark Mitchell (mark@markmitchell.com).
 
5
 
 
6
This file is part of GNU CC.
 
7
   
 
8
GNU CC is free software; you can redistribute it and/or modify it
 
9
under the terms of the GNU General Public License as published by
 
10
the Free Software Foundation; either version 2, or (at your option)
 
11
any later version.
 
12
 
 
13
GNU CC is distributed in the hope that it will be useful, but
 
14
WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
16
General Public License for more details.
 
17
 
 
18
You should have received a copy of the GNU General Public License
 
19
along with GNU CC; see the file COPYING.  If not, write to
 
20
the Free Software Foundation, 51 Franklin Street - Fifth Floor,
 
21
Boston, MA 02110-1301, USA.  */
 
22
 
 
23
/* For an easily readable description of splay-trees, see:
 
24
 
 
25
     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
 
26
     Algorithms.  Harper-Collins, Inc.  1991.  */
 
27
 
 
28
#ifdef HAVE_CONFIG_H
 
29
#include "config.h"
 
30
#endif
 
31
 
 
32
#ifdef HAVE_STDLIB_H
 
33
#include <stdlib.h>
 
34
#endif
 
35
 
 
36
#include <stdio.h>
 
37
 
 
38
#include "libiberty.h"
 
39
#include "splay-tree.h"
 
40
 
 
41
static void splay_tree_delete_helper (splay_tree, splay_tree_node);
 
42
static inline void rotate_left (splay_tree_node *,
 
43
                                splay_tree_node, splay_tree_node);
 
44
static inline void rotate_right (splay_tree_node *,
 
45
                                splay_tree_node, splay_tree_node);
 
46
static void splay_tree_splay (splay_tree, splay_tree_key);
 
47
static int splay_tree_foreach_helper (splay_tree_node,
 
48
                                      splay_tree_foreach_fn, void*);
 
49
 
 
50
/* Deallocate NODE (a member of SP), and all its sub-trees.  */
 
51
 
 
52
static void 
 
53
splay_tree_delete_helper (splay_tree sp, splay_tree_node node)
 
54
{
 
55
  splay_tree_node pending = 0;
 
56
  splay_tree_node active = 0;
 
57
 
 
58
  if (!node)
 
59
    return;
 
60
 
 
61
#define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
 
62
#define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);
 
63
 
 
64
  KDEL (node->key);
 
65
  VDEL (node->value);
 
66
 
 
67
  /* We use the "key" field to hold the "next" pointer.  */
 
68
  node->key = (splay_tree_key)pending;
 
69
  pending = (splay_tree_node)node;
 
70
 
 
71
  /* Now, keep processing the pending list until there aren't any
 
72
     more.  This is a little more complicated than just recursing, but
 
73
     it doesn't toast the stack for large trees.  */
 
74
 
 
75
  while (pending)
 
76
    {
 
77
      active = pending;
 
78
      pending = 0;
 
79
      while (active)
 
80
        {
 
81
          splay_tree_node temp;
 
82
 
 
83
          /* active points to a node which has its key and value
 
84
             deallocated, we just need to process left and right.  */
 
85
 
 
86
          if (active->left)
 
87
            {
 
88
              KDEL (active->left->key);
 
89
              VDEL (active->left->value);
 
90
              active->left->key = (splay_tree_key)pending;
 
91
              pending = (splay_tree_node)(active->left);
 
92
            }
 
93
          if (active->right)
 
94
            {
 
95
              KDEL (active->right->key);
 
96
              VDEL (active->right->value);
 
97
              active->right->key = (splay_tree_key)pending;
 
98
              pending = (splay_tree_node)(active->right);
 
99
            }
 
100
 
 
101
          temp = active;
 
102
          active = (splay_tree_node)(temp->key);
 
103
          (*sp->deallocate) ((char*) temp, sp->allocate_data);
 
104
        }
 
105
    }
 
106
#undef KDEL
 
107
#undef VDEL
 
108
}
 
109
 
 
110
/* Rotate the edge joining the left child N with its parent P.  PP is the
 
111
   grandparents' pointer to P.  */
 
112
 
 
113
static inline void
 
114
rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
 
115
{
 
116
  splay_tree_node tmp;
 
117
  tmp = n->right;
 
118
  n->right = p;
 
119
  p->left = tmp;
 
120
  *pp = n;
 
121
}
 
122
 
 
123
/* Rotate the edge joining the right child N with its parent P.  PP is the
 
124
   grandparents' pointer to P.  */
 
125
 
 
126
static inline void
 
127
rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
 
128
{
 
129
  splay_tree_node tmp;
 
130
  tmp = n->left;
 
131
  n->left = p;
 
132
  p->right = tmp;
 
133
  *pp = n;
 
134
}
 
135
 
 
136
/* Bottom up splay of key.  */
 
137
 
 
138
static void
 
139
splay_tree_splay (splay_tree sp, splay_tree_key key)
 
140
{
 
141
  if (sp->root == 0)
 
142
    return;
 
143
 
 
144
  do {
 
145
    int cmp1, cmp2;
 
146
    splay_tree_node n, c;
 
147
 
 
148
    n = sp->root;
 
149
    cmp1 = (*sp->comp) (key, n->key);
 
150
 
 
151
    /* Found.  */
 
152
    if (cmp1 == 0)
 
153
      return;
 
154
 
 
155
    /* Left or right?  If no child, then we're done.  */
 
156
    if (cmp1 < 0)
 
157
      c = n->left;
 
158
    else
 
159
      c = n->right;
 
160
    if (!c)
 
161
      return;
 
162
 
 
163
    /* Next one left or right?  If found or no child, we're done
 
164
       after one rotation.  */
 
165
    cmp2 = (*sp->comp) (key, c->key);
 
166
    if (cmp2 == 0
 
167
        || (cmp2 < 0 && !c->left)
 
168
        || (cmp2 > 0 && !c->right))
 
169
      {
 
170
        if (cmp1 < 0)
 
171
          rotate_left (&sp->root, n, c);
 
172
        else
 
173
          rotate_right (&sp->root, n, c);
 
174
        return;
 
175
      }
 
176
 
 
177
    /* Now we have the four cases of double-rotation.  */
 
178
    if (cmp1 < 0 && cmp2 < 0)
 
179
      {
 
180
        rotate_left (&n->left, c, c->left);
 
181
        rotate_left (&sp->root, n, n->left);
 
182
      }
 
183
    else if (cmp1 > 0 && cmp2 > 0)
 
184
      {
 
185
        rotate_right (&n->right, c, c->right);
 
186
        rotate_right (&sp->root, n, n->right);
 
187
      }
 
188
    else if (cmp1 < 0 && cmp2 > 0)
 
189
      {
 
190
        rotate_right (&n->left, c, c->right);
 
191
        rotate_left (&sp->root, n, n->left);
 
192
      }
 
193
    else if (cmp1 > 0 && cmp2 < 0)
 
194
      {
 
195
        rotate_left (&n->right, c, c->left);
 
196
        rotate_right (&sp->root, n, n->right);
 
197
      }
 
198
  } while (1);
 
199
}
 
200
 
 
201
/* Call FN, passing it the DATA, for every node below NODE, all of
 
202
   which are from SP, following an in-order traversal.  If FN every
 
203
   returns a non-zero value, the iteration ceases immediately, and the
 
204
   value is returned.  Otherwise, this function returns 0.  */
 
205
 
 
206
static int
 
207
splay_tree_foreach_helper (splay_tree_node node,
 
208
                           splay_tree_foreach_fn fn, void *data)
 
209
{
 
210
  int val;
 
211
  splay_tree_node *stack;
 
212
  int stack_ptr, stack_size;
 
213
 
 
214
  /* A non-recursive implementation is used to avoid filling the stack
 
215
     for large trees.  Splay trees are worst case O(n) in the depth of
 
216
     the tree.  */
 
217
 
 
218
#define INITIAL_STACK_SIZE 100
 
219
  stack_size = INITIAL_STACK_SIZE;
 
220
  stack_ptr = 0;
 
221
  stack = XNEWVEC (splay_tree_node, stack_size);
 
222
  val = 0;
 
223
 
 
224
  for (;;)
 
225
    {
 
226
      while (node != NULL)
 
227
        {
 
228
          if (stack_ptr == stack_size)
 
229
            {
 
230
              stack_size *= 2;
 
231
              stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
 
232
            }
 
233
          stack[stack_ptr++] = node;
 
234
          node = node->left;
 
235
        }
 
236
 
 
237
      if (stack_ptr == 0)
 
238
        break;
 
239
 
 
240
      node = stack[--stack_ptr];
 
241
 
 
242
      val = (*fn) (node, data);
 
243
      if (val)
 
244
        break;
 
245
 
 
246
      node = node->right;
 
247
    }
 
248
 
 
249
  XDELETEVEC (stack);
 
250
  return val;
 
251
}
 
252
 
 
253
/* An allocator and deallocator based on xmalloc.  */
 
254
static void *
 
255
splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
 
256
{
 
257
  return (void *) xmalloc (size);
 
258
}
 
259
 
 
260
static void
 
261
splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
 
262
{
 
263
  free (object);
 
264
}
 
265
 
 
266
 
 
267
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 
268
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 
269
   values.  Use xmalloc to allocate the splay tree structure, and any
 
270
   nodes added.  */
 
271
 
 
272
splay_tree 
 
273
splay_tree_new (splay_tree_compare_fn compare_fn,
 
274
                splay_tree_delete_key_fn delete_key_fn,
 
275
                splay_tree_delete_value_fn delete_value_fn)
 
276
{
 
277
  return (splay_tree_new_with_allocator
 
278
          (compare_fn, delete_key_fn, delete_value_fn,
 
279
           splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
 
280
}
 
281
 
 
282
 
 
283
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 
284
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 
285
   values.  */
 
286
 
 
287
splay_tree 
 
288
splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
 
289
                               splay_tree_delete_key_fn delete_key_fn,
 
290
                               splay_tree_delete_value_fn delete_value_fn,
 
291
                               splay_tree_allocate_fn allocate_fn,
 
292
                               splay_tree_deallocate_fn deallocate_fn,
 
293
                               void *allocate_data)
 
294
{
 
295
  return
 
296
    splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn,
 
297
                                allocate_fn, allocate_fn, deallocate_fn,
 
298
                                allocate_data);
 
299
}
 
300
 
 
301
/*
 
302
 
 
303
@deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
 
304
(splay_tree_compare_fn @var{compare_fn}, @
 
305
splay_tree_delete_key_fn @var{delete_key_fn}, @
 
306
splay_tree_delete_value_fn @var{delete_value_fn}, @
 
307
splay_tree_allocate_fn @var{tree_allocate_fn}, @
 
308
splay_tree_allocate_fn @var{node_allocate_fn}, @
 
309
splay_tree_deallocate_fn @var{deallocate_fn}, @
 
310
void * @var{allocate_data})
 
311
 
 
312
This function creates a splay tree that uses two different allocators
 
313
@var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
 
314
tree itself and its nodes respectively.  This is useful when variables of
 
315
different types need to be allocated with different allocators.
 
316
 
 
317
The splay tree will use @var{compare_fn} to compare nodes,
 
318
@var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
 
319
deallocate values.
 
320
 
 
321
@end deftypefn
 
322
 
 
323
*/
 
324
 
 
325
splay_tree
 
326
splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn,
 
327
                            splay_tree_delete_key_fn delete_key_fn,
 
328
                            splay_tree_delete_value_fn delete_value_fn,
 
329
                            splay_tree_allocate_fn tree_allocate_fn,
 
330
                            splay_tree_allocate_fn node_allocate_fn,
 
331
                            splay_tree_deallocate_fn deallocate_fn,
 
332
                            void * allocate_data)
 
333
{
 
334
  splay_tree sp = (splay_tree) (*tree_allocate_fn)
 
335
    (sizeof (struct splay_tree_s), allocate_data);
 
336
 
 
337
  sp->root = 0;
 
338
  sp->comp = compare_fn;
 
339
  sp->delete_key = delete_key_fn;
 
340
  sp->delete_value = delete_value_fn;
 
341
  sp->allocate = node_allocate_fn;
 
342
  sp->deallocate = deallocate_fn;
 
343
  sp->allocate_data = allocate_data;
 
344
 
 
345
  return sp;
 
346
}
 
347
 
 
348
/* Deallocate SP.  */
 
349
 
 
350
void 
 
351
splay_tree_delete (splay_tree sp)
 
352
{
 
353
  splay_tree_delete_helper (sp, sp->root);
 
354
  (*sp->deallocate) ((char*) sp, sp->allocate_data);
 
355
}
 
356
 
 
357
/* Insert a new node (associating KEY with DATA) into SP.  If a
 
358
   previous node with the indicated KEY exists, its data is replaced
 
359
   with the new value.  Returns the new node.  */
 
360
 
 
361
splay_tree_node
 
362
splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
 
363
{
 
364
  int comparison = 0;
 
365
 
 
366
  splay_tree_splay (sp, key);
 
367
 
 
368
  if (sp->root)
 
369
    comparison = (*sp->comp)(sp->root->key, key);
 
370
 
 
371
  if (sp->root && comparison == 0)
 
372
    {
 
373
      /* If the root of the tree already has the indicated KEY, just
 
374
         replace the value with VALUE.  */
 
375
      if (sp->delete_value)
 
376
        (*sp->delete_value)(sp->root->value);
 
377
      sp->root->value = value;
 
378
    } 
 
379
  else 
 
380
    {
 
381
      /* Create a new node, and insert it at the root.  */
 
382
      splay_tree_node node;
 
383
 
 
384
      node = ((splay_tree_node)
 
385
              (*sp->allocate) (sizeof (struct splay_tree_node_s),
 
386
                               sp->allocate_data));
 
387
      node->key = key;
 
388
      node->value = value;
 
389
      
 
390
      if (!sp->root)
 
391
        node->left = node->right = 0;
 
392
      else if (comparison < 0)
 
393
        {
 
394
          node->left = sp->root;
 
395
          node->right = node->left->right;
 
396
          node->left->right = 0;
 
397
        }
 
398
      else
 
399
        {
 
400
          node->right = sp->root;
 
401
          node->left = node->right->left;
 
402
          node->right->left = 0;
 
403
        }
 
404
 
 
405
      sp->root = node;
 
406
    }
 
407
 
 
408
  return sp->root;
 
409
}
 
410
 
 
411
/* Remove KEY from SP.  It is not an error if it did not exist.  */
 
412
 
 
413
void
 
414
splay_tree_remove (splay_tree sp, splay_tree_key key)
 
415
{
 
416
  splay_tree_splay (sp, key);
 
417
 
 
418
  if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
 
419
    {
 
420
      splay_tree_node left, right;
 
421
 
 
422
      left = sp->root->left;
 
423
      right = sp->root->right;
 
424
 
 
425
      /* Delete the root node itself.  */
 
426
      if (sp->delete_value)
 
427
        (*sp->delete_value) (sp->root->value);
 
428
      (*sp->deallocate) (sp->root, sp->allocate_data);
 
429
 
 
430
      /* One of the children is now the root.  Doesn't matter much
 
431
         which, so long as we preserve the properties of the tree.  */
 
432
      if (left)
 
433
        {
 
434
          sp->root = left;
 
435
 
 
436
          /* If there was a right child as well, hang it off the 
 
437
             right-most leaf of the left child.  */
 
438
          if (right)
 
439
            {
 
440
              while (left->right)
 
441
                left = left->right;
 
442
              left->right = right;
 
443
            }
 
444
        }
 
445
      else
 
446
        sp->root = right;
 
447
    }
 
448
}
 
449
 
 
450
/* Lookup KEY in SP, returning VALUE if present, and NULL 
 
451
   otherwise.  */
 
452
 
 
453
splay_tree_node
 
454
splay_tree_lookup (splay_tree sp, splay_tree_key key)
 
455
{
 
456
  splay_tree_splay (sp, key);
 
457
 
 
458
  if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
 
459
    return sp->root;
 
460
  else
 
461
    return 0;
 
462
}
 
463
 
 
464
/* Return the node in SP with the greatest key.  */
 
465
 
 
466
splay_tree_node
 
467
splay_tree_max (splay_tree sp)
 
468
{
 
469
  splay_tree_node n = sp->root;
 
470
 
 
471
  if (!n)
 
472
    return NULL;
 
473
 
 
474
  while (n->right)
 
475
    n = n->right;
 
476
 
 
477
  return n;
 
478
}
 
479
 
 
480
/* Return the node in SP with the smallest key.  */
 
481
 
 
482
splay_tree_node
 
483
splay_tree_min (splay_tree sp)
 
484
{
 
485
  splay_tree_node n = sp->root;
 
486
 
 
487
  if (!n)
 
488
    return NULL;
 
489
 
 
490
  while (n->left)
 
491
    n = n->left;
 
492
 
 
493
  return n;
 
494
}
 
495
 
 
496
/* Return the immediate predecessor KEY, or NULL if there is no
 
497
   predecessor.  KEY need not be present in the tree.  */
 
498
 
 
499
splay_tree_node
 
500
splay_tree_predecessor (splay_tree sp, splay_tree_key key)
 
501
{
 
502
  int comparison;
 
503
  splay_tree_node node;
 
504
 
 
505
  /* If the tree is empty, there is certainly no predecessor.  */
 
506
  if (!sp->root)
 
507
    return NULL;
 
508
 
 
509
  /* Splay the tree around KEY.  That will leave either the KEY
 
510
     itself, its predecessor, or its successor at the root.  */
 
511
  splay_tree_splay (sp, key);
 
512
  comparison = (*sp->comp)(sp->root->key, key);
 
513
 
 
514
  /* If the predecessor is at the root, just return it.  */
 
515
  if (comparison < 0)
 
516
    return sp->root;
 
517
 
 
518
  /* Otherwise, find the rightmost element of the left subtree.  */
 
519
  node = sp->root->left;
 
520
  if (node)
 
521
    while (node->right)
 
522
      node = node->right;
 
523
 
 
524
  return node;
 
525
}
 
526
 
 
527
/* Return the immediate successor KEY, or NULL if there is no
 
528
   successor.  KEY need not be present in the tree.  */
 
529
 
 
530
splay_tree_node
 
531
splay_tree_successor (splay_tree sp, splay_tree_key key)
 
532
{
 
533
  int comparison;
 
534
  splay_tree_node node;
 
535
 
 
536
  /* If the tree is empty, there is certainly no successor.  */
 
537
  if (!sp->root)
 
538
    return NULL;
 
539
 
 
540
  /* Splay the tree around KEY.  That will leave either the KEY
 
541
     itself, its predecessor, or its successor at the root.  */
 
542
  splay_tree_splay (sp, key);
 
543
  comparison = (*sp->comp)(sp->root->key, key);
 
544
 
 
545
  /* If the successor is at the root, just return it.  */
 
546
  if (comparison > 0)
 
547
    return sp->root;
 
548
 
 
549
  /* Otherwise, find the leftmost element of the right subtree.  */
 
550
  node = sp->root->right;
 
551
  if (node)
 
552
    while (node->left)
 
553
      node = node->left;
 
554
 
 
555
  return node;
 
556
}
 
557
 
 
558
/* Call FN, passing it the DATA, for every node in SP, following an
 
559
   in-order traversal.  If FN every returns a non-zero value, the
 
560
   iteration ceases immediately, and the value is returned.
 
561
   Otherwise, this function returns 0.  */
 
562
 
 
563
int
 
564
splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 
565
{
 
566
  return splay_tree_foreach_helper (sp->root, fn, data);
 
567
}
 
568
 
 
569
/* Splay-tree comparison function, treating the keys as ints.  */
 
570
 
 
571
int
 
572
splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
 
573
{
 
574
  if ((int) k1 < (int) k2)
 
575
    return -1;
 
576
  else if ((int) k1 > (int) k2)
 
577
    return 1;
 
578
  else 
 
579
    return 0;
 
580
}
 
581
 
 
582
/* Splay-tree comparison function, treating the keys as pointers.  */
 
583
 
 
584
int
 
585
splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
 
586
{
 
587
  if ((char*) k1 < (char*) k2)
 
588
    return -1;
 
589
  else if ((char*) k1 > (char*) k2)
 
590
    return 1;
 
591
  else 
 
592
    return 0;
 
593
}