OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [insight/] [libiberty/] [splay-tree.c] - Blame information for rev 578

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 578 markom
/* A splay-tree datatype.
2
   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3
   Contributed by Mark Mitchell (mark@markmitchell.com).
4
 
5
This file is part of GNU CC.
6
 
7
GNU CC is free software; you can redistribute it and/or modify it
8
under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2, or (at your option)
10
any later version.
11
 
12
GNU CC is distributed in the hope that it will be useful, but
13
WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15
General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GNU CC; see the file COPYING.  If not, write to
19
the Free Software Foundation, 59 Temple Place - Suite 330,
20
Boston, MA 02111-1307, USA.  */
21
 
22
/* For an easily readable description of splay-trees, see:
23
 
24
     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
25
     Algorithms.  Harper-Collins, Inc.  1991.  */
26
 
27
#ifdef HAVE_CONFIG_H
28
#include "config.h"
29
#endif
30
 
31
#ifdef HAVE_STDLIB_H
32
#include <stdlib.h>
33
#endif
34
 
35
#include <stdio.h>
36
 
37
#include "libiberty.h"
38
#include "splay-tree.h"
39
 
40
static void splay_tree_delete_helper    PARAMS((splay_tree,
41
                                                splay_tree_node));
42
static void splay_tree_splay            PARAMS((splay_tree,
43
                                                splay_tree_key));
44
static splay_tree_node splay_tree_splay_helper
45
                                        PARAMS((splay_tree,
46
                                                splay_tree_key,
47
                                                splay_tree_node*,
48
                                                splay_tree_node*,
49
                                                splay_tree_node*));
50
static int splay_tree_foreach_helper    PARAMS((splay_tree,
51
                                                splay_tree_node,
52
                                                splay_tree_foreach_fn,
53
                                                void*));
54
 
55
/* Deallocate NODE (a member of SP), and all its sub-trees.  */
56
 
57
static void
58
splay_tree_delete_helper (sp, node)
59
     splay_tree sp;
60
     splay_tree_node node;
61
{
62
  if (!node)
63
    return;
64
 
65
  splay_tree_delete_helper (sp, node->left);
66
  splay_tree_delete_helper (sp, node->right);
67
 
68
  if (sp->delete_key)
69
    (*sp->delete_key)(node->key);
70
  if (sp->delete_value)
71
    (*sp->delete_value)(node->value);
72
 
73
  free ((char*) node);
74
}
75
 
76
/* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
77
   and grandparent, respectively, of NODE.  */
78
 
79
static splay_tree_node
80
splay_tree_splay_helper (sp, key, node, parent, grandparent)
81
     splay_tree sp;
82
     splay_tree_key key;
83
     splay_tree_node *node;
84
     splay_tree_node *parent;
85
     splay_tree_node *grandparent;
86
{
87
  splay_tree_node *next;
88
  splay_tree_node n;
89
  int comparison;
90
 
91
  n = *node;
92
 
93
  if (!n)
94
    return *parent;
95
 
96
  comparison = (*sp->comp) (key, n->key);
97
 
98
  if (comparison == 0)
99
    /* We've found the target.  */
100
    next = 0;
101
  else if (comparison < 0)
102
    /* The target is to the left.  */
103
    next = &n->left;
104
  else
105
    /* The target is to the right.  */
106
    next = &n->right;
107
 
108
  if (next)
109
    {
110
      /* Continue down the tree.  */
111
      n = splay_tree_splay_helper (sp, key, next, node, parent);
112
 
113
      /* The recursive call will change the place to which NODE
114
         points.  */
115
      if (*node != n)
116
        return n;
117
    }
118
 
119
  if (!parent)
120
    /* NODE is the root.  We are done.  */
121
    return n;
122
 
123
  /* First, handle the case where there is no grandparent (i.e.,
124
     *PARENT is the root of the tree.)  */
125
  if (!grandparent)
126
    {
127
      if (n == (*parent)->left)
128
        {
129
          *node = n->right;
130
          n->right = *parent;
131
        }
132
      else
133
        {
134
          *node = n->left;
135
          n->left = *parent;
136
        }
137
      *parent = n;
138
      return n;
139
    }
140
 
141
  /* Next handle the cases where both N and *PARENT are left children,
142
     or where both are right children.  */
143
  if (n == (*parent)->left && *parent == (*grandparent)->left)
144
    {
145
      splay_tree_node p = *parent;
146
 
147
      (*grandparent)->left = p->right;
148
      p->right = *grandparent;
149
      p->left = n->right;
150
      n->right = p;
151
      *grandparent = n;
152
      return n;
153
    }
154
  else if  (n == (*parent)->right && *parent == (*grandparent)->right)
155
    {
156
      splay_tree_node p = *parent;
157
 
158
      (*grandparent)->right = p->left;
159
      p->left = *grandparent;
160
      p->right = n->left;
161
      n->left = p;
162
      *grandparent = n;
163
      return n;
164
    }
165
 
166
  /* Finally, deal with the case where N is a left child, but *PARENT
167
     is a right child, or vice versa.  */
168
  if (n == (*parent)->left)
169
    {
170
      (*parent)->left = n->right;
171
      n->right = *parent;
172
      (*grandparent)->right = n->left;
173
      n->left = *grandparent;
174
      *grandparent = n;
175
      return n;
176
    }
177
  else
178
    {
179
      (*parent)->right = n->left;
180
      n->left = *parent;
181
      (*grandparent)->left = n->right;
182
      n->right = *grandparent;
183
      *grandparent = n;
184
      return n;
185
    }
186
}
187
 
