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