libstdc++
debug_map_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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 terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file debug_map_base.hpp
38  * Contains a debug-mode base for all maps.
39  */
40 
41 #ifndef PB_DS_DEBUG_MAP_BASE_HPP
42 #define PB_DS_DEBUG_MAP_BASE_HPP
43 
44 #ifdef _GLIBCXX_DEBUG
45 
46 #include <list>
47 #include <utility>
48 #include <cstdlib>
49 #include <iostream>
50 #include <ext/throw_allocator.h>
51 #include <debug/debug.h>
52 
53 namespace __gnu_pbds
54 {
55  namespace detail
56  {
57  // Need std::pair ostream extractor.
58  template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2>
60  operator<<(std::basic_ostream<_CharT, _Traits>& __out,
61  const std::pair<_Tp1, _Tp2>& p)
62  { return (__out << '(' << p.first << ',' << p.second << ')'); }
63 
64 #define PB_DS_CLASS_T_DEC \
65  template<typename Key, class Eq_Fn, typename Const_Key_Reference>
66 
67 #define PB_DS_CLASS_C_DEC \
68  debug_map_base<Key, Eq_Fn, Const_Key_Reference>
69 
70  template<typename Key, class Eq_Fn, typename Const_Key_Reference>
71  class debug_map_base
72  {
73  private:
74  typedef typename std::allocator< Key> key_allocator;
75 
76  typedef typename key_allocator::size_type size_type;
77 
78  typedef Const_Key_Reference const_key_reference;
79 
80  protected:
81  debug_map_base();
82 
83  debug_map_base(const PB_DS_CLASS_C_DEC& other);
84 
85  ~debug_map_base();
86 
87  inline void
88  insert_new(const_key_reference r_key);
89 
90  inline void
91  erase_existing(const_key_reference r_key);
92 
93  void
94  clear();
95 
96  inline void
97  check_key_exists(const_key_reference r_key) const;
98 
99  inline void
100  check_key_does_not_exist(const_key_reference r_key) const;
101 
102  inline void
103  check_size(size_type size) const;
104 
105  void
106  swap(PB_DS_CLASS_C_DEC& other);
107 
108  template<typename Cmp_Fn>
109  void
110  split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
111 
112  void
113  join(PB_DS_CLASS_C_DEC& other);
114 
115  private:
116  typedef std::list< Key> key_set;
117  typedef typename key_set::iterator key_set_iterator;
118  typedef typename key_set::const_iterator const_key_set_iterator;
119 
120 #ifdef _GLIBCXX_DEBUG
121  void
122  assert_valid() const;
123 #endif
124 
125  const_key_set_iterator
126  find(const_key_reference r_key) const;
127 
128  key_set_iterator
129  find(const_key_reference r_key);
130 
131  key_set m_key_set;
132  Eq_Fn m_eq;
133  };
134 
135  PB_DS_CLASS_T_DEC
136  PB_DS_CLASS_C_DEC::
137  debug_map_base()
138  { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
139 
140  PB_DS_CLASS_T_DEC
141  PB_DS_CLASS_C_DEC::
142  debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
143  { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
144 
145  PB_DS_CLASS_T_DEC
146  PB_DS_CLASS_C_DEC::
147  ~debug_map_base()
148  { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
149 
150  PB_DS_CLASS_T_DEC
151  inline void
152  PB_DS_CLASS_C_DEC::
153  insert_new(const_key_reference r_key)
154  {
155  _GLIBCXX_DEBUG_ONLY(assert_valid();)
157  const double orig_throw_prob = alloc.get_throw_prob();
158  alloc.set_throw_prob(0);
159  if (find(r_key) != m_key_set.end())
160  {
161  std::cerr << "insert_new" << r_key << std::endl;
162  std::abort();
163  }
164 
165  __try
166  {
167  m_key_set.push_back(r_key);
168  }
169  __catch(...)
170  {
171  std::cerr << "insert_new" << r_key << std::endl;
172  std::abort();
173  }
174  alloc.set_throw_prob(orig_throw_prob);
175  _GLIBCXX_DEBUG_ONLY(assert_valid();)
176  }
177 
178  PB_DS_CLASS_T_DEC
179  inline void
180  PB_DS_CLASS_C_DEC::
181  erase_existing(const_key_reference r_key)
182  {
183  _GLIBCXX_DEBUG_ONLY(assert_valid();)
184  key_set_iterator it = find(r_key);
185  if (it == m_key_set.end())
186  {
187  std::cerr << "erase_existing" << r_key << std::endl;
188  std::abort();
189  }
190  m_key_set.erase(it);
191  _GLIBCXX_DEBUG_ONLY(assert_valid();)
192  }
193 
194  PB_DS_CLASS_T_DEC
195  void
196  PB_DS_CLASS_C_DEC::
197  clear()
198  {
199  _GLIBCXX_DEBUG_ONLY(assert_valid();)
200  m_key_set.clear();
201  _GLIBCXX_DEBUG_ONLY(assert_valid();)
202  }
203 
204  PB_DS_CLASS_T_DEC
205  inline void
206  PB_DS_CLASS_C_DEC::
207  check_key_exists(const_key_reference r_key) const
208  {
209  _GLIBCXX_DEBUG_ONLY(assert_valid();)
210  if (find(r_key) == m_key_set.end())
211  {
212  std::cerr << "check_key_exists" << r_key << std::endl;
213  std::abort();
214  }
215  _GLIBCXX_DEBUG_ONLY(assert_valid();)
216  }
217 
218  PB_DS_CLASS_T_DEC
219  inline void
220  PB_DS_CLASS_C_DEC::
221  check_key_does_not_exist(const_key_reference r_key) const
222  {
223  _GLIBCXX_DEBUG_ONLY(assert_valid();)
224  if (find(r_key) != m_key_set.end())
225  {
226  using std::cerr;
227  using std::endl;
228  cerr << "check_key_does_not_exist" << r_key << endl;
229  std::abort();
230  }
231  }
232 
233  PB_DS_CLASS_T_DEC
234  inline void
235  PB_DS_CLASS_C_DEC::
236  check_size(size_type size) const
237  {
238  _GLIBCXX_DEBUG_ONLY(assert_valid();)
239  const size_type key_set_size = m_key_set.size();
240  if (size != key_set_size)
241  {
242  std::cerr << "check_size " << size
243  << " " << key_set_size << std::endl;
244  std::abort();
245  }
246  _GLIBCXX_DEBUG_ONLY(assert_valid();)
247  }
248 
249  PB_DS_CLASS_T_DEC
250  void
251  PB_DS_CLASS_C_DEC::
252  swap(PB_DS_CLASS_C_DEC& other)
253  {
254  _GLIBCXX_DEBUG_ONLY(assert_valid();)
255  m_key_set.swap(other.m_key_set);
256  _GLIBCXX_DEBUG_ONLY(assert_valid();)
257  }
258 
259  PB_DS_CLASS_T_DEC
260  typename PB_DS_CLASS_C_DEC::const_key_set_iterator
261  PB_DS_CLASS_C_DEC::
262  find(const_key_reference r_key) const
263  {
264  _GLIBCXX_DEBUG_ONLY(assert_valid();)
265  typedef const_key_set_iterator iterator_type;
266  for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
267  if (m_eq(*it, r_key))
268  return it;
269  return m_key_set.end();
270  }
271 
272  PB_DS_CLASS_T_DEC
273  typename PB_DS_CLASS_C_DEC::key_set_iterator
274  PB_DS_CLASS_C_DEC::
275  find(const_key_reference r_key)
276  {
277  _GLIBCXX_DEBUG_ONLY(assert_valid();)
278  key_set_iterator it = m_key_set.begin();
279  while (it != m_key_set.end())
280  {
281  if (m_eq(*it, r_key))
282  return it;
283  ++it;
284  }
285  return it;
286  _GLIBCXX_DEBUG_ONLY(assert_valid();)
287  }
288 
289 #ifdef _GLIBCXX_DEBUG
290  PB_DS_CLASS_T_DEC
291  void
292  PB_DS_CLASS_C_DEC::
293  assert_valid() const
294  {
295  const_key_set_iterator prime_it = m_key_set.begin();
296  while (prime_it != m_key_set.end())
297  {
298  const_key_set_iterator sec_it = prime_it;
299  ++sec_it;
300  while (sec_it != m_key_set.end())
301  {
302  _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
303  _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
304  ++sec_it;
305  }
306  ++prime_it;
307  }
308  }
309 #endif
310 
311  PB_DS_CLASS_T_DEC
312  template<typename Cmp_Fn>
313  void
314  PB_DS_CLASS_C_DEC::
315  split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
316  {
318  const double orig_throw_prob = alloc.get_throw_prob();
319  alloc.set_throw_prob(0);
320  other.clear();
321  key_set_iterator it = m_key_set.begin();
322  while (it != m_key_set.end())
323  if (cmp_fn(r_key, * it))
324  {
325  other.insert_new(*it);
326  it = m_key_set.erase(it);
327  }
328  else
329  ++it;
330  alloc.set_throw_prob(orig_throw_prob);
331  }
332 
333  PB_DS_CLASS_T_DEC
334  void
335  PB_DS_CLASS_C_DEC::
336  join(PB_DS_CLASS_C_DEC& other)
337  {
339  const double orig_throw_prob = alloc.get_throw_prob();
340  alloc.set_throw_prob(0);
341  key_set_iterator it = other.m_key_set.begin();
342  while (it != other.m_key_set.end())
343  {
344  insert_new(*it);
345  it = other.m_key_set.erase(it);
346  }
347  _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
348  alloc.set_throw_prob(orig_throw_prob);
349  }
350 
351 #undef PB_DS_CLASS_T_DEC
352 #undef PB_DS_CLASS_C_DEC
353 
354 } // namespace detail
355 } // namespace __gnu_pbds
356 
357 #endif
358 
359 #endif
360 
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:417
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
Definition: ostream:538
ostream cerr
Linked to standard error (unbuffered)
Allocator class with logging and exception control.
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
Definition: allocator.h:60
Controlling output.This is the base class for all output streams. It provides text formatting of all ...
Definition: iosfwd:56