Back to index

cell-binutils  2.17cvs20070401
Defines | Typedefs | Functions
splay-tree.h File Reference
#include "ansidecl.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

#define GTY(X)

Typedefs

typedef unsigned long int splay_tree_key
typedef unsigned long int splay_tree_value
typedef struct splay_tree_node_s * splay_tree_node
typedef int(* splay_tree_compare_fn )(splay_tree_key, splay_tree_key)
typedef void(* splay_tree_delete_key_fn )(splay_tree_key)
typedef void(* splay_tree_delete_value_fn )(splay_tree_value)
typedef int(* splay_tree_foreach_fn )(splay_tree_node, void *)
typedef void *(* splay_tree_allocate_fn )(int, void *)
typedef void(* splay_tree_deallocate_fn )(void *, void *)
typedef struct splay_tree_s * splay_tree

Functions

struct splay_tree_node_s GTY (())
splay_tree splay_tree_new (splay_tree_compare_fn, splay_tree_delete_key_fn, splay_tree_delete_value_fn)
splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, splay_tree_delete_key_fn, splay_tree_delete_value_fn, splay_tree_allocate_fn, splay_tree_deallocate_fn, void *)
void splay_tree_delete (splay_tree)
splay_tree_node splay_tree_insert (splay_tree, splay_tree_key, splay_tree_value)
void splay_tree_remove (splay_tree, splay_tree_key)
splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key)
splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key)
splay_tree_node splay_tree_successor (splay_tree, splay_tree_key)
splay_tree_node splay_tree_max (splay_tree)
splay_tree_node splay_tree_min (splay_tree)
int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void *)
int splay_tree_compare_ints (splay_tree_key, splay_tree_key)
int splay_tree_compare_pointers (splay_tree_key, splay_tree_key)

Define Documentation

#define GTY (   X)

Definition at line 40 of file splay-tree.h.


Typedef Documentation

typedef struct splay_tree_s* splay_tree

Definition at line 115 of file splay-tree.h.

typedef void*(* splay_tree_allocate_fn)(int, void *)

Definition at line 72 of file splay-tree.h.

Definition at line 55 of file splay-tree.h.

typedef void(* splay_tree_deallocate_fn)(void *, void *)

Definition at line 78 of file splay-tree.h.

Definition at line 59 of file splay-tree.h.

Definition at line 63 of file splay-tree.h.

Definition at line 66 of file splay-tree.h.

Definition at line 47 of file splay-tree.h.

typedef struct splay_tree_node_s* splay_tree_node

Definition at line 51 of file splay-tree.h.

Definition at line 48 of file splay-tree.h.


Function Documentation

struct splay_tree_node_s GTY ( ()  ) [read]

Definition at line 81 of file splay-tree.h.

{
  /* The key.  */
  splay_tree_key GTY ((use_param1)) key;

  /* The value.  */
  splay_tree_value GTY ((use_param2)) value;

  /* The left and right children, respectively.  */
  splay_tree_node GTY ((use_params)) left;
  splay_tree_node GTY ((use_params)) right;
};

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:

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:

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:

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:

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: