]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/ext/pb_assoc/detail/splay_tree_/splay_tree_.hpp
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
* typeck.c (build_modify_expr): Tidy diagnostic message.
[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_assoc / detail / splay_tree_ / splay_tree_.hpp
CommitLineData
fd1e1726
BK		 1// -*- C++ -*-
2
3// Copyright (C) 2005 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING. If not, write to the Free
83f51799 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
fd1e1726
BK		 19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction. Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License. This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
32// Permission to use, copy, modify, sell, and distribute this software
33// is hereby granted without fee, provided that the above copyright
34// notice appears in all copies, and that both that copyright notice and
35// this permission notice appear in supporting documentation. None of
36// the above authors, nor IBM Haifa Research Laboratories, make any
37// representation about the suitability of this software for any
38// purpose. It is provided "as is" without express or implied warranty.
39
40/**
41 * @file splay_tree_.hpp
42 * Contains an implementation class for splay_tree_.
43 */
44
45#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
46#ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
47#define BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
48#include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
49#endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
50#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
51
52#ifdef PB_ASSOC_DATA_FALSE_INDICATOR
53#ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
54#define BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
55#include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
56#endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
57#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
58
59#include <ext/pb_assoc/detail/splay_tree_/node.hpp>
60#include <utility>
61#include <vector>
62#include <assert.h>
63
64namespace pb_assoc
65{
66
67 namespace detail
68 {
69
70#ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
71#define PB_ASSOC_DBG_ASSERT(X) assert(X)
72#define PB_ASSOC_DBG_VERIFY(X) assert(X)
73#define PB_ASSOC_DBG_ONLY(X) X
74#else // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
75#define PB_ASSOC_DBG_ASSERT(X)
76#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
77#define PB_ASSOC_DBG_ONLY(X) ;
78#endif // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
79
80#define PB_ASSOC_CLASS_T_DEC \
81 template< \
82 typename Key, \
83 typename Data, \
84 class Cmp_Fn, \
85 class Allocator, \
86 class Node_Updator>
87
88#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
89#define PB_ASSOC_CLASS_NAME \
90 splay_tree_data_
91#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
92
93#ifdef PB_ASSOC_DATA_FALSE_INDICATOR
94#define PB_ASSOC_CLASS_NAME \
95 splay_tree_no_data_
96#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
97
98#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
99#define PB_ASSOC_BASE_CLASS_NAME \
100 bin_search_tree_data_
101#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
102
103#ifdef PB_ASSOC_DATA_FALSE_INDICATOR
104#define PB_ASSOC_BASE_CLASS_NAME \
105 bin_search_tree_no_data_
106#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
107
108#define PB_ASSOC_CLASS_C_DEC \
109 PB_ASSOC_CLASS_NAME< \
110 Key, \
111 Data, \
112 Cmp_Fn, \
113 Allocator, \
114 Node_Updator>
115
116#define PB_ASSOC_TYPES_TRAITS_C_DEC \
117 types_traits< \
118 Key, \
119 Data, \
120 Allocator>
121
122#define PB_ASSOC_NODE_C_DEC \
123 splay_tree_node_< \
124 typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type, \
125 Allocator>
126
127#define PB_ASSOC_BASE_C_DEC \
128 PB_ASSOC_BASE_CLASS_NAME< \
129 Key, \
130 Data, \
131 PB_ASSOC_NODE_C_DEC, \
132 Cmp_Fn, \
133 Allocator, \
134 Node_Updator>
135
136 template<typename Key,
137 typename Data,
138 class Cmp_Fn,
139 class Allocator,
140 class Node_Updator>
141 struct PB_ASSOC_CLASS_NAME : public PB_ASSOC_BASE_C_DEC
142 {
143
144 protected:
145
146 typedef typename Allocator::size_type size_type;
147
148 typedef
149 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
150 const_key_reference;
151
152 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
153
154 typedef
155 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
156 data_reference;
157
158 typedef
159 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
160 const_data_reference;
161
162 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
163
164 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
165
166 typedef
167 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
168 const_pointer;
169
170 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
171
172 typedef
173 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
174 const_reference;
175
176 typedef typename PB_ASSOC_BASE_C_DEC::node_pointer node_pointer;
177
178 typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
179
180 typedef
181 typename PB_ASSOC_BASE_C_DEC::const_iterator
182 const_find_iterator;
183
184 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
185
186 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
187
188 typedef
189 typename PB_ASSOC_BASE_C_DEC::reverse_iterator
190 reverse_iterator;
191
192 typedef
193 typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
194 const_reverse_iterator;
195
196 protected:
197
198 PB_ASSOC_CLASS_NAME();
199
200 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
201
202 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
203
204 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
205
206 void
207 swap(PB_ASSOC_CLASS_C_DEC& r_other);
208
209 template<class It>
210 void
211 copy_from_range(It first_it, It last_it);
212
213 void
214 initialize();
215
216 inline std::pair<find_iterator, bool>
217 insert(const_reference r_value);
218
219#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
220 inline data_reference
221 subscript_imp(const_key_reference r_key);
222#endif // #ifdef PB_ASSOC_DATA_TRUE
223
224 inline find_iterator
225 lower_bound(const_key_reference r_key);
226
227 inline const_find_iterator
228 lower_bound(const_key_reference r_key) const;
229
230 inline find_iterator
231 upper_bound(const_key_reference r_key);
232
233 inline const_find_iterator
234 upper_bound(const_key_reference r_key) const;
235
236 inline find_iterator
237 find(const_key_reference r_key);
238
239 inline const_find_iterator
240 find(const_key_reference r_key) const;
241
242 inline size_type
243 erase(const_key_reference r_key);
244
245 inline const_iterator
246 erase(const_iterator it);
247
248#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
249 inline iterator
250 erase(iterator it);
251#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
252
253 inline const_reverse_iterator
254 erase(const_reverse_iterator it);
255
256#ifdef PB_ASSOC_DATA_TRUE_INDICATOR
257 inline reverse_iterator
258 erase(reverse_iterator it);
259#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
260
261 template<class Pred>
262 inline size_type
263 erase_if(Pred pred);
264
265 inline node_pointer
266 leftmost(node_pointer p_nd);
267
268 void
269 join(PB_ASSOC_CLASS_C_DEC& r_other);
270
271 void
272 split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
273
274#ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
275
276 virtual void
277 assert_valid() const;
278
279 void
280 assert_special_imp(const node_pointer p_nd) const;
281
282#endif // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
283
284 private:
285
286 void
287 splay(node_pointer p_nd);
288
289 inline void
290 splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
291
292 inline void
293 splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
294
295 inline void
296 splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
297
298 inline void
299 splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
300
301 inline void
302 splay_zz_start(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
303
304 inline void
305 splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
306
307 void
308 erase_node(node_pointer p_nd);
309
310 };
311
312#include <ext/pb_assoc/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
313#include <ext/pb_assoc/detail/splay_tree_/info_fn_imps.hpp>
314#include <ext/pb_assoc/detail/splay_tree_/insert_fn_imps.hpp>
315#include <ext/pb_assoc/detail/splay_tree_/splay_fn_imps.hpp>
316#include <ext/pb_assoc/detail/splay_tree_/erase_fn_imps.hpp>
317#include <ext/pb_assoc/detail/splay_tree_/find_fn_imps.hpp>
318#include <ext/pb_assoc/detail/splay_tree_/debug_fn_imps.hpp>
319#include <ext/pb_assoc/detail/splay_tree_/split_join_fn_imps.hpp>
320
321#undef PB_ASSOC_CLASS_T_DEC
322
323#undef PB_ASSOC_CLASS_C_DEC
324
325#undef PB_ASSOC_CLASS_NAME
326
327#undef PB_ASSOC_TYPES_TRAITS_C_DEC
328
329#undef PB_ASSOC_BASE_CLASS_NAME
330
331#undef PB_ASSOC_NODE_C_DEC
332
333#undef PB_ASSOC_BASE_C_DEC
334
335#undef PB_ASSOC_DBG_ASSERT
336#undef PB_ASSOC_DBG_VERIFY
337#undef PB_ASSOC_DBG_ONLY
338
339 } // namespace detail
340
341} // namespace pb_assoc
342
Mirror of https://gcc.gnu.org/git/gcc.git