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