188
/* Splay SP around KEY.  */
189
 
190
static void
191
splay_tree_splay (sp, key)
192
     splay_tree sp;
193
     splay_tree_key key;
194
{
195
  if (sp->root == 0)
196
    return;
197
 
198
  splay_tree_splay_helper (sp, key, &sp->root,
199
                           /*grandparent=*/0, /*parent=*/0);
200
}
201
 
202
/* Call FN, passing it the DATA, for every node below NODE, all of
203
   which are from SP, following an in-order traversal.  If FN every
204
   returns a non-zero value, the iteration ceases immediately, and the
205
   value is returned.  Otherwise, this function returns 0.  */
206
 
207
static int
208
splay_tree_foreach_helper (sp, node, fn, data)
209
     splay_tree sp;
210
     splay_tree_node node;
211
     splay_tree_foreach_fn fn;
212
     void* data;
213
{
214
  int val;
215
 
216
  if (!node)
217
    return 0;
218
 
219
  val = splay_tree_foreach_helper (sp, node->left, fn, data);
220
  if (val)
221
    return val;
222
 
223
  val = (*fn)(node, data);
224
  if (val)
225
    return val;
226
 
227
  return splay_tree_foreach_helper (sp, node->right, fn, data);
228
}
229
 
230
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
231
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
232
   values.  */
233
 
234
splay_tree
235
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
236
     splay_tree_compare_fn compare_fn;
237
     splay_tree_delete_key_fn delete_key_fn;
238
     splay_tree_delete_value_fn delete_value_fn;
239
{
240
  splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
241
  sp->root = 0;
242
  sp->comp = compare_fn;
243
  sp->delete_key = delete_key_fn;
244
  sp->delete_value = delete_value_fn;
245
 
246
  return sp;
247
}
248
 
249
/* Deallocate SP.  */
250
 
251
void
252
splay_tree_delete (sp)
253
     splay_tree sp;
254
{
255
  splay_tree_delete_helper (sp, sp->root);
256
  free ((char*) sp);
257
}
258
 
259
/* Insert a new node (associating KEY with DATA) into SP.  If a
260
   previous node with the indicated KEY exists, its data is replaced
261
   with the new value.  Returns the new node.  */
262
 
263
splay_tree_node
264
splay_tree_insert (sp, key, value)
265
     splay_tree sp;
266
     splay_tree_key key;
267
     splay_tree_value value;
268
{
269
  int comparison = 0;
270
 
271
  splay_tree_splay (sp, key);
272
 
273
  if (sp->root)
274
    comparison = (*sp->comp)(sp->root->key, key);
275
 
276
  if (sp->root && comparison == 0)
277
    {
278
      /* If the root of the tree already has the indicated KEY, just
279
         replace the value with VALUE.  */
280
      if (sp->delete_value)
281
        (*sp->delete_value)(sp->root->value);
282
      sp->root->value = value;
283
    }
284
  else
285
    {
286
      /* Create a new node, and insert it at the root.  */
287
      splay_tree_node node;
288
 
289
      node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
290
      node->key = key;
291
      node->value = value;
292
 
293
      if (!sp->root)
294
        node->left = node->right = 0;
295
      else if (comparison < 0)
296
        {
297
          node->left = sp->root;
298
          node->right = node->left->right;
299
          node->left->right = 0;
300
        }
301
      else
302
        {
303
          node->right = sp->root;
304
          node->left = node->right->left;
305
          node->right->left = 0;
306
        }
307
 
308
      sp->root = node;
309
    }
310
 
311
  return sp->root;
312
}
313
 
314
/* Remove KEY from SP.  It is not an error if it did not exist.  */
315
 
316
void
317
splay_tree_remove (sp, key)
318
     splay_tree sp;
319
     splay_tree_key key;
320
{
321
  splay_tree_splay (sp, key);
322
 
323
  if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
324
    {
325
      splay_tree_node left, right;
326
 
327
      left = sp->root->left;
328
      right = sp->root->right;
329
 
330
      /* Delete the root node itself.  */
331
      if (sp->delete_value)
332
        (*sp->delete_value) (sp->root->value);
333
      free (sp->root);
334
 
335
      /* One of the children is now the root.  Doesn't matter much
336
         which, so long as we preserve the properties of the tree.  */
337
      if (left)
338
        {
339
          sp->root = left;
340
 
341
          /* If there was a right child as well, hang it off the
342
             right-most leaf of the left child.  */
343
          if (right)
344
            {
345
              while (left->right)
346
                left = left->right;
347
              left->right = right;
348
            }
349
        }
350
      else
351
        sp->root = right;
352
    }
353
}
354
 
