Back to index

cell-binutils  2.17cvs20070401
Defines | Functions
splay-tree.c File Reference
#include <stdio.h>
#include "libiberty.h"
#include "splay-tree.h"

Go to the source code of this file.

Defines

#define KDEL(x)   if (sp->delete_key) (*sp->delete_key)(x);
#define VDEL(x)   if (sp->delete_value) (*sp->delete_value)(x);

Functions

static void splay_tree_delete_helper (splay_tree, splay_tree_node)
static void rotate_left (splay_tree_node *, splay_tree_node, splay_tree_node)
static void rotate_right (splay_tree_node *, splay_tree_node, splay_tree_node)
static void splay_tree_splay (splay_tree, splay_tree_key)
static int splay_tree_foreach_helper (splay_tree, splay_tree_node, splay_tree_foreach_fn, void *)
static void * splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED)
static void splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED)
splay_tree splay_tree_new (splay_tree_compare_fn compare_fn, splay_tree_delete_key_fn delete_key_fn, splay_tree_delete_value_fn delete_value_fn)
splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, splay_tree_delete_key_fn delete_key_fn, splay_tree_delete_value_fn delete_value_fn, splay_tree_allocate_fn allocate_fn, splay_tree_deallocate_fn deallocate_fn, void *allocate_data)
void splay_tree_delete (splay_tree sp)
splay_tree_node splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
void splay_tree_remove (splay_tree sp, splay_tree_key key)
splay_tree_node splay_tree_lookup (splay_tree sp, splay_tree_key key)
splay_tree_node splay_tree_max (splay_tree sp)
splay_tree_node splay_tree_min (splay_tree sp)
splay_tree_node splay_tree_predecessor (splay_tree sp, splay_tree_key key)
splay_tree_node splay_tree_successor (splay_tree sp, splay_tree_key key)
int splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
int splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2)
int splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)

Define Documentation

#define KDEL (   x)    if (sp->delete_key) (*sp->delete_key)(x);
#define VDEL (   x)    if (sp->delete_value) (*sp->delete_value)(x);

Function Documentation

static void rotate_left ( splay_tree_node pp,
splay_tree_node  p,
splay_tree_node  n 
) [inline, static]

Definition at line 113 of file splay-tree.c.

