libstdc++-v3/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 PB_DS_USE_MAP_DEBUG_BASE
  51
  52 #include <assert.h>
  53 #include <list>
  54 #include <utility>
  55 #include <pb_ds/testsuite/regression/res_mng/dbg_ex_allocator.hpp>
  56
  57 namespace pb_ds
  58 {
  59
  60   namespace detail
  61   {
  62
  63 #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
  64 #define PB_DS_DBG_ASSERT(X) assert(X)
  65 #define PB_DS_DBG_VERIFY(X) assert(X)
  66 #define PB_DS_DBG_ONLY(X) X
  67 #else // #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
  68 #define PB_DS_DBG_ASSERT(X)
  69 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
  70 #define PB_DS_DBG_ONLY(X) ;
  71 #endif // #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
  72
  73 #define PB_DS_CLASS_T_DEC                                               \
  74     template<typename Key, class Eq_Fn, typename Const_Key_Reference>
  75
  76 #define PB_DS_CLASS_C_DEC                                               \
  77     map_debug_base<                                                     \
  78                                                 Key,                    \
  79                                                 Eq_Fn,                  \
  80                                                 Const_Key_Reference>
  81
  82     template<typename Key, class Eq_Fn, typename Const_Key_Reference>
  83     class map_debug_base
  84     {
  85     private:
  86       typedef typename std::allocator< Key> key_allocator;
  87
  88       typedef typename key_allocator::size_type size_type;
  89
  90       typedef Const_Key_Reference const_key_reference;
  91
  92     protected:
  93       map_debug_base();
  94
  95       map_debug_base(const PB_DS_CLASS_C_DEC& other);
  96
  97       ~map_debug_base();
  98
  99       inline void
 100       insert_new(const_key_reference r_key);
 101
 102       inline void
 103       erase_existing(const_key_reference r_key);
 104
 105       void
 106       clear();
 107
 108       inline void
 109       check_key_exists(const_key_reference r_key) const;
 110
 111       inline void
 112       check_key_does_not_exist(const_key_reference r_key) const;
 113
 114       inline void
 115       check_size(size_type size) const;
 116
 117       void
 118       swap(PB_DS_CLASS_C_DEC& other);
 119
 120       template<typename Cmp_Fn>
 121       void
 122       split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other);
 123
 124       void
 125       join(PB_DS_CLASS_C_DEC& other);
 126
 127     private:
 128       typedef std::list< Key> key_set;
 129
 130       typedef typename key_set::iterator key_set_iterator;
 131
 132       typedef typename key_set::const_iterator const_key_set_iterator;
 133
 134     private:
 135 #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
 136       void
 137       assert_valid() const;
 138 #endif // #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
 139
 140       const_key_set_iterator
 141       find(const_key_reference r_key) const;
 142
 143       key_set_iterator
 144       find(const_key_reference r_key);
 145
 146     private:
 147       key_set m_key_set;
 148
 149       Eq_Fn m_eq;
 150     };
 151
 152     PB_DS_CLASS_T_DEC
 153     PB_DS_CLASS_C_DEC::
 154     map_debug_base()
 155     {
 156       PB_DS_DBG_ONLY(assert_valid();)
 157         }
 158
 159     PB_DS_CLASS_T_DEC
 160     PB_DS_CLASS_C_DEC::
 161     map_debug_base(const PB_DS_CLASS_C_DEC& other) :
 162       m_key_set(other.m_key_set)
 163     {
 164       PB_DS_DBG_ONLY(assert_valid();)
 165         }
 166
 167     PB_DS_CLASS_T_DEC
 168     PB_DS_CLASS_C_DEC::
 169     ~map_debug_base()
 170     {
 171       PB_DS_DBG_ONLY(assert_valid();)
 172         }
 173
 174     PB_DS_CLASS_T_DEC
 175     inline void
 176     PB_DS_CLASS_C_DEC::
 177     insert_new(const_key_reference r_key)
 178     {
 179       PB_DS_DBG_ONLY(assert_valid();)
 180
 181         pb_ds::test::dbg_ex_allocator<char> alloc;
 182
 183       const double orig_throw_prob = alloc.get_throw_prob();
 184
 185       alloc.set_throw_prob(0);
 186
 187       if (find(r_key) != m_key_set.end())
 188         {
 189           std::cerr << "insert_new " << r_key << std::endl;
 190
 191           abort();
 192         }
 193
 194       try
 195         {
 196           m_key_set.push_back(r_key);
 197         }
 198       catch(...)
 199         {
 200           std::cerr << "insert_new 1" << r_key << std::endl;
 201
 202           abort();
 203         }
 204
 205       alloc.set_throw_prob(orig_throw_prob);
 206
 207       PB_DS_DBG_ONLY(assert_valid();)
 208         }
 209
 210     PB_DS_CLASS_T_DEC
 211     inline void
 212     PB_DS_CLASS_C_DEC::
 213     erase_existing(const_key_reference r_key)
 214     {
 215       PB_DS_DBG_ONLY(assert_valid();)
 216
 217         key_set_iterator it = find(r_key);
 218
 219       if (it == m_key_set.end())
 220         {
 221           std::cerr << "erase_existing " << r_key << std::endl;
 222
 223           abort();
 224         }
 225
 226       m_key_set.erase(it);
 227
 228       PB_DS_DBG_ONLY(assert_valid();)
 229         }
 230
 231     PB_DS_CLASS_T_DEC
 232     void
 233     PB_DS_CLASS_C_DEC::
 234     clear()
 235     {
 236       PB_DS_DBG_ONLY(assert_valid();)
 237
 238         m_key_set.clear();
 239
 240       PB_DS_DBG_ONLY(assert_valid();)
 241         }
 242
 243     PB_DS_CLASS_T_DEC
 244     inline void
 245     PB_DS_CLASS_C_DEC::
 246     check_key_exists(const_key_reference r_key) const
 247     {
 248       PB_DS_DBG_ONLY(assert_valid();)
 249
 250         if (find(r_key) == m_key_set.end())
 251           {
 252             std::cerr << "check_key_exists " << r_key << std::endl;
 253
 254             abort();
 255           }
 256
 257       PB_DS_DBG_ONLY(assert_valid();)
 258         }
 259
 260     PB_DS_CLASS_T_DEC
 261     inline void
 262     PB_DS_CLASS_C_DEC::
 263     check_key_does_not_exist(const_key_reference r_key) const
 264     {
 265       PB_DS_DBG_ONLY(assert_valid();)
 266
 267         if (find(r_key) != m_key_set.end())
 268           {
 269             std::cerr << "check_key_does_not_exist " << r_key << std::endl;
 270
 271             abort();
 272           }
 273     }
 274
 275     PB_DS_CLASS_T_DEC
 276     inline void
 277     PB_DS_CLASS_C_DEC::
 278     check_size(size_type size) const
 279     {
 280       PB_DS_DBG_ONLY(assert_valid();)
 281
 282         const size_type key_set_size = m_key_set.size();
 283
 284       if (size != key_set_size)
 285         {
 286           std::cerr << "check_size " << size << " " << key_set_size << std::endl;
 287
 288           abort();
 289         }
 290
 291       PB_DS_DBG_ONLY(assert_valid();)
 292         }
 293
 294     PB_DS_CLASS_T_DEC
 295     void
 296     PB_DS_CLASS_C_DEC::
 297     swap(PB_DS_CLASS_C_DEC& other)
 298     {
 299       PB_DS_DBG_ONLY(assert_valid();)
 300
 301         m_key_set.swap(other.m_key_set);
 302
 303       PB_DS_DBG_ONLY(assert_valid();)
 304         }
 305
 306     PB_DS_CLASS_T_DEC
 307     typename PB_DS_CLASS_C_DEC::const_key_set_iterator
 308     PB_DS_CLASS_C_DEC::
 309     find(const_key_reference r_key) const
 310     {
 311       PB_DS_DBG_ONLY(assert_valid();)
 312
 313         for (const_key_set_iterator it = m_key_set.begin(); it != m_key_set.end();
 314              ++it)
 315           if (m_eq(*it, r_key))
 316             return (it);
 317
 318       return (m_key_set.end());
 319     }
 320
 321     PB_DS_CLASS_T_DEC
 322     typename PB_DS_CLASS_C_DEC::key_set_iterator
 323     PB_DS_CLASS_C_DEC::
 324     find(const_key_reference r_key)
 325     {
 326       PB_DS_DBG_ONLY(assert_valid();)
 327
 328         key_set_iterator it = m_key_set.begin();
 329
 330       while (it != m_key_set.end())
 331         {
 332           if (m_eq(*it, r_key))
 333             return (it);
 334
 335           ++it;
 336         }
 337
 338       return (it);
 339
 340       PB_DS_DBG_ONLY(assert_valid();)
 341         }
 342
 343 #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
 344     PB_DS_CLASS_T_DEC
 345     void
 346     PB_DS_CLASS_C_DEC::
 347     assert_valid() const
 348     {
 349       const_key_set_iterator prime_it = m_key_set.begin();
 350
 351       while (prime_it != m_key_set.end())
 352         {
 353           const_key_set_iterator sec_it = prime_it;
 354
 355           ++sec_it;
 356
 357           while (sec_it != m_key_set.end())
 358             {
 359               assert(!m_eq(*sec_it, * prime_it));
 360               assert(!m_eq(*prime_it, * sec_it));
 361
 362               ++sec_it;
 363             }
 364
 365           ++prime_it;
 366         }
 367     }
 368 #endif // #ifdef PB_DS_MAP_DEBUG_BASE_DEBUG
 369
 370     PB_DS_CLASS_T_DEC
 371     template<typename Cmp_Fn>
 372     void
 373     PB_DS_CLASS_C_DEC::
 374     split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
 375     {
 376       pb_ds::test::dbg_ex_allocator<char> alloc;
 377
 378       const double orig_throw_prob = alloc.get_throw_prob();
 379
 380       alloc.set_throw_prob(0);
 381
 382       other.clear();
 383
 384       key_set_iterator it = m_key_set.begin();
 385
 386       while (it != m_key_set.end())
 387         if (cmp_fn(r_key, * it))
 388           {
 389             other.insert_new(*it);
 390
 391             it = m_key_set.erase(it);
 392           }
 393         else
 394           ++it;
 395
 396       alloc.set_throw_prob(orig_throw_prob);
 397     }
 398
 399     PB_DS_CLASS_T_DEC
 400     void
 401     PB_DS_CLASS_C_DEC::
 402     join(PB_DS_CLASS_C_DEC& other)
 403     {
 404       pb_ds::test::dbg_ex_allocator<char> alloc;
 405
 406       const double orig_throw_prob = alloc.get_throw_prob();
 407
 408       alloc.set_throw_prob(0);
 409
 410       key_set_iterator it = other.m_key_set.begin();
 411
 412       while (it != other.m_key_set.end())
 413         {
 414           insert_new(*it);
 415
 416           it = other.m_key_set.erase(it);
 417         }
 418
 419       PB_DS_DBG_ASSERT(other.m_key_set.empty());
 420
 421       alloc.set_throw_prob(orig_throw_prob);
 422     }
 423
 424 #undef PB_DS_CLASS_T_DEC
 425 #undef PB_DS_CLASS_C_DEC
 426
 427 #undef PB_DS_DBG_ASSERT
 428 #undef PB_DS_DBG_VERIFY
 429 #undef PB_DS_DBG_ONLY
 430
 431   } // namespace detail
 432
 433 } // namespace pb_ds
 434
 435 #endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
 436
 437 #endif // #ifndef PB_DS_MAP_DEBUG_BASE_HPP
 438