Mercurial > hg > CbC > CbC_gcc
annotate include/splay-tree.h @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | 77e2b8dfacca |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* A splay-tree datatype. |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright 1998, 1999, 2000, 2002, 2005, 2007, 2009, 2010 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Free Software Foundation, Inc. |
| 0 | 4 Contributed by Mark Mitchell (mark@markmitchell.com). |
| 5 | |
| 6 This file is part of GCC. | |
| 7 | |
| 8 GCC is free software; you can redistribute it and/or modify it | |
| 9 under the terms of the GNU General Public License as published by | |
| 10 the Free Software Foundation; either version 2, or (at your option) | |
| 11 any later version. | |
| 12 | |
| 13 GCC is distributed in the hope that it will be useful, but | |
| 14 WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 16 General Public License for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with GCC; see the file COPYING. If not, write to | |
| 20 the Free Software Foundation, 51 Franklin Street - Fifth Floor, | |
| 21 Boston, MA 02110-1301, USA. */ | |
| 22 | |
| 23 /* For an easily readable description of splay-trees, see: | |
| 24 | |
| 25 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their | |
| 26 Algorithms. Harper-Collins, Inc. 1991. | |
| 27 | |
| 28 The major feature of splay trees is that all basic tree operations | |
| 29 are amortized O(log n) time for a tree with n nodes. */ | |
| 30 | |
| 31 #ifndef _SPLAY_TREE_H | |
| 32 #define _SPLAY_TREE_H | |
| 33 | |
| 34 #ifdef __cplusplus | |
| 35 extern "C" { | |
| 36 #endif /* __cplusplus */ | |
| 37 | |
| 38 #include "ansidecl.h" | |
| 39 | |
| 40 #ifndef _WIN64 | |
| 41 typedef unsigned long int libi_uhostptr_t; | |
| 42 typedef long int libi_shostptr_t; | |
| 43 #else | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
44 #ifdef __GNUC__ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
45 __extension__ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
46 #endif |
| 0 | 47 typedef unsigned long long libi_uhostptr_t; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
48 #ifdef __GNUC__ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
49 __extension__ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
50 #endif |
| 0 | 51 typedef long long libi_shostptr_t; |
| 52 #endif | |
| 53 | |
| 54 #ifndef GTY | |
| 55 #define GTY(X) | |
| 56 #endif | |
| 57 | |
| 58 /* Use typedefs for the key and data types to facilitate changing | |
| 59 these types, if necessary. These types should be sufficiently wide | |
| 60 that any pointer or scalar can be cast to these types, and then | |
| 61 cast back, without loss of precision. */ | |
| 62 typedef libi_uhostptr_t splay_tree_key; | |
| 63 typedef libi_uhostptr_t splay_tree_value; | |
| 64 | |
| 65 /* Forward declaration for a node in the tree. */ | |
| 66 typedef struct splay_tree_node_s *splay_tree_node; | |
| 67 | |
| 68 /* The type of a function which compares two splay-tree keys. The | |
| 69 function should return values as for qsort. */ | |
| 70 typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); | |
| 71 | |
| 72 /* The type of a function used to deallocate any resources associated | |
| 73 with the key. */ | |
| 74 typedef void (*splay_tree_delete_key_fn) (splay_tree_key); | |
| 75 | |
| 76 /* The type of a function used to deallocate any resources associated | |
| 77 with the value. */ | |
| 78 typedef void (*splay_tree_delete_value_fn) (splay_tree_value); | |
| 79 | |
| 80 /* The type of a function used to iterate over the tree. */ | |
| 81 typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); | |
| 82 | |
| 83 /* The type of a function used to allocate memory for tree root and | |
| 84 node structures. The first argument is the number of bytes needed; | |
| 85 the second is a data pointer the splay tree functions pass through | |
| 86 to the allocator. This function must never return zero. */ | |
| 87 typedef void *(*splay_tree_allocate_fn) (int, void *); | |
| 88 | |
| 89 /* The type of a function used to free memory allocated using the | |
| 90 corresponding splay_tree_allocate_fn. The first argument is the | |
| 91 memory to be freed; the latter is a data pointer the splay tree | |
| 92 functions pass through to the freer. */ | |
| 93 typedef void (*splay_tree_deallocate_fn) (void *, void *); | |
| 94 | |
| 95 /* The nodes in the splay tree. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
96 struct GTY(()) splay_tree_node_s { |
| 0 | 97 /* The key. */ |
| 98 splay_tree_key GTY ((use_param1)) key; | |
| 99 | |
| 100 /* The value. */ | |
| 101 splay_tree_value GTY ((use_param2)) value; | |
| 102 | |
| 103 /* The left and right children, respectively. */ | |
| 104 splay_tree_node GTY ((use_params)) left; | |
| 105 splay_tree_node GTY ((use_params)) right; | |
| 106 }; | |
| 107 | |
| 108 /* The splay tree itself. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 struct GTY(()) splay_tree_s { |
| 0 | 110 /* The root of the tree. */ |
| 111 splay_tree_node GTY ((use_params)) root; | |
| 112 | |
| 113 /* The comparision function. */ | |
| 114 splay_tree_compare_fn comp; | |
| 115 | |
| 116 /* The deallocate-key function. NULL if no cleanup is necessary. */ | |
| 117 splay_tree_delete_key_fn delete_key; | |
| 118 | |
| 119 /* The deallocate-value function. NULL if no cleanup is necessary. */ | |
| 120 splay_tree_delete_value_fn delete_value; | |
| 121 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
122 /* Node allocate function. Takes allocate_data as a parameter. */ |
| 0 | 123 splay_tree_allocate_fn allocate; |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
124 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
125 /* Free function for nodes and trees. Takes allocate_data as a parameter. */ |
| 0 | 126 splay_tree_deallocate_fn deallocate; |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
127 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
128 /* Parameter for allocate/free functions. */ |
| 0 | 129 void * GTY((skip)) allocate_data; |
| 130 }; | |
| 131 | |
| 132 typedef struct splay_tree_s *splay_tree; | |
| 133 | |
| 134 extern splay_tree splay_tree_new (splay_tree_compare_fn, | |
| 135 splay_tree_delete_key_fn, | |
| 136 splay_tree_delete_value_fn); | |
| 137 extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, | |
| 138 splay_tree_delete_key_fn, | |
| 139 splay_tree_delete_value_fn, | |
| 140 splay_tree_allocate_fn, | |
| 141 splay_tree_deallocate_fn, | |
| 142 void *); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
143 extern splay_tree splay_tree_new_typed_alloc (splay_tree_compare_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
144 splay_tree_delete_key_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
145 splay_tree_delete_value_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
146 splay_tree_allocate_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
147 splay_tree_allocate_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
148 splay_tree_deallocate_fn, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
149 void *); |
| 0 | 150 extern void splay_tree_delete (splay_tree); |
| 151 extern splay_tree_node splay_tree_insert (splay_tree, | |
| 152 splay_tree_key, | |
| 153 splay_tree_value); | |
| 154 extern void splay_tree_remove (splay_tree, splay_tree_key); | |
| 155 extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); | |
| 156 extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); | |
| 157 extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); | |
| 158 extern splay_tree_node splay_tree_max (splay_tree); | |
| 159 extern splay_tree_node splay_tree_min (splay_tree); | |
| 160 extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); | |
| 161 extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); | |
| 162 extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); | |
| 163 | |
| 164 #ifdef __cplusplus | |
| 165 } | |
| 166 #endif /* __cplusplus */ | |
| 167 | |
| 168 #endif /* _SPLAY_TREE_H */ |