cellbinutils
2.17cvs20070401

#include "ansidecl.h"
Go to the source code of this file.
Definition at line 40 of file splaytree.h.
typedef struct splay_tree_s* splay_tree 
Definition at line 115 of file splaytree.h.
typedef void*(* splay_tree_allocate_fn)(int, void *) 
Definition at line 72 of file splaytree.h.
typedef int(* splay_tree_compare_fn)(splay_tree_key, splay_tree_key) 
Definition at line 55 of file splaytree.h.
typedef void(* splay_tree_deallocate_fn)(void *, void *) 
Definition at line 78 of file splaytree.h.
typedef void(* splay_tree_delete_key_fn)(splay_tree_key) 
Definition at line 59 of file splaytree.h.
typedef void(* splay_tree_delete_value_fn)(splay_tree_value) 
Definition at line 63 of file splaytree.h.
typedef int(* splay_tree_foreach_fn)(splay_tree_node, void *) 
Definition at line 66 of file splaytree.h.
typedef unsigned long int splay_tree_key 
Definition at line 47 of file splaytree.h.
typedef struct splay_tree_node_s* splay_tree_node 
Definition at line 51 of file splaytree.h.
typedef unsigned long int splay_tree_value 
Definition at line 48 of file splaytree.h.
Definition at line 81 of file splaytree.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 splaytree.c.
Definition at line 518 of file splaytree.c.
void splay_tree_delete  (  splay_tree  ) 
int splay_tree_foreach  (  splay_tree  , 
splay_tree_foreach_fn  ,  
void *  
) 
Definition at line 497 of file splaytree.c.
{ return splay_tree_foreach_helper (sp, sp>root, fn, data); }
Definition at line 295 of file splaytree.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; }
Definition at line 387 of file splaytree.c.
{ splay_tree_splay (sp, key); if (sp>root && (*sp>comp)(sp>root>key, key) == 0) return sp>root; else return 0; }
Definition at line 400 of file splaytree.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 splaytree.c.
{ splay_tree_node n = sp>root; if (!n) return NULL; while (n>left) n = n>left; return n; }
splay_tree splay_tree_new  (  splay_tree_compare_fn  , 
splay_tree_delete_key_fn  ,  
splay_tree_delete_value_fn  
) 
Definition at line 246 of file splaytree.c.
{ return (splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn, splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); }
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 *  
) 
Definition at line 261 of file splaytree.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; }
Definition at line 433 of file splaytree.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; }
void splay_tree_remove  (  splay_tree  , 
splay_tree_key  
) 
Definition at line 347 of file splaytree.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 rightmost leaf of the left child. */ if (right) { while (left>right) left = left>right; left>right = right; } } else sp>root = right; } }
Definition at line 464 of file splaytree.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; }