]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
bc2631e0 | 3 | // Copyright (C) 2005, 2006, 2007, 2008, 2009 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> |
52e07aa1 | 55 | #include <iostream> |
a86151e1 | 56 | #include <ext/throw_allocator.h> |
47bea7b8 | 57 | #include <debug/debug.h> |
4569a895 | 58 | |
5e11f978 | 59 | namespace __gnu_pbds |
4569a895 | 60 | { |
4569a895 AT |
61 | namespace detail |
62 | { | |
551fe1a2 BK |
63 | // Need std::pair ostream extractor. |
64 | template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2> | |
65 | inline std::basic_ostream<_CharT, _Traits>& | |
66 | operator<<(std::basic_ostream<_CharT, _Traits>& __out, | |
67 | const std::pair<_Tp1, _Tp2>& p) | |
68 | { return (__out << '(' << p.first << ',' << p.second << ')'); } | |
4569a895 | 69 | |
47bea7b8 | 70 | #define PB_DS_CLASS_T_DEC \ |
4569a895 AT |
71 | template<typename Key, class Eq_Fn, typename Const_Key_Reference> |
72 | ||
47bea7b8 | 73 | #define PB_DS_CLASS_C_DEC \ |
551fe1a2 | 74 | debug_map_base<Key, Eq_Fn, Const_Key_Reference> |
4569a895 AT |
75 | |
76 | template<typename Key, class Eq_Fn, typename Const_Key_Reference> | |
551fe1a2 | 77 | class debug_map_base |
4569a895 AT |
78 | { |
79 | private: | |
80 | typedef typename std::allocator< Key> key_allocator; | |
81 | ||
82 | typedef typename key_allocator::size_type size_type; | |
83 | ||
84 | typedef Const_Key_Reference const_key_reference; | |
85 | ||
86 | protected: | |
551fe1a2 | 87 | debug_map_base(); |
4569a895 | 88 | |
551fe1a2 | 89 | debug_map_base(const PB_DS_CLASS_C_DEC& other); |
4569a895 | 90 | |
551fe1a2 | 91 | ~debug_map_base(); |
4569a895 AT |
92 | |
93 | inline void | |
94 | insert_new(const_key_reference r_key); | |
95 | ||
96 | inline void | |
97 | erase_existing(const_key_reference r_key); | |
98 | ||
99 | void | |
100 | clear(); | |
101 | ||
102 | inline void | |
103 | check_key_exists(const_key_reference r_key) const; | |
104 | ||
105 | inline void | |
106 | check_key_does_not_exist(const_key_reference r_key) const; | |
107 | ||
108 | inline void | |
109 | check_size(size_type size) const; | |
110 | ||
111 | void | |
112 | swap(PB_DS_CLASS_C_DEC& other); | |
113 | ||
114 | template<typename Cmp_Fn> | |
115 | void | |
47bea7b8 | 116 | split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); |
4569a895 AT |
117 | |
118 | void | |
119 | join(PB_DS_CLASS_C_DEC& other); | |
120 | ||
121 | private: | |
47bea7b8 BK |
122 | typedef std::list< Key> key_set; |
123 | typedef typename key_set::iterator key_set_iterator; | |
124 | typedef typename key_set::const_iterator const_key_set_iterator; | |
4569a895 | 125 | |
47bea7b8 | 126 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
127 | void |
128 | assert_valid() const; | |
47bea7b8 | 129 | #endif |
4569a895 AT |
130 | |
131 | const_key_set_iterator | |
132 | find(const_key_reference r_key) const; | |
133 | ||
134 | key_set_iterator | |
135 | find(const_key_reference r_key); | |
136 | ||
47bea7b8 BK |
137 | key_set m_key_set; |
138 | Eq_Fn m_eq; | |
4569a895 AT |
139 | }; |
140 | ||
141 | PB_DS_CLASS_T_DEC | |
142 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 143 | debug_map_base() |
47bea7b8 | 144 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
145 | |
146 | PB_DS_CLASS_T_DEC | |
147 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 148 | debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set) |
47bea7b8 | 149 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
150 | |
151 | PB_DS_CLASS_T_DEC | |
152 | PB_DS_CLASS_C_DEC:: | |
551fe1a2 | 153 | ~debug_map_base() |
47bea7b8 | 154 | { _GLIBCXX_DEBUG_ONLY(assert_valid();) } |
4569a895 AT |
155 | |
156 | PB_DS_CLASS_T_DEC | |
157 | inline void | |
158 | PB_DS_CLASS_C_DEC:: | |
159 | insert_new(const_key_reference r_key) | |
160 | { | |
47bea7b8 | 161 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
a86151e1 | 162 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 163 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 164 | alloc.set_throw_prob(0); |
4569a895 AT |
165 | if (find(r_key) != m_key_set.end()) |
166 | { | |
551fe1a2 | 167 | std::cerr << "insert_new" << r_key << std::endl; |
4ba851b5 | 168 | std::abort(); |
4569a895 AT |
169 | } |
170 | ||
bc2631e0 | 171 | __try |
4569a895 AT |
172 | { |
173 | m_key_set.push_back(r_key); | |
174 | } | |
bc2631e0 | 175 | __catch(...) |
4569a895 | 176 | { |
551fe1a2 | 177 | std::cerr << "insert_new" << r_key << std::endl; |
4ba851b5 | 178 | std::abort(); |
4569a895 | 179 | } |
4569a895 | 180 | alloc.set_throw_prob(orig_throw_prob); |
47bea7b8 BK |
181 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
182 | } | |
4569a895 AT |
183 | |
184 | PB_DS_CLASS_T_DEC | |
185 | inline void | |
186 | PB_DS_CLASS_C_DEC:: | |
187 | erase_existing(const_key_reference r_key) | |
188 | { | |
47bea7b8 BK |
189 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
190 | key_set_iterator it = find(r_key); | |
4569a895 AT |
191 | if (it == m_key_set.end()) |
192 | { | |
551fe1a2 | 193 | std::cerr << "erase_existing" << r_key << std::endl; |
4ba851b5 | 194 | std::abort(); |
4569a895 | 195 | } |
4569a895 | 196 | m_key_set.erase(it); |
47bea7b8 BK |
197 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
198 | } | |
4569a895 AT |
199 | |
200 | PB_DS_CLASS_T_DEC | |
201 | void | |
202 | PB_DS_CLASS_C_DEC:: | |
203 | clear() | |
204 | { | |
47bea7b8 BK |
205 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
206 | m_key_set.clear(); | |
207 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
208 | } | |
4569a895 AT |
209 | |
210 | PB_DS_CLASS_T_DEC | |
211 | inline void | |
212 | PB_DS_CLASS_C_DEC:: | |
213 | check_key_exists(const_key_reference r_key) const | |
214 | { | |
47bea7b8 BK |
215 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
216 | if (find(r_key) == m_key_set.end()) | |
217 | { | |
551fe1a2 | 218 | std::cerr << "check_key_exists" << r_key << std::endl; |
4ba851b5 | 219 | std::abort(); |
47bea7b8 BK |
220 | } |
221 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
222 | } | |
4569a895 AT |
223 | |
224 | PB_DS_CLASS_T_DEC | |
225 | inline void | |
226 | PB_DS_CLASS_C_DEC:: | |
227 | check_key_does_not_exist(const_key_reference r_key) const | |
228 | { | |
47bea7b8 BK |
229 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
230 | if (find(r_key) != m_key_set.end()) | |
231 | { | |
551fe1a2 BK |
232 | using std::cerr; |
233 | using std::endl; | |
234 | cerr << "check_key_does_not_exist" << r_key << endl; | |
4ba851b5 | 235 | std::abort(); |
47bea7b8 | 236 | } |
4569a895 AT |
237 | } |
238 | ||
239 | PB_DS_CLASS_T_DEC | |
240 | inline void | |
241 | PB_DS_CLASS_C_DEC:: | |
242 | check_size(size_type size) const | |
243 | { | |
47bea7b8 BK |
244 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
245 | const size_type key_set_size = m_key_set.size(); | |
4569a895 AT |
246 | if (size != key_set_size) |
247 | { | |
47bea7b8 BK |
248 | std::cerr << "check_size " << size |
249 | << " " << key_set_size << std::endl; | |
4ba851b5 | 250 | std::abort(); |
4569a895 | 251 | } |
47bea7b8 BK |
252 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
253 | } | |
4569a895 AT |
254 | |
255 | PB_DS_CLASS_T_DEC | |
256 | void | |
257 | PB_DS_CLASS_C_DEC:: | |
258 | swap(PB_DS_CLASS_C_DEC& other) | |
259 | { | |
47bea7b8 BK |
260 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
261 | m_key_set.swap(other.m_key_set); | |
262 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
263 | } | |
4569a895 AT |
264 | |
265 | PB_DS_CLASS_T_DEC | |
266 | typename PB_DS_CLASS_C_DEC::const_key_set_iterator | |
267 | PB_DS_CLASS_C_DEC:: | |
268 | find(const_key_reference r_key) const | |
269 | { | |
47bea7b8 BK |
270 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
271 | typedef const_key_set_iterator iterator_type; | |
272 | for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it) | |
273 | if (m_eq(*it, r_key)) | |
274 | return it; | |
275 | return m_key_set.end(); | |
4569a895 AT |
276 | } |
277 | ||
278 | PB_DS_CLASS_T_DEC | |
279 | typename PB_DS_CLASS_C_DEC::key_set_iterator | |
280 | PB_DS_CLASS_C_DEC:: | |
281 | find(const_key_reference r_key) | |
282 | { | |
47bea7b8 BK |
283 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
284 | key_set_iterator it = m_key_set.begin(); | |
4569a895 AT |
285 | while (it != m_key_set.end()) |
286 | { | |
287 | if (m_eq(*it, r_key)) | |
47bea7b8 | 288 | return it; |
4569a895 AT |
289 | ++it; |
290 | } | |
47bea7b8 BK |
291 | return it; |
292 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
293 | } | |
4569a895 | 294 | |
47bea7b8 | 295 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
296 | PB_DS_CLASS_T_DEC |
297 | void | |
298 | PB_DS_CLASS_C_DEC:: | |
299 | assert_valid() const | |
300 | { | |
301 | const_key_set_iterator prime_it = m_key_set.begin(); | |
4569a895 AT |
302 | while (prime_it != m_key_set.end()) |
303 | { | |
304 | const_key_set_iterator sec_it = prime_it; | |
4569a895 | 305 | ++sec_it; |
4569a895 AT |
306 | while (sec_it != m_key_set.end()) |
307 | { | |
47bea7b8 BK |
308 | _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it)); |
309 | _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it)); | |
4569a895 AT |
310 | ++sec_it; |
311 | } | |
4569a895 AT |
312 | ++prime_it; |
313 | } | |
314 | } | |
47bea7b8 | 315 | #endif |
4569a895 AT |
316 | |
317 | PB_DS_CLASS_T_DEC | |
318 | template<typename Cmp_Fn> | |
319 | void | |
320 | PB_DS_CLASS_C_DEC:: | |
321 | split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) | |
322 | { | |
a86151e1 | 323 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 324 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 325 | alloc.set_throw_prob(0); |
4569a895 | 326 | other.clear(); |
4569a895 | 327 | key_set_iterator it = m_key_set.begin(); |
4569a895 AT |
328 | while (it != m_key_set.end()) |
329 | if (cmp_fn(r_key, * it)) | |
330 | { | |
331 | other.insert_new(*it); | |
4569a895 AT |
332 | it = m_key_set.erase(it); |
333 | } | |
334 | else | |
335 | ++it; | |
4569a895 AT |
336 | alloc.set_throw_prob(orig_throw_prob); |
337 | } | |
338 | ||
339 | PB_DS_CLASS_T_DEC | |
340 | void | |
341 | PB_DS_CLASS_C_DEC:: | |
342 | join(PB_DS_CLASS_C_DEC& other) | |
343 | { | |
a86151e1 | 344 | __gnu_cxx::throw_allocator<char> alloc; |
4569a895 | 345 | const double orig_throw_prob = alloc.get_throw_prob(); |
4569a895 | 346 | alloc.set_throw_prob(0); |
4569a895 | 347 | key_set_iterator it = other.m_key_set.begin(); |
4569a895 AT |
348 | while (it != other.m_key_set.end()) |
349 | { | |
350 | insert_new(*it); | |
4569a895 AT |
351 | it = other.m_key_set.erase(it); |
352 | } | |
47bea7b8 | 353 | _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty()); |
4569a895 AT |
354 | alloc.set_throw_prob(orig_throw_prob); |
355 | } | |
356 | ||
357 | #undef PB_DS_CLASS_T_DEC | |
358 | #undef PB_DS_CLASS_C_DEC | |
359 | ||
47bea7b8 | 360 | } // namespace detail |
5e11f978 | 361 | } // namespace __gnu_pbds |
4569a895 | 362 | |
47bea7b8 | 363 | #endif |
4569a895 | 364 | |
47bea7b8 | 365 | #endif |
4569a895 | 366 |