Back to index

cell-binutils  2.17cvs20070401
splay-tree.h
Go to the documentation of this file.
00001 /* A splay-tree datatype.  
00002    Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc.
00003    Contributed by Mark Mitchell (mark@markmitchell.com).
00004 
00005 This file is part of GCC.
00006    
00007 GCC is free software; you can redistribute it and/or modify it
00008 under the terms of the GNU General Public License as published by
00009 the Free Software Foundation; either version 2, or (at your option)
00010 any later version.
00011 
00012 GCC is distributed in the hope that it will be useful, but
00013 WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 General Public License for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with GCC; see the file COPYING.  If not, write to
00019 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
00020 Boston, MA 02110-1301, USA.  */
00021 
00022 /* For an easily readable description of splay-trees, see:
00023 
00024      Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
00025      Algorithms.  Harper-Collins, Inc.  1991.  
00026 
00027    The major feature of splay trees is that all basic tree operations
00028    are amortized O(log n) time for a tree with n nodes.  */
00029 
00030 #ifndef _SPLAY_TREE_H
00031 #define _SPLAY_TREE_H
00032 
00033 #ifdef __cplusplus
00034 extern "C" {
00035 #endif /* __cplusplus */
00036 
00037 #include "ansidecl.h"
00038 
00039 #ifndef GTY
00040 #define GTY(X)
00041 #endif
00042 
00043 /* Use typedefs for the key and data types to facilitate changing
00044    these types, if necessary.  These types should be sufficiently wide
00045    that any pointer or scalar can be cast to these types, and then
00046    cast back, without loss of precision.  */
00047 typedef unsigned long int splay_tree_key;
00048 typedef unsigned long int splay_tree_value;
00049 
00050 /* Forward declaration for a node in the tree.  */
00051 typedef struct splay_tree_node_s *splay_tree_node;
00052 
00053 /* The type of a function which compares two splay-tree keys.  The
00054    function should return values as for qsort.  */
00055 typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key);
00056 
00057 /* The type of a function used to deallocate any resources associated
00058    with the key.  */
00059 typedef void (*splay_tree_delete_key_fn) (splay_tree_key);
00060 
00061 /* The type of a function used to deallocate any resources associated
00062    with the value.  */
00063 typedef void (*splay_tree_delete_value_fn) (splay_tree_value);
00064 
00065 /* The type of a function used to iterate over the tree.  */
00066 typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*);
00067 
00068 /* The type of a function used to allocate memory for tree root and
00069    node structures.  The first argument is the number of bytes needed;
00070    the second is a data pointer the splay tree functions pass through
00071    to the allocator.  This function must never return zero.  */
00072 typedef void *(*splay_tree_allocate_fn) (int, void *);
00073 
00074 /* The type of a function used to free memory allocated using the
00075    corresponding splay_tree_allocate_fn.  The first argument is the
00076    memory to be freed; the latter is a data pointer the splay tree
00077    functions pass through to the freer.  */
00078 typedef void (*splay_tree_deallocate_fn) (void *, void *);
00079 
00080 /* The nodes in the splay tree.  */
00081 struct splay_tree_node_s GTY(())
00082 {
00083   /* The key.  */
00084   splay_tree_key GTY ((use_param1)) key;
00085 
00086   /* The value.  */
00087   splay_tree_value GTY ((use_param2)) value;
00088 
00089   /* The left and right children, respectively.  */
00090   splay_tree_node GTY ((use_params)) left;
00091   splay_tree_node GTY ((use_params)) right;
00092 };
00093 
00094 /* The splay tree itself.  */
00095 struct splay_tree_s GTY(())
00096 {
00097   /* The root of the tree.  */
00098   splay_tree_node GTY ((use_params)) root;
00099 
00100   /* The comparision function.  */
00101   splay_tree_compare_fn comp;
00102 
00103   /* The deallocate-key function.  NULL if no cleanup is necessary.  */
00104   splay_tree_delete_key_fn delete_key;
00105 
00106   /* The deallocate-value function.  NULL if no cleanup is necessary.  */
00107   splay_tree_delete_value_fn delete_value;
00108 
00109   /* Allocate/free functions, and a data pointer to pass to them.  */
00110   splay_tree_allocate_fn allocate;
00111   splay_tree_deallocate_fn deallocate;
00112   void * GTY((skip)) allocate_data;
00113 
00114 };
00115 typedef struct splay_tree_s *splay_tree;
00116 
00117 extern splay_tree splay_tree_new        (splay_tree_compare_fn,
00118                                          splay_tree_delete_key_fn,
00119                                          splay_tree_delete_value_fn);
00120 extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn,
00121                                                  splay_tree_delete_key_fn,
00122                                            splay_tree_delete_value_fn,
00123                                                  splay_tree_allocate_fn,
00124                                                  splay_tree_deallocate_fn,
00125                                                  void *);
00126 extern void splay_tree_delete           (splay_tree);
00127 extern splay_tree_node splay_tree_insert (splay_tree,
00128                                           splay_tree_key,
00129                                           splay_tree_value);
00130 extern void splay_tree_remove      (splay_tree, splay_tree_key);
00131 extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
00132 extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
00133 extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
00134 extern splay_tree_node splay_tree_max (splay_tree);
00135 extern splay_tree_node splay_tree_min (splay_tree);
00136 extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*);
00137 extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key);
00138 extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key);
00139                                           
00140 #ifdef __cplusplus
00141 }
00142 #endif /* __cplusplus */
00143 
00144 #endif /* _SPLAY_TREE_H */