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