{
  splay_tree_node tmp;
  tmp = n->right;
  n->right = p;
  p->left = tmp;
  *pp = n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void rotate_right ( splay_tree_node pp,
splay_tree_node  p,
splay_tree_node  n 
) [inline, static]

Definition at line 126 of file splay-tree.c.

{
  splay_tree_node tmp;
  tmp = n->left;
  n->left = p;
  p->right = tmp;
  *pp = n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 505 of file splay-tree.c.

{
  if ((int) k1 < (int) k2)
    return -1;
  else if ((int) k1 > (int) k2)
    return 1;
  else 
    return 0;
}

Definition at line 518 of file splay-tree.c.

{
  if ((char*) k1 < (char*) k2)
    return -1;
  else if ((char*) k1 > (char*) k2)
    return 1;
  else 
    return 0;
}

Definition at line 284 of file splay-tree.c.

{
  splay_tree_delete_helper (sp, sp->root);
  (*sp->deallocate) ((char*) sp, sp->allocate_data);
}

Here is the call graph for this function:

static void splay_tree_delete_helper ( splay_tree  sp,
splay_tree_node  node 
) [static]

Definition at line 52 of file splay-tree.c.

{
  splay_tree_node pending = 0;
  splay_tree_node active = 0;

  if (!node)
    return;

#define KDEL(x)  if (sp->delete_key) (*sp->delete_key)(x);
#define VDEL(x)  if (sp->delete_value) (*sp->delete_value)(x);

  KDEL (node->key);
  VDEL (node->value);

  /* We use the "key" field to hold the "next" pointer.  */
  node->key = (splay_tree_key)pending;
  pending = (splay_tree_node)node;

  /* Now, keep processing the pending list until there aren't any
     more.  This is a little more complicated than just recursing, but
     it doesn't toast the stack for large trees.  */

  while (pending)
    {
      active = pending;
      pending = 0;
      while (active)
       {
         splay_tree_node temp;

         /* active points to a node which has its key and value
            deallocated, we just need to process left and right.  */

         if (active->left)
           {
             KDEL (active->left->key);
             VDEL (active->left->value);
             active->left->key = (splay_tree_key)pending;
             pending = (splay_tree_node)(active->left);
           }
         if (active->right)
           {
             KDEL (active->right->key);
             VDEL (active->right->value);
             active->right->key = (splay_tree_key)pending;
             pending = (splay_tree_node)(active->right);
           }

         temp = active;
         active = (splay_tree_node)(temp->key);
         (*sp->deallocate) ((char*) temp, sp->allocate_data);
       }
    }
#undef KDEL
#undef VDEL
}

Here is the caller graph for this function:

int splay_tree_foreach ( splay_tree  sp,
splay_tree_foreach_fn  fn,
void *  data 
)

Definition at line 497 of file splay-tree.c.

{
  return splay_tree_foreach_helper (sp, sp->root, fn, data);
}

Here is the call graph for this function:

static int splay_tree_foreach_helper ( splay_tree  sp,
splay_tree_node  node,
splay_tree_foreach_fn  fn,
void *  data 
) [static]

Definition at line 206 of file splay-tree.c.

{
  int val;

  if (!node)
    return 0;

  val = splay_tree_foreach_helper (sp, node->left, fn, data);
  if (val)
    return val;

  val = (*fn)(node, data);
  if (val)
    return val;

  return splay_tree_foreach_helper (sp, node->right, fn, data);
}

Here is the caller graph for this function:

Definition at line 295 of file splay-tree.c.

{
  int comparison = 0;

  splay_tree_splay (sp, key);

  if (sp->root)
    comparison = (*sp->comp)(sp->root->key, key);

  if (sp->root && comparison == 0)
    {
      /* If the root of the tree already has the indicated KEY, just
        replace the value with VALUE.  */
      if (sp->delete_value)
       (*sp->delete_value)(sp->root->value);
      sp->root->value = value;
    } 
  else 
    {
      /* Create a new node, and insert it at the root.  */
      splay_tree_node node;
      
      node = ((splay_tree_node)
              (*sp->allocate) (sizeof (struct splay_tree_node_s),
                               sp->allocate_data));
      node->key = key;
      node->value = value;
      
      if (!sp->root)
       node->left = node->right = 0;
      else if (comparison < 0)
       {
         node->left = sp->root;
         node->right = node->left->right;
         node->left->right = 0;
       }
      else
       {
         node->right = sp->root;
         node->left = node->right->left;
         node->right->left = 0;
       }

      sp->root = node;
    }

  return sp->root;
}

Here is the call graph for this function:

Definition at line 387 of file splay-tree.c.

{
  splay_tree_splay (sp, key);

  if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
    return sp->root;
  else
    return 0;
}

Here is the call graph for this function:

Definition at line 400 of file splay-tree.c.

{
  splay_tree_node n = sp->root;

  if (!n)
    return NULL;

  while (n->right)
    n = n->right;

  return n;
}

Definition at line 416 of file splay-tree.c.

{
  splay_tree_node n = sp->root;

  if (!n)
    return NULL;

  while (n->left)
    n = n->left;

  return n;
}

Definition at line 246 of file splay-tree.c.

{
  return (splay_tree_new_with_allocator
          (compare_fn, delete_key_fn, delete_value_fn,
           splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
}

Here is the call graph for this function:

splay_tree splay_tree_new_with_allocator ( splay_tree_compare_fn  compare_fn,
splay_tree_delete_key_fn  delete_key_fn,
splay_tree_delete_value_fn  delete_value_fn,
splay_tree_allocate_fn  allocate_fn,
splay_tree_deallocate_fn  deallocate_fn,
void *  allocate_data 
)

Definition at line 261 of file splay-tree.c.

{
  splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
                                               allocate_data);
  sp->root = 0;
  sp->comp = compare_fn;
  sp->delete_key = delete_key_fn;
  sp->delete_value = delete_value_fn;
  sp->allocate = allocate_fn;
  sp->deallocate = deallocate_fn;
  sp->allocate_data = allocate_data;

  return sp;
}

Here is the caller graph for this function:

Definition at line 433 of file splay-tree.c.

{
  int comparison;
  splay_tree_node node;

  /* If the tree is empty, there is certainly no predecessor.  */
  if (!sp->root)
    return NULL;

  /* Splay the tree around KEY.  That will leave either the KEY
     itself, its predecessor, or its successor at the root.  */
  splay_tree_splay (sp, key);
  comparison = (*sp->comp)(sp->root->key, key);

  /* If the predecessor is at the root, just return it.  */
  if (comparison < 0)
    return sp->root;

  /* Otherwise, find the rightmost element of the left subtree.  */
  node = sp->root->left;
  if (node)
    while (node->right)
      node = node->right;

  return node;
}

Here is the call graph for this function:

Definition at line 347 of file splay-tree.c.

{
  splay_tree_splay (sp, key);

  if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
    {
      splay_tree_node left, right;

      left = sp->root->left;
      right = sp->root->right;

      /* Delete the root node itself.  */
      if (sp->delete_value)
       (*sp->delete_value) (sp->root->value);
      (*sp->deallocate) (sp->root, sp->allocate_data);

      /* One of the children is now the root.  Doesn't matter much
        which, so long as we preserve the properties of the tree.  */
      if (left)
       {
         sp->root = left;

         /* If there was a right child as well, hang it off the 
            right-most leaf of the left child.  */
         if (right)
           {
             while (left->right)
              left = left->right;
             left->right = right;
           }
       }
      else
       sp->root = right;
    }
}

Here is the call graph for this function:

static void splay_tree_splay ( splay_tree  sp,
splay_tree_key  key 
) [static]

Definition at line 138 of file splay-tree.c.

{
  if (sp->root == 0)
    return;

  do {
    int cmp1, cmp2;
    splay_tree_node n, c;

    n = sp->root;
    cmp1 = (*sp->comp) (key, n->key);

    /* Found.  */
    if (cmp1 == 0)
      return;

    /* Left or right?  If no child, then we're done.  */
    if (cmp1 < 0)
      c = n->left;
    else
      c = n->right;
    if (!c)
      return;

    /* Next one left or right?  If found or no child, we're done
       after one rotation.  */
    cmp2 = (*sp->comp) (key, c->key);
    if (cmp2 == 0
        || (cmp2 < 0 && !c->left)
        || (cmp2 > 0 && !c->right))
      {
       if (cmp1 < 0)
         rotate_left (&sp->root, n, c);
       else
         rotate_right (&sp->root, n, c);
        return;
      }

    /* Now we have the four cases of double-rotation.  */
    if (cmp1 < 0 && cmp2 < 0)
      {
       rotate_left (&n->left, c, c->left);
       rotate_left (&sp->root, n, n->left);
      }
    else if (cmp1 > 0 && cmp2 > 0)
      {
       rotate_right (&n->right, c, c->right);
       rotate_right (&sp->root, n, n->right);
      }
    else if (cmp1 < 0 && cmp2 > 0)
      {
       rotate_right (&n->left, c, c->right);
       rotate_left (&sp->root, n, n->left);
      }
    else if (cmp1 > 0 && cmp2 < 0)
      {
       rotate_left (&n->right, c, c->left);
       rotate_right (&sp->root, n, n->right);
      }
  } while (1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 464 of file splay-tree.c.

{
  int comparison;
  splay_tree_node node;

  /* If the tree is empty, there is certainly no successor.  */
  if (!sp->root)
    return NULL;

  /* Splay the tree around KEY.  That will leave either the KEY
     itself, its predecessor, or its successor at the root.  */
  splay_tree_splay (sp, key);
  comparison = (*sp->comp)(sp->root->key, key);

  /* If the successor is at the root, just return it.  */
  if (comparison > 0)
    return sp->root;

  /* Otherwise, find the leftmost element of the right subtree.  */
  node = sp->root->right;
  if (node)
    while (node->left)
      node = node->left;

  return node;
}

Here is the call graph for this function:

static void* splay_tree_xmalloc_allocate ( int  size,
void *data  ATTRIBUTE_UNUSED 
) [static]

Definition at line 228 of file splay-tree.c.

{
  return (void *) xmalloc (size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void splay_tree_xmalloc_deallocate ( void *  object,
void *data  ATTRIBUTE_UNUSED 
) [static]

Definition at line 234 of file splay-tree.c.

{
  free (object);
}

Here is the call graph for this function:

Here is the caller graph for this function: