contrib/gcc-8.0/libstdc++-v3/include/bits/node_handle.h

   1 // Node handles for containers -*- C++ -*-
   2
   3 // Copyright (C) 2016-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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, 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 // 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 /** @file bits/node_handle.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly.
  28  *  @headername{map,set,unordered_map,unordered_set}
  29  */
  30
  31 #ifndef _NODE_HANDLE
  32 #define _NODE_HANDLE 1
  33
  34 #pragma GCC system_header
  35
  36 #if __cplusplus > 201402L
  37 # define __cpp_lib_node_extract 201606
  38
  39 #include <optional>
  40 #include <bits/alloc_traits.h>
  41 #include <bits/ptr_traits.h>
  42
  43 namespace std _GLIBCXX_VISIBILITY(default)
  44 {
  45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  46
  47   /// Base class for node handle types of maps and sets.
  48   template<typename _Val, typename _NodeAlloc>
  49     class _Node_handle_common
  50     {
  51       using _AllocTraits = allocator_traits<_NodeAlloc>;
  52
  53     public:
  54       using allocator_type = __alloc_rebind<_NodeAlloc, _Val>;
  55
  56       allocator_type
  57       get_allocator() const noexcept
  58       {
  59         __glibcxx_assert(!this->empty());
  60         return allocator_type(*_M_alloc);
  61       }
  62
  63       explicit operator bool() const noexcept { return _M_ptr != nullptr; }
  64
  65       [[nodiscard]] bool empty() const noexcept { return _M_ptr == nullptr; }
  66
  67     protected:
  68       constexpr _Node_handle_common() noexcept : _M_ptr(), _M_alloc() {}
  69
  70       ~_Node_handle_common() { _M_destroy(); }
  71
  72       _Node_handle_common(_Node_handle_common&& __nh) noexcept
  73       : _M_ptr(__nh._M_ptr), _M_alloc(std::move(__nh._M_alloc))
  74       {
  75         __nh._M_ptr = nullptr;
  76         __nh._M_alloc = nullopt;
  77       }
  78
  79       _Node_handle_common&
  80       operator=(_Node_handle_common&& __nh) noexcept
  81       {
  82         _M_destroy();
  83         _M_ptr = __nh._M_ptr;
  84         if constexpr (is_move_assignable_v<_NodeAlloc>)
  85           {
  86             if (_AllocTraits::propagate_on_container_move_assignment::value
  87                 || !this->_M_alloc)
  88               this->_M_alloc = std::move(__nh._M_alloc);
  89             else
  90               {
  91                 __glibcxx_assert(this->_M_alloc == __nh._M_alloc);
  92               }
  93           }
  94         else
  95           {
  96             __glibcxx_assert(_M_alloc);
  97           }
  98         __nh._M_ptr = nullptr;
  99         __nh._M_alloc = nullopt;
 100         return *this;
 101       }
 102
 103       _Node_handle_common(typename _AllocTraits::pointer __ptr,
 104                           const _NodeAlloc& __alloc)
 105       : _M_ptr(__ptr), _M_alloc(__alloc) { }
 106
 107       void
 108       _M_swap(_Node_handle_common& __nh) noexcept
 109       {
 110         using std::swap;
 111         swap(_M_ptr, __nh._M_ptr);
 112         if (_AllocTraits::propagate_on_container_swap
 113             || !_M_alloc || !__nh._M_alloc)
 114           _M_alloc.swap(__nh._M_alloc);
 115         else
 116           {
 117             __glibcxx_assert(_M_alloc == __nh._M_alloc);
 118           }
 119       }
 120
 121     private:
 122       void
 123       _M_destroy() noexcept
 124       {
 125         if (_M_ptr != nullptr)
 126           {
 127             allocator_type __alloc(*_M_alloc);
 128             allocator_traits<allocator_type>::destroy(__alloc,
 129                                                       _M_ptr->_M_valptr());
 130             _AllocTraits::deallocate(*_M_alloc, _M_ptr, 1);
 131           }
 132       }
 133
 134     protected:
 135       typename _AllocTraits::pointer    _M_ptr;
 136     private:
 137       optional<_NodeAlloc>              _M_alloc;
 138
 139       template<typename _Key2, typename _Value2, typename _KeyOfValue,
 140                typename _Compare, typename _ValueAlloc>
 141         friend class _Rb_tree;
 142     };
 143
 144   /// Node handle type for maps.
 145   template<typename _Key, typename _Value, typename _NodeAlloc>
 146     class _Node_handle : public _Node_handle_common<_Value, _NodeAlloc>
 147     {
 148     public:
 149       constexpr _Node_handle() noexcept = default;
 150       ~_Node_handle() = default;
 151       _Node_handle(_Node_handle&&) noexcept = default;
 152
 153       _Node_handle&
 154       operator=(_Node_handle&&) noexcept = default;
 155
 156       using key_type = _Key;
 157       using mapped_type = typename _Value::second_type;
 158
 159       key_type&
 160       key() const noexcept
 161       {
 162         __glibcxx_assert(!this->empty());
 163         return *_M_pkey;
 164       }
 165
 166       mapped_type&
 167       mapped() const noexcept
 168       {
 169         __glibcxx_assert(!this->empty());
 170         return *_M_pmapped;
 171       }
 172
 173       void
 174       swap(_Node_handle& __nh) noexcept
 175       {
 176         this->_M_swap(__nh);
 177         using std::swap;
 178         swap(_M_pkey, __nh._M_pkey);
 179         swap(_M_pmapped, __nh._M_pmapped);
 180       }
 181
 182       friend void
 183       swap(_Node_handle& __x, _Node_handle& __y)
 184       noexcept(noexcept(__x.swap(__y)))
 185       { __x.swap(__y); }
 186
 187     private:
 188       using _AllocTraits = allocator_traits<_NodeAlloc>;
 189
 190       _Node_handle(typename _AllocTraits::pointer __ptr,
 191                    const _NodeAlloc& __alloc)
 192       : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc)
 193       {
 194         if (__ptr)
 195           {
 196             auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
 197             _M_pkey = _S_pointer_to(__key);
 198             _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);
 199           }
 200         else
 201           {
 202             _M_pkey = nullptr;
 203             _M_pmapped = nullptr;
 204           }
 205       }
 206
 207       template<typename _Tp>
 208         using __pointer
 209           = __ptr_rebind<typename _AllocTraits::pointer,
 210                          remove_reference_t<_Tp>>;
 211
 212       __pointer<_Key>                           _M_pkey = nullptr;
 213       __pointer<typename _Value::second_type>   _M_pmapped = nullptr;
 214
 215       template<typename _Tp>
 216         __pointer<_Tp>
 217         _S_pointer_to(_Tp& __obj)
 218         { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }
 219
 220       const key_type&
 221       _M_key() const noexcept { return key(); }
 222
 223       template<typename _Key2, typename _Value2, typename _KeyOfValue,
 224                typename _Compare, typename _ValueAlloc>
 225         friend class _Rb_tree;
 226
 227       template<typename _Key2, typename _Value2, typename _ValueAlloc,
 228                typename _ExtractKey, typename _Equal,
 229                typename _H1, typename _H2, typename _Hash,
 230                typename _RehashPolicy, typename _Traits>
 231         friend class _Hashtable;
 232     };
 233
 234   /// Node handle type for sets.
 235   template<typename _Value, typename _NodeAlloc>
 236     class _Node_handle<_Value, _Value, _NodeAlloc>
 237     : public _Node_handle_common<_Value, _NodeAlloc>
 238     {
 239     public:
 240       constexpr _Node_handle() noexcept = default;
 241       ~_Node_handle() = default;
 242       _Node_handle(_Node_handle&&) noexcept = default;
 243
 244       _Node_handle&
 245       operator=(_Node_handle&&) noexcept = default;
 246
 247       using value_type = _Value;
 248
 249       value_type&
 250       value() const noexcept
 251       {
 252         __glibcxx_assert(!this->empty());
 253         return *this->_M_ptr->_M_valptr();
 254       }
 255
 256       void
 257       swap(_Node_handle& __nh) noexcept
 258       { this->_M_swap(__nh); }
 259
 260       friend void
 261       swap(_Node_handle& __x, _Node_handle& __y)
 262       noexcept(noexcept(__x.swap(__y)))
 263       { __x.swap(__y); }
 264
 265     private:
 266       using _AllocTraits = allocator_traits<_NodeAlloc>;
 267
 268       _Node_handle(typename _AllocTraits::pointer __ptr,
 269                    const _NodeAlloc& __alloc)
 270       : _Node_handle_common<_Value, _NodeAlloc>(__ptr, __alloc) { }
 271
 272       const value_type&
 273       _M_key() const noexcept { return value(); }
 274
 275       template<typename _Key, typename _Val, typename _KeyOfValue,
 276                typename _Compare, typename _Alloc>
 277         friend class _Rb_tree;
 278
 279       template<typename _Key2, typename _Value2, typename _ValueAlloc,
 280                typename _ExtractKey, typename _Equal,
 281                typename _H1, typename _H2, typename _Hash,
 282                typename _RehashPolicy, typename _Traits>
 283         friend class _Hashtable;
 284     };
 285
 286   /// Return type of insert(node_handle&&) on unique maps/sets.
 287   template<typename _Iterator, typename _NodeHandle>
 288     struct _Node_insert_return
 289     {
 290       _Iterator         position = _Iterator();
 291       bool              inserted = false;
 292       _NodeHandle       node;
 293     };
 294
 295 _GLIBCXX_END_NAMESPACE_VERSION
 296 } // namespace std
 297
 298 #endif // C++17
 299 #endif