1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 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.
41
42/**
43 * @file map_debug_base.hpp
44 * Contains a debug-mode base for all maps.
45 */
46
47#ifndef PB_DS_MAP_DEBUG_BASE_HPP
48#define PB_DS_MAP_DEBUG_BASE_HPP
49
50#ifdef _GLIBCXX_DEBUG
51
52#include <list>
53#include <utility>
54#include <ext/throw_allocator.h>
55#include <debug/debug.h>
56
57namespace pb_ds
58{
59  namespace detail
60  {
61
62#define PB_DS_CLASS_T_DEC \
63    template<typename Key, class Eq_Fn, typename Const_Key_Reference>
64
65#define PB_DS_CLASS_C_DEC \
66    map_debug_base<Key, Eq_Fn, Const_Key_Reference>
67
68    template<typename Key, class Eq_Fn, typename Const_Key_Reference>
69    class map_debug_base
70    {
71    private:
72      typedef typename std::allocator< Key> key_allocator;
73
74      typedef typename key_allocator::size_type size_type;
75
76      typedef Const_Key_Reference const_key_reference;
77
78    protected:
79      map_debug_base();
80
81      map_debug_base(const PB_DS_CLASS_C_DEC& other);
82
83      ~map_debug_base();
84
85      inline void
86      insert_new(const_key_reference r_key);
87
88      inline void
89      erase_existing(const_key_reference r_key);
90
91      void
92      clear();
93
94      inline void
95      check_key_exists(const_key_reference r_key) const;
96
97      inline void
98      check_key_does_not_exist(const_key_reference r_key) const;
99
100      inline void
101      check_size(size_type size) const;
102
103      void
104      swap(PB_DS_CLASS_C_DEC& other);
105
106      template<typename Cmp_Fn>
107      void
108      split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
109
110      void
111      join(PB_DS_CLASS_C_DEC& other);
112
113    private:
114      typedef std::list< Key> 			key_set;
115      typedef typename key_set::iterator 	key_set_iterator;
116      typedef typename key_set::const_iterator 	const_key_set_iterator;
117
118#ifdef _GLIBCXX_DEBUG
119      void
120      assert_valid() const;
121#endif
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    map_debug_base()
136    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
137
138    PB_DS_CLASS_T_DEC
139    PB_DS_CLASS_C_DEC::
140    map_debug_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    ~map_debug_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      __gnu_cxx::throw_allocator<char> alloc;
155      const double orig_throw_prob = alloc.get_throw_prob();
156      alloc.set_throw_prob(0);
157      if (find(r_key) != m_key_set.end())
158	{
159	  std::cerr << "insert_new " << r_key << std::endl;
160	  abort();
161	}
162
163      try
164	{
165	  m_key_set.push_back(r_key);
166	}
167      catch(...)
168	{
169	  std::cerr << "insert_new 1" << r_key << std::endl;
170	  abort();
171	}
172      alloc.set_throw_prob(orig_throw_prob);
173      _GLIBCXX_DEBUG_ONLY(assert_valid();)
174    }
175
176    PB_DS_CLASS_T_DEC
177    inline void
178    PB_DS_CLASS_C_DEC::
179    erase_existing(const_key_reference r_key)
180    {
181      _GLIBCXX_DEBUG_ONLY(assert_valid();)
182      key_set_iterator it = find(r_key);
183      if (it == m_key_set.end())
184	{
185	  std::cerr << "erase_existing " << r_key << std::endl;
186	  abort();
187	}
188      m_key_set.erase(it);
189      _GLIBCXX_DEBUG_ONLY(assert_valid();)
190    }
191
192    PB_DS_CLASS_T_DEC
193    void
194    PB_DS_CLASS_C_DEC::
195    clear()
196    {
197      _GLIBCXX_DEBUG_ONLY(assert_valid();)
198      m_key_set.clear();
199      _GLIBCXX_DEBUG_ONLY(assert_valid();)
200    }
201
202    PB_DS_CLASS_T_DEC
203    inline void
204    PB_DS_CLASS_C_DEC::
205    check_key_exists(const_key_reference r_key) const
206    {
207      _GLIBCXX_DEBUG_ONLY(assert_valid();)
208      if (find(r_key) == m_key_set.end())
209        {
210          std::cerr << "check_key_exists " << r_key << std::endl;
211          abort();
212        }
213      _GLIBCXX_DEBUG_ONLY(assert_valid();)
214    }
215
216    PB_DS_CLASS_T_DEC
217    inline void
218    PB_DS_CLASS_C_DEC::
219    check_key_does_not_exist(const_key_reference r_key) const
220    {
221      _GLIBCXX_DEBUG_ONLY(assert_valid();)
222      if (find(r_key) != m_key_set.end())
223        {
224	  std::cerr << "check_key_does_not_exist " << r_key << std::endl;
225          abort();
226        }
227    }
228
229    PB_DS_CLASS_T_DEC
230    inline void
231    PB_DS_CLASS_C_DEC::
232    check_size(size_type size) const
233    {
234      _GLIBCXX_DEBUG_ONLY(assert_valid();)
235      const size_type key_set_size = m_key_set.size();
236      if (size != key_set_size)
237	{
238	  std::cerr << "check_size " << size
239		    << " " << key_set_size << std::endl;
240	  abort();
241	}
242      _GLIBCXX_DEBUG_ONLY(assert_valid();)
243     }
244
245    PB_DS_CLASS_T_DEC
246    void
247    PB_DS_CLASS_C_DEC::
248    swap(PB_DS_CLASS_C_DEC& other)
249    {
250      _GLIBCXX_DEBUG_ONLY(assert_valid();)
251      m_key_set.swap(other.m_key_set);
252      _GLIBCXX_DEBUG_ONLY(assert_valid();)
253    }
254
255    PB_DS_CLASS_T_DEC
256    typename PB_DS_CLASS_C_DEC::const_key_set_iterator
257    PB_DS_CLASS_C_DEC::
258    find(const_key_reference r_key) const
259    {
260      _GLIBCXX_DEBUG_ONLY(assert_valid();)
261      typedef const_key_set_iterator iterator_type;
262      for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
263	if (m_eq(*it, r_key))
264          return it;
265      return m_key_set.end();
266    }
267
268    PB_DS_CLASS_T_DEC
269    typename PB_DS_CLASS_C_DEC::key_set_iterator
270    PB_DS_CLASS_C_DEC::
271    find(const_key_reference r_key)
272    {
273      _GLIBCXX_DEBUG_ONLY(assert_valid();)
274      key_set_iterator it = m_key_set.begin();
275      while (it != m_key_set.end())
276	{
277	  if (m_eq(*it, r_key))
278            return it;
279	  ++it;
280	}
281      return it;
282      _GLIBCXX_DEBUG_ONLY(assert_valid();)
283     }
284
285#ifdef _GLIBCXX_DEBUG
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#endif
306
307    PB_DS_CLASS_T_DEC
308    template<typename Cmp_Fn>
309    void
310    PB_DS_CLASS_C_DEC::
311    split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
312    {
313      __gnu_cxx::throw_allocator<char> alloc;
314      const double orig_throw_prob = alloc.get_throw_prob();
315      alloc.set_throw_prob(0);
316      other.clear();
317      key_set_iterator it = m_key_set.begin();
318      while (it != m_key_set.end())
319        if (cmp_fn(r_key, * it))
320	  {
321            other.insert_new(*it);
322            it = m_key_set.erase(it);
323	  }
324        else
325	  ++it;
326      alloc.set_throw_prob(orig_throw_prob);
327    }
328
329    PB_DS_CLASS_T_DEC
330    void
331    PB_DS_CLASS_C_DEC::
332    join(PB_DS_CLASS_C_DEC& other)
333    {
334      __gnu_cxx::throw_allocator<char> alloc;
335      const double orig_throw_prob = alloc.get_throw_prob();
336      alloc.set_throw_prob(0);
337      key_set_iterator it = other.m_key_set.begin();
338      while (it != other.m_key_set.end())
339	{
340	  insert_new(*it);
341	  it = other.m_key_set.erase(it);
342	}
343      _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
344      alloc.set_throw_prob(orig_throw_prob);
345    }
346
347#undef PB_DS_CLASS_T_DEC
348#undef PB_DS_CLASS_C_DEC
349
350} // namespace detail
351} // namespace pb_ds
352
353#endif
354
355#endif
356
357