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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file detail/debug_map_base.hpp
  39  * Contains a debug-mode base for all maps.
  40  */
  41
  42 #ifndef PB_DS_DEBUG_MAP_BASE_HPP
  43 #define PB_DS_DEBUG_MAP_BASE_HPP
  44
  45 #ifdef _GLIBCXX_DEBUG
  46
  47 #include <list>
  48 #include <utility>
  49 #include <cstdlib>
  50 #include <iostream>
  51 #include <ext/throw_allocator.h>
  52 #include <debug/debug.h>
  53
  54 namespace __gnu_pbds
  55 {
  56   namespace detail
  57   {
  58     // Need std::pair ostream extractor.
  59     template<typename _CharT, typename _Traits, typename _Tp1, typename _Tp2>
  60     inline std::basic_ostream<_CharT, _Traits>&
  61     operator<<(std::basic_ostream<_CharT, _Traits>& __out,
  62                const std::pair<_Tp1, _Tp2>& p)
  63     { return (__out << '(' << p.first << ',' << p.second << ')'); }
  64
  65 #define PB_DS_CLASS_T_DEC \
  66     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
  67
  68 #define PB_DS_CLASS_C_DEC \
  69     debug_map_base<Key, Eq_Fn, Const_Key_Reference>
  70
  71     /// Debug base class.
  72     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
  73     class debug_map_base
  74     {
  75     private:
  76       typedef Const_Key_Reference                       key_const_reference;
  77       typedef std::_GLIBCXX_STD_C::list<Key>            key_repository;
  78       typedef typename key_repository::size_type        size_type;
  79       typedef typename key_repository::iterator         iterator;
  80       typedef typename key_repository::const_iterator   const_iterator;
  81
  82     protected:
  83       debug_map_base();
  84
  85       debug_map_base(const PB_DS_CLASS_C_DEC&);
  86
  87       ~debug_map_base();
  88
  89       inline void
  90       insert_new(key_const_reference);
  91
  92       inline void
  93       erase_existing(key_const_reference);
  94
  95       void
  96       clear();
  97
  98       inline void
  99       check_key_exists(key_const_reference, const char*, int) const;
 100
 101       inline void
 102       check_key_does_not_exist(key_const_reference, const char*, int) const;
 103
 104       inline void
 105       check_size(size_type, const char*, int) const;
 106
 107       void
 108       swap(PB_DS_CLASS_C_DEC&);
 109
 110       template<typename Cmp_Fn>
 111       void
 112       split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
 113
 114       void
 115       join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true);
 116
 117     private:
 118       void
 119       assert_valid(const char*, int) const;
 120
 121       const_iterator
 122       find(key_const_reference) const;
 123
 124       iterator
 125       find(key_const_reference);
 126
 127       key_repository    m_keys;
 128       Eq_Fn             m_eq;
 129     };
 130
 131     PB_DS_CLASS_T_DEC
 132     PB_DS_CLASS_C_DEC::
 133     debug_map_base()
 134     { PB_DS_ASSERT_VALID((*this)) }
 135
 136     PB_DS_CLASS_T_DEC
 137     PB_DS_CLASS_C_DEC::
 138     debug_map_base(const PB_DS_CLASS_C_DEC& other)
 139     : m_keys(other.m_keys), m_eq(other.m_eq)
 140     { PB_DS_ASSERT_VALID((*this)) }
 141
 142     PB_DS_CLASS_T_DEC
 143     PB_DS_CLASS_C_DEC::
 144     ~debug_map_base()
 145     { PB_DS_ASSERT_VALID((*this)) }
 146
 147     PB_DS_CLASS_T_DEC
 148     inline void
 149     PB_DS_CLASS_C_DEC::
 150     insert_new(key_const_reference r_key)
 151     {
 152       PB_DS_ASSERT_VALID((*this))
 153
 154       if (find(r_key) != m_keys.end())
 155         {
 156           std::cerr << "insert_new key already present " << r_key << std::endl;
 157           std::abort();
 158         }
 159
 160       __try
 161         {
 162           m_keys.push_back(r_key);
 163         }
 164       __catch(...)
 165         {
 166           std::cerr << "insert_new " << r_key << std::endl;
 167           std::abort();
 168         }
 169
 170       PB_DS_ASSERT_VALID((*this))
 171     }
 172
 173     PB_DS_CLASS_T_DEC
 174     inline void
 175     PB_DS_CLASS_C_DEC::
 176     erase_existing(key_const_reference r_key)
 177     {
 178       PB_DS_ASSERT_VALID((*this))
 179       iterator it = find(r_key);
 180       if (it == m_keys.end())
 181         {
 182           std::cerr << "erase_existing" << r_key << std::endl;
 183           std::abort();
 184         }
 185       m_keys.erase(it);
 186       PB_DS_ASSERT_VALID((*this))
 187     }
 188
 189     PB_DS_CLASS_T_DEC
 190     void
 191     PB_DS_CLASS_C_DEC::
 192     clear()
 193     {
 194       PB_DS_ASSERT_VALID((*this))
 195       m_keys.clear();
 196       PB_DS_ASSERT_VALID((*this))
 197     }
 198
 199     PB_DS_CLASS_T_DEC
 200     inline void
 201     PB_DS_CLASS_C_DEC::
 202     check_key_exists(key_const_reference r_key,
 203                      const char* __file, int __line) const
 204     {
 205       assert_valid(__file, __line);
 206       if (find(r_key) == m_keys.end())
 207         {
 208           std::cerr << __file << ':' << __line << ": check_key_exists "
 209                     << r_key << std::endl;
 210           std::abort();
 211         }
 212     }
 213
 214     PB_DS_CLASS_T_DEC
 215     inline void
 216     PB_DS_CLASS_C_DEC::
 217     check_key_does_not_exist(key_const_reference r_key,
 218                              const char* __file, int __line) const
 219     {
 220       assert_valid(__file, __line);
 221       if (find(r_key) != m_keys.end())
 222         {
 223           using std::cerr;
 224           using std::endl;
 225           cerr << __file << ':' << __line << ": check_key_does_not_exist "
 226                << r_key << endl;
 227           std::abort();
 228         }
 229     }
 230
 231     PB_DS_CLASS_T_DEC
 232     inline void
 233     PB_DS_CLASS_C_DEC::
 234     check_size(size_type size, const char* __file, int __line) const
 235     {
 236       assert_valid(__file, __line);
 237       const size_type keys_size = m_keys.size();
 238       if (size != keys_size)
 239         {
 240           std::cerr << __file << ':' << __line << ": check_size "
 241                     << size << " != " << keys_size << std::endl;
 242           std::abort();
 243         }
 244      }
 245
 246     PB_DS_CLASS_T_DEC
 247     void
 248     PB_DS_CLASS_C_DEC::
 249     swap(PB_DS_CLASS_C_DEC& other)
 250     {
 251       PB_DS_ASSERT_VALID((*this))
 252       m_keys.swap(other.m_keys);
 253       std::swap(m_eq, other.m_eq);
 254       PB_DS_ASSERT_VALID((*this))
 255     }
 256
 257     PB_DS_CLASS_T_DEC
 258     typename PB_DS_CLASS_C_DEC::const_iterator
 259     PB_DS_CLASS_C_DEC::
 260     find(key_const_reference r_key) const
 261     {
 262       PB_DS_ASSERT_VALID((*this))
 263       typedef const_iterator iterator_type;
 264       for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it)
 265         if (m_eq(*it, r_key))
 266           return it;
 267       return m_keys.end();
 268     }
 269
 270     PB_DS_CLASS_T_DEC
 271     typename PB_DS_CLASS_C_DEC::iterator
 272     PB_DS_CLASS_C_DEC::
 273     find(key_const_reference r_key)
 274     {
 275       PB_DS_ASSERT_VALID((*this))
 276       iterator it = m_keys.begin();
 277       while (it != m_keys.end())
 278         {
 279           if (m_eq(*it, r_key))
 280             return it;
 281           ++it;
 282         }
 283       return it;
 284      }
 285
 286     PB_DS_CLASS_T_DEC
 287     void
 288     PB_DS_CLASS_C_DEC::
 289     assert_valid(const char* __file, int __line) const
 290     {
 291       const_iterator prime_it = m_keys.begin();
 292       while (prime_it != m_keys.end())
 293         {
 294           const_iterator sec_it = prime_it;
 295           ++sec_it;
 296           while (sec_it != m_keys.end())
 297             {
 298               PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it));
 299               PB_DS_DEBUG_VERIFY(!m_eq(*prime_it, *sec_it));
 300               ++sec_it;
 301             }
 302           ++prime_it;
 303         }
 304     }
 305
 306     PB_DS_CLASS_T_DEC
 307     template<typename Cmp_Fn>
 308     void
 309     PB_DS_CLASS_C_DEC::
 310     split(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
 311     {
 312       other.clear();
 313       iterator it = m_keys.begin();
 314       while (it != m_keys.end())
 315         if (cmp_fn(r_key, *it))
 316           {
 317             other.insert_new(*it);
 318             it = m_keys.erase(it);
 319           }
 320         else
 321           ++it;
 322     }
 323
 324     PB_DS_CLASS_T_DEC
 325     void
 326     PB_DS_CLASS_C_DEC::
 327     join(PB_DS_CLASS_C_DEC& other, bool with_cleanup)
 328     {
 329       iterator it = other.m_keys.begin();
 330       while (it != other.m_keys.end())
 331         {
 332           insert_new(*it);
 333           if (with_cleanup)
 334             it = other.m_keys.erase(it);
 335           else
 336             ++it;
 337         }
 338       _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty());
 339     }
 340
 341 #undef PB_DS_CLASS_T_DEC
 342 #undef PB_DS_CLASS_C_DEC
 343
 344 } // namespace detail
 345 } // namespace __gnu_pbds
 346
 347
 348 #endif
 349
 350 #endif