1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
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 detail/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, typename 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     /// Debug base class.
72     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
73     class debug_map_base
74     {
75     private:
76       typedef Const_Key_Reference 			key_const_reference;
77       typedef std::_GLIBCXX_STD_C::list<Key> 		key_repository;
78       typedef typename key_repository::size_type       	size_type;
79       typedef typename key_repository::iterator	       	iterator;
80       typedef typename key_repository::const_iterator  	const_iterator;
81 
82     protected:
83       debug_map_base();
84 
85       debug_map_base(const PB_DS_CLASS_C_DEC&);
86 
87       ~debug_map_base();
88 
89       inline void
90       insert_new(key_const_reference);
91 
92       inline void
93       erase_existing(key_const_reference);
94 
95       void
96       clear();
97 
98       inline void
99       check_key_exists(key_const_reference, const char*, int) const;
100 
101       inline void
102       check_key_does_not_exist(key_const_reference, const char*, int) const;
103 
104       inline void
105       check_size(size_type, const char*, int) const;
106 
107       void
108       swap(PB_DS_CLASS_C_DEC&);
109 
110       template<typename Cmp_Fn>
111       void
112       split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
113 
114       void
115       join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true);
116 
117     private:
118       void
119       assert_valid(const char*, int) const;
120 
121       const_iterator
122       find(key_const_reference) const;
123 
124       iterator
125       find(key_const_reference);
126 
127       key_repository 	m_keys;
128       Eq_Fn 		m_eq;
129     };
130 
131     PB_DS_CLASS_T_DEC
132     PB_DS_CLASS_C_DEC::
133     debug_map_base()
134     { PB_DS_ASSERT_VALID((*this)) }
135 
136     PB_DS_CLASS_T_DEC
137     PB_DS_CLASS_C_DEC::
138     debug_map_base(const PB_DS_CLASS_C_DEC& other)
139     : m_keys(other.m_keys), m_eq(other.m_eq)
140     { PB_DS_ASSERT_VALID((*this)) }
141 
142     PB_DS_CLASS_T_DEC
143     PB_DS_CLASS_C_DEC::
144     ~debug_map_base()
145     { PB_DS_ASSERT_VALID((*this)) }
146 
147     PB_DS_CLASS_T_DEC
148     inline void
149     PB_DS_CLASS_C_DEC::
150     insert_new(key_const_reference r_key)
151     {
152       PB_DS_ASSERT_VALID((*this))
153 
154       if (find(r_key) != m_keys.end())
155 	{
156 	  std::cerr << "insert_new key already present " << r_key << std::endl;
157 	  std::abort();
158 	}
159 
160       __try
161 	{
162 	  m_keys.push_back(r_key);
163 	}
164       __catch(...)
165 	{
166 	  std::cerr << "insert_new " << r_key << std::endl;
167 	  std::abort();
168 	}
169 
170       PB_DS_ASSERT_VALID((*this))
171     }
172 
173     PB_DS_CLASS_T_DEC
174     inline void
175     PB_DS_CLASS_C_DEC::
176     erase_existing(key_const_reference r_key)
177     {
178       PB_DS_ASSERT_VALID((*this))
179       iterator it = find(r_key);
180       if (it == m_keys.end())
181 	{
182 	  std::cerr << "erase_existing" << r_key << std::endl;
183 	  std::abort();
184 	}
185       m_keys.erase(it);
186       PB_DS_ASSERT_VALID((*this))
187     }
188 
189     PB_DS_CLASS_T_DEC
190     void
191     PB_DS_CLASS_C_DEC::
192     clear()
193     {
194       PB_DS_ASSERT_VALID((*this))
195       m_keys.clear();
196       PB_DS_ASSERT_VALID((*this))
197     }
198 
199     PB_DS_CLASS_T_DEC
200     inline void
201     PB_DS_CLASS_C_DEC::
202     check_key_exists(key_const_reference r_key,
203 		     const char* __file, int __line) const
204     {
205       assert_valid(__file, __line);
206       if (find(r_key) == m_keys.end())
207 	{
208 	  std::cerr << __file << ':' << __line << ": check_key_exists "
209 		    << r_key << std::endl;
210 	  std::abort();
211 	}
212     }
213 
214     PB_DS_CLASS_T_DEC
215     inline void
216     PB_DS_CLASS_C_DEC::
217     check_key_does_not_exist(key_const_reference r_key,
218 			     const char* __file, int __line) const
219     {
220       assert_valid(__file, __line);
221       if (find(r_key) != m_keys.end())
222 	{
223 	  using std::cerr;
224 	  using std::endl;
225 	  cerr << __file << ':' << __line << ": check_key_does_not_exist "
226 	       << r_key << endl;
227 	  std::abort();
228 	}
229     }
230 
231     PB_DS_CLASS_T_DEC
232     inline void
233     PB_DS_CLASS_C_DEC::
234     check_size(size_type size, const char* __file, int __line) const
235     {
236       assert_valid(__file, __line);
237       const size_type keys_size = m_keys.size();
238       if (size != keys_size)
239 	{
240 	  std::cerr << __file << ':' << __line << ": check_size "
241 		    << size << " != " << keys_size << std::endl;
242 	  std::abort();
243 	}
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       PB_DS_ASSERT_VALID((*this))
252       m_keys.swap(other.m_keys);
253       std::swap(m_eq, other.m_eq);
254       PB_DS_ASSERT_VALID((*this))
255     }
256 
257     PB_DS_CLASS_T_DEC
258     typename PB_DS_CLASS_C_DEC::const_iterator
259     PB_DS_CLASS_C_DEC::
260     find(key_const_reference r_key) const
261     {
262       PB_DS_ASSERT_VALID((*this))
263       typedef const_iterator iterator_type;
264       for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it)
265 	if (m_eq(*it, r_key))
266 	  return it;
267       return m_keys.end();
268     }
269 
270     PB_DS_CLASS_T_DEC
271     typename PB_DS_CLASS_C_DEC::iterator
272     PB_DS_CLASS_C_DEC::
273     find(key_const_reference r_key)
274     {
275       PB_DS_ASSERT_VALID((*this))
276       iterator it = m_keys.begin();
277       while (it != m_keys.end())
278 	{
279 	  if (m_eq(*it, r_key))
280 	    return it;
281 	  ++it;
282 	}
283       return it;
284      }
285 
286     PB_DS_CLASS_T_DEC
287     void
288     PB_DS_CLASS_C_DEC::
289     assert_valid(const char* __file, int __line) const
290     {
291       const_iterator prime_it = m_keys.begin();
292       while (prime_it != m_keys.end())
293 	{
294 	  const_iterator sec_it = prime_it;
295 	  ++sec_it;
296 	  while (sec_it != m_keys.end())
297 	    {
298 	      PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it));
299 	      PB_DS_DEBUG_VERIFY(!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(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
311     {
312       other.clear();
313       iterator it = m_keys.begin();
314       while (it != m_keys.end())
315 	if (cmp_fn(r_key, *it))
316 	  {
317 	    other.insert_new(*it);
318 	    it = m_keys.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, bool with_cleanup)
328     {
329       iterator it = other.m_keys.begin();
330       while (it != other.m_keys.end())
331 	{
332 	  insert_new(*it);
333 	  if (with_cleanup)
334 	    it = other.m_keys.erase(it);
335 	  else
336 	    ++it;
337 	}
338       _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty());
339     }
340 
341 #undef PB_DS_CLASS_T_DEC
342 #undef PB_DS_CLASS_C_DEC
343 
344 } // namespace detail
345 } // namespace __gnu_pbds
346 
347 
348 #endif
349 
350 #endif
351