contrib/gcc-8.0/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2018 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file ov_tree_map_/ov_tree_map_.hpp
  38  * Contains an implementation class for ov_tree.
  39  */
  40
  41 #include <map>
  42 #include <set>
  43 #include <ext/pb_ds/exception.hpp>
  44 #include <ext/pb_ds/tree_policy.hpp>
  45 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  46 #include <ext/pb_ds/detail/types_traits.hpp>
  47 #include <ext/pb_ds/detail/type_utils.hpp>
  48 #include <ext/pb_ds/detail/tree_trace_base.hpp>
  49 #ifdef _GLIBCXX_DEBUG
  50 #include <ext/pb_ds/detail/debug_map_base.hpp>
  51 #endif
  52 #include <utility>
  53 #include <functional>
  54 #include <algorithm>
  55 #include <vector>
  56 #include <assert.h>
  57 #include <debug/debug.h>
  58
  59 namespace __gnu_pbds
  60 {
  61   namespace detail
  62   {
  63 #ifdef PB_DS_DATA_TRUE_INDICATOR
  64 #define PB_DS_OV_TREE_NAME ov_tree_map
  65 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map
  66 #endif
  67
  68 #ifdef PB_DS_DATA_FALSE_INDICATOR
  69 #define PB_DS_OV_TREE_NAME ov_tree_set
  70 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set
  71 #endif
  72
  73 #define PB_DS_CLASS_T_DEC \
  74     template<typename Key, typename Mapped, typename Cmp_Fn, \
  75              typename Node_And_It_Traits, typename _Alloc>
  76
  77 #define PB_DS_CLASS_C_DEC \
  78    PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
  79
  80 #define PB_DS_OV_TREE_TRAITS_BASE \
  81     types_traits<Key, Mapped, _Alloc, false>
  82
  83 #ifdef _GLIBCXX_DEBUG
  84 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
  85     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
  86         typename _Alloc::template rebind<Key>::other::const_reference>
  87 #endif
  88
  89 #ifdef PB_DS_TREE_TRACE
  90 #define PB_DS_TREE_TRACE_BASE_C_DEC \
  91     tree_trace_base<typename Node_And_It_Traits::node_const_iterator,   \
  92                     typename Node_And_It_Traits::node_iterator,         \
  93                     Cmp_Fn, false, _Alloc>
  94 #endif
  95
  96 #ifndef PB_DS_CHECK_KEY_EXISTS
  97 #  error Missing definition
  98 #endif
  99
 100     /**
 101      *  @brief Ordered-vector tree associative-container.
 102      *  @ingroup branch-detail
 103      */
 104     template<typename Key, typename Mapped, typename Cmp_Fn,
 105              typename Node_And_It_Traits, typename _Alloc>
 106     class PB_DS_OV_TREE_NAME :
 107 #ifdef _GLIBCXX_DEBUG
 108       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
 109 #endif
 110 #ifdef PB_DS_TREE_TRACE
 111       public PB_DS_TREE_TRACE_BASE_C_DEC,
 112 #endif
 113       public Cmp_Fn,
 114       public Node_And_It_Traits::node_update,
 115       public PB_DS_OV_TREE_TRAITS_BASE
 116     {
 117     private:
 118       typedef PB_DS_OV_TREE_TRAITS_BASE                 traits_base;
 119       typedef Node_And_It_Traits                        traits_type;
 120
 121       typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
 122
 123       typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
 124       typedef typename value_allocator::pointer         value_vector;
 125
 126 #ifdef _GLIBCXX_DEBUG
 127       typedef PB_DS_DEBUG_MAP_BASE_C_DEC                debug_base;
 128 #endif
 129
 130 #ifdef PB_DS_TREE_TRACE
 131       typedef PB_DS_TREE_TRACE_BASE_C_DEC               trace_base;
 132 #endif
 133
 134       typedef typename traits_base::pointer             mapped_pointer_;
 135       typedef typename traits_base::const_pointer       mapped_const_pointer_;
 136
 137       typedef typename traits_type::metadata_type       metadata_type;
 138
 139       typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
 140       typedef typename metadata_allocator::pointer      metadata_pointer;
 141       typedef typename metadata_allocator::const_reference metadata_const_reference;
 142       typedef typename metadata_allocator::reference    metadata_reference;
 143
 144       typedef typename traits_type::null_node_update_pointer
 145       null_node_update_pointer;
 146
 147     public:
 148       typedef ov_tree_tag                                container_category;
 149       typedef _Alloc                                    allocator_type;
 150       typedef typename _Alloc::size_type                size_type;
 151       typedef typename _Alloc::difference_type          difference_type;
 152       typedef Cmp_Fn                                    cmp_fn;
 153
 154       typedef typename traits_base::key_type            key_type;
 155       typedef typename traits_base::key_pointer         key_pointer;
 156       typedef typename traits_base::key_const_pointer   key_const_pointer;
 157       typedef typename traits_base::key_reference       key_reference;
 158       typedef typename traits_base::key_const_reference key_const_reference;
 159       typedef typename traits_base::mapped_type         mapped_type;
 160       typedef typename traits_base::mapped_pointer      mapped_pointer;
 161       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
 162       typedef typename traits_base::mapped_reference    mapped_reference;
 163       typedef typename traits_base::mapped_const_reference mapped_const_reference;
 164       typedef typename traits_base::value_type          value_type;
 165       typedef typename traits_base::pointer             pointer;
 166       typedef typename traits_base::const_pointer       const_pointer;
 167       typedef typename traits_base::reference           reference;
 168       typedef typename traits_base::const_reference     const_reference;
 169
 170       typedef const_pointer                             point_const_iterator;
 171 #ifdef PB_DS_DATA_TRUE_INDICATOR
 172       typedef pointer                                   point_iterator;
 173 #else
 174       typedef point_const_iterator                      point_iterator;
 175 #endif
 176
 177       typedef point_iterator                            iterator;
 178       typedef point_const_iterator                      const_iterator;
 179
 180       /// Conditional destructor.
 181       template<typename Size_Type>
 182         class cond_dtor
 183         {
 184         public:
 185           cond_dtor(value_vector a_vec, iterator& r_last_it,
 186                     Size_Type total_size)
 187           : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
 188             m_no_action(false)
 189           { }
 190
 191           ~cond_dtor()
 192           {
 193             if (m_no_action)
 194               return;
 195             iterator it = m_a_vec;
 196             while (it != m_r_last_it)
 197               {
 198                 it->~value_type();
 199                 ++it;
 200               }
 201
 202             if (m_max_size > 0)
 203               value_allocator().deallocate(m_a_vec, m_max_size);
 204           }
 205
 206           inline void
 207           set_no_action()
 208           { m_no_action = true; }
 209
 210         protected:
 211           value_vector          m_a_vec;
 212           iterator&             m_r_last_it;
 213           const Size_Type       m_max_size;
 214           bool                  m_no_action;
 215        };
 216
 217       typedef typename traits_type::node_update         node_update;
 218       typedef typename traits_type::node_iterator       node_iterator;
 219       typedef typename traits_type::node_const_iterator node_const_iterator;
 220
 221
 222       PB_DS_OV_TREE_NAME();
 223
 224       PB_DS_OV_TREE_NAME(const Cmp_Fn&);
 225
 226       PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&);
 227
 228       PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&);
 229
 230       ~PB_DS_OV_TREE_NAME();
 231
 232       void
 233       swap(PB_DS_CLASS_C_DEC&);
 234
 235       template<typename It>
 236       void
 237       copy_from_range(It, It);
 238
 239       inline size_type
 240       max_size() const;
 241
 242       inline bool
 243       empty() const;
 244
 245       inline size_type
 246       size() const;
 247
 248       Cmp_Fn&
 249       get_cmp_fn();
 250
 251       const Cmp_Fn&
 252       get_cmp_fn() const;
 253
 254       inline mapped_reference
 255       operator[](key_const_reference r_key)
 256       {
 257 #ifdef PB_DS_DATA_TRUE_INDICATOR
 258         PB_DS_ASSERT_VALID((*this))
 259         point_iterator it = lower_bound(r_key);
 260         if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
 261           {
 262             PB_DS_CHECK_KEY_EXISTS(r_key)
 263             PB_DS_ASSERT_VALID((*this))
 264              return it->second;
 265           }
 266         return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second;
 267 #else
 268         insert(r_key);
 269         return traits_base::s_null_type;
 270 #endif
 271       }
 272
 273       inline std::pair<point_iterator, bool>
 274       insert(const_reference r_value)
 275       {
 276         PB_DS_ASSERT_VALID((*this))
 277         key_const_reference r_key = PB_DS_V2F(r_value);
 278         point_iterator it = lower_bound(r_key);
 279
 280         if (it != end()&&  !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
 281           {
 282             PB_DS_ASSERT_VALID((*this))
 283             PB_DS_CHECK_KEY_EXISTS(r_key)
 284             return std::make_pair(it, false);
 285           }
 286
 287         return std::make_pair(insert_new_val(it, r_value), true);
 288       }
 289
 290       inline point_iterator
 291       lower_bound(key_const_reference r_key)
 292       {
 293         pointer it = m_a_values;
 294         pointer e_it = m_a_values + m_size;
 295         while (it != e_it)
 296           {
 297             pointer mid_it = it + ((e_it - it) >> 1);
 298             if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
 299               it = ++mid_it;
 300             else
 301               e_it = mid_it;
 302           }
 303         return it;
 304       }
 305
 306       inline point_const_iterator
 307       lower_bound(key_const_reference r_key) const
 308       { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); }
 309
 310       inline point_iterator
 311       upper_bound(key_const_reference r_key)
 312       {
 313         iterator pot_it = lower_bound(r_key);
 314         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
 315           {
 316             PB_DS_CHECK_KEY_EXISTS(r_key)
 317             return ++pot_it;
 318           }
 319
 320         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
 321         return pot_it;
 322       }
 323
 324       inline point_const_iterator
 325       upper_bound(key_const_reference r_key) const
 326       { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
 327
 328       inline point_iterator
 329       find(key_const_reference r_key)
 330       {
 331         PB_DS_ASSERT_VALID((*this))
 332         iterator pot_it = lower_bound(r_key);
 333         if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
 334           {
 335             PB_DS_CHECK_KEY_EXISTS(r_key)
 336             return pot_it;
 337           }
 338
 339         PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
 340         return end();
 341       }
 342
 343       inline point_const_iterator
 344       find(key_const_reference r_key) const
 345       { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); }
 346
 347       bool
 348       erase(key_const_reference);
 349
 350       template<typename Pred>
 351       inline size_type
 352       erase_if(Pred);
 353
 354       inline iterator
 355       erase(iterator it)
 356       { return erase_imp<iterator>(it); }
 357
 358       void
 359       clear();
 360
 361       void
 362       join(PB_DS_CLASS_C_DEC&);
 363
 364       void
 365       split(key_const_reference, PB_DS_CLASS_C_DEC&);
 366
 367       inline iterator
 368       begin()
 369       { return m_a_values; }
 370
 371       inline const_iterator
 372       begin() const
 373       { return m_a_values; }
 374
 375       inline iterator
 376       end()
 377       { return m_end_it; }
 378
 379       inline const_iterator
 380       end() const
 381       { return m_end_it; }
 382
 383       /// Returns a const node_iterator corresponding to the node at the
 384       /// root of the tree.
 385       inline node_const_iterator
 386       node_begin() const;
 387
 388       /// Returns a node_iterator corresponding to the node at the
 389       /// root of the tree.
 390       inline node_iterator
 391       node_begin();
 392
 393       /// Returns a const node_iterator corresponding to a node just
 394       /// after a leaf of the tree.
 395       inline node_const_iterator
 396       node_end() const;
 397
 398       /// Returns a node_iterator corresponding to a node just
 399       /// after a leaf of the tree.
 400       inline node_iterator
 401       node_end();
 402
 403     private:
 404
 405       inline void
 406       update(node_iterator, null_node_update_pointer);
 407
 408       template<typename Node_Update>
 409       void
 410       update(node_iterator, Node_Update*);
 411
 412       void
 413       reallocate_metadata(null_node_update_pointer, size_type);
 414
 415       template<typename Node_Update_>
 416       void
 417       reallocate_metadata(Node_Update_*, size_type);
 418
 419       template<typename It>
 420       void
 421       copy_from_ordered_range(It, It);
 422
 423       void
 424       value_swap(PB_DS_CLASS_C_DEC&);
 425
 426       template<typename It>
 427       void
 428       copy_from_ordered_range(It, It, It, It);
 429
 430       template<typename Ptr>
 431       inline static Ptr
 432       mid_pointer(Ptr p_begin, Ptr p_end)
 433       {
 434         _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
 435         return (p_begin + (p_end - p_begin) / 2);
 436       }
 437
 438       inline iterator
 439       insert_new_val(iterator it, const_reference r_value)
 440       {
 441 #ifdef PB_DS_REGRESSION
 442         typename _Alloc::group_adjustor adjust(m_size);
 443 #endif
 444
 445         PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value))
 446
 447         value_vector a_values = s_value_alloc.allocate(m_size + 1);
 448
 449         iterator source_it = begin();
 450         iterator source_end_it = end();
 451         iterator target_it = a_values;
 452         iterator ret_it;
 453
 454         cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
 455         while (source_it != it)
 456           {
 457             new (const_cast<void*>(static_cast<const void*>(target_it)))
 458               value_type(*source_it++);
 459             ++target_it;
 460           }
 461
 462         new (const_cast<void*>(static_cast<const void*>(ret_it = target_it)))
 463           value_type(r_value);
 464         ++target_it;
 465
 466         while (source_it != source_end_it)
 467           {
 468             new (const_cast<void*>(static_cast<const void*>(target_it)))
 469               value_type(*source_it++);
 470             ++target_it;
 471           }
 472
 473         reallocate_metadata((node_update*)this, m_size + 1);
 474         cd.set_no_action();
 475         if (m_size != 0)
 476           {
 477             cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
 478           }
 479
 480         ++m_size;
 481         m_a_values = a_values;
 482         m_end_it = m_a_values + m_size;
 483         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value)));
 484         update(node_begin(), (node_update* )this);
 485         PB_DS_ASSERT_VALID((*this))
 486         return ret_it;
 487       }
 488
 489 #ifdef _GLIBCXX_DEBUG
 490       void
 491       assert_valid(const char*, int) const;
 492
 493       void
 494       assert_iterators(const char*, int) const;
 495 #endif
 496
 497       template<typename It>
 498       It
 499       erase_imp(It);
 500
 501       inline node_const_iterator
 502       PB_DS_node_begin_imp() const;
 503
 504       inline node_const_iterator
 505       PB_DS_node_end_imp() const;
 506
 507       inline node_iterator
 508       PB_DS_node_begin_imp();
 509
 510       inline node_iterator
 511       PB_DS_node_end_imp();
 512
 513     private:
 514       static value_allocator    s_value_alloc;
 515       static metadata_allocator s_metadata_alloc;
 516
 517       value_vector              m_a_values;
 518       metadata_pointer          m_a_metadata;
 519       iterator                  m_end_it;
 520       size_type                 m_size;
 521     };
 522
 523 #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
 524 #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
 525 #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
 526 #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
 527 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
 528 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
 529 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
 530 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 531
 532 #undef PB_DS_CLASS_C_DEC
 533 #undef PB_DS_CLASS_T_DEC
 534 #undef PB_DS_OV_TREE_NAME
 535 #undef PB_DS_OV_TREE_TRAITS_BASE
 536 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 537 #ifdef PB_DS_TREE_TRACE
 538 #undef PB_DS_TREE_TRACE_BASE_C_DEC
 539 #endif
 540 #undef PB_DS_CONST_NODE_ITERATOR_NAME
 541   } // namespace detail
 542 } // namespace __gnu_pbds