OSDN Git Service

fce62566edc8431e2c512b2c7b782925ecac0e39
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / pb_ds / detail / map_debug_base.hpp
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 <regression/res_mng/dbg_ex_allocator.hpp>
55 #include <debug/debug.h>
56
57 namespace 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       pb_ds::test::dbg_ex_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       pb_ds::test::dbg_ex_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       pb_ds::test::dbg_ex_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