← Back to branch summary

~pac72/ubuntu/lucid/ddd/devel

« back to all changes in this revision

Viewing changes to libiberty/splay-tree.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel Schepler
  • Date: 2004-07-22 03:49:37 UTC
  • mfrom: (1.2.1 upstream) (2.1.1 warty)
  • Revision ID: james.westby@ubuntu.com-20040722034937-cysl08t1jvba4jrx
Tags: 1:3.3.9-3
USERINFO has been renamed to USERINFO.txt; adjust debian/rules code
to match, to get correct information on the About DDD dialog.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libiberty/splay-tree.c
1
1
/* A splay-tree datatype.  
2
 
   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
 
2
   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3
3
   Contributed by Mark Mitchell (mark@markmitchell.com).
4
4
 
5
5
This file is part of GNU CC.
32
32
#include <stdlib.h>
33
33
#endif
34
34
 
 
35
#include <stdio.h>
 
36
 
35
37
#include "libiberty.h"
36
38
#include "splay-tree.h"
37
39
 
68
70
  if (sp->delete_value)
69
71
    (*sp->delete_value)(node->value);
70
72
 
71
 
  free ((char*) node);
 
73
  (*sp->deallocate) ((char*) node, sp->allocate_data);
72
74
}
73
75
 
74
76
/* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
225
227
  return splay_tree_foreach_helper (sp, node->right, fn, data);
226
228
}
227
229
 
 
230
 
 
231
/* An allocator and deallocator based on xmalloc.  */
 
232
static void *
 
233
splay_tree_xmalloc_allocate (size, data)
 
234
     int size;
 
235
     void *data ATTRIBUTE_UNUSED;
 
236
{
 
237
  return (void *) xmalloc (size);
 
238
}
 
239
 
 
240
static void
 
241
splay_tree_xmalloc_deallocate (object, data)
 
242
     void *object;
 
243
     void *data ATTRIBUTE_UNUSED;
 
244
{
 
245
  free (object);
 
246
}
 
247
 
 
248
 
 
249
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
 
250
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
 
251
   values.  Use xmalloc to allocate the splay tree structure, and any
 
252
   nodes added.  */
 
253
 
 
254
splay_tree 
 
255
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
 
256
     splay_tree_compare_fn compare_fn;
 
257
     splay_tree_delete_key_fn delete_key_fn;
 
258
     splay_tree_delete_value_fn delete_value_fn;
 
259
{
 
260
  return (splay_tree_new_with_allocator
 
261
          (compare_fn, delete_key_fn, delete_value_fn,
 
262
           splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
 
263
}
 
264
 
 
265
 
228
266
/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
229
267
   DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
230
268
   values.  */
231
269
 
232
270
splay_tree 
233
 
splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
 
271
splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn,
 
272
                               allocate_fn, deallocate_fn, allocate_data)
234
273
     splay_tree_compare_fn compare_fn;
235
274
     splay_tree_delete_key_fn delete_key_fn;
236
275
     splay_tree_delete_value_fn delete_value_fn;
 
276
     splay_tree_allocate_fn allocate_fn;
 
277
     splay_tree_deallocate_fn deallocate_fn;
 
278
     void *allocate_data;
237
279
{
238
 
  splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
 
280
  splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
 
281
                                               allocate_data);
239
282
  sp->root = 0;
240
283
  sp->comp = compare_fn;
241
284
  sp->delete_key = delete_key_fn;
242
285
  sp->delete_value = delete_value_fn;
 
286
  sp->allocate = allocate_fn;
 
287
  sp->deallocate = deallocate_fn;
 
288
  sp->allocate_data = allocate_data;
243
289
 
244
290
  return sp;
245
291
}
251
297
     splay_tree sp;
252
298
{
253
299
  splay_tree_delete_helper (sp, sp->root);
254
 
  free ((char*) sp);
 
300
  (*sp->deallocate) ((char*) sp, sp->allocate_data);
255
301
}
256
302
 
257
303
/* Insert a new node (associating KEY with DATA) into SP.  If a
284
330
      /* Create a new node, and insert it at the root.  */
285
331
      splay_tree_node node;
286
332
      
287
 
      node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
 
333
      node = ((splay_tree_node)
 
334
              (*sp->allocate) (sizeof (struct splay_tree_node_s),
 
335
                               sp->allocate_data));
