l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/ext/pb_ds/detail/debug_map_base.hpp

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