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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2024 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 detail/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, typename 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     /// Debug base class.
  71     template<typename Key, typename Eq_Fn, typename Const_Key_Reference>
  72     class debug_map_base
  73     {
  74     private:
  75       typedef Const_Key_Reference                       key_const_reference;
  76       typedef std::_GLIBCXX_STD_C::list<Key>            key_repository;
  77       typedef typename key_repository::size_type        size_type;
  78       typedef typename key_repository::iterator         iterator;
  79       typedef typename key_repository::const_iterator   const_iterator;
  80
  81     protected:
  82       debug_map_base();
  83
  84       debug_map_base(const PB_DS_CLASS_C_DEC&);
  85
  86       ~debug_map_base();
  87
  88       inline void
  89       insert_new(key_const_reference);
  90
  91       inline void
  92       erase_existing(key_const_reference);
  93
  94       void
  95       clear();
  96
  97       inline void
  98       check_key_exists(key_const_reference, const char*, int) const;
  99
 100       inline void
 101       check_key_does_not_exist(key_const_reference, const char*, int) const;
 102
 103       inline void
 104       check_size(size_type, const char*, int) const;
 105
 106       void
 107       swap(PB_DS_CLASS_C_DEC&);
 108
 109       template<typename Cmp_Fn>
 110       void
 111       split(key_const_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
 112
 113       void
 114       join(PB_DS_CLASS_C_DEC&, bool with_cleanup = true);
 115
 116     private:
 117       void
 118       assert_valid(const char*, int) const;
 119
 120       const_iterator
 121       find(key_const_reference) const;
 122
 123       iterator
 124       find(key_const_reference);
 125
 126       key_repository    m_keys;
 127       Eq_Fn             m_eq;
 128     };
 129
 130     PB_DS_CLASS_T_DEC
 131     PB_DS_CLASS_C_DEC::
 132     debug_map_base()
 133     { PB_DS_ASSERT_VALID((*this)) }
 134
 135     PB_DS_CLASS_T_DEC
 136     PB_DS_CLASS_C_DEC::
 137     debug_map_base(const PB_DS_CLASS_C_DEC& other)
 138     : m_keys(other.m_keys), m_eq(other.m_eq)
 139     { PB_DS_ASSERT_VALID((*this)) }
 140
 141     PB_DS_CLASS_T_DEC
 142     PB_DS_CLASS_C_DEC::
 143     ~debug_map_base()
 144     { PB_DS_ASSERT_VALID((*this)) }
 145
 146     PB_DS_CLASS_T_DEC
 147     inline void
 148     PB_DS_CLASS_C_DEC::
 149     insert_new(key_const_reference r_key)
 150     {
 151       PB_DS_ASSERT_VALID((*this))
 152
 153       if (find(r_key) != m_keys.end())
 154         {
 155           std::cerr << "insert_new key already present " << r_key << std::endl;
 156           std::abort();
 157         }
 158
 159       __try
 160         {
 161           m_keys.push_back(r_key);
 162         }
 163       __catch(...)
 164         {
 165           std::cerr << "insert_new " << r_key << std::endl;
 166           std::abort();
 167         }
 168
 169       PB_DS_ASSERT_VALID((*this))
 170     }
 171
 172     PB_DS_CLASS_T_DEC
 173     inline void
 174     PB_DS_CLASS_C_DEC::
 175     erase_existing(key_const_reference r_key)
 176     {
 177       PB_DS_ASSERT_VALID((*this))
 178       iterator it = find(r_key);
 179       if (it == m_keys.end())
 180         {
 181           std::cerr << "erase_existing" << r_key << std::endl;
 182           std::abort();
 183         }
 184       m_keys.erase(it);
 185       PB_DS_ASSERT_VALID((*this))
 186     }
 187
 188     PB_DS_CLASS_T_DEC
 189     void
 190     PB_DS_CLASS_C_DEC::
 191     clear()
 192     {
 193       PB_DS_ASSERT_VALID((*this))
 194       m_keys.clear();
 195       PB_DS_ASSERT_VALID((*this))
 196     }
 197
 198     PB_DS_CLASS_T_DEC
 199     inline void
 200     PB_DS_CLASS_C_DEC::
 201     check_key_exists(key_const_reference r_key,
 202                      const char* __file, int __line) const
 203     {
 204       assert_valid(__file, __line);
 205       if (find(r_key) == m_keys.end())
 206         {
 207           std::cerr << __file << ':' << __line << ": check_key_exists "
 208                     << r_key << std::endl;
 209           std::abort();
 210         }
 211     }
 212
 213     PB_DS_CLASS_T_DEC
 214     inline void
 215     PB_DS_CLASS_C_DEC::
 216     check_key_does_not_exist(key_const_reference r_key,
 217                              const char* __file, int __line) const
 218     {
 219       assert_valid(__file, __line);
 220       if (find(r_key) != m_keys.end())
 221         {
 222           using std::cerr;
 223           using std::endl;
 224           cerr << __file << ':' << __line << ": check_key_does_not_exist "
 225                << r_key << endl;
 226           std::abort();
 227         }
 228     }
 229
 230     PB_DS_CLASS_T_DEC
 231     inline void
 232     PB_DS_CLASS_C_DEC::
 233     check_size(size_type size, const char* __file, int __line) const
 234     {
 235       assert_valid(__file, __line);
 236       const size_type keys_size = m_keys.size();
 237       if (size != keys_size)
 238         {
 239           std::cerr << __file << ':' << __line << ": check_size "
 240                     << size << " != " << keys_size << std::endl;
 241           std::abort();
 242         }
 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       PB_DS_ASSERT_VALID((*this))
 251       m_keys.swap(other.m_keys);
 252       std::swap(m_eq, other.m_eq);
 253       PB_DS_ASSERT_VALID((*this))
 254     }
 255
 256     PB_DS_CLASS_T_DEC
 257     typename PB_DS_CLASS_C_DEC::const_iterator
 258     PB_DS_CLASS_C_DEC::
 259     find(key_const_reference r_key) const
 260     {
 261       PB_DS_ASSERT_VALID((*this))
 262       typedef const_iterator iterator_type;
 263       for (iterator_type it = m_keys.begin(); it != m_keys.end(); ++it)
 264         if (m_eq(*it, r_key))
 265           return it;
 266       return m_keys.end();
 267     }
 268
 269     PB_DS_CLASS_T_DEC
 270     typename PB_DS_CLASS_C_DEC::iterator
 271     PB_DS_CLASS_C_DEC::
 272     find(key_const_reference r_key)
 273     {
 274       PB_DS_ASSERT_VALID((*this))
 275       iterator it = m_keys.begin();
 276       while (it != m_keys.end())
 277         {
 278           if (m_eq(*it, r_key))
 279             return it;
 280           ++it;
 281         }
 282       return it;
 283      }
 284
 285     PB_DS_CLASS_T_DEC
 286     void
 287     PB_DS_CLASS_C_DEC::
 288     assert_valid(const char* __file, int __line) const
 289     {
 290       const_iterator prime_it = m_keys.begin();
 291       while (prime_it != m_keys.end())
 292         {
 293           const_iterator sec_it = prime_it;
 294           ++sec_it;
 295           while (sec_it != m_keys.end())
 296             {
 297               PB_DS_DEBUG_VERIFY(!m_eq(*sec_it, *prime_it));
 298               PB_DS_DEBUG_VERIFY(!m_eq(*prime_it, *sec_it));
 299               ++sec_it;
 300             }
 301           ++prime_it;
 302         }
 303     }
 304
 305     PB_DS_CLASS_T_DEC
 306     template<typename Cmp_Fn>
 307     void
 308     PB_DS_CLASS_C_DEC::
 309     split(key_const_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
 310     {
 311       other.clear();
 312       iterator it = m_keys.begin();
 313       while (it != m_keys.end())
 314         if (cmp_fn(r_key, *it))
 315           {
 316             other.insert_new(*it);
 317             it = m_keys.erase(it);
 318           }
 319         else
 320           ++it;
 321     }
 322
 323     PB_DS_CLASS_T_DEC
 324     void
 325     PB_DS_CLASS_C_DEC::
 326     join(PB_DS_CLASS_C_DEC& other, bool with_cleanup)
 327     {
 328       iterator it = other.m_keys.begin();
 329       while (it != other.m_keys.end())
 330         {
 331           insert_new(*it);
 332           if (with_cleanup)
 333             it = other.m_keys.erase(it);
 334           else
 335             ++it;
 336         }
 337       _GLIBCXX_DEBUG_ASSERT(!with_cleanup || other.m_keys.empty());
 338     }
 339
 340 #undef PB_DS_CLASS_T_DEC
 341 #undef PB_DS_CLASS_C_DEC
 342
 343 } // namespace detail
 344 } // namespace __gnu_pbds
 345
 346
 347 #endif
 348
 349 #endif