355
/* Lookup KEY in SP, returning VALUE if present, and NULL
356
   otherwise.  */
357
 
358
splay_tree_node
359
splay_tree_lookup (sp, key)
360
     splay_tree sp;
361
     splay_tree_key key;
362
{
363
  splay_tree_splay (sp, key);
364
 
365
  if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
366
    return sp->root;
367
  else
368
    return 0;
369
}
370
 
371
/* Return the node in SP with the greatest key.  */
372
 
373
splay_tree_node
374
splay_tree_max (sp)
375
     splay_tree sp;
376
{
377
  splay_tree_node n = sp->root;
378
 
379
  if (!n)
380
    return NULL;
381
 
382
  while (n->right)
383
    n = n->right;
384
 
385
  return n;
386
}
387
 
388
/* Return the node in SP with the smallest key.  */
389
 
390
splay_tree_node
391
splay_tree_min (sp)
392
     splay_tree sp;
393
{
394
  splay_tree_node n = sp->root;
395
 
396
  if (!n)
397
    return NULL;
398
 
399
  while (n->left)
400
    n = n->left;
401
 
402
  return n;
403
}
404
 
405
/* Return the immediate predecessor KEY, or NULL if there is no
406
   predecessor.  KEY need not be present in the tree.  */
407
 
408
splay_tree_node
409
splay_tree_predecessor (sp, key)
410
     splay_tree sp;
411
     splay_tree_key key;
412
{
413
  int comparison;
414
  splay_tree_node node;
415
 
416
  /* If the tree is empty, there is certainly no predecessor.  */
417
  if (!sp->root)
418
    return NULL;
419
 
420
  /* Splay the tree around KEY.  That will leave either the KEY
421
     itself, its predecessor, or its successor at the root.  */
422
  splay_tree_splay (sp, key);
423
  comparison = (*sp->comp)(sp->root->key, key);
424
 
425
  /* If the predecessor is at the root, just return it.  */
426
  if (comparison < 0)
427
    return sp->root;
428
 
429
  /* Otherwise, find the leftmost element of the right subtree.  */
430
  node = sp->root->left;
431
  if (node)
432
    while (node->right)
433
      node = node->right;
434
 
435
  return node;
436
}
437
 
438
/* Return the immediate successor KEY, or NULL if there is no
439
   predecessor.  KEY need not be present in the tree.  */
440
 
441
splay_tree_node
442
splay_tree_successor (sp, key)
443
     splay_tree sp;
444
     splay_tree_key key;
445
{
446
  int comparison;
447
  splay_tree_node node;
448
 
449
  /* If the tree is empty, there is certainly no predecessor.  */
450
  if (!sp->root)
451
    return NULL;
452
 
453
  /* Splay the tree around KEY.  That will leave either the KEY
454
     itself, its predecessor, or its successor at the root.  */
455
  splay_tree_splay (sp, key);
456
  comparison = (*sp->comp)(sp->root->key, key);
457
 
458
  /* If the successor is at the root, just return it.  */
459
  if (comparison > 0)
460
    return sp->root;
461
 
462
  /* Otherwise, find the rightmost element of the left subtree.  */
463
  node = sp->root->right;
464
  if (node)
465
    while (node->left)
466
      node = node->left;
467
 
468
  return node;
469
}
470
 
471
/* Call FN, passing it the DATA, for every node in SP, following an
472
   in-order traversal.  If FN every returns a non-zero value, the
473
   iteration ceases immediately, and the value is returned.
474
   Otherwise, this function returns 0.  */
475
 
476
int
477
splay_tree_foreach (sp, fn, data)
478
     splay_tree sp;
479
     splay_tree_foreach_fn fn;
480
     void *data;
481
{
482
  return splay_tree_foreach_helper (sp, sp->root, fn, data);
483
}
484
 
485
/* Splay-tree comparison function, treating the keys as ints.  */
486
 
487
int
488
splay_tree_compare_ints (k1, k2)
489
     splay_tree_key k1;
490
     splay_tree_key k2;
491
{
492
  if ((int) k1 < (int) k2)
493
    return -1;
494
  else if ((int) k1 > (int) k2)
495
    return 1;
496
  else
497
    return 0;
498
}
499
 
500
/* Splay-tree comparison function, treating the keys as pointers.  */
501
 
502
int
503
splay_tree_compare_pointers (k1, k2)
504
     splay_tree_key k1;
505
     splay_tree_key k2;
506
{
507
  if ((char*) k1 < (char*) k2)
508
    return -1;
509
  else if ((char*) k1 > (char*) k2)
510
    return 1;
511
  else
512
    return 0;
513
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.