contrib/gcc-4.4/libstdc++-v3/include/ext/pb_ds/detail/debug_map_base.hpp

   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>
  59     inline std::basic_ostream<_CharT, _Traits>&
  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();)
 156       __gnu_cxx::throw_allocator<char> alloc;
 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     {
 317       __gnu_cxx::throw_allocator<char> alloc;
 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     {
 338       __gnu_cxx::throw_allocator<char> alloc;
 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