Mercurial > hg > CbC > CbC_gcc
annotate include/splay-tree.h @ 131:84e7813d76e9
gcc-8.2
| author | mir3636 |
|---|---|
| date | Thu, 25 Oct 2018 07:37:49 +0900 |
| parents | 04ced10e8804 |
| children | 1830386684a0 |
| rev | line source |
|---|---|
| 0 | 1 /* A splay-tree datatype. |
| 131 | 2 Copyright (C) 1998-2018 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 | |
| 61 with the key. */ | |
| 62 typedef void (*splay_tree_delete_key_fn) (splay_tree_key); | |
| 63 | |
| 64 /* The type of a function used to deallocate any resources associated | |
| 65 with the value. */ | |
| 66 typedef void (*splay_tree_delete_value_fn) (splay_tree_value); | |
| 67 | |
| 68 /* The type of a function used to iterate over the tree. */ | |
| 69 typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); | |
| 70 | |
| 71 /* The type of a function used to allocate memory for tree root and | |
| 72 node structures. The first argument is the number of bytes needed; | |
| 73 the second is a data pointer the splay tree functions pass through | |
| 74 to the allocator. This function must never return zero. */ | |
| 75 typedef void *(*splay_tree_allocate_fn) (int, void *); | |
| 76 | |
| 77 /* The type of a function used to free memory allocated using the | |
| 78 corresponding splay_tree_allocate_fn. The first argument is the | |
| 79 memory to be freed; the latter is a data pointer the splay tree | |
| 80 functions pass through to the freer. */ | |
| 81 typedef void (*splay_tree_deallocate_fn) (void *, void *); | |
| 82 | |
| 83 /* The nodes in the splay tree. */ | |
| 111 | 84 struct splay_tree_node_s { |
| 0 | 85 /* The key. */ |
| 111 | 86 splay_tree_key key; |
| 0 | 87 |
| 88 /* The value. */ | |
| 111 | 89 splay_tree_value value; |
| 0 | 90 |
| 91 /* The left and right children, respectively. */ | |
| 111 | 92 splay_tree_node left; |
| 93 splay_tree_node right; | |
| 0 | 94 }; |
| 95 | |
| 96 /* The splay tree itself. */ | |
| 111 | 97 struct splay_tree_s { |
| 0 | 98 /* The root of the tree. */ |
| 111 | 99 splay_tree_node root; |
| 0 | 100 |
| 101 /* The comparision function. */ | |
| 102 splay_tree_compare_fn comp; | |
| 103 | |
| 104 /* The deallocate-key function. NULL if no cleanup is necessary. */ | |
| 105 splay_tree_delete_key_fn delete_key; | |
| 106 | |
| 107 /* The deallocate-value function. NULL if no cleanup is necessary. */ | |
| 108 splay_tree_delete_value_fn delete_value; | |
| 109 | |
|
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
|
110 /* Node allocate function. Takes allocate_data as a parameter. */ |
| 0 | 111 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
|
112 |
|
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
|
113 /* Free function for nodes and trees. Takes allocate_data as a parameter. */ |
| 0 | 114 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
|
115 |
|
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
|
116 /* Parameter for allocate/free functions. */ |
| 111 | 117 void *allocate_data; |
| 0 | 118 }; |
| 119 | |
| 120 typedef struct splay_tree_s *splay_tree; | |
| 121 | |
| 122 extern splay_tree splay_tree_new (splay_tree_compare_fn, | |
| 123 splay_tree_delete_key_fn, | |
| 124 splay_tree_delete_value_fn); | |
| 125 extern splay_tree splay_tree_new_with_allocator (splay_tree_compare_fn, | |
| 126 splay_tree_delete_key_fn, | |
| 127 splay_tree_delete_value_fn, | |
| 128 splay_tree_allocate_fn, | |
| 129 splay_tree_deallocate_fn, | |
| 130 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
|
131 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
|
132 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
|
133 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
|
134 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
|
135 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
|
136 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
|
137 void *); |
| 0 | 138 extern void splay_tree_delete (splay_tree); |
| 139 extern splay_tree_node splay_tree_insert (splay_tree, | |
| 140 splay_tree_key, | |
| 141 splay_tree_value); | |
| 142 extern void splay_tree_remove (splay_tree, splay_tree_key); | |
| 143 extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key); | |
| 144 extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key); | |
| 145 extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key); | |
| 146 extern splay_tree_node splay_tree_max (splay_tree); | |
| 147 extern splay_tree_node splay_tree_min (splay_tree); | |
| 148 extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); | |
| 149 extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); | |
| 131 | 150 extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); |
| 151 extern int splay_tree_compare_strings (splay_tree_key, splay_tree_key); | |
| 152 extern void splay_tree_delete_pointers (splay_tree_value); | |
| 0 | 153 |
| 154 #ifdef __cplusplus | |
| 155 } | |
| 156 #endif /* __cplusplus */ | |
| 157 | |
| 158 #endif /* _SPLAY_TREE_H */ |