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