contrib/libstdc++/include/ext/pb_ds/detail/map_debug_base.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 map_debug_base.hpp
  44  * Contains a debug-mode base for all maps.
  45  */
  46
  47 #ifndef PB_DS_MAP_DEBUG_BASE_HPP
  48 #define PB_DS_MAP_DEBUG_BASE_HPP
  49
  50 #ifdef _GLIBCXX_DEBUG
  51
  52 #include <list>
  53 #include <utility>
  54 #include <ext/throw_allocator.h>
  55 #include <debug/debug.h>
  56
  57 namespace pb_ds
  58 {
  59   namespace detail
  60   {
  61
  62 #define PB_DS_CLASS_T_DEC \
  63     template<typename Key, class Eq_Fn, typename Const_Key_Reference>
  64
  65 #define PB_DS_CLASS_C_DEC \
  66     map_debug_base<Key, Eq_Fn, Const_Key_Reference>
  67
  68     template<typename Key, class Eq_Fn, typename Const_Key_Reference>
  69     class map_debug_base
  70     {
  71     private:
  72       typedef typename std::allocator< Key> key_allocator;
  73
  74       typedef typename key_allocator::size_type size_type;
  75
  76       typedef Const_Key_Reference const_key_reference;
  77
  78     protected:
  79       map_debug_base();
  80
  81       map_debug_base(const PB_DS_CLASS_C_DEC& other);
  82
  83       ~map_debug_base();
  84
  85       inline void
  86       insert_new(const_key_reference r_key);
  87
  88       inline void
  89       erase_existing(const_key_reference r_key);
  90
  91       void
  92       clear();
  93
  94       inline void
  95       check_key_exists(const_key_reference r_key) const;
  96
  97       inline void
  98       check_key_does_not_exist(const_key_reference r_key) const;
  99
 100       inline void
 101       check_size(size_type size) const;
 102
 103       void
 104       swap(PB_DS_CLASS_C_DEC& other);
 105
 106       template<typename Cmp_Fn>
 107       void
 108       split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);
 109
 110       void
 111       join(PB_DS_CLASS_C_DEC& other);
 112
 113     private:
 114       typedef std::list< Key>                   key_set;
 115       typedef typename key_set::iterator        key_set_iterator;
 116       typedef typename key_set::const_iterator  const_key_set_iterator;
 117
 118 #ifdef _GLIBCXX_DEBUG
 119       void
 120       assert_valid() const;
 121 #endif
 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     map_debug_base()
 136     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
 137
 138     PB_DS_CLASS_T_DEC
 139     PB_DS_CLASS_C_DEC::
 140     map_debug_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     ~map_debug_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       __gnu_cxx::throw_allocator<char> alloc;
 155       const double orig_throw_prob = alloc.get_throw_prob();
 156       alloc.set_throw_prob(0);
 157       if (find(r_key) != m_key_set.end())
 158         {
 159           std::cerr << "insert_new " << r_key << std::endl;
 160           abort();
 161         }
 162
 163       try
 164         {
 165           m_key_set.push_back(r_key);
 166         }
 167       catch(...)
 168         {
 169           std::cerr << "insert_new 1" << r_key << std::endl;
 170           abort();
 171         }
 172       alloc.set_throw_prob(orig_throw_prob);
 173       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 174     }
 175
 176     PB_DS_CLASS_T_DEC
 177     inline void
 178     PB_DS_CLASS_C_DEC::
 179     erase_existing(const_key_reference r_key)
 180     {
 181       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 182       key_set_iterator it = find(r_key);
 183       if (it == m_key_set.end())
 184         {
 185           std::cerr << "erase_existing " << r_key << std::endl;
 186           abort();
 187         }
 188       m_key_set.erase(it);
 189       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 190     }
 191
 192     PB_DS_CLASS_T_DEC
 193     void
 194     PB_DS_CLASS_C_DEC::
 195     clear()
 196     {
 197       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 198       m_key_set.clear();
 199       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 200     }
 201
 202     PB_DS_CLASS_T_DEC
 203     inline void
 204     PB_DS_CLASS_C_DEC::
 205     check_key_exists(const_key_reference r_key) const
 206     {
 207       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 208       if (find(r_key) == m_key_set.end())
 209         {
 210           std::cerr << "check_key_exists " << r_key << std::endl;
 211           abort();
 212         }
 213       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 214     }
 215
 216     PB_DS_CLASS_T_DEC
 217     inline void
 218     PB_DS_CLASS_C_DEC::
 219     check_key_does_not_exist(const_key_reference r_key) const
 220     {
 221       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 222       if (find(r_key) != m_key_set.end())
 223         {
 224           std::cerr << "check_key_does_not_exist " << r_key << std::endl;
 225           abort();
 226         }
 227     }
 228
 229     PB_DS_CLASS_T_DEC
 230     inline void
 231     PB_DS_CLASS_C_DEC::
 232     check_size(size_type size) const
 233     {
 234       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 235       const size_type key_set_size = m_key_set.size();
 236       if (size != key_set_size)
 237         {
 238           std::cerr << "check_size " << size
 239                     << " " << key_set_size << std::endl;
 240           abort();
 241         }
 242       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 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       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 251       m_key_set.swap(other.m_key_set);
 252       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 253     }
 254
 255     PB_DS_CLASS_T_DEC
 256     typename PB_DS_CLASS_C_DEC::const_key_set_iterator
 257     PB_DS_CLASS_C_DEC::
 258     find(const_key_reference r_key) const
 259     {
 260       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 261       typedef const_key_set_iterator iterator_type;
 262       for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
 263         if (m_eq(*it, r_key))
 264           return it;
 265       return m_key_set.end();
 266     }
 267
 268     PB_DS_CLASS_T_DEC
 269     typename PB_DS_CLASS_C_DEC::key_set_iterator
 270     PB_DS_CLASS_C_DEC::
 271     find(const_key_reference r_key)
 272     {
 273       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 274       key_set_iterator it = m_key_set.begin();
 275       while (it != m_key_set.end())
 276         {
 277           if (m_eq(*it, r_key))
 278             return it;
 279           ++it;
 280         }
 281       return it;
 282       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 283      }
 284
 285 #ifdef _GLIBCXX_DEBUG
 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 #endif
 306
 307     PB_DS_CLASS_T_DEC
 308     template<typename Cmp_Fn>
 309     void
 310     PB_DS_CLASS_C_DEC::
 311     split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
 312     {
 313       __gnu_cxx::throw_allocator<char> alloc;
 314       const double orig_throw_prob = alloc.get_throw_prob();
 315       alloc.set_throw_prob(0);
 316       other.clear();
 317       key_set_iterator it = m_key_set.begin();
 318       while (it != m_key_set.end())
 319         if (cmp_fn(r_key, * it))
 320           {
 321             other.insert_new(*it);
 322             it = m_key_set.erase(it);
 323           }
 324         else
 325           ++it;
 326       alloc.set_throw_prob(orig_throw_prob);
 327     }
 328
 329     PB_DS_CLASS_T_DEC
 330     void
 331     PB_DS_CLASS_C_DEC::
 332     join(PB_DS_CLASS_C_DEC& other)
 333     {
 334       __gnu_cxx::throw_allocator<char> alloc;
 335       const double orig_throw_prob = alloc.get_throw_prob();
 336       alloc.set_throw_prob(0);
 337       key_set_iterator it = other.m_key_set.begin();
 338       while (it != other.m_key_set.end())
 339         {
 340           insert_new(*it);
 341           it = other.m_key_set.erase(it);
 342         }
 343       _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
 344       alloc.set_throw_prob(orig_throw_prob);
 345     }
 346
 347 #undef PB_DS_CLASS_T_DEC
 348 #undef PB_DS_CLASS_C_DEC
 349
 350 } // namespace detail
 351 } // namespace pb_ds
 352
 353 #endif
 354
 355 #endif
 356