mingw/lib/gcc/mingw32/4.3.3/include/c++/ext/pb_ds/detail/debug_map_base.hpp

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