]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
4ba851b5 | 3 | // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. |
4569a895 AT |
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 terms | |
7 | // of the GNU General Public License as published by the Free Software | |
8 | // Foundation; either version 2, or (at your option) any later | |
9 | // version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
32 | ||
33 | // Permission to use, copy, modify, sell, and distribute this software | |
34 | // is hereby granted without fee, provided that the above copyright | |
35 | // notice appears in all copies, and that both that copyright notice | |
36 | // and this permission notice appear in supporting documentation. None | |
37 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
38 | // representation about the suitability of this software for any | |
39 | // purpose. It is provided "as is" without express or implied | |
40 | // warranty. | |
47bea7b8 | 41 | |
4569a895 | 42 | /** |
551fe1a2 | 43 | * @file debug_map_base.hpp |
4569a895 AT |
44 | * Contains a debug-mode base for all maps. |
45 | */ | |
46 | ||
551fe1a2 BK |
47 | #ifndef PB_DS_DEBUG_MAP_BASE_HPP |
48 | #define PB_DS_DEBUG_MAP_BASE_HPP | |
4569a895 | 49 | |
47bea7b8 | 50 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 51 | |
4569a895 AT |
52 | #include <list> |
53 | #include <utility> | |
4ba851b5 | 54 | #include <cstdlib> |
a86151e1 | 55 | #include <ext/throw_allocator.h> |
47bea7b8 | 56 | #include <debug/debug.h> |
4569a895 | 57 | |
5e11f978 | 58 | namespace __gnu_pbds |
4569a895 | 59 | { |
4569a895 AT |
60 | namespace detail |
61 | { | |
551fe1a2 BK |
62 | // Need std::pair ostream extractor. |
63 | template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2> | |
64 | inline std::basic_ostream<_CharT, _Traits>& | |
65 | operator<<(std::basic_ostream<_CharT, _Traits>& __out, | |
66 | const std::pair<_Tp1, _Tp2>& p) | |
67 | { return (__out << '(' << p.first << ',' << p.second << ')'); } | |
4569a895 | 68 | |
47bea7b8 | 69 | #define PB_DS_CLASS_T_DEC \ |
4569a895 AT |
70 | template<typename Key, class Eq_Fn, typename Const_Key_Reference> |
71 | ||
47bea7b8 | 72 | #define PB_DS_CLASS_C_DEC \ |
551fe1a2 | 73 | debug_map_base<Key, Eq_Fn, Const_Key_Reference> |
4569a895 AT |
74 | |
75 | template<typename Key, class Eq_Fn, typename Const_Key_Reference> | |
551fe1a2 | 76 | class debug_map_base |
4569a895 AT |
77 | { |
78 | private: | |
79 | typedef typename std::allocator< Key> key_allocator; | |
80 | ||
81 | typedef typename key_allocator::size_type size_type; | |
82 | ||
83 | typedef Const_Key_Reference const_key_reference; | |
84 | ||
85 | protected: | |
551fe1a2 | 86 | debug_map_base(); |
4569a895 | 87 | |
551fe1a2 | 88 | debug_map_base(const PB_DS_CLASS_C_DEC& other); |
4569a895 | 89 | |
551fe1a2 | 90 | ~debug_map_base(); |
4569a895 AT |
91 | |
92 | inline void | |
93 | insert_new(const_key_reference r_key); | |
94 | ||
95 | inline void | |
96 | erase_existing(const_key_reference r_key); | |
97 | ||
98 | void | |
99 | clear(); | |
100 | ||
101 | inline void | |
102 | check_key_exists(const_key_reference r_key) const; | |
103 | ||
104 | inline void | |
105 | check_key_does_not_exist(const_key_reference r_key) const; | |
106 | ||
107 | inline void | |
108 | check_size(size_type size) const; | |
109 | ||
110 | void | |
111 | swap(PB_DS_CLASS_C_DEC& other); | |
112 | ||
113 | template<typename Cmp_Fn> | |
114 | void | |
47bea7b8 | 115 | split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); |
4569a895 AT |
116 | |
117 | void | |
118 | join(PB_DS_CLASS_C_DEC& other); | |
119 | ||
120 | private: | |
47bea7b8 BK |
121 | typedef std::list< Key> key_set; |
122 | typedef typename key_set::iterator key_set_iterator; | |
123 | typedef typename key_set::const_iterator const_key_set_iterator; | |
4569a895 | 124 | |
47bea7b8 | 125 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
126 | void |
127 | assert_valid() const; | |
47bea7b8 | 128 | #endif |
4569a895 AT |
129 | |
130 | const_key_set_iterator | |
131 | find(const_key_reference r_key) const; | |
132 | ||
133 | key_set_iterator | |
134 | find(const_key_reference r_key); | |
135 | ||
47bea7b8 BK |
136 | key_set m_key_set; |
137 | Eq_Fn m_eq; | |
4569a895 AT |
138 | }; |
139 | ||
140 | PB_DS_CLASS_T_DEC | |
141 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 142 | debug_map_base() |
47bea7b8 | 143 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
144 | |
145 | PB_DS_CLASS_T_DEC | |
146 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 147 | debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set) |
47bea7b8 | 148 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
149 | |
150 | PB_DS_CLASS_T_DEC | |
151 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 152 | ~debug_map_base() |
47bea7b8 | 153 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
154 | |
155 | PB_DS_CLASS_T_DEC | |
156 | inline void | |
157 | PB_DS_CLASS_C_DEC:: | |
158 | insert_new(const_key_reference r_key) | |
159 | { | |
47bea7b8 | 160 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
a86151e1 | 161 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 162 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 163 | alloc.set_throw_prob(0); |
4569a895 AT |
164 | if (find(r_key) != m_key_set.end()) |
165 | { | |
551fe1a2 | 166 | std::cerr << "insert_new" << r_key << std::endl; |
4ba851b5 | 167 | std::abort(); |
4569a895 AT |
168 | } |
169 | ||
170 | try | |
171 | { | |
172 | m_key_set.push_back(r_key); | |
173 | } | |
174 | catch(...) | |
175 | { | |
551fe1a2 | 176 | std::cerr << "insert_new" << r_key << std::endl; |
4ba851b5 | 177 | std::abort(); |
4569a895 | 178 | } |
4569a895 | 179 | alloc.set_throw_prob(orig_throw_prob); |
47bea7b8 BK |
180 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
181 | } | |
4569a895 AT |
182 | |
183 | PB_DS_CLASS_T_DEC | |
184 | inline void | |
185 | PB_DS_CLASS_C_DEC:: | |
186 | erase_existing(const_key_reference r_key) | |
187 | { | |
47bea7b8 BK |
188 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
189 | key_set_iterator it = find(r_key); | |
4569a895 AT |
190 | if (it == m_key_set.end()) |
191 | { | |
551fe1a2 | 192 | std::cerr << "erase_existing" << r_key << std::endl; |
4ba851b5 | 193 | std::abort(); |
4569a895 | 194 | } |
4569a895 | 195 | m_key_set.erase(it); |
47bea7b8 BK |
196 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
197 | } | |
4569a895 AT |
198 | |
199 | PB_DS_CLASS_T_DEC | |
200 | void | |
201 | PB_DS_CLASS_C_DEC:: | |
202 | clear() | |
203 | { | |
47bea7b8 BK |
204 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
205 | m_key_set.clear(); | |
206 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
207 | } | |
4569a895 AT |
208 | |
209 | PB_DS_CLASS_T_DEC | |
210 | inline void | |
211 | PB_DS_CLASS_C_DEC:: | |
212 | check_key_exists(const_key_reference r_key) const | |
213 | { | |
47bea7b8 BK |
214 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
215 | if (find(r_key) == m_key_set.end()) | |
216 | { | |
551fe1a2 | 217 | std::cerr << "check_key_exists" << r_key << std::endl; |
4ba851b5 | 218 | std::abort(); |
47bea7b8 BK |
219 | } |
220 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
221 | } | |
4569a895 AT |
222 | |
223 | PB_DS_CLASS_T_DEC | |
224 | inline void | |
225 | PB_DS_CLASS_C_DEC:: | |
226 | check_key_does_not_exist(const_key_reference r_key) const | |
227 | { | |
47bea7b8 BK |
228 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
229 | if (find(r_key) != m_key_set.end()) | |
230 | { | |
551fe1a2 BK |
231 | using std::cerr; |
232 | using std::endl; | |
233 | cerr << "check_key_does_not_exist" << r_key << endl; | |
4ba851b5 | 234 | std::abort(); |
47bea7b8 | 235 | } |
4569a895 AT |
236 | } |
237 | ||
238 | PB_DS_CLASS_T_DEC | |
239 | inline void | |
240 | PB_DS_CLASS_C_DEC:: | |
241 | check_size(size_type size) const | |
242 | { | |
47bea7b8 BK |
243 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
244 | const size_type key_set_size = m_key_set.size(); | |
4569a895 AT |
245 | if (size != key_set_size) |
246 | { | |
47bea7b8 BK |
247 | std::cerr << "check_size " << size |
248 | << " " << key_set_size << std::endl; | |
4ba851b5 | 249 | std::abort(); |
4569a895 | 250 | } |
47bea7b8 BK |
251 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
252 | } | |
4569a895 AT |
253 | |
254 | PB_DS_CLASS_T_DEC | |
255 | void | |
256 | PB_DS_CLASS_C_DEC:: | |
257 | swap(PB_DS_CLASS_C_DEC& other) | |
258 | { | |
47bea7b8 BK |
259 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
260 | m_key_set.swap(other.m_key_set); | |
261 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
262 | } | |
4569a895 AT |
263 | |
264 | PB_DS_CLASS_T_DEC | |
265 | typename PB_DS_CLASS_C_DEC::const_key_set_iterator | |
266 | PB_DS_CLASS_C_DEC:: | |
267 | find(const_key_reference r_key) const | |
268 | { | |
47bea7b8 BK |
269 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
270 | typedef const_key_set_iterator iterator_type; | |
271 | for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it) | |
272 | if (m_eq(*it, r_key)) | |
273 | return it; | |
274 | return m_key_set.end(); | |
4569a895 AT |
275 | } |
276 | ||
277 | PB_DS_CLASS_T_DEC | |
278 | typename PB_DS_CLASS_C_DEC::key_set_iterator | |
279 | PB_DS_CLASS_C_DEC:: | |
280 | find(const_key_reference r_key) | |
281 | { | |
47bea7b8 BK |
282 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
283 | key_set_iterator it = m_key_set.begin(); | |
4569a895 AT |
284 | while (it != m_key_set.end()) |
285 | { | |
286 | if (m_eq(*it, r_key)) | |
47bea7b8 | 287 | return it; |
4569a895 AT |
288 | ++it; |
289 | } | |
47bea7b8 BK |
290 | return it; |
291 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
292 | } | |
4569a895 | 293 | |
47bea7b8 | 294 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
295 | PB_DS_CLASS_T_DEC |
296 | void | |
297 | PB_DS_CLASS_C_DEC:: | |
298 | assert_valid() const | |
299 | { | |
300 | const_key_set_iterator prime_it = m_key_set.begin(); | |
4569a895 AT |
301 | while (prime_it != m_key_set.end()) |
302 | { | |
303 | const_key_set_iterator sec_it = prime_it; | |
4569a895 | 304 | ++sec_it; |
4569a895 AT |
305 | while (sec_it != m_key_set.end()) |
306 | { | |
47bea7b8 BK |
307 | _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it)); |
308 | _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it)); | |
4569a895 AT |
309 | ++sec_it; |
310 | } | |
4569a895 AT |
311 | ++prime_it; |
312 | } | |
313 | } | |
47bea7b8 | 314 | #endif |
4569a895 AT |
315 | |
316 | PB_DS_CLASS_T_DEC | |
317 | template<typename Cmp_Fn> | |
318 | void | |
319 | PB_DS_CLASS_C_DEC:: | |
320 | split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) | |
321 | { | |
a86151e1 | 322 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 323 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 324 | alloc.set_throw_prob(0); |
4569a895 | 325 | other.clear(); |
4569a895 | 326 | key_set_iterator it = m_key_set.begin(); |
4569a895 AT |
327 | while (it != m_key_set.end()) |
328 | if (cmp_fn(r_key, * it)) | |
329 | { | |
330 | other.insert_new(*it); | |
4569a895 AT |
331 | it = m_key_set.erase(it); |
332 | } | |
333 | else | |
334 | ++it; | |
4569a895 AT |
335 | alloc.set_throw_prob(orig_throw_prob); |
336 | } | |
337 | ||
338 | PB_DS_CLASS_T_DEC | |
339 | void | |
340 | PB_DS_CLASS_C_DEC:: | |
341 | join(PB_DS_CLASS_C_DEC& other) | |
342 | { | |
a86151e1 | 343 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 344 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 345 | alloc.set_throw_prob(0); |
4569a895 | 346 | key_set_iterator it = other.m_key_set.begin(); |
4569a895 AT |
347 | while (it != other.m_key_set.end()) |
348 | { | |
349 | insert_new(*it); | |
4569a895 AT |
350 | it = other.m_key_set.erase(it); |
351 | } | |
47bea7b8 | 352 | _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty()); |
4569a895 AT |
353 | alloc.set_throw_prob(orig_throw_prob); |
354 | } | |
355 | ||
356 | #undef PB_DS_CLASS_T_DEC | |
357 | #undef PB_DS_CLASS_C_DEC | |
358 | ||
47bea7b8 | 359 | } // namespace detail |
5e11f978 | 360 | } // namespace __gnu_pbds |
4569a895 | 361 | |
47bea7b8 | 362 | #endif |
4569a895 | 363 | |
47bea7b8 | 364 | #endif |
4569a895 | 365 |