Warning: That file was not part of the compilation database. It may have many parsing errors.
1 | /* A typesafe wrapper around libiberty's splay-tree.h. |
---|---|
2 | Copyright (C) 2015-2017 Free Software Foundation, Inc. |
3 | |
4 | This file is part of GCC. |
5 | |
6 | GCC is free software; you can redistribute it and/or modify it under |
7 | the terms of the GNU General Public License as published by the Free |
8 | Software Foundation; either version 3, or (at your option) any later |
9 | version. |
10 | |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | for more details. |
15 | |
16 | You should have received a copy of the GNU General Public License |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ |
19 | |
20 | #ifndef GCC_TYPED_SPLAY_TREE_H |
21 | #define GCC_TYPED_SPLAY_TREE_H |
22 | |
23 | #include "splay-tree.h" |
24 | |
25 | /* Typesafe wrapper around libiberty's splay-tree.h. */ |
26 | template <typename KEY_TYPE, typename VALUE_TYPE> |
27 | class typed_splay_tree |
28 | { |
29 | public: |
30 | typedef KEY_TYPE key_type; |
31 | typedef VALUE_TYPE value_type; |
32 | |
33 | typedef int (*compare_fn) (key_type, key_type); |
34 | typedef void (*delete_key_fn) (key_type); |
35 | typedef void (*delete_value_fn) (value_type); |
36 | typedef int (*foreach_fn) (key_type, value_type, void *); |
37 | |
38 | typed_splay_tree (compare_fn, |
39 | delete_key_fn, |
40 | delete_value_fn); |
41 | ~typed_splay_tree (); |
42 | |
43 | value_type lookup (key_type k); |
44 | value_type predecessor (key_type k); |
45 | value_type successor (key_type k); |
46 | void insert (key_type k, value_type v); |
47 | value_type max (); |
48 | value_type min (); |
49 | int foreach (foreach_fn, void *); |
50 | |
51 | private: |
52 | /* Helper type for typed_splay_tree::foreach. */ |
53 | struct closure |
54 | { |
55 | closure (foreach_fn outer_cb, void *outer_user_data) |
56 | : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {} |
57 | |
58 | foreach_fn m_outer_cb; |
59 | void *m_outer_user_data; |
60 | }; |
61 | |
62 | static int inner_foreach_fn (splay_tree_node node, void *user_data); |
63 | |
64 | static value_type node_to_value (splay_tree_node node); |
65 | |
66 | private: |
67 | ::splay_tree m_inner; |
68 | }; |
69 | |
70 | /* Constructor for typed_splay_tree <K, V>. */ |
71 | |
72 | template <typename KEY_TYPE, typename VALUE_TYPE> |
73 | inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |
74 | typed_splay_tree (compare_fn compare_fn, |
75 | delete_key_fn delete_key_fn, |
76 | delete_value_fn delete_value_fn) |
77 | { |
78 | m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn, |
79 | (splay_tree_delete_key_fn)delete_key_fn, |
80 | (splay_tree_delete_value_fn)delete_value_fn); |
81 | } |
82 | |
83 | /* Destructor for typed_splay_tree <K, V>. */ |
84 | |
85 | template <typename KEY_TYPE, typename VALUE_TYPE> |
86 | inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |
87 | ~typed_splay_tree () |
88 | { |
89 | splay_tree_delete (m_inner); |
90 | } |
91 | |
92 | /* Lookup KEY, returning a value if present, and NULL |
93 | otherwise. */ |
94 | |
95 | template <typename KEY_TYPE, typename VALUE_TYPE> |
96 | inline VALUE_TYPE |
97 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) |
98 | { |
99 | splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key); |
100 | return node_to_value (node); |
101 | } |
102 | |
103 | /* Return the immediate predecessor of KEY, or NULL if there is no |
104 | predecessor. KEY need not be present in the tree. */ |
105 | |
106 | template <typename KEY_TYPE, typename VALUE_TYPE> |
107 | inline VALUE_TYPE |
108 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) |
109 | { |
110 | splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key); |
111 | return node_to_value (node); |
112 | } |
113 | |
114 | /* Return the immediate successor of KEY, or NULL if there is no |
115 | successor. KEY need not be present in the tree. */ |
116 | |
117 | template <typename KEY_TYPE, typename VALUE_TYPE> |
118 | inline VALUE_TYPE |
119 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k) |
120 | { |
121 | splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k); |
122 | return node_to_value (node); |
123 | } |
124 | |
125 | /* Insert a new node (associating KEY with VALUE). If a |
126 | previous node with the indicated KEY exists, its data is replaced |
127 | with the new value. */ |
128 | |
129 | template <typename KEY_TYPE, typename VALUE_TYPE> |
130 | inline void |
131 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, |
132 | value_type value) |
133 | { |
134 | splay_tree_insert (m_inner, |
135 | (splay_tree_key)key, |
136 | (splay_tree_value)value); |
137 | } |
138 | |
139 | /* Get the value with maximal key. */ |
140 | |
141 | template <typename KEY_TYPE, typename VALUE_TYPE> |
142 | inline VALUE_TYPE |
143 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () |
144 | { |
145 | return node_to_value (splay_tree_max (m_inner)); |
146 | } |
147 | |
148 | /* Get the value with minimal key. */ |
149 | |
150 | template <typename KEY_TYPE, typename VALUE_TYPE> |
151 | inline VALUE_TYPE |
152 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () |
153 | { |
154 | return node_to_value (splay_tree_min (m_inner)); |
155 | } |
156 | |
157 | /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, |
158 | following an in-order traversal. If OUTER_CB ever returns a non-zero |
159 | value, the iteration ceases immediately, and the value is returned. |
160 | Otherwise, this function returns 0. */ |
161 | |
162 | template <typename KEY_TYPE, typename VALUE_TYPE> |
163 | inline int |
164 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb, |
165 | void *outer_user_data) |
166 | { |
167 | closure c (outer_cb, outer_user_data); |
168 | |
169 | return splay_tree_foreach (m_inner, inner_foreach_fn, &c); |
170 | } |
171 | |
172 | /* Helper function for typed_splay_tree::foreach. */ |
173 | |
174 | template <typename KEY_TYPE, typename VALUE_TYPE> |
175 | int |
176 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node, |
177 | void *user_data) |
178 | { |
179 | closure *c = (closure *)user_data; |
180 | |
181 | return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value, |
182 | c->m_outer_user_data); |
183 | } |
184 | |
185 | /* Internal function for converting from splay_tree_node to |
186 | VALUE_TYPE. */ |
187 | template <typename KEY_TYPE, typename VALUE_TYPE> |
188 | inline VALUE_TYPE |
189 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) |
190 | { |
191 | if (node) |
192 | return (value_type)node->value; |
193 | else |
194 | return 0; |
195 | } |
196 | |
197 | #endif /* GCC_TYPED_SPLAY_TREE_H */ |
198 |
Warning: That file was not part of the compilation database. It may have many parsing errors.