old-autovect-branch/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/ov_tree_map_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file ov_tree_map_.hpp
  42  * Contains an implementation class for ov_tree_.
  43  */
  44
  45 #include <map>
  46 #include <set>
  47 #include <ext/pb_assoc/trivial_iterator_def.hpp>
  48 #include <ext/pb_assoc/tree_policy.hpp>
  49 #include <ext/pb_assoc/detail/eq_fn/eq_by_less.hpp>
  50 #include <ext/pb_assoc/detail/types_traits.hpp>
  51 #include <ext/pb_assoc/detail/map_debug_base.hpp>
  52 #include <ext/pb_assoc/detail/type_utils.hpp>
  53 #include <ext/pb_assoc/exception.hpp>
  54 #include <utility>
  55 #include <functional>
  56 #include <algorithm>
  57 #include <vector>
  58 #include <cassert>
  59 #ifdef PB_ASSOC_BASIC_REGRESSION
  60 #include <pb_assoc/testsuite/regression/basic_test/throw_prob_adjustor.hpp>
  61 #endif // #ifdef PB_ASSOC_BASIC_REGRESSION
  62
  63 namespace pb_assoc
  64 {
  65
  66   namespace detail
  67   {
  68
  69 #ifdef PB_ASSOC_OV_TREE_DEBUG_
  70 #define PB_ASSOC_DBG_ASSERT(X) assert(X);
  71 #define PB_ASSOC_DBG_VERIFY(X) PB_ASSOC_DBG_ASSERT(X)
  72 #define PB_ASSOC_DBG_ONLY(X) X
  73 #else // #ifdef PB_ASSOC_OV_TREE_DEBUG_
  74 #define PB_ASSOC_DBG_ASSERT(X) ((void)0)
  75 #define PB_ASSOC_DBG_VERIFY(X) X
  76 #define PB_ASSOC_DBG_ONLY(X) ;
  77 #endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_
  78
  79 #define PB_ASSOC_CLASS_T_DEC \
  80         template< \
  81                 typename Key, \
  82                 typename Data, \
  83                 class Cmp_Fn, \
  84                 class Allocator, \
  85                 class Node_Updator>
  86
  87 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  88 #define PB_ASSOC_OV_TREE_CLASS_NAME \
  89         ov_tree_data_
  90 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  91
  92 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  93 #define PB_ASSOC_OV_TREE_CLASS_NAME \
  94         ov_tree_no_data_
  95 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  96
  97 #define PB_ASSOC_CLASS_C_DEC \
  98         PB_ASSOC_OV_TREE_CLASS_NAME< \
  99                 Key, \
 100                 Data, \
 101                 Cmp_Fn, \
 102                 Allocator, \
 103                 Node_Updator>
 104
 105 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
 106         types_traits< \
 107                 Key, \
 108                 Data, \
 109                 Allocator>
 110
 111 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 112 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
 113         pb_assoc::detail::map_debug_base< \
 114                 Key, \
 115                 eq_by_less<Key, Cmp_Fn> >
 116 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 117
 118 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 119 #define PB_ASSOC_V2F(X) (X).first
 120 #define PB_ASSOC_V2S(X) (X).second
 121 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
 122 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 123
 124 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 125 #define PB_ASSOC_V2F(X) (X)
 126 #define PB_ASSOC_V2S(X) Mapped_Data()
 127 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
 128 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 129
 130     template<typename Key,
 131              typename Data,
 132              class Cmp_Fn,
 133              class Allocator,
 134              class Node_Updator>
 135     class PB_ASSOC_OV_TREE_CLASS_NAME :
 136 #ifdef PB_ASSOC_OV_TREE_DEBUG_
 137       protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
 138 #endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_
 139       public Cmp_Fn,
 140       public PB_ASSOC_TYPES_TRAITS_C_DEC,
 141       public Node_Updator
 142     {
 143
 144     protected:
 145
 146       typedef typename Allocator::size_type size_type;
 147
 148       typedef typename Allocator::difference_type difference_type;
 149
 150       typedef
 151       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
 152       const_key_reference;
 153
 154       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
 155
 156       typedef
 157       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
 158       data_reference;
 159
 160       typedef
 161       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
 162       const_data_reference;
 163
 164       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
 165
 166       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
 167
 168       typedef
 169       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
 170       const_pointer;
 171
 172       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
 173
 174       typedef
 175       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
 176       const_reference;
 177
 178       typedef const_pointer const_find_iterator;
 179
 180       typedef pointer find_iterator;
 181
 182       typedef const_find_iterator const_iterator;
 183
 184       typedef find_iterator iterator;
 185
 186       typedef pointer value_pointer;
 187
 188 #include <ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp>
 189
 190 #include <ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp>
 191
 192       typedef Cmp_Fn cmp_fn;
 193
 194       typedef Allocator allocator;
 195
 196       typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
 197
 198       typedef cmp_fn my_cmp_fn_base;
 199
 200 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 201       typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
 202 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 203
 204     protected:
 205
 206       PB_ASSOC_OV_TREE_CLASS_NAME();
 207
 208       PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 209
 210       PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
 211
 212       PB_ASSOC_OV_TREE_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
 213
 214       ~PB_ASSOC_OV_TREE_CLASS_NAME();
 215
 216       void
 217       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 218
 219       template<class It>
 220       void
 221       copy_from_range(It first_it, It last_it);
 222
 223       template<class Node_Updator_>
 224       void
 225       update(node_iterator it, Node_Updator_* p_updator)
 226       {
 227         if (it == node_end())
 228           return;
 229
 230         update(it.l_child(), p_updator);
 231         update(it.r_child(), p_updator);
 232
 233         p_updator->operator()(it.m_p_value,(it.l_child() == node_end())? NULL : it.l_child().m_p_value,(it.r_child() == node_end())? NULL : it.r_child().m_p_value);
 234       }
 235
 236       inline void
 237       update(node_iterator /*it*/, pb_assoc::null_node_updator* )
 238       { }
 239
 240       bool
 241       cmp_with_other(const PB_ASSOC_CLASS_C_DEC& r_other) const;
 242
 243       inline size_type
 244       max_size() const;
 245
 246       inline bool
 247       empty() const;
 248
 249       inline size_type
 250       size() const;
 251
 252       Cmp_Fn&
 253       get_cmp_fn();
 254
 255       const Cmp_Fn&
 256       get_cmp_fn() const;
 257
 258 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 259       inline data_reference
 260       subscript_imp(const_key_reference r_key)
 261       {
 262         PB_ASSOC_DBG_ONLY(assert_valid();)
 263
 264           find_iterator it = lower_bound(r_key);
 265
 266         if (it != find_end()&&  !Cmp_Fn::operator()(
 267                                                     r_key,
 268                                                     PB_ASSOC_V2F(*it)))
 269           {
 270             PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
 271
 272             PB_ASSOC_DBG_ONLY(assert_valid();)
 273
 274               return (it->second);
 275           }
 276
 277         PB_ASSOC_DBG_ONLY(assert_valid();)
 278
 279           return (insert_new_val(it,
 280                                  std::make_pair(r_key, data_type()))->second);
 281       }
 282
 283       inline const_data_reference
 284       subscript_imp(const_key_reference r_key) const
 285       {
 286         PB_ASSOC_DBG_ONLY(assert_valid();)
 287
 288           PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
 289
 290         find_iterator it =       lower_bound(r_key);
 291
 292         PB_ASSOC_DBG_ASSERT(it != find_end());
 293
 294         return (it->second);
 295       }
 296 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 297
 298       inline std::pair<find_iterator, bool>
 299       insert(const_reference r_value)
 300       {
 301         PB_ASSOC_DBG_ONLY(assert_valid();)
 302
 303           const_key_reference r_key = PB_ASSOC_V2F(r_value);
 304
 305         find_iterator it = lower_bound(r_key);
 306
 307         if (it != find_end()&&  !Cmp_Fn::operator()(
 308                                                     r_key,
 309                                                     PB_ASSOC_V2F(*it)))
 310           {
 311             PB_ASSOC_DBG_ONLY(assert_valid();)
 312
 313               PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
 314
 315             return (std::make_pair(it, false));
 316           }
 317
 318         PB_ASSOC_DBG_ONLY(assert_valid();)
 319
 320           return (std::make_pair(insert_new_val(it, r_value), true));
 321       }
 322
 323       inline static pointer
 324       mid_pointer(pointer p_begin, pointer p_end)
 325       {
 326         PB_ASSOC_DBG_ASSERT(p_end >= p_begin);
 327
 328         return (p_begin + (p_end - p_begin) / 2);
 329       }
 330
 331       inline find_iterator
 332       lower_bound(const_key_reference r_key)
 333       {
 334         pointer it = m_a_values;
 335
 336         difference_type dist = m_size;
 337
 338         while (dist > 0)
 339           {
 340             const difference_type mid_dist  = dist >> 1;
 341
 342             pointer mid_it = it + mid_dist;
 343
 344             if (my_cmp_fn_base::operator()(
 345                                            PB_ASSOC_V2F(*(it + mid_dist)),
 346                                            r_key))
 347               {
 348                 it = ++mid_it;
 349
 350                 dist -= mid_dist + 1;
 351               }
 352             else
 353               dist = mid_dist;
 354           }
 355
 356         return (it);
 357       }
 358
 359       inline const_find_iterator
 360       lower_bound(const_key_reference r_key) const
 361       {
 362         return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).lower_bound(r_key));
 363       }
 364
 365       inline find_iterator
 366       upper_bound(const_key_reference r_key)
 367       {
 368         iterator pot_it = lower_bound(r_key);
 369
 370         if (pot_it != find_end()&&  !Cmp_Fn::operator()(
 371                                                         r_key,
 372                                                         PB_ASSOC_V2F(*pot_it)))
 373           {
 374             PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
 375
 376             return (++pot_it);
 377           }
 378
 379         PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key));
 380
 381         return (pot_it);
 382       }
 383
 384       inline const_find_iterator
 385       upper_bound(const_key_reference r_key) const
 386       {
 387         return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).upper_bound(r_key));
 388       }
 389
 390       inline find_iterator
 391       find(const_key_reference r_key)
 392       {
 393         PB_ASSOC_DBG_ONLY(assert_valid();)
 394
 395           iterator pot_it = lower_bound(r_key);
 396
 397         if (pot_it != find_end()&&  !Cmp_Fn::operator()(
 398                                                         r_key,
 399                                                         PB_ASSOC_V2F(*pot_it)))
 400           {
 401             PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
 402
 403             return (pot_it);
 404           }
 405
 406         PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key));
 407
 408         return (find_end());
 409       }
 410
 411       inline const_find_iterator
 412       find(const_key_reference r_key) const
 413       {
 414         return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).find(r_key));
 415       }
 416
 417       inline size_type
 418       erase(const_key_reference r_key);
 419
 420       template<class Pred>
 421       inline size_type
 422       erase_if(Pred pred);
 423
 424       template<class It>
 425       inline It
 426       erase(It it);
 427
 428       void
 429       clear();
 430
 431       void
 432       join(PB_ASSOC_CLASS_C_DEC& r_other);
 433
 434       void
 435       split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
 436
 437       inline iterator
 438       begin()
 439       {
 440         return (m_a_values);
 441       }
 442
 443       inline const_iterator
 444       begin() const
 445       {
 446         return (m_a_values);
 447       }
 448
 449       inline iterator
 450       find_end()
 451       {
 452         return (end());
 453       }
 454
 455       inline const_iterator
 456       find_end() const
 457       {
 458         return (end());
 459       }
 460
 461       inline iterator
 462       end()
 463       {
 464         return (m_end_it);
 465       }
 466
 467       inline const_iterator
 468       end() const
 469       {
 470         return (m_end_it);
 471       }
 472
 473       inline const_node_iterator
 474       node_begin() const
 475       {
 476         return (const_node_iterator(mid_pointer(begin(), end()), begin(), end()));
 477       }
 478
 479       inline node_iterator
 480       node_begin()
 481       {
 482         return (node_iterator(mid_pointer(begin(), end()), begin(), end()));
 483       }
 484
 485       inline const_node_iterator
 486       node_end() const
 487       {
 488         return (const_node_iterator(end(), end(), end()));
 489       }
 490
 491       inline node_iterator
 492       node_end()
 493       {
 494         return (node_iterator(end(), end(), end()));
 495       }
 496
 497     private:
 498
 499       inline pointer
 500       insert_new_val(iterator it, const_reference r_value)
 501       {
 502         PB_ASSOC_DBG_ONLY(assert_valid();)
 503
 504 #ifdef PB_ASSOC_BASIC_REGRESSION
 505           throw_prob_adjustor adjust(m_size);
 506 #endif // #ifdef PB_ASSOC_BASIC_REGRESSION
 507
 508         PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(
 509                                                                       PB_ASSOC_V2F(r_value)));
 510
 511         pointer a_values = s_alloc.allocate(m_size + 1);
 512
 513         iterator source_it = begin();
 514         iterator source_end_it = end();
 515         iterator target_it = a_values;
 516         iterator ret_it;
 517
 518         cond_dtor cd(a_values, target_it, m_size + 1);
 519
 520         while (source_it != it)
 521           {
 522             new (const_cast<void* >(
 523                                     static_cast<const void* >(target_it)))
 524               value_type(*source_it++);
 525
 526             ++target_it;
 527           }
 528
 529         new (const_cast<void* >(
 530                                 static_cast<const void* >(ret_it = target_it)))
 531           value_type(r_value);
 532
 533         ++target_it;
 534
 535         while (source_it != source_end_it)
 536           {
 537             new (const_cast<void* >(
 538                                     static_cast<const void* >(target_it)))
 539               value_type(*source_it++);
 540
 541             ++target_it;
 542           }
 543
 544         cd.set_no_action();
 545
 546         if (m_size != 0)
 547           {
 548             cond_dtor cd1(m_a_values, m_end_it, m_size);
 549           }
 550
 551         ++m_size;
 552
 553         m_a_values = a_values;
 554
 555         m_end_it = m_a_values + m_size;
 556
 557         PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new(
 558                                                         PB_ASSOC_V2F(r_value)));
 559
 560         update(node_begin(), (Node_Updator* )this);
 561
 562         PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
 563
 564           return (ret_it);
 565       }
 566
 567 #ifdef PB_ASSOC_OV_TREE_DEBUG_
 568
 569       virtual void
 570       assert_valid() const;
 571
 572       void
 573       assert_iterators() const;
 574
 575 #endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_
 576
 577       template<class It>
 578       void
 579       copy_from_ordered_range(It first_it, It last_it);
 580
 581       template<class It>
 582       void
 583       copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it);
 584
 585     private:
 586       typedef
 587       typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type_allocator
 588       value_allocator;
 589
 590       pointer m_a_values;
 591
 592       static value_allocator s_alloc;
 593
 594       pointer m_end_it;
 595
 596       size_type m_size;
 597     };
 598
 599 #include <ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
 600 #include <ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp>
 601 #include <ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp>
 602 #include <ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp>
 603 #include <ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp>
 604 #include <ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp>
 605 #include <ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp>
 606 #include <ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp>
 607
 608 #undef PB_ASSOC_CLASS_C_DEC
 609
 610 #undef PB_ASSOC_CLASS_T_DEC
 611
 612 #undef PB_ASSOC_OV_TREE_CLASS_NAME
 613
 614 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
 615
 616 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
 617
 618 #undef PB_ASSOC_V2F
 619 #undef PB_ASSOC_EP2VP
 620 #undef PB_ASSOC_V2S
 621
 622 #undef PB_ASSOC_DBG_ASSERT
 623 #undef PB_ASSOC_DBG_VERIFY
 624 #undef PB_ASSOC_DBG_ONLY
 625
 626   } // namespace detail
 627
 628 } // namespace pb_assoc