288
336
      node->key = key;
289
337
      node->value = value;
290
338
      
303
351
          node->right->left = 0;
304
352
        }
305
353
 
306
 
    sp->root = node;
307
 
  }
 
354
      sp->root = node;
 
355
    }
308
356
 
309
357
  return sp->root;
310
358
}
328
376
      /* Delete the root node itself.  */
329
377
      if (sp->delete_value)
330
378
        (*sp->delete_value) (sp->root->value);
331
 
      free (sp->root);
 
379
      (*sp->deallocate) (sp->root, sp->allocate_data);
332
380
 
333
381
      /* One of the children is now the root.  Doesn't matter much
334
382
         which, so long as we preserve the properties of the tree.  */
366
414
    return 0;
367
415
}
368
416
 
 
417
/* Return the node in SP with the greatest key.  */
 
418
 
 
419
splay_tree_node
 
420
splay_tree_max (sp)
 
421
     splay_tree sp;
 
422
{
 
423
  splay_tree_node n = sp->root;
 
424
 
 
425
  if (!n)
 
426
    return NULL;
 
427
 
 
428
  while (n->right)
 
429
    n = n->right;
 
430
 
 
431
  return n;
 
432
}
 
433
 
 
434
/* Return the node in SP with the smallest key.  */
 
435
 
 
436
splay_tree_node
 
437
splay_tree_min (sp)
 
438
     splay_tree sp;
 
439
{
 
440
  splay_tree_node n = sp->root;
 
441
 
 
442
  if (!n)
 
443
    return NULL;
 
444
 
 
445
  while (n->left)
 
446
    n = n->left;
 
447
 
 
448
  return n;
 
449
}
 
450
 
 
451
/* Return the immediate predecessor KEY, or NULL if there is no
 
452
   predecessor.  KEY need not be present in the tree.  */
 
453
 
 
454
splay_tree_node
 
455
splay_tree_predecessor (sp, key)
 
456
     splay_tree sp;
 
457
     splay_tree_key key;
 
458
{
 
459
  int comparison;
 
460
  splay_tree_node node;
 
461
 
 
462
  /* If the tree is empty, there is certainly no predecessor.  */
 
463
  if (!sp->root)
 
464
    return NULL;
 
465
 
 
466
  /* Splay the tree around KEY.  That will leave either the KEY
 
467
     itself, its predecessor, or its successor at the root.  */
 
468
  splay_tree_splay (sp, key);
 
469
  comparison = (*sp->comp)(sp->root->key, key);
 
470
 
 
471
  /* If the predecessor is at the root, just return it.  */
 
472
  if (comparison < 0)
 
473
    return sp->root;
 
474
 
 
475
  /* Otherwise, find the rightmost element of the left subtree.  */
 
476
  node = sp->root->left;
 
477
  if (node)
 
478
    while (node->right)
 
479
      node = node->right;
 
480
 
 
481
  return node;
 
482
}
 
483
 
 
484
/* Return the immediate successor KEY, or NULL if there is no
 
485
   successor.  KEY need not be present in the tree.  */
 
486
 
 
487
splay_tree_node
 
488
splay_tree_successor (sp, key)
 
489
     splay_tree sp;
 
490
     splay_tree_key key;
 
491
{
 
492
  int comparison;
 
493
  splay_tree_node node;
 
494
 
 
495
  /* If the tree is empty, there is certainly no successor.  */
 
496
  if (!sp->root)
 
497
    return NULL;
 
498
 
 
499
  /* Splay the tree around KEY.  That will leave either the KEY
 
500
     itself, its predecessor, or its successor at the root.  */
 
501
  splay_tree_splay (sp, key);
 
502
  comparison = (*sp->comp)(sp->root->key, key);
 
503
 
 
504
  /* If the successor is at the root, just return it.  */
 
505
  if (comparison > 0)
 
506
    return sp->root;
 
507
 
 
508
  /* Otherwise, find the leftmost element of the right subtree.  */
 
509
  node = sp->root->right;
 
510
  if (node)
 
511
    while (node->left)
 
512
      node = node->left;
 
513
 
 
514
  return node;
 
515
}
 
516
 
369
517
/* Call FN, passing it the DATA, for every node in SP, following an
370
518
   in-order traversal.  If FN every returns a non-zero value, the
371
519
   iteration ceases immediately, and the value is returned.