|
111
|
1 // hashtable.h header -*- C++ -*-
|
|
|
2
|
|
131
|
3 // Copyright (C) 2007-2018 Free Software Foundation, Inc.
|
|
111
|
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/hashtable.h
|
|
|
26 * This is an internal header file, included by other library headers.
|
|
|
27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
|
|
|
28 */
|
|
|
29
|
|
|
30 #ifndef _HASHTABLE_H
|
|
|
31 #define _HASHTABLE_H 1
|
|
|
32
|
|
|
33 #pragma GCC system_header
|
|
|
34
|
|
|
35 #include <bits/hashtable_policy.h>
|
|
|
36 #if __cplusplus > 201402L
|
|
|
37 # include <bits/node_handle.h>
|
|
|
38 #endif
|
|
|
39
|
|
|
40 namespace std _GLIBCXX_VISIBILITY(default)
|
|
|
41 {
|
|
|
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
|
|
43
|
|
|
44 template<typename _Tp, typename _Hash>
|
|
|
45 using __cache_default
|
|
|
46 = __not_<__and_<// Do not cache for fast hasher.
|
|
|
47 __is_fast_hash<_Hash>,
|
|
|
48 // Mandatory to have erase not throwing.
|
|
131
|
49 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
|
|
111
|
50
|
|
|
51 /**
|
|
|
52 * Primary class template _Hashtable.
|
|
|
53 *
|
|
|
54 * @ingroup hashtable-detail
|
|
|
55 *
|
|
|
56 * @tparam _Value CopyConstructible type.
|
|
|
57 *
|
|
|
58 * @tparam _Key CopyConstructible type.
|
|
|
59 *
|
|
|
60 * @tparam _Alloc An allocator type
|
|
|
61 * ([lib.allocator.requirements]) whose _Alloc::value_type is
|
|
|
62 * _Value. As a conforming extension, we allow for
|
|
|
63 * _Alloc::value_type != _Value.
|
|
|
64 *
|
|
|
65 * @tparam _ExtractKey Function object that takes an object of type
|
|
|
66 * _Value and returns a value of type _Key.
|
|
|
67 *
|
|
|
68 * @tparam _Equal Function object that takes two objects of type k
|
|
|
69 * and returns a bool-like value that is true if the two objects
|
|
|
70 * are considered equal.
|
|
|
71 *
|
|
|
72 * @tparam _H1 The hash function. A unary function object with
|
|
|
73 * argument type _Key and result type size_t. Return values should
|
|
|
74 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
|
|
|
75 *
|
|
|
76 * @tparam _H2 The range-hashing function (in the terminology of
|
|
|
77 * Tavori and Dreizin). A binary function object whose argument
|
|
|
78 * types and result type are all size_t. Given arguments r and N,
|
|
|
79 * the return value is in the range [0, N).
|
|
|
80 *
|
|
|
81 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
|
|
|
82 * binary function whose argument types are _Key and size_t and
|
|
|
83 * whose result type is size_t. Given arguments k and N, the
|
|
|
84 * return value is in the range [0, N). Default: hash(k, N) =
|
|
|
85 * h2(h1(k), N). If _Hash is anything other than the default, _H1
|
|
|
86 * and _H2 are ignored.
|
|
|
87 *
|
|
|
88 * @tparam _RehashPolicy Policy class with three members, all of
|
|
|
89 * which govern the bucket count. _M_next_bkt(n) returns a bucket
|
|
|
90 * count no smaller than n. _M_bkt_for_elements(n) returns a
|
|
|
91 * bucket count appropriate for an element count of n.
|
|
|
92 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
|
|
|
93 * current bucket count is n_bkt and the current element count is
|
|
|
94 * n_elt, we need to increase the bucket count. If so, returns
|
|
|
95 * make_pair(true, n), where n is the new bucket count. If not,
|
|
|
96 * returns make_pair(false, <anything>)
|
|
|
97 *
|
|
|
98 * @tparam _Traits Compile-time class with three boolean
|
|
|
99 * std::integral_constant members: __cache_hash_code, __constant_iterators,
|
|
|
100 * __unique_keys.
|
|
|
101 *
|
|
|
102 * Each _Hashtable data structure has:
|
|
|
103 *
|
|
|
104 * - _Bucket[] _M_buckets
|
|
|
105 * - _Hash_node_base _M_before_begin
|
|
|
106 * - size_type _M_bucket_count
|
|
|
107 * - size_type _M_element_count
|
|
|
108 *
|
|
|
109 * with _Bucket being _Hash_node* and _Hash_node containing:
|
|
|
110 *
|
|
|
111 * - _Hash_node* _M_next
|
|
|
112 * - Tp _M_value
|
|
|
113 * - size_t _M_hash_code if cache_hash_code is true
|
|
|
114 *
|
|
|
115 * In terms of Standard containers the hashtable is like the aggregation of:
|
|
|
116 *
|
|
|
117 * - std::forward_list<_Node> containing the elements
|
|
|
118 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
|
|
|
119 *
|
|
|
120 * The non-empty buckets contain the node before the first node in the
|
|
|
121 * bucket. This design makes it possible to implement something like a
|
|
|
122 * std::forward_list::insert_after on container insertion and
|
|
|
123 * std::forward_list::erase_after on container erase
|
|
|
124 * calls. _M_before_begin is equivalent to
|
|
|
125 * std::forward_list::before_begin. Empty buckets contain
|
|
|
126 * nullptr. Note that one of the non-empty buckets contains
|
|
|
127 * &_M_before_begin which is not a dereferenceable node so the
|
|
|
128 * node pointer in a bucket shall never be dereferenced, only its
|
|
|
129 * next node can be.
|
|
|
130 *
|
|
|
131 * Walking through a bucket's nodes requires a check on the hash code to
|
|
|
132 * see if each node is still in the bucket. Such a design assumes a
|
|
|
133 * quite efficient hash functor and is one of the reasons it is
|
|
|
134 * highly advisable to set __cache_hash_code to true.
|
|
|
135 *
|
|
|
136 * The container iterators are simply built from nodes. This way
|
|
|
137 * incrementing the iterator is perfectly efficient independent of
|
|
|
138 * how many empty buckets there are in the container.
|
|
|
139 *
|
|
|
140 * On insert we compute the element's hash code and use it to find the
|
|
|
141 * bucket index. If the element must be inserted in an empty bucket
|
|
|
142 * we add it at the beginning of the singly linked list and make the
|
|
|
143 * bucket point to _M_before_begin. The bucket that used to point to
|
|
|
144 * _M_before_begin, if any, is updated to point to its new before
|
|
|
145 * begin node.
|
|
|
146 *
|
|
|
147 * On erase, the simple iterator design requires using the hash
|
|
|
148 * functor to get the index of the bucket to update. For this
|
|
|
149 * reason, when __cache_hash_code is set to false the hash functor must
|
|
|
150 * not throw and this is enforced by a static assertion.
|
|
|
151 *
|
|
|
152 * Functionality is implemented by decomposition into base classes,
|
|
|
153 * where the derived _Hashtable class is used in _Map_base,
|
|
|
154 * _Insert, _Rehash_base, and _Equality base classes to access the
|
|
|
155 * "this" pointer. _Hashtable_base is used in the base classes as a
|
|
|
156 * non-recursive, fully-completed-type so that detailed nested type
|
|
|
157 * information, such as iterator type and node type, can be
|
|
|
158 * used. This is similar to the "Curiously Recurring Template
|
|
|
159 * Pattern" (CRTP) technique, but uses a reconstructed, not
|
|
|
160 * explicitly passed, template pattern.
|
|
|
161 *
|
|
|
162 * Base class templates are:
|
|
|
163 * - __detail::_Hashtable_base
|
|
|
164 * - __detail::_Map_base
|
|
|
165 * - __detail::_Insert
|
|
|
166 * - __detail::_Rehash_base
|
|
|
167 * - __detail::_Equality
|
|
|
168 */
|
|
|
169 template<typename _Key, typename _Value, typename _Alloc,
|
|
|
170 typename _ExtractKey, typename _Equal,
|
|
|
171 typename _H1, typename _H2, typename _Hash,
|
|
|
172 typename _RehashPolicy, typename _Traits>
|
|
|
173 class _Hashtable
|
|
|
174 : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
175 _H1, _H2, _Hash, _Traits>,
|
|
|
176 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
|
|
|
178 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
|
|
|
180 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
|
|
|
182 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
|
|
|
184 private __detail::_Hashtable_alloc<
|
|
|
185 __alloc_rebind<_Alloc,
|
|
|
186 __detail::_Hash_node<_Value,
|
|
|
187 _Traits::__hash_cached::value>>>
|
|
|
188 {
|
|
131
|
189 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
|
|
|
190 "unordered container must have a non-const, non-volatile value_type");
|
|
|
191 #ifdef __STRICT_ANSI__
|
|
|
192 static_assert(is_same<typename _Alloc::value_type, _Value>{},
|
|
|
193 "unordered container must have the same value_type as its allocator");
|
|
|
194 #endif
|
|
|
195 static_assert(__is_invocable<const _H1&, const _Key&>{},
|
|
|
196 "hash function must be invocable with an argument of key type");
|
|
|
197 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
|
|
|
198 "key equality predicate must be invocable with two arguments of "
|
|
|
199 "key type");
|
|
|
200
|
|
111
|
201 using __traits_type = _Traits;
|
|
|
202 using __hash_cached = typename __traits_type::__hash_cached;
|
|
|
203 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
|
|
|
204 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
|
|
|
205
|
|
|
206 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
|
|
|
207
|
|
|
208 using __value_alloc_traits =
|
|
|
209 typename __hashtable_alloc::__value_alloc_traits;
|
|
|
210 using __node_alloc_traits =
|
|
|
211 typename __hashtable_alloc::__node_alloc_traits;
|
|
|
212 using __node_base = typename __hashtable_alloc::__node_base;
|
|
|
213 using __bucket_type = typename __hashtable_alloc::__bucket_type;
|
|
|
214
|
|
|
215 public:
|
|
|
216 typedef _Key key_type;
|
|
|
217 typedef _Value value_type;
|
|
|
218 typedef _Alloc allocator_type;
|
|
|
219 typedef _Equal key_equal;
|
|
|
220
|
|
|
221 // mapped_type, if present, comes from _Map_base.
|
|
|
222 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
|
|
|
223 typedef typename __value_alloc_traits::pointer pointer;
|
|
|
224 typedef typename __value_alloc_traits::const_pointer const_pointer;
|
|
|
225 typedef value_type& reference;
|
|
|
226 typedef const value_type& const_reference;
|
|
|
227
|
|
|
228 private:
|
|
|
229 using __rehash_type = _RehashPolicy;
|
|
|
230 using __rehash_state = typename __rehash_type::_State;
|
|
|
231
|
|
|
232 using __constant_iterators = typename __traits_type::__constant_iterators;
|
|
|
233 using __unique_keys = typename __traits_type::__unique_keys;
|
|
|
234
|
|
|
235 using __key_extract = typename std::conditional<
|
|
|
236 __constant_iterators::value,
|
|
|
237 __detail::_Identity,
|
|
|
238 __detail::_Select1st>::type;
|
|
|
239
|
|
|
240 using __hashtable_base = __detail::
|
|
|
241 _Hashtable_base<_Key, _Value, _ExtractKey,
|
|
|
242 _Equal, _H1, _H2, _Hash, _Traits>;
|
|
|
243
|
|
|
244 using __hash_code_base = typename __hashtable_base::__hash_code_base;
|
|
|
245 using __hash_code = typename __hashtable_base::__hash_code;
|
|
|
246 using __ireturn_type = typename __hashtable_base::__ireturn_type;
|
|
|
247
|
|
|
248 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
|
|
|
249 _Equal, _H1, _H2, _Hash,
|
|
|
250 _RehashPolicy, _Traits>;
|
|
|
251
|
|
|
252 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
|
|
|
253 _ExtractKey, _Equal,
|
|
|
254 _H1, _H2, _Hash,
|
|
|
255 _RehashPolicy, _Traits>;
|
|
|
256
|
|
|
257 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
|
|
|
258 _Equal, _H1, _H2, _Hash,
|
|
|
259 _RehashPolicy, _Traits>;
|
|
|
260
|
|
|
261 using __reuse_or_alloc_node_type =
|
|
|
262 __detail::_ReuseOrAllocNode<__node_alloc_type>;
|
|
|
263
|
|
|
264 // Metaprogramming for picking apart hash caching.
|
|
|
265 template<typename _Cond>
|
|
|
266 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
|
|
|
267
|
|
|
268 template<typename _Cond>
|
|
|
269 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
|
|
|
270
|
|
|
271 // Compile-time diagnostics.
|
|
|
272
|
|
|
273 // _Hash_code_base has everything protected, so use this derived type to
|
|
|
274 // access it.
|
|
|
275 struct __hash_code_base_access : __hash_code_base
|
|
|
276 { using __hash_code_base::_M_bucket_index; };
|
|
|
277
|
|
|
278 // Getting a bucket index from a node shall not throw because it is used
|
|
|
279 // in methods (erase, swap...) that shall not throw.
|
|
|
280 static_assert(noexcept(declval<const __hash_code_base_access&>()
|
|
|
281 ._M_bucket_index((const __node_type*)nullptr,
|
|
|
282 (std::size_t)0)),
|
|
|
283 "Cache the hash code or qualify your functors involved"
|
|
|
284 " in hash code and bucket index computation with noexcept");
|
|
|
285
|
|
|
286 // Following two static assertions are necessary to guarantee
|
|
|
287 // that local_iterator will be default constructible.
|
|
|
288
|
|
|
289 // When hash codes are cached local iterator inherits from H2 functor
|
|
|
290 // which must then be default constructible.
|
|
|
291 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
|
|
|
292 "Functor used to map hash code to bucket index"
|
|
|
293 " must be default constructible");
|
|
|
294
|
|
|
295 template<typename _Keya, typename _Valuea, typename _Alloca,
|
|
|
296 typename _ExtractKeya, typename _Equala,
|
|
|
297 typename _H1a, typename _H2a, typename _Hasha,
|
|
|
298 typename _RehashPolicya, typename _Traitsa,
|
|
|
299 bool _Unique_keysa>
|
|
|
300 friend struct __detail::_Map_base;
|
|
|
301
|
|
|
302 template<typename _Keya, typename _Valuea, typename _Alloca,
|
|
|
303 typename _ExtractKeya, typename _Equala,
|
|
|
304 typename _H1a, typename _H2a, typename _Hasha,
|
|
|
305 typename _RehashPolicya, typename _Traitsa>
|
|
|
306 friend struct __detail::_Insert_base;
|
|
|
307
|
|
|
308 template<typename _Keya, typename _Valuea, typename _Alloca,
|
|
|
309 typename _ExtractKeya, typename _Equala,
|
|
|
310 typename _H1a, typename _H2a, typename _Hasha,
|
|
|
311 typename _RehashPolicya, typename _Traitsa,
|
|
|
312 bool _Constant_iteratorsa>
|
|
|
313 friend struct __detail::_Insert;
|
|
|
314
|
|
|
315 public:
|
|
|
316 using size_type = typename __hashtable_base::size_type;
|
|
|
317 using difference_type = typename __hashtable_base::difference_type;
|
|
|
318
|
|
|
319 using iterator = typename __hashtable_base::iterator;
|
|
|
320 using const_iterator = typename __hashtable_base::const_iterator;
|
|
|
321
|
|
|
322 using local_iterator = typename __hashtable_base::local_iterator;
|
|
|
323 using const_local_iterator = typename __hashtable_base::
|
|
|
324 const_local_iterator;
|
|
|
325
|
|
|
326 #if __cplusplus > 201402L
|
|
|
327 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
|
|
|
328 using insert_return_type = _Node_insert_return<iterator, node_type>;
|
|
|
329 #endif
|
|
|
330
|
|
|
331 private:
|
|
|
332 __bucket_type* _M_buckets = &_M_single_bucket;
|
|
|
333 size_type _M_bucket_count = 1;
|
|
|
334 __node_base _M_before_begin;
|
|
|
335 size_type _M_element_count = 0;
|
|
|
336 _RehashPolicy _M_rehash_policy;
|
|
|
337
|
|
|
338 // A single bucket used when only need for 1 bucket. Especially
|
|
|
339 // interesting in move semantic to leave hashtable with only 1 buckets
|
|
|
340 // which is not allocated so that we can have those operations noexcept
|
|
|
341 // qualified.
|
|
|
342 // Note that we can't leave hashtable with 0 bucket without adding
|
|
|
343 // numerous checks in the code to avoid 0 modulus.
|
|
|
344 __bucket_type _M_single_bucket = nullptr;
|
|
|
345
|
|
|
346 bool
|
|
|
347 _M_uses_single_bucket(__bucket_type* __bkts) const
|
|
|
348 { return __builtin_expect(__bkts == &_M_single_bucket, false); }
|
|
|
349
|
|
|
350 bool
|
|
|
351 _M_uses_single_bucket() const
|
|
|
352 { return _M_uses_single_bucket(_M_buckets); }
|
|
|
353
|
|
|
354 __hashtable_alloc&
|
|
|
355 _M_base_alloc() { return *this; }
|
|
|
356
|
|
|
357 __bucket_type*
|
|
|
358 _M_allocate_buckets(size_type __n)
|
|
|
359 {
|
|
|
360 if (__builtin_expect(__n == 1, false))
|
|
|
361 {
|
|
|
362 _M_single_bucket = nullptr;
|
|
|
363 return &_M_single_bucket;
|
|
|
364 }
|
|
|
365
|
|
|
366 return __hashtable_alloc::_M_allocate_buckets(__n);
|
|
|
367 }
|
|
|
368
|
|
|
369 void
|
|
|
370 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
|
|
|
371 {
|
|
|
372 if (_M_uses_single_bucket(__bkts))
|
|
|
373 return;
|
|
|
374
|
|
|
375 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
|
|
|
376 }
|
|
|
377
|
|
|
378 void
|
|
|
379 _M_deallocate_buckets()
|
|
|
380 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
|
|
|
381
|
|
|
382 // Gets bucket begin, deals with the fact that non-empty buckets contain
|
|
|
383 // their before begin node.
|
|
|
384 __node_type*
|
|
|
385 _M_bucket_begin(size_type __bkt) const;
|
|
|
386
|
|
|
387 __node_type*
|
|
|
388 _M_begin() const
|
|
|
389 { return static_cast<__node_type*>(_M_before_begin._M_nxt); }
|
|
|
390
|
|
|
391 template<typename _NodeGenerator>
|
|
|
392 void
|
|
|
393 _M_assign(const _Hashtable&, const _NodeGenerator&);
|
|
|
394
|
|
|
395 void
|
|
|
396 _M_move_assign(_Hashtable&&, std::true_type);
|
|
|
397
|
|
|
398 void
|
|
|
399 _M_move_assign(_Hashtable&&, std::false_type);
|
|
|
400
|
|
|
401 void
|
|
|
402 _M_reset() noexcept;
|
|
|
403
|
|
|
404 _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h,
|
|
|
405 const _Equal& __eq, const _ExtractKey& __exk,
|
|
|
406 const allocator_type& __a)
|
|
|
407 : __hashtable_base(__exk, __h1, __h2, __h, __eq),
|
|
|
408 __hashtable_alloc(__node_alloc_type(__a))
|
|
|
409 { }
|
|
|
410
|
|
|
411 public:
|
|
|
412 // Constructor, destructor, assignment, swap
|
|
|
413 _Hashtable() = default;
|
|
|
414 _Hashtable(size_type __bucket_hint,
|
|
|
415 const _H1&, const _H2&, const _Hash&,
|
|
|
416 const _Equal&, const _ExtractKey&,
|
|
|
417 const allocator_type&);
|
|
|
418
|
|
|
419 template<typename _InputIterator>
|
|
|
420 _Hashtable(_InputIterator __first, _InputIterator __last,
|
|
|
421 size_type __bucket_hint,
|
|
|
422 const _H1&, const _H2&, const _Hash&,
|
|
|
423 const _Equal&, const _ExtractKey&,
|
|
|
424 const allocator_type&);
|
|
|
425
|
|
|
426 _Hashtable(const _Hashtable&);
|
|
|
427
|
|
|
428 _Hashtable(_Hashtable&&) noexcept;
|
|
|
429
|
|
|
430 _Hashtable(const _Hashtable&, const allocator_type&);
|
|
|
431
|
|
|
432 _Hashtable(_Hashtable&&, const allocator_type&);
|
|
|
433
|
|
|
434 // Use delegating constructors.
|
|
|
435 explicit
|
|
|
436 _Hashtable(const allocator_type& __a)
|
|
|
437 : __hashtable_alloc(__node_alloc_type(__a))
|
|
|
438 { }
|
|
|
439
|
|
|
440 explicit
|
|
|
441 _Hashtable(size_type __n,
|
|
|
442 const _H1& __hf = _H1(),
|
|
|
443 const key_equal& __eql = key_equal(),
|
|
|
444 const allocator_type& __a = allocator_type())
|
|
|
445 : _Hashtable(__n, __hf, _H2(), _Hash(), __eql,
|
|
|
446 __key_extract(), __a)
|
|
|
447 { }
|
|
|
448
|
|
|
449 template<typename _InputIterator>
|
|
|
450 _Hashtable(_InputIterator __f, _InputIterator __l,
|
|
|
451 size_type __n = 0,
|
|
|
452 const _H1& __hf = _H1(),
|
|
|
453 const key_equal& __eql = key_equal(),
|
|
|
454 const allocator_type& __a = allocator_type())
|
|
|
455 : _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
|
|
|
456 __key_extract(), __a)
|
|
|
457 { }
|
|
|
458
|
|
|
459 _Hashtable(initializer_list<value_type> __l,
|
|
|
460 size_type __n = 0,
|
|
|
461 const _H1& __hf = _H1(),
|
|
|
462 const key_equal& __eql = key_equal(),
|
|
|
463 const allocator_type& __a = allocator_type())
|
|
|
464 : _Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
|
|
|
465 __key_extract(), __a)
|
|
|
466 { }
|
|
|
467
|
|
|
468 _Hashtable&
|
|
|
469 operator=(const _Hashtable& __ht);
|
|
|
470
|
|
|
471 _Hashtable&
|
|
|
472 operator=(_Hashtable&& __ht)
|
|
|
473 noexcept(__node_alloc_traits::_S_nothrow_move()
|
|
|
474 && is_nothrow_move_assignable<_H1>::value
|
|
|
475 && is_nothrow_move_assignable<_Equal>::value)
|
|
|
476 {
|
|
|
477 constexpr bool __move_storage =
|
|
|
478 __node_alloc_traits::_S_propagate_on_move_assign()
|
|
|
479 || __node_alloc_traits::_S_always_equal();
|
|
|
480 _M_move_assign(std::move(__ht), __bool_constant<__move_storage>());
|
|
|
481 return *this;
|
|
|
482 }
|
|
|
483
|
|
|
484 _Hashtable&
|
|
|
485 operator=(initializer_list<value_type> __l)
|
|
|
486 {
|
|
|
487 __reuse_or_alloc_node_type __roan(_M_begin(), *this);
|
|
|
488 _M_before_begin._M_nxt = nullptr;
|
|
|
489 clear();
|
|
131
|
490 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
|
|
111
|
491 return *this;
|
|
|
492 }
|
|
|
493
|
|
|
494 ~_Hashtable() noexcept;
|
|
|
495
|
|
|
496 void
|
|
|
497 swap(_Hashtable&)
|
|
|
498 noexcept(__and_<__is_nothrow_swappable<_H1>,
|
|
|
499 __is_nothrow_swappable<_Equal>>::value);
|
|
|
500
|
|
|
501 // Basic container operations
|
|
|
502 iterator
|
|
|
503 begin() noexcept
|
|
|
504 { return iterator(_M_begin()); }
|
|
|
505
|
|
|
506 const_iterator
|
|
|
507 begin() const noexcept
|
|
|
508 { return const_iterator(_M_begin()); }
|
|
|
509
|
|
|
510 iterator
|
|
|
511 end() noexcept
|
|
|
512 { return iterator(nullptr); }
|
|
|
513
|
|
|
514 const_iterator
|
|
|
515 end() const noexcept
|
|
|
516 { return const_iterator(nullptr); }
|
|
|
517
|
|
|
518 const_iterator
|
|
|
519 cbegin() const noexcept
|
|
|
520 { return const_iterator(_M_begin()); }
|
|
|
521
|
|
|
522 const_iterator
|
|
|
523 cend() const noexcept
|
|
|
524 { return const_iterator(nullptr); }
|
|
|
525
|
|
|
526 size_type
|
|
|
527 size() const noexcept
|
|
|
528 { return _M_element_count; }
|
|
|
529
|
|
|
530 bool
|
|
|
531 empty() const noexcept
|
|
|
532 { return size() == 0; }
|
|
|
533
|
|
|
534 allocator_type
|
|
|
535 get_allocator() const noexcept
|
|
|
536 { return allocator_type(this->_M_node_allocator()); }
|
|
|
537
|
|
|
538 size_type
|
|
|
539 max_size() const noexcept
|
|
|
540 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
|
|
|
541
|
|
|
542 // Observers
|
|
|
543 key_equal
|
|
|
544 key_eq() const
|
|
|
545 { return this->_M_eq(); }
|
|
|
546
|
|
|
547 // hash_function, if present, comes from _Hash_code_base.
|
|
|
548
|
|
|
549 // Bucket operations
|
|
|
550 size_type
|
|
|
551 bucket_count() const noexcept
|
|
|
552 { return _M_bucket_count; }
|
|
|
553
|
|
|
554 size_type
|
|
|
555 max_bucket_count() const noexcept
|
|
|
556 { return max_size(); }
|
|
|
557
|
|
|
558 size_type
|
|
|
559 bucket_size(size_type __n) const
|
|
|
560 { return std::distance(begin(__n), end(__n)); }
|
|
|
561
|
|
|
562 size_type
|
|
|
563 bucket(const key_type& __k) const
|
|
|
564 { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
|
|
|
565
|
|
|
566 local_iterator
|
|
|
567 begin(size_type __n)
|
|
|
568 {
|
|
|
569 return local_iterator(*this, _M_bucket_begin(__n),
|
|
|
570 __n, _M_bucket_count);
|
|
|
571 }
|
|
|
572
|
|
|
573 local_iterator
|
|
|
574 end(size_type __n)
|
|
|
575 { return local_iterator(*this, nullptr, __n, _M_bucket_count); }
|
|
|
576
|
|
|
577 const_local_iterator
|
|
|
578 begin(size_type __n) const
|
|
|
579 {
|
|
|
580 return const_local_iterator(*this, _M_bucket_begin(__n),
|
|
|
581 __n, _M_bucket_count);
|
|
|
582 }
|
|
|
583
|
|
|
584 const_local_iterator
|
|
|
585 end(size_type __n) const
|
|
|
586 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
|
|
|
587
|
|
|
588 // DR 691.
|
|
|
589 const_local_iterator
|
|
|
590 cbegin(size_type __n) const
|
|
|
591 {
|
|
|
592 return const_local_iterator(*this, _M_bucket_begin(__n),
|
|
|
593 __n, _M_bucket_count);
|
|
|
594 }
|
|
|
595
|
|
|
596 const_local_iterator
|
|
|
597 cend(size_type __n) const
|
|
|
598 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
|
|
|
599
|
|
|
600 float
|
|
|
601 load_factor() const noexcept
|
|
|
602 {
|
|
|
603 return static_cast<float>(size()) / static_cast<float>(bucket_count());
|
|
|
604 }
|
|
|
605
|
|
|
606 // max_load_factor, if present, comes from _Rehash_base.
|
|
|
607
|
|
|
608 // Generalization of max_load_factor. Extension, not found in
|
|
|
609 // TR1. Only useful if _RehashPolicy is something other than
|
|
|
610 // the default.
|
|
|
611 const _RehashPolicy&
|
|
|
612 __rehash_policy() const
|
|
|
613 { return _M_rehash_policy; }
|
|
|
614
|
|
|
615 void
|
|
|
616 __rehash_policy(const _RehashPolicy& __pol)
|
|
|
617 { _M_rehash_policy = __pol; }
|
|
|
618
|
|
|
619 // Lookup.
|
|
|
620 iterator
|
|
|
621 find(const key_type& __k);
|
|
|
622
|
|
|
623 const_iterator
|
|
|
624 find(const key_type& __k) const;
|
|
|
625
|
|
|
626 size_type
|
|
|
627 count(const key_type& __k) const;
|
|
|
628
|
|
|
629 std::pair<iterator, iterator>
|
|
|
630 equal_range(const key_type& __k);
|
|
|
631
|
|
|
632 std::pair<const_iterator, const_iterator>
|
|
|
633 equal_range(const key_type& __k) const;
|
|
|
634
|
|
|
635 protected:
|
|
|
636 // Bucket index computation helpers.
|
|
|
637 size_type
|
|
|
638 _M_bucket_index(__node_type* __n) const noexcept
|
|
|
639 { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
|
|
|
640
|
|
|
641 size_type
|
|
|
642 _M_bucket_index(const key_type& __k, __hash_code __c) const
|
|
|
643 { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
|
|
|
644
|
|
|
645 // Find and insert helper functions and types
|
|
|
646 // Find the node before the one matching the criteria.
|
|
|
647 __node_base*
|
|
|
648 _M_find_before_node(size_type, const key_type&, __hash_code) const;
|
|
|
649
|
|
|
650 __node_type*
|
|
|
651 _M_find_node(size_type __bkt, const key_type& __key,
|
|
|
652 __hash_code __c) const
|
|
|
653 {
|
|
|
654 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
|
|
|
655 if (__before_n)
|
|
|
656 return static_cast<__node_type*>(__before_n->_M_nxt);
|
|
|
657 return nullptr;
|
|
|
658 }
|
|
|
659
|
|
|
660 // Insert a node at the beginning of a bucket.
|
|
|
661 void
|
|
|
662 _M_insert_bucket_begin(size_type, __node_type*);
|
|
|
663
|
|
|
664 // Remove the bucket first node
|
|
|
665 void
|
|
|
666 _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n,
|
|
|
667 size_type __next_bkt);
|
|
|
668
|
|
|
669 // Get the node before __n in the bucket __bkt
|
|
|
670 __node_base*
|
|
|
671 _M_get_previous_node(size_type __bkt, __node_base* __n);
|
|
|
672
|
|
|
673 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
|
|
|
674 // no element with its key already present). Take ownership of the node,
|
|
|
675 // deallocate it on exception.
|
|
|
676 iterator
|
|
|
677 _M_insert_unique_node(size_type __bkt, __hash_code __code,
|
|
131
|
678 __node_type* __n, size_type __n_elt = 1);
|
|
111
|
679
|
|
|
680 // Insert node with hash code __code. Take ownership of the node,
|
|
|
681 // deallocate it on exception.
|
|
|
682 iterator
|
|
|
683 _M_insert_multi_node(__node_type* __hint,
|
|
|
684 __hash_code __code, __node_type* __n);
|
|
|
685
|
|
|
686 template<typename... _Args>
|
|
|
687 std::pair<iterator, bool>
|
|
|
688 _M_emplace(std::true_type, _Args&&... __args);
|
|
|
689
|
|
|
690 template<typename... _Args>
|
|
|
691 iterator
|
|
|
692 _M_emplace(std::false_type __uk, _Args&&... __args)
|
|
|
693 { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
|
|
|
694
|
|
|
695 // Emplace with hint, useless when keys are unique.
|
|
|
696 template<typename... _Args>
|
|
|
697 iterator
|
|
|
698 _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args)
|
|
|
699 { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
|
|
|
700
|
|
|
701 template<typename... _Args>
|
|
|
702 iterator
|
|
|
703 _M_emplace(const_iterator, std::false_type, _Args&&... __args);
|
|
|
704
|
|
|
705 template<typename _Arg, typename _NodeGenerator>
|
|
|
706 std::pair<iterator, bool>
|
|
131
|
707 _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
|
|
111
|
708
|
|
|
709 template<typename _Arg, typename _NodeGenerator>
|
|
|
710 iterator
|
|
|
711 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
|
|
131
|
712 false_type __uk)
|
|
111
|
713 {
|
|
|
714 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
|
|
|
715 __uk);
|
|
|
716 }
|
|
|
717
|
|
|
718 // Insert with hint, not used when keys are unique.
|
|
|
719 template<typename _Arg, typename _NodeGenerator>
|
|
|
720 iterator
|
|
|
721 _M_insert(const_iterator, _Arg&& __arg,
|
|
131
|
722 const _NodeGenerator& __node_gen, true_type __uk)
|
|
111
|
723 {
|
|
|
724 return
|
|
|
725 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
|
|
|
726 }
|
|
|
727
|
|
|
728 // Insert with hint when keys are not unique.
|
|
|
729 template<typename _Arg, typename _NodeGenerator>
|
|
|
730 iterator
|
|
|
731 _M_insert(const_iterator, _Arg&&,
|
|
131
|
732 const _NodeGenerator&, false_type);
|
|
111
|
733
|
|
|
734 size_type
|
|
|
735 _M_erase(std::true_type, const key_type&);
|
|
|
736
|
|
|
737 size_type
|
|
|
738 _M_erase(std::false_type, const key_type&);
|
|
|
739
|
|
|
740 iterator
|
|
|
741 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
|
|
|
742
|
|
|
743 public:
|
|
|
744 // Emplace
|
|
|
745 template<typename... _Args>
|
|
|
746 __ireturn_type
|
|
|
747 emplace(_Args&&... __args)
|
|
|
748 { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
|
|
|
749
|
|
|
750 template<typename... _Args>
|
|
|
751 iterator
|
|
|
752 emplace_hint(const_iterator __hint, _Args&&... __args)
|
|
|
753 {
|
|
|
754 return _M_emplace(__hint, __unique_keys(),
|
|
|
755 std::forward<_Args>(__args)...);
|
|
|
756 }
|
|
|
757
|
|
|
758 // Insert member functions via inheritance.
|
|
|
759
|
|
|
760 // Erase
|
|
|
761 iterator
|
|
|
762 erase(const_iterator);
|
|
|
763
|
|
|
764 // LWG 2059.
|
|
|
765 iterator
|
|
|
766 erase(iterator __it)
|
|
|
767 { return erase(const_iterator(__it)); }
|
|
|
768
|
|
|
769 size_type
|
|
|
770 erase(const key_type& __k)
|
|
|
771 { return _M_erase(__unique_keys(), __k); }
|
|
|
772
|
|
|
773 iterator
|
|
|
774 erase(const_iterator, const_iterator);
|
|
|
775
|
|
|
776 void
|
|
|
777 clear() noexcept;
|
|
|
778
|
|
|
779 // Set number of buckets to be appropriate for container of n element.
|
|
|
780 void rehash(size_type __n);
|
|
|
781
|
|
|
782 // DR 1189.
|
|
|
783 // reserve, if present, comes from _Rehash_base.
|
|
|
784
|
|
|
785 #if __cplusplus > 201402L
|
|
|
786 /// Re-insert an extracted node into a container with unique keys.
|
|
|
787 insert_return_type
|
|
|
788 _M_reinsert_node(node_type&& __nh)
|
|
|
789 {
|
|
|
790 insert_return_type __ret;
|
|
|
791 if (__nh.empty())
|
|
|
792 __ret.position = end();
|
|
|
793 else
|
|
|
794 {
|
|
|
795 __glibcxx_assert(get_allocator() == __nh.get_allocator());
|
|
|
796
|
|
|
797 const key_type& __k = __nh._M_key();
|
|
|
798 __hash_code __code = this->_M_hash_code(__k);
|
|
|
799 size_type __bkt = _M_bucket_index(__k, __code);
|
|
|
800 if (__node_type* __n = _M_find_node(__bkt, __k, __code))
|
|
|
801 {
|
|
|
802 __ret.node = std::move(__nh);
|
|
|
803 __ret.position = iterator(__n);
|
|
|
804 __ret.inserted = false;
|
|
|
805 }
|
|
|
806 else
|
|
|
807 {
|
|
|
808 __ret.position
|
|
|
809 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
|
|
|
810 __nh._M_ptr = nullptr;
|
|
|
811 __ret.inserted = true;
|
|
|
812 }
|
|
|
813 }
|
|
|
814 return __ret;
|
|
|
815 }
|
|
|
816
|
|
|
817 /// Re-insert an extracted node into a container with equivalent keys.
|
|
|
818 iterator
|
|
|
819 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
|
|
|
820 {
|
|
|
821 iterator __ret;
|
|
|
822 if (__nh.empty())
|
|
|
823 __ret = end();
|
|
|
824 else
|
|
|
825 {
|
|
|
826 __glibcxx_assert(get_allocator() == __nh.get_allocator());
|
|
|
827
|
|
|
828 auto __code = this->_M_hash_code(__nh._M_key());
|
|
|
829 auto __node = std::exchange(__nh._M_ptr, nullptr);
|
|
|
830 // FIXME: this deallocates the node on exception.
|
|
|
831 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
|
|
|
832 }
|
|
|
833 return __ret;
|
|
|
834 }
|
|
|
835
|
|
|
836 /// Extract a node.
|
|
|
837 node_type
|
|
|
838 extract(const_iterator __pos)
|
|
|
839 {
|
|
|
840 __node_type* __n = __pos._M_cur;
|
|
|
841 size_t __bkt = _M_bucket_index(__n);
|
|
|
842
|
|
|
843 // Look for previous node to unlink it from the erased one, this
|
|
|
844 // is why we need buckets to contain the before begin to make
|
|
|
845 // this search fast.
|
|
|
846 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
|
|
|
847
|
|
|
848 if (__prev_n == _M_buckets[__bkt])
|
|
|
849 _M_remove_bucket_begin(__bkt, __n->_M_next(),
|
|
|
850 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
|
|
|
851 else if (__n->_M_nxt)
|
|
|
852 {
|
|
|
853 size_type __next_bkt = _M_bucket_index(__n->_M_next());
|
|
|
854 if (__next_bkt != __bkt)
|
|
|
855 _M_buckets[__next_bkt] = __prev_n;
|
|
|
856 }
|
|
|
857
|
|
|
858 __prev_n->_M_nxt = __n->_M_nxt;
|
|
|
859 __n->_M_nxt = nullptr;
|
|
|
860 --_M_element_count;
|
|
|
861 return { __n, this->_M_node_allocator() };
|
|
|
862 }
|
|
|
863
|
|
|
864 /// Extract a node.
|
|
|
865 node_type
|
|
|
866 extract(const _Key& __k)
|
|
|
867 {
|
|
|
868 node_type __nh;
|
|
|
869 auto __pos = find(__k);
|
|
|
870 if (__pos != end())
|
|
|
871 __nh = extract(const_iterator(__pos));
|
|
|
872 return __nh;
|
|
|
873 }
|
|
|
874
|
|
|
875 /// Merge from a compatible container into one with unique keys.
|
|
|
876 template<typename _Compatible_Hashtable>
|
|
|
877 void
|
|
|
878 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
|
|
|
879 {
|
|
|
880 static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
|
|
|
881 node_type>, "Node types are compatible");
|
|
|
882 __glibcxx_assert(get_allocator() == __src.get_allocator());
|
|
|
883
|
|
131
|
884 auto __n_elt = __src.size();
|
|
111
|
885 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
|
|
|
886 {
|
|
|
887 auto __pos = __i++;
|
|
|
888 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
|
|
|
889 __hash_code __code = this->_M_hash_code(__k);
|
|
|
890 size_type __bkt = _M_bucket_index(__k, __code);
|
|
|
891 if (_M_find_node(__bkt, __k, __code) == nullptr)
|
|
|
892 {
|
|
|
893 auto __nh = __src.extract(__pos);
|
|
131
|
894 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
|
|
111
|
895 __nh._M_ptr = nullptr;
|
|
131
|
896 __n_elt = 1;
|
|
111
|
897 }
|
|
131
|
898 else if (__n_elt != 1)
|
|
|
899 --__n_elt;
|
|
111
|
900 }
|
|
|
901 }
|
|
|
902
|
|
|
903 /// Merge from a compatible container into one with equivalent keys.
|
|
|
904 template<typename _Compatible_Hashtable>
|
|
|
905 void
|
|
|
906 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
|
|
|
907 {
|
|
|
908 static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
|
|
|
909 node_type>, "Node types are compatible");
|
|
|
910 __glibcxx_assert(get_allocator() == __src.get_allocator());
|
|
|
911
|
|
|
912 this->reserve(size() + __src.size());
|
|
|
913 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
|
|
|
914 _M_reinsert_node_multi(cend(), __src.extract(__i++));
|
|
|
915 }
|
|
|
916 #endif // C++17
|
|
|
917
|
|
|
918 private:
|
|
|
919 // Helper rehash method used when keys are unique.
|
|
|
920 void _M_rehash_aux(size_type __n, std::true_type);
|
|
|
921
|
|
|
922 // Helper rehash method used when keys can be non-unique.
|
|
|
923 void _M_rehash_aux(size_type __n, std::false_type);
|
|
|
924
|
|
|
925 // Unconditionally change size of bucket array to n, restore
|
|
|
926 // hash policy state to __state on exception.
|
|
|
927 void _M_rehash(size_type __n, const __rehash_state& __state);
|
|
|
928 };
|
|
|
929
|
|
|
930
|
|
|
931 // Definitions of class template _Hashtable's out-of-line member functions.
|
|
|
932 template<typename _Key, typename _Value,
|
|
|
933 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
934 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
935 typename _Traits>
|
|
|
936 auto
|
|
|
937 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
938 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
939 _M_bucket_begin(size_type __bkt) const
|
|
|
940 -> __node_type*
|
|
|
941 {
|
|
|
942 __node_base* __n = _M_buckets[__bkt];
|
|
|
943 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
|
|
|
944 }
|
|
|
945
|
|
|
946 template<typename _Key, typename _Value,
|
|
|
947 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
948 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
949 typename _Traits>
|
|
|
950 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
951 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
952 _Hashtable(size_type __bucket_hint,
|
|
|
953 const _H1& __h1, const _H2& __h2, const _Hash& __h,
|
|
|
954 const _Equal& __eq, const _ExtractKey& __exk,
|
|
|
955 const allocator_type& __a)
|
|
|
956 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
|
|
|
957 {
|
|
|
958 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
|
|
|
959 if (__bkt > _M_bucket_count)
|
|
|
960 {
|
|
|
961 _M_buckets = _M_allocate_buckets(__bkt);
|
|
|
962 _M_bucket_count = __bkt;
|
|
|
963 }
|
|
|
964 }
|
|
|
965
|
|
|
966 template<typename _Key, typename _Value,
|
|
|
967 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
968 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
969 typename _Traits>
|
|
|
970 template<typename _InputIterator>
|
|
|
971 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
972 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
973 _Hashtable(_InputIterator __f, _InputIterator __l,
|
|
|
974 size_type __bucket_hint,
|
|
|
975 const _H1& __h1, const _H2& __h2, const _Hash& __h,
|
|
|
976 const _Equal& __eq, const _ExtractKey& __exk,
|
|
|
977 const allocator_type& __a)
|
|
|
978 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
|
|
|
979 {
|
|
|
980 auto __nb_elems = __detail::__distance_fw(__f, __l);
|
|
|
981 auto __bkt_count =
|
|
|
982 _M_rehash_policy._M_next_bkt(
|
|
|
983 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
|
|
|
984 __bucket_hint));
|
|
|
985
|
|
|
986 if (__bkt_count > _M_bucket_count)
|
|
|
987 {
|
|
|
988 _M_buckets = _M_allocate_buckets(__bkt_count);
|
|
|
989 _M_bucket_count = __bkt_count;
|
|
|
990 }
|
|
|
991
|
|
|
992 for (; __f != __l; ++__f)
|
|
|
993 this->insert(*__f);
|
|
|
994 }
|
|
|
995
|
|
|
996 template<typename _Key, typename _Value,
|
|
|
997 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
998 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
999 typename _Traits>
|
|
|
1000 auto
|
|
|
1001 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1002 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1003 operator=(const _Hashtable& __ht)
|
|
|
1004 -> _Hashtable&
|
|
|
1005 {
|
|
|
1006 if (&__ht == this)
|
|
|
1007 return *this;
|
|
|
1008
|
|
|
1009 if (__node_alloc_traits::_S_propagate_on_copy_assign())
|
|
|
1010 {
|
|
|
1011 auto& __this_alloc = this->_M_node_allocator();
|
|
|
1012 auto& __that_alloc = __ht._M_node_allocator();
|
|
|
1013 if (!__node_alloc_traits::_S_always_equal()
|
|
|
1014 && __this_alloc != __that_alloc)
|
|
|
1015 {
|
|
|
1016 // Replacement allocator cannot free existing storage.
|
|
|
1017 this->_M_deallocate_nodes(_M_begin());
|
|
|
1018 _M_before_begin._M_nxt = nullptr;
|
|
|
1019 _M_deallocate_buckets();
|
|
|
1020 _M_buckets = nullptr;
|
|
|
1021 std::__alloc_on_copy(__this_alloc, __that_alloc);
|
|
|
1022 __hashtable_base::operator=(__ht);
|
|
|
1023 _M_bucket_count = __ht._M_bucket_count;
|
|
|
1024 _M_element_count = __ht._M_element_count;
|
|
|
1025 _M_rehash_policy = __ht._M_rehash_policy;
|
|
|
1026 __try
|
|
|
1027 {
|
|
|
1028 _M_assign(__ht,
|
|
|
1029 [this](const __node_type* __n)
|
|
|
1030 { return this->_M_allocate_node(__n->_M_v()); });
|
|
|
1031 }
|
|
|
1032 __catch(...)
|
|
|
1033 {
|
|
|
1034 // _M_assign took care of deallocating all memory. Now we
|
|
|
1035 // must make sure this instance remains in a usable state.
|
|
|
1036 _M_reset();
|
|
|
1037 __throw_exception_again;
|
|
|
1038 }
|
|
|
1039 return *this;
|
|
|
1040 }
|
|
|
1041 std::__alloc_on_copy(__this_alloc, __that_alloc);
|
|
|
1042 }
|
|
|
1043
|
|
|
1044 // Reuse allocated buckets and nodes.
|
|
|
1045 __bucket_type* __former_buckets = nullptr;
|
|
|
1046 std::size_t __former_bucket_count = _M_bucket_count;
|
|
|
1047 const __rehash_state& __former_state = _M_rehash_policy._M_state();
|
|
|
1048
|
|
|
1049 if (_M_bucket_count != __ht._M_bucket_count)
|
|
|
1050 {
|
|
|
1051 __former_buckets = _M_buckets;
|
|
|
1052 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
|
|
|
1053 _M_bucket_count = __ht._M_bucket_count;
|
|
|
1054 }
|
|
|
1055 else
|
|
|
1056 __builtin_memset(_M_buckets, 0,
|
|
|
1057 _M_bucket_count * sizeof(__bucket_type));
|
|
|
1058
|
|
|
1059 __try
|
|
|
1060 {
|
|
|
1061 __hashtable_base::operator=(__ht);
|
|
|
1062 _M_element_count = __ht._M_element_count;
|
|
|
1063 _M_rehash_policy = __ht._M_rehash_policy;
|
|
|
1064 __reuse_or_alloc_node_type __roan(_M_begin(), *this);
|
|
|
1065 _M_before_begin._M_nxt = nullptr;
|
|
|
1066 _M_assign(__ht,
|
|
|
1067 [&__roan](const __node_type* __n)
|
|
|
1068 { return __roan(__n->_M_v()); });
|
|
|
1069 if (__former_buckets)
|
|
|
1070 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
|
|
|
1071 }
|
|
|
1072 __catch(...)
|
|
|
1073 {
|
|
|
1074 if (__former_buckets)
|
|
|
1075 {
|
|
|
1076 // Restore previous buckets.
|
|
|
1077 _M_deallocate_buckets();
|
|
|
1078 _M_rehash_policy._M_reset(__former_state);
|
|
|
1079 _M_buckets = __former_buckets;
|
|
|
1080 _M_bucket_count = __former_bucket_count;
|
|
|
1081 }
|
|
|
1082 __builtin_memset(_M_buckets, 0,
|
|
|
1083 _M_bucket_count * sizeof(__bucket_type));
|
|
|
1084 __throw_exception_again;
|
|
|
1085 }
|
|
|
1086 return *this;
|
|
|
1087 }
|
|
|
1088
|
|
|
1089 template<typename _Key, typename _Value,
|
|
|
1090 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1091 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1092 typename _Traits>
|
|
|
1093 template<typename _NodeGenerator>
|
|
|
1094 void
|
|
|
1095 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1096 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1097 _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
|
|
|
1098 {
|
|
|
1099 __bucket_type* __buckets = nullptr;
|
|
|
1100 if (!_M_buckets)
|
|
|
1101 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
|
|
|
1102
|
|
|
1103 __try
|
|
|
1104 {
|
|
|
1105 if (!__ht._M_before_begin._M_nxt)
|
|
|
1106 return;
|
|
|
1107
|
|
|
1108 // First deal with the special first node pointed to by
|
|
|
1109 // _M_before_begin.
|
|
|
1110 __node_type* __ht_n = __ht._M_begin();
|
|
|
1111 __node_type* __this_n = __node_gen(__ht_n);
|
|
|
1112 this->_M_copy_code(__this_n, __ht_n);
|
|
|
1113 _M_before_begin._M_nxt = __this_n;
|
|
|
1114 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
|
|
|
1115
|
|
|
1116 // Then deal with other nodes.
|
|
|
1117 __node_base* __prev_n = __this_n;
|
|
|
1118 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
|
|
|
1119 {
|
|
|
1120 __this_n = __node_gen(__ht_n);
|
|
|
1121 __prev_n->_M_nxt = __this_n;
|
|
|
1122 this->_M_copy_code(__this_n, __ht_n);
|
|
|
1123 size_type __bkt = _M_bucket_index(__this_n);
|
|
|
1124 if (!_M_buckets[__bkt])
|
|
|
1125 _M_buckets[__bkt] = __prev_n;
|
|
|
1126 __prev_n = __this_n;
|
|
|
1127 }
|
|
|
1128 }
|
|
|
1129 __catch(...)
|
|
|
1130 {
|
|
|
1131 clear();
|
|
|
1132 if (__buckets)
|
|
|
1133 _M_deallocate_buckets();
|
|
|
1134 __throw_exception_again;
|
|
|
1135 }
|
|
|
1136 }
|
|
|
1137
|
|
|
1138 template<typename _Key, typename _Value,
|
|
|
1139 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1140 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1141 typename _Traits>
|
|
|
1142 void
|
|
|
1143 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1144 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1145 _M_reset() noexcept
|
|
|
1146 {
|
|
|
1147 _M_rehash_policy._M_reset();
|
|
|
1148 _M_bucket_count = 1;
|
|
|
1149 _M_single_bucket = nullptr;
|
|
|
1150 _M_buckets = &_M_single_bucket;
|
|
|
1151 _M_before_begin._M_nxt = nullptr;
|
|
|
1152 _M_element_count = 0;
|
|
|
1153 }
|
|
|
1154
|
|
|
1155 template<typename _Key, typename _Value,
|
|
|
1156 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1157 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1158 typename _Traits>
|
|
|
1159 void
|
|
|
1160 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1161 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1162 _M_move_assign(_Hashtable&& __ht, std::true_type)
|
|
|
1163 {
|
|
|
1164 this->_M_deallocate_nodes(_M_begin());
|
|
|
1165 _M_deallocate_buckets();
|
|
|
1166 __hashtable_base::operator=(std::move(__ht));
|
|
|
1167 _M_rehash_policy = __ht._M_rehash_policy;
|
|
|
1168 if (!__ht._M_uses_single_bucket())
|
|
|
1169 _M_buckets = __ht._M_buckets;
|
|
|
1170 else
|
|
|
1171 {
|
|
|
1172 _M_buckets = &_M_single_bucket;
|
|
|
1173 _M_single_bucket = __ht._M_single_bucket;
|
|
|
1174 }
|
|
|
1175 _M_bucket_count = __ht._M_bucket_count;
|
|
|
1176 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
|
|
|
1177 _M_element_count = __ht._M_element_count;
|
|
|
1178 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
|
|
|
1179
|
|
|
1180 // Fix buckets containing the _M_before_begin pointers that can't be
|
|
|
1181 // moved.
|
|
|
1182 if (_M_begin())
|
|
|
1183 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
|
|
|
1184 __ht._M_reset();
|
|
|
1185 }
|
|
|
1186
|
|
|
1187 template<typename _Key, typename _Value,
|
|
|
1188 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1189 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1190 typename _Traits>
|
|
|
1191 void
|
|
|
1192 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1193 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1194 _M_move_assign(_Hashtable&& __ht, std::false_type)
|
|
|
1195 {
|
|
|
1196 if (__ht._M_node_allocator() == this->_M_node_allocator())
|
|
|
1197 _M_move_assign(std::move(__ht), std::true_type());
|
|
|
1198 else
|
|
|
1199 {
|
|
|
1200 // Can't move memory, move elements then.
|
|
|
1201 __bucket_type* __former_buckets = nullptr;
|
|
|
1202 size_type __former_bucket_count = _M_bucket_count;
|
|
|
1203 const __rehash_state& __former_state = _M_rehash_policy._M_state();
|
|
|
1204
|
|
|
1205 if (_M_bucket_count != __ht._M_bucket_count)
|
|
|
1206 {
|
|
|
1207 __former_buckets = _M_buckets;
|
|
|
1208 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
|
|
|
1209 _M_bucket_count = __ht._M_bucket_count;
|
|
|
1210 }
|
|
|
1211 else
|
|
|
1212 __builtin_memset(_M_buckets, 0,
|
|
|
1213 _M_bucket_count * sizeof(__bucket_type));
|
|
|
1214
|
|
|
1215 __try
|
|
|
1216 {
|
|
|
1217 __hashtable_base::operator=(std::move(__ht));
|
|
|
1218 _M_element_count = __ht._M_element_count;
|
|
|
1219 _M_rehash_policy = __ht._M_rehash_policy;
|
|
|
1220 __reuse_or_alloc_node_type __roan(_M_begin(), *this);
|
|
|
1221 _M_before_begin._M_nxt = nullptr;
|
|
|
1222 _M_assign(__ht,
|
|
|
1223 [&__roan](__node_type* __n)
|
|
|
1224 { return __roan(std::move_if_noexcept(__n->_M_v())); });
|
|
|
1225 __ht.clear();
|
|
|
1226 }
|
|
|
1227 __catch(...)
|
|
|
1228 {
|
|
|
1229 if (__former_buckets)
|
|
|
1230 {
|
|
|
1231 _M_deallocate_buckets();
|
|
|
1232 _M_rehash_policy._M_reset(__former_state);
|
|
|
1233 _M_buckets = __former_buckets;
|
|
|
1234 _M_bucket_count = __former_bucket_count;
|
|
|
1235 }
|
|
|
1236 __builtin_memset(_M_buckets, 0,
|
|
|
1237 _M_bucket_count * sizeof(__bucket_type));
|
|
|
1238 __throw_exception_again;
|
|
|
1239 }
|
|
|
1240 }
|
|
|
1241 }
|
|
|
1242
|
|
|
1243 template<typename _Key, typename _Value,
|
|
|
1244 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1245 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1246 typename _Traits>
|
|
|
1247 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1248 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1249 _Hashtable(const _Hashtable& __ht)
|
|
|
1250 : __hashtable_base(__ht),
|
|
|
1251 __map_base(__ht),
|
|
|
1252 __rehash_base(__ht),
|
|
|
1253 __hashtable_alloc(
|
|
|
1254 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
|
|
|
1255 _M_buckets(nullptr),
|
|
|
1256 _M_bucket_count(__ht._M_bucket_count),
|
|
|
1257 _M_element_count(__ht._M_element_count),
|
|
|
1258 _M_rehash_policy(__ht._M_rehash_policy)
|
|
|
1259 {
|
|
|
1260 _M_assign(__ht,
|
|
|
1261 [this](const __node_type* __n)
|
|
|
1262 { return this->_M_allocate_node(__n->_M_v()); });
|
|
|
1263 }
|
|
|
1264
|
|
|
1265 template<typename _Key, typename _Value,
|
|
|
1266 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1267 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1268 typename _Traits>
|
|
|
1269 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1270 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1271 _Hashtable(_Hashtable&& __ht) noexcept
|
|
|
1272 : __hashtable_base(__ht),
|
|
|
1273 __map_base(__ht),
|
|
|
1274 __rehash_base(__ht),
|
|
|
1275 __hashtable_alloc(std::move(__ht._M_base_alloc())),
|
|
|
1276 _M_buckets(__ht._M_buckets),
|
|
|
1277 _M_bucket_count(__ht._M_bucket_count),
|
|
|
1278 _M_before_begin(__ht._M_before_begin._M_nxt),
|
|
|
1279 _M_element_count(__ht._M_element_count),
|
|
|
1280 _M_rehash_policy(__ht._M_rehash_policy)
|
|
|
1281 {
|
|
|
1282 // Update, if necessary, buckets if __ht is using its single bucket.
|
|
|
1283 if (__ht._M_uses_single_bucket())
|
|
|
1284 {
|
|
|
1285 _M_buckets = &_M_single_bucket;
|
|
|
1286 _M_single_bucket = __ht._M_single_bucket;
|
|
|
1287 }
|
|
|
1288
|
|
|
1289 // Update, if necessary, bucket pointing to before begin that hasn't
|
|
|
1290 // moved.
|
|
|
1291 if (_M_begin())
|
|
|
1292 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
|
|
|
1293
|
|
|
1294 __ht._M_reset();
|
|
|
1295 }
|
|
|
1296
|
|
|
1297 template<typename _Key, typename _Value,
|
|
|
1298 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1299 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1300 typename _Traits>
|
|
|
1301 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1302 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1303 _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
|
|
|
1304 : __hashtable_base(__ht),
|
|
|
1305 __map_base(__ht),
|
|
|
1306 __rehash_base(__ht),
|
|
|
1307 __hashtable_alloc(__node_alloc_type(__a)),
|
|
|
1308 _M_buckets(),
|
|
|
1309 _M_bucket_count(__ht._M_bucket_count),
|
|
|
1310 _M_element_count(__ht._M_element_count),
|
|
|
1311 _M_rehash_policy(__ht._M_rehash_policy)
|
|
|
1312 {
|
|
|
1313 _M_assign(__ht,
|
|
|
1314 [this](const __node_type* __n)
|
|
|
1315 { return this->_M_allocate_node(__n->_M_v()); });
|
|
|
1316 }
|
|
|
1317
|
|
|
1318 template<typename _Key, typename _Value,
|
|
|
1319 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1320 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1321 typename _Traits>
|
|
|
1322 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1323 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1324 _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
|
|
|
1325 : __hashtable_base(__ht),
|
|
|
1326 __map_base(__ht),
|
|
|
1327 __rehash_base(__ht),
|
|
|
1328 __hashtable_alloc(__node_alloc_type(__a)),
|
|
|
1329 _M_buckets(nullptr),
|
|
|
1330 _M_bucket_count(__ht._M_bucket_count),
|
|
|
1331 _M_element_count(__ht._M_element_count),
|
|
|
1332 _M_rehash_policy(__ht._M_rehash_policy)
|
|
|
1333 {
|
|
|
1334 if (__ht._M_node_allocator() == this->_M_node_allocator())
|
|
|
1335 {
|
|
|
1336 if (__ht._M_uses_single_bucket())
|
|
|
1337 {
|
|
|
1338 _M_buckets = &_M_single_bucket;
|
|
|
1339 _M_single_bucket = __ht._M_single_bucket;
|
|
|
1340 }
|
|
|
1341 else
|
|
|
1342 _M_buckets = __ht._M_buckets;
|
|
|
1343
|
|
|
1344 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
|
|
|
1345 // Update, if necessary, bucket pointing to before begin that hasn't
|
|
|
1346 // moved.
|
|
|
1347 if (_M_begin())
|
|
|
1348 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
|
|
|
1349 __ht._M_reset();
|
|
|
1350 }
|
|
|
1351 else
|
|
|
1352 {
|
|
|
1353 _M_assign(__ht,
|
|
|
1354 [this](__node_type* __n)
|
|
|
1355 {
|
|
|
1356 return this->_M_allocate_node(
|
|
|
1357 std::move_if_noexcept(__n->_M_v()));
|
|
|
1358 });
|
|
|
1359 __ht.clear();
|
|
|
1360 }
|
|
|
1361 }
|
|
|
1362
|
|
|
1363 template<typename _Key, typename _Value,
|
|
|
1364 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1365 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1366 typename _Traits>
|
|
|
1367 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1368 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1369 ~_Hashtable() noexcept
|
|
|
1370 {
|
|
|
1371 clear();
|
|
|
1372 _M_deallocate_buckets();
|
|
|
1373 }
|
|
|
1374
|
|
|
1375 template<typename _Key, typename _Value,
|
|
|
1376 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1377 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1378 typename _Traits>
|
|
|
1379 void
|
|
|
1380 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1381 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1382 swap(_Hashtable& __x)
|
|
|
1383 noexcept(__and_<__is_nothrow_swappable<_H1>,
|
|
|
1384 __is_nothrow_swappable<_Equal>>::value)
|
|
|
1385 {
|
|
|
1386 // The only base class with member variables is hash_code_base.
|
|
|
1387 // We define _Hash_code_base::_M_swap because different
|
|
|
1388 // specializations have different members.
|
|
|
1389 this->_M_swap(__x);
|
|
|
1390
|
|
|
1391 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
|
|
|
1392 std::swap(_M_rehash_policy, __x._M_rehash_policy);
|
|
|
1393
|
|
|
1394 // Deal properly with potentially moved instances.
|
|
|
1395 if (this->_M_uses_single_bucket())
|
|
|
1396 {
|
|
|
1397 if (!__x._M_uses_single_bucket())
|
|
|
1398 {
|
|
|
1399 _M_buckets = __x._M_buckets;
|
|
|
1400 __x._M_buckets = &__x._M_single_bucket;
|
|
|
1401 }
|
|
|
1402 }
|
|
|
1403 else if (__x._M_uses_single_bucket())
|
|
|
1404 {
|
|
|
1405 __x._M_buckets = _M_buckets;
|
|
|
1406 _M_buckets = &_M_single_bucket;
|
|
|
1407 }
|
|
|
1408 else
|
|
|
1409 std::swap(_M_buckets, __x._M_buckets);
|
|
|
1410
|
|
|
1411 std::swap(_M_bucket_count, __x._M_bucket_count);
|
|
|
1412 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
|
|
|
1413 std::swap(_M_element_count, __x._M_element_count);
|
|
|
1414 std::swap(_M_single_bucket, __x._M_single_bucket);
|
|
|
1415
|
|
|
1416 // Fix buckets containing the _M_before_begin pointers that can't be
|
|
|
1417 // swapped.
|
|
|
1418 if (_M_begin())
|
|
|
1419 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
|
|
|
1420
|
|
|
1421 if (__x._M_begin())
|
|
|
1422 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
|
|
|
1423 = &__x._M_before_begin;
|
|
|
1424 }
|
|
|
1425
|
|
|
1426 template<typename _Key, typename _Value,
|
|
|
1427 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1428 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1429 typename _Traits>
|
|
|
1430 auto
|
|
|
1431 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1432 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1433 find(const key_type& __k)
|
|
|
1434 -> iterator
|
|
|
1435 {
|
|
|
1436 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1437 std::size_t __n = _M_bucket_index(__k, __code);
|
|
|
1438 __node_type* __p = _M_find_node(__n, __k, __code);
|
|
|
1439 return __p ? iterator(__p) : end();
|
|
|
1440 }
|
|
|
1441
|
|
|
1442 template<typename _Key, typename _Value,
|
|
|
1443 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1444 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1445 typename _Traits>
|
|
|
1446 auto
|
|
|
1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1448 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1449 find(const key_type& __k) const
|
|
|
1450 -> const_iterator
|
|
|
1451 {
|
|
|
1452 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1453 std::size_t __n = _M_bucket_index(__k, __code);
|
|
|
1454 __node_type* __p = _M_find_node(__n, __k, __code);
|
|
|
1455 return __p ? const_iterator(__p) : end();
|
|
|
1456 }
|
|
|
1457
|
|
|
1458 template<typename _Key, typename _Value,
|
|
|
1459 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1460 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1461 typename _Traits>
|
|
|
1462 auto
|
|
|
1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1464 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1465 count(const key_type& __k) const
|
|
|
1466 -> size_type
|
|
|
1467 {
|
|
|
1468 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1469 std::size_t __n = _M_bucket_index(__k, __code);
|
|
|
1470 __node_type* __p = _M_bucket_begin(__n);
|
|
|
1471 if (!__p)
|
|
|
1472 return 0;
|
|
|
1473
|
|
|
1474 std::size_t __result = 0;
|
|
|
1475 for (;; __p = __p->_M_next())
|
|
|
1476 {
|
|
|
1477 if (this->_M_equals(__k, __code, __p))
|
|
|
1478 ++__result;
|
|
|
1479 else if (__result)
|
|
|
1480 // All equivalent values are next to each other, if we
|
|
|
1481 // found a non-equivalent value after an equivalent one it
|
|
|
1482 // means that we won't find any new equivalent value.
|
|
|
1483 break;
|
|
|
1484 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
|
|
|
1485 break;
|
|
|
1486 }
|
|
|
1487 return __result;
|
|
|
1488 }
|
|
|
1489
|
|
|
1490 template<typename _Key, typename _Value,
|
|
|
1491 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1492 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1493 typename _Traits>
|
|
|
1494 auto
|
|
|
1495 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1496 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1497 equal_range(const key_type& __k)
|
|
|
1498 -> pair<iterator, iterator>
|
|
|
1499 {
|
|
|
1500 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1501 std::size_t __n = _M_bucket_index(__k, __code);
|
|
|
1502 __node_type* __p = _M_find_node(__n, __k, __code);
|
|
|
1503
|
|
|
1504 if (__p)
|
|
|
1505 {
|
|
|
1506 __node_type* __p1 = __p->_M_next();
|
|
|
1507 while (__p1 && _M_bucket_index(__p1) == __n
|
|
|
1508 && this->_M_equals(__k, __code, __p1))
|
|
|
1509 __p1 = __p1->_M_next();
|
|
|
1510
|
|
|
1511 return std::make_pair(iterator(__p), iterator(__p1));
|
|
|
1512 }
|
|
|
1513 else
|
|
|
1514 return std::make_pair(end(), end());
|
|
|
1515 }
|
|
|
1516
|
|
|
1517 template<typename _Key, typename _Value,
|
|
|
1518 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1519 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1520 typename _Traits>
|
|
|
1521 auto
|
|
|
1522 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1523 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1524 equal_range(const key_type& __k) const
|
|
|
1525 -> pair<const_iterator, const_iterator>
|
|
|
1526 {
|
|
|
1527 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1528 std::size_t __n = _M_bucket_index(__k, __code);
|
|
|
1529 __node_type* __p = _M_find_node(__n, __k, __code);
|
|
|
1530
|
|
|
1531 if (__p)
|
|
|
1532 {
|
|
|
1533 __node_type* __p1 = __p->_M_next();
|
|
|
1534 while (__p1 && _M_bucket_index(__p1) == __n
|
|
|
1535 && this->_M_equals(__k, __code, __p1))
|
|
|
1536 __p1 = __p1->_M_next();
|
|
|
1537
|
|
|
1538 return std::make_pair(const_iterator(__p), const_iterator(__p1));
|
|
|
1539 }
|
|
|
1540 else
|
|
|
1541 return std::make_pair(end(), end());
|
|
|
1542 }
|
|
|
1543
|
|
|
1544 // Find the node whose key compares equal to k in the bucket n.
|
|
|
1545 // Return nullptr if no node is found.
|
|
|
1546 template<typename _Key, typename _Value,
|
|
|
1547 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1548 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1549 typename _Traits>
|
|
|
1550 auto
|
|
|
1551 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1552 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1553 _M_find_before_node(size_type __n, const key_type& __k,
|
|
|
1554 __hash_code __code) const
|
|
|
1555 -> __node_base*
|
|
|
1556 {
|
|
|
1557 __node_base* __prev_p = _M_buckets[__n];
|
|
|
1558 if (!__prev_p)
|
|
|
1559 return nullptr;
|
|
|
1560
|
|
|
1561 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
|
|
|
1562 __p = __p->_M_next())
|
|
|
1563 {
|
|
|
1564 if (this->_M_equals(__k, __code, __p))
|
|
|
1565 return __prev_p;
|
|
|
1566
|
|
|
1567 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
|
|
|
1568 break;
|
|
|
1569 __prev_p = __p;
|
|
|
1570 }
|
|
|
1571 return nullptr;
|
|
|
1572 }
|
|
|
1573
|
|
|
1574 template<typename _Key, typename _Value,
|
|
|
1575 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1576 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1577 typename _Traits>
|
|
|
1578 void
|
|
|
1579 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1580 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1581 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
|
|
|
1582 {
|
|
|
1583 if (_M_buckets[__bkt])
|
|
|
1584 {
|
|
|
1585 // Bucket is not empty, we just need to insert the new node
|
|
|
1586 // after the bucket before begin.
|
|
|
1587 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
|
|
|
1588 _M_buckets[__bkt]->_M_nxt = __node;
|
|
|
1589 }
|
|
|
1590 else
|
|
|
1591 {
|
|
|
1592 // The bucket is empty, the new node is inserted at the
|
|
|
1593 // beginning of the singly-linked list and the bucket will
|
|
|
1594 // contain _M_before_begin pointer.
|
|
|
1595 __node->_M_nxt = _M_before_begin._M_nxt;
|
|
|
1596 _M_before_begin._M_nxt = __node;
|
|
|
1597 if (__node->_M_nxt)
|
|
|
1598 // We must update former begin bucket that is pointing to
|
|
|
1599 // _M_before_begin.
|
|
|
1600 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
|
|
|
1601 _M_buckets[__bkt] = &_M_before_begin;
|
|
|
1602 }
|
|
|
1603 }
|
|
|
1604
|
|
|
1605 template<typename _Key, typename _Value,
|
|
|
1606 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1607 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1608 typename _Traits>
|
|
|
1609 void
|
|
|
1610 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1611 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1612 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
|
|
|
1613 size_type __next_bkt)
|
|
|
1614 {
|
|
|
1615 if (!__next || __next_bkt != __bkt)
|
|
|
1616 {
|
|
|
1617 // Bucket is now empty
|
|
|
1618 // First update next bucket if any
|
|
|
1619 if (__next)
|
|
|
1620 _M_buckets[__next_bkt] = _M_buckets[__bkt];
|
|
|
1621
|
|
|
1622 // Second update before begin node if necessary
|
|
|
1623 if (&_M_before_begin == _M_buckets[__bkt])
|
|
|
1624 _M_before_begin._M_nxt = __next;
|
|
|
1625 _M_buckets[__bkt] = nullptr;
|
|
|
1626 }
|
|
|
1627 }
|
|
|
1628
|
|
|
1629 template<typename _Key, typename _Value,
|
|
|
1630 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1631 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1632 typename _Traits>
|
|
|
1633 auto
|
|
|
1634 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1635 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1636 _M_get_previous_node(size_type __bkt, __node_base* __n)
|
|
|
1637 -> __node_base*
|
|
|
1638 {
|
|
|
1639 __node_base* __prev_n = _M_buckets[__bkt];
|
|
|
1640 while (__prev_n->_M_nxt != __n)
|
|
|
1641 __prev_n = __prev_n->_M_nxt;
|
|
|
1642 return __prev_n;
|
|
|
1643 }
|
|
|
1644
|
|
|
1645 template<typename _Key, typename _Value,
|
|
|
1646 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1647 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1648 typename _Traits>
|
|
|
1649 template<typename... _Args>
|
|
|
1650 auto
|
|
|
1651 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1652 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1653 _M_emplace(std::true_type, _Args&&... __args)
|
|
|
1654 -> pair<iterator, bool>
|
|
|
1655 {
|
|
|
1656 // First build the node to get access to the hash code
|
|
|
1657 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
|
|
|
1658 const key_type& __k = this->_M_extract()(__node->_M_v());
|
|
|
1659 __hash_code __code;
|
|
|
1660 __try
|
|
|
1661 {
|
|
|
1662 __code = this->_M_hash_code(__k);
|
|
|
1663 }
|
|
|
1664 __catch(...)
|
|
|
1665 {
|
|
|
1666 this->_M_deallocate_node(__node);
|
|
|
1667 __throw_exception_again;
|
|
|
1668 }
|
|
|
1669
|
|
|
1670 size_type __bkt = _M_bucket_index(__k, __code);
|
|
|
1671 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
|
|
|
1672 {
|
|
|
1673 // There is already an equivalent node, no insertion
|
|
|
1674 this->_M_deallocate_node(__node);
|
|
|
1675 return std::make_pair(iterator(__p), false);
|
|
|
1676 }
|
|
|
1677
|
|
|
1678 // Insert the node
|
|
|
1679 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
|
|
|
1680 true);
|
|
|
1681 }
|
|
|
1682
|
|
|
1683 template<typename _Key, typename _Value,
|
|
|
1684 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1685 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1686 typename _Traits>
|
|
|
1687 template<typename... _Args>
|
|
|
1688 auto
|
|
|
1689 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1690 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1691 _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
|
|
|
1692 -> iterator
|
|
|
1693 {
|
|
|
1694 // First build the node to get its hash code.
|
|
|
1695 __node_type* __node =
|
|
|
1696 this->_M_allocate_node(std::forward<_Args>(__args)...);
|
|
|
1697
|
|
|
1698 __hash_code __code;
|
|
|
1699 __try
|
|
|
1700 {
|
|
|
1701 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
|
|
|
1702 }
|
|
|
1703 __catch(...)
|
|
|
1704 {
|
|
|
1705 this->_M_deallocate_node(__node);
|
|
|
1706 __throw_exception_again;
|
|
|
1707 }
|
|
|
1708
|
|
|
1709 return _M_insert_multi_node(__hint._M_cur, __code, __node);
|
|
|
1710 }
|
|
|
1711
|
|
|
1712 template<typename _Key, typename _Value,
|
|
|
1713 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1714 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1715 typename _Traits>
|
|
|
1716 auto
|
|
|
1717 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1718 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1719 _M_insert_unique_node(size_type __bkt, __hash_code __code,
|
|
131
|
1720 __node_type* __node, size_type __n_elt)
|
|
111
|
1721 -> iterator
|
|
|
1722 {
|
|
|
1723 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
|
|
|
1724 std::pair<bool, std::size_t> __do_rehash
|
|
131
|
1725 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
|
|
|
1726 __n_elt);
|
|
111
|
1727
|
|
|
1728 __try
|
|
|
1729 {
|
|
|
1730 if (__do_rehash.first)
|
|
|
1731 {
|
|
|
1732 _M_rehash(__do_rehash.second, __saved_state);
|
|
|
1733 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
|
|
|
1734 }
|
|
|
1735
|
|
|
1736 this->_M_store_code(__node, __code);
|
|
|
1737
|
|
|
1738 // Always insert at the beginning of the bucket.
|
|
|
1739 _M_insert_bucket_begin(__bkt, __node);
|
|
|
1740 ++_M_element_count;
|
|
|
1741 return iterator(__node);
|
|
|
1742 }
|
|
|
1743 __catch(...)
|
|
|
1744 {
|
|
|
1745 this->_M_deallocate_node(__node);
|
|
|
1746 __throw_exception_again;
|
|
|
1747 }
|
|
|
1748 }
|
|
|
1749
|
|
|
1750 // Insert node, in bucket bkt if no rehash (assumes no element with its key
|
|
|
1751 // already present). Take ownership of the node, deallocate it on exception.
|
|
|
1752 template<typename _Key, typename _Value,
|
|
|
1753 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1754 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1755 typename _Traits>
|
|
|
1756 auto
|
|
|
1757 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1758 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1759 _M_insert_multi_node(__node_type* __hint, __hash_code __code,
|
|
|
1760 __node_type* __node)
|
|
|
1761 -> iterator
|
|
|
1762 {
|
|
|
1763 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
|
|
|
1764 std::pair<bool, std::size_t> __do_rehash
|
|
|
1765 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
|
|
|
1766
|
|
|
1767 __try
|
|
|
1768 {
|
|
|
1769 if (__do_rehash.first)
|
|
|
1770 _M_rehash(__do_rehash.second, __saved_state);
|
|
|
1771
|
|
|
1772 this->_M_store_code(__node, __code);
|
|
|
1773 const key_type& __k = this->_M_extract()(__node->_M_v());
|
|
|
1774 size_type __bkt = _M_bucket_index(__k, __code);
|
|
|
1775
|
|
|
1776 // Find the node before an equivalent one or use hint if it exists and
|
|
|
1777 // if it is equivalent.
|
|
|
1778 __node_base* __prev
|
|
|
1779 = __builtin_expect(__hint != nullptr, false)
|
|
|
1780 && this->_M_equals(__k, __code, __hint)
|
|
|
1781 ? __hint
|
|
|
1782 : _M_find_before_node(__bkt, __k, __code);
|
|
|
1783 if (__prev)
|
|
|
1784 {
|
|
|
1785 // Insert after the node before the equivalent one.
|
|
|
1786 __node->_M_nxt = __prev->_M_nxt;
|
|
|
1787 __prev->_M_nxt = __node;
|
|
|
1788 if (__builtin_expect(__prev == __hint, false))
|
|
|
1789 // hint might be the last bucket node, in this case we need to
|
|
|
1790 // update next bucket.
|
|
|
1791 if (__node->_M_nxt
|
|
|
1792 && !this->_M_equals(__k, __code, __node->_M_next()))
|
|
|
1793 {
|
|
|
1794 size_type __next_bkt = _M_bucket_index(__node->_M_next());
|
|
|
1795 if (__next_bkt != __bkt)
|
|
|
1796 _M_buckets[__next_bkt] = __node;
|
|
|
1797 }
|
|
|
1798 }
|
|
|
1799 else
|
|
|
1800 // The inserted node has no equivalent in the
|
|
|
1801 // hashtable. We must insert the new node at the
|
|
|
1802 // beginning of the bucket to preserve equivalent
|
|
|
1803 // elements' relative positions.
|
|
|
1804 _M_insert_bucket_begin(__bkt, __node);
|
|
|
1805 ++_M_element_count;
|
|
|
1806 return iterator(__node);
|
|
|
1807 }
|
|
|
1808 __catch(...)
|
|
|
1809 {
|
|
|
1810 this->_M_deallocate_node(__node);
|
|
|
1811 __throw_exception_again;
|
|
|
1812 }
|
|
|
1813 }
|
|
|
1814
|
|
|
1815 // Insert v if no element with its key is already present.
|
|
|
1816 template<typename _Key, typename _Value,
|
|
|
1817 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1818 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1819 typename _Traits>
|
|
|
1820 template<typename _Arg, typename _NodeGenerator>
|
|
|
1821 auto
|
|
|
1822 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1823 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
131
|
1824 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
|
|
|
1825 size_type __n_elt)
|
|
111
|
1826 -> pair<iterator, bool>
|
|
|
1827 {
|
|
|
1828 const key_type& __k = this->_M_extract()(__v);
|
|
|
1829 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1830 size_type __bkt = _M_bucket_index(__k, __code);
|
|
|
1831
|
|
|
1832 __node_type* __n = _M_find_node(__bkt, __k, __code);
|
|
|
1833 if (__n)
|
|
|
1834 return std::make_pair(iterator(__n), false);
|
|
|
1835
|
|
|
1836 __n = __node_gen(std::forward<_Arg>(__v));
|
|
131
|
1837 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
|
|
111
|
1838 }
|
|
|
1839
|
|
|
1840 // Insert v unconditionally.
|
|
|
1841 template<typename _Key, typename _Value,
|
|
|
1842 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1843 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1844 typename _Traits>
|
|
|
1845 template<typename _Arg, typename _NodeGenerator>
|
|
|
1846 auto
|
|
|
1847 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1848 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1849 _M_insert(const_iterator __hint, _Arg&& __v,
|
|
131
|
1850 const _NodeGenerator& __node_gen, false_type)
|
|
111
|
1851 -> iterator
|
|
|
1852 {
|
|
|
1853 // First compute the hash code so that we don't do anything if it
|
|
|
1854 // throws.
|
|
|
1855 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
|
|
|
1856
|
|
|
1857 // Second allocate new node so that we don't rehash if it throws.
|
|
|
1858 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
|
|
|
1859
|
|
|
1860 return _M_insert_multi_node(__hint._M_cur, __code, __node);
|
|
|
1861 }
|
|
|
1862
|
|
|
1863 template<typename _Key, typename _Value,
|
|
|
1864 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1865 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1866 typename _Traits>
|
|
|
1867 auto
|
|
|
1868 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1869 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1870 erase(const_iterator __it)
|
|
|
1871 -> iterator
|
|
|
1872 {
|
|
|
1873 __node_type* __n = __it._M_cur;
|
|
|
1874 std::size_t __bkt = _M_bucket_index(__n);
|
|
|
1875
|
|
|
1876 // Look for previous node to unlink it from the erased one, this
|
|
|
1877 // is why we need buckets to contain the before begin to make
|
|
|
1878 // this search fast.
|
|
|
1879 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
|
|
|
1880 return _M_erase(__bkt, __prev_n, __n);
|
|
|
1881 }
|
|
|
1882
|
|
|
1883 template<typename _Key, typename _Value,
|
|
|
1884 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1885 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1886 typename _Traits>
|
|
|
1887 auto
|
|
|
1888 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1889 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1890 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
|
|
|
1891 -> iterator
|
|
|
1892 {
|
|
|
1893 if (__prev_n == _M_buckets[__bkt])
|
|
|
1894 _M_remove_bucket_begin(__bkt, __n->_M_next(),
|
|
|
1895 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
|
|
|
1896 else if (__n->_M_nxt)
|
|
|
1897 {
|
|
|
1898 size_type __next_bkt = _M_bucket_index(__n->_M_next());
|
|
|
1899 if (__next_bkt != __bkt)
|
|
|
1900 _M_buckets[__next_bkt] = __prev_n;
|
|
|
1901 }
|
|
|
1902
|
|
|
1903 __prev_n->_M_nxt = __n->_M_nxt;
|
|
|
1904 iterator __result(__n->_M_next());
|
|
|
1905 this->_M_deallocate_node(__n);
|
|
|
1906 --_M_element_count;
|
|
|
1907
|
|
|
1908 return __result;
|
|
|
1909 }
|
|
|
1910
|
|
|
1911 template<typename _Key, typename _Value,
|
|
|
1912 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1913 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1914 typename _Traits>
|
|
|
1915 auto
|
|
|
1916 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1917 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1918 _M_erase(std::true_type, const key_type& __k)
|
|
|
1919 -> size_type
|
|
|
1920 {
|
|
|
1921 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1922 std::size_t __bkt = _M_bucket_index(__k, __code);
|
|
|
1923
|
|
|
1924 // Look for the node before the first matching node.
|
|
|
1925 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
|
|
|
1926 if (!__prev_n)
|
|
|
1927 return 0;
|
|
|
1928
|
|
|
1929 // We found a matching node, erase it.
|
|
|
1930 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
|
|
|
1931 _M_erase(__bkt, __prev_n, __n);
|
|
|
1932 return 1;
|
|
|
1933 }
|
|
|
1934
|
|
|
1935 template<typename _Key, typename _Value,
|
|
|
1936 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1937 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1938 typename _Traits>
|
|
|
1939 auto
|
|
|
1940 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1941 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1942 _M_erase(std::false_type, const key_type& __k)
|
|
|
1943 -> size_type
|
|
|
1944 {
|
|
|
1945 __hash_code __code = this->_M_hash_code(__k);
|
|
|
1946 std::size_t __bkt = _M_bucket_index(__k, __code);
|
|
|
1947
|
|
|
1948 // Look for the node before the first matching node.
|
|
|
1949 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
|
|
|
1950 if (!__prev_n)
|
|
|
1951 return 0;
|
|
|
1952
|
|
|
1953 // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|
|
1954 // 526. Is it undefined if a function in the standard changes
|
|
|
1955 // in parameters?
|
|
|
1956 // We use one loop to find all matching nodes and another to deallocate
|
|
|
1957 // them so that the key stays valid during the first loop. It might be
|
|
|
1958 // invalidated indirectly when destroying nodes.
|
|
|
1959 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
|
|
|
1960 __node_type* __n_last = __n;
|
|
|
1961 std::size_t __n_last_bkt = __bkt;
|
|
|
1962 do
|
|
|
1963 {
|
|
|
1964 __n_last = __n_last->_M_next();
|
|
|
1965 if (!__n_last)
|
|
|
1966 break;
|
|
|
1967 __n_last_bkt = _M_bucket_index(__n_last);
|
|
|
1968 }
|
|
|
1969 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
|
|
|
1970
|
|
|
1971 // Deallocate nodes.
|
|
|
1972 size_type __result = 0;
|
|
|
1973 do
|
|
|
1974 {
|
|
|
1975 __node_type* __p = __n->_M_next();
|
|
|
1976 this->_M_deallocate_node(__n);
|
|
|
1977 __n = __p;
|
|
|
1978 ++__result;
|
|
|
1979 --_M_element_count;
|
|
|
1980 }
|
|
|
1981 while (__n != __n_last);
|
|
|
1982
|
|
|
1983 if (__prev_n == _M_buckets[__bkt])
|
|
|
1984 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
|
|
|
1985 else if (__n_last && __n_last_bkt != __bkt)
|
|
|
1986 _M_buckets[__n_last_bkt] = __prev_n;
|
|
|
1987 __prev_n->_M_nxt = __n_last;
|
|
|
1988 return __result;
|
|
|
1989 }
|
|
|
1990
|
|
|
1991 template<typename _Key, typename _Value,
|
|
|
1992 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
1993 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1994 typename _Traits>
|
|
|
1995 auto
|
|
|
1996 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
1997 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
1998 erase(const_iterator __first, const_iterator __last)
|
|
|
1999 -> iterator
|
|
|
2000 {
|
|
|
2001 __node_type* __n = __first._M_cur;
|
|
|
2002 __node_type* __last_n = __last._M_cur;
|
|
|
2003 if (__n == __last_n)
|
|
|
2004 return iterator(__n);
|
|
|
2005
|
|
|
2006 std::size_t __bkt = _M_bucket_index(__n);
|
|
|
2007
|
|
|
2008 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
|
|
|
2009 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
|
|
|
2010 std::size_t __n_bkt = __bkt;
|
|
|
2011 for (;;)
|
|
|
2012 {
|
|
|
2013 do
|
|
|
2014 {
|
|
|
2015 __node_type* __tmp = __n;
|
|
|
2016 __n = __n->_M_next();
|
|
|
2017 this->_M_deallocate_node(__tmp);
|
|
|
2018 --_M_element_count;
|
|
|
2019 if (!__n)
|
|
|
2020 break;
|
|
|
2021 __n_bkt = _M_bucket_index(__n);
|
|
|
2022 }
|
|
|
2023 while (__n != __last_n && __n_bkt == __bkt);
|
|
|
2024 if (__is_bucket_begin)
|
|
|
2025 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
|
|
|
2026 if (__n == __last_n)
|
|
|
2027 break;
|
|
|
2028 __is_bucket_begin = true;
|
|
|
2029 __bkt = __n_bkt;
|
|
|
2030 }
|
|
|
2031
|
|
|
2032 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
|
|
|
2033 _M_buckets[__n_bkt] = __prev_n;
|
|
|
2034 __prev_n->_M_nxt = __n;
|
|
|
2035 return iterator(__n);
|
|
|
2036 }
|
|
|
2037
|
|
|
2038 template<typename _Key, typename _Value,
|
|
|
2039 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
2040 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
2041 typename _Traits>
|
|
|
2042 void
|
|
|
2043 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
2044 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
2045 clear() noexcept
|
|
|
2046 {
|
|
|
2047 this->_M_deallocate_nodes(_M_begin());
|
|
|
2048 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
|
|
|
2049 _M_element_count = 0;
|
|
|
2050 _M_before_begin._M_nxt = nullptr;
|
|
|
2051 }
|
|
|
2052
|
|
|
2053 template<typename _Key, typename _Value,
|
|
|
2054 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
2055 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
2056 typename _Traits>
|
|
|
2057 void
|
|
|
2058 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
2059 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
2060 rehash(size_type __n)
|
|
|
2061 {
|
|
|
2062 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
|
|
|
2063 std::size_t __buckets
|
|
|
2064 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
|
|
|
2065 __n);
|
|
|
2066 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
|
|
|
2067
|
|
|
2068 if (__buckets != _M_bucket_count)
|
|
|
2069 _M_rehash(__buckets, __saved_state);
|
|
|
2070 else
|
|
|
2071 // No rehash, restore previous state to keep a consistent state.
|
|
|
2072 _M_rehash_policy._M_reset(__saved_state);
|
|
|
2073 }
|
|
|
2074
|
|
|
2075 template<typename _Key, typename _Value,
|
|
|
2076 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
2077 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
2078 typename _Traits>
|
|
|
2079 void
|
|
|
2080 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
2081 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
2082 _M_rehash(size_type __n, const __rehash_state& __state)
|
|
|
2083 {
|
|
|
2084 __try
|
|
|
2085 {
|
|
|
2086 _M_rehash_aux(__n, __unique_keys());
|
|
|
2087 }
|
|
|
2088 __catch(...)
|
|
|
2089 {
|
|
|
2090 // A failure here means that buckets allocation failed. We only
|
|
|
2091 // have to restore hash policy previous state.
|
|
|
2092 _M_rehash_policy._M_reset(__state);
|
|
|
2093 __throw_exception_again;
|
|
|
2094 }
|
|
|
2095 }
|
|
|
2096
|
|
|
2097 // Rehash when there is no equivalent elements.
|
|
|
2098 template<typename _Key, typename _Value,
|
|
|
2099 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
2100 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
2101 typename _Traits>
|
|
|
2102 void
|
|
|
2103 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
2104 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
2105 _M_rehash_aux(size_type __n, std::true_type)
|
|
|
2106 {
|
|
|
2107 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
|
|
|
2108 __node_type* __p = _M_begin();
|
|
|
2109 _M_before_begin._M_nxt = nullptr;
|
|
|
2110 std::size_t __bbegin_bkt = 0;
|
|
|
2111 while (__p)
|
|
|
2112 {
|
|
|
2113 __node_type* __next = __p->_M_next();
|
|
|
2114 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
|
|
|
2115 if (!__new_buckets[__bkt])
|
|
|
2116 {
|
|
|
2117 __p->_M_nxt = _M_before_begin._M_nxt;
|
|
|
2118 _M_before_begin._M_nxt = __p;
|
|
|
2119 __new_buckets[__bkt] = &_M_before_begin;
|
|
|
2120 if (__p->_M_nxt)
|
|
|
2121 __new_buckets[__bbegin_bkt] = __p;
|
|
|
2122 __bbegin_bkt = __bkt;
|
|
|
2123 }
|
|
|
2124 else
|
|
|
2125 {
|
|
|
2126 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
|
|
|
2127 __new_buckets[__bkt]->_M_nxt = __p;
|
|
|
2128 }
|
|
|
2129 __p = __next;
|
|
|
2130 }
|
|
|
2131
|
|
|
2132 _M_deallocate_buckets();
|
|
|
2133 _M_bucket_count = __n;
|
|
|
2134 _M_buckets = __new_buckets;
|
|
|
2135 }
|
|
|
2136
|
|
|
2137 // Rehash when there can be equivalent elements, preserve their relative
|
|
|
2138 // order.
|
|
|
2139 template<typename _Key, typename _Value,
|
|
|
2140 typename _Alloc, typename _ExtractKey, typename _Equal,
|
|
|
2141 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
2142 typename _Traits>
|
|
|
2143 void
|
|
|
2144 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
|
|
|
2145 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
|
|
|
2146 _M_rehash_aux(size_type __n, std::false_type)
|
|
|
2147 {
|
|
|
2148 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
|
|
|
2149
|
|
|
2150 __node_type* __p = _M_begin();
|
|
|
2151 _M_before_begin._M_nxt = nullptr;
|
|
|
2152 std::size_t __bbegin_bkt = 0;
|
|
|
2153 std::size_t __prev_bkt = 0;
|
|
|
2154 __node_type* __prev_p = nullptr;
|
|
|
2155 bool __check_bucket = false;
|
|
|
2156
|
|
|
2157 while (__p)
|
|
|
2158 {
|
|
|
2159 __node_type* __next = __p->_M_next();
|
|
|
2160 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
|
|
|
2161
|
|
|
2162 if (__prev_p && __prev_bkt == __bkt)
|
|
|
2163 {
|
|
|
2164 // Previous insert was already in this bucket, we insert after
|
|
|
2165 // the previously inserted one to preserve equivalent elements
|
|
|
2166 // relative order.
|
|
|
2167 __p->_M_nxt = __prev_p->_M_nxt;
|
|
|
2168 __prev_p->_M_nxt = __p;
|
|
|
2169
|
|
|
2170 // Inserting after a node in a bucket require to check that we
|
|
|
2171 // haven't change the bucket last node, in this case next
|
|
|
2172 // bucket containing its before begin node must be updated. We
|
|
|
2173 // schedule a check as soon as we move out of the sequence of
|
|
|
2174 // equivalent nodes to limit the number of checks.
|
|
|
2175 __check_bucket = true;
|
|
|
2176 }
|
|
|
2177 else
|
|
|
2178 {
|
|
|
2179 if (__check_bucket)
|
|
|
2180 {
|
|
|
2181 // Check if we shall update the next bucket because of
|
|
|
2182 // insertions into __prev_bkt bucket.
|
|
|
2183 if (__prev_p->_M_nxt)
|
|
|
2184 {
|
|
|
2185 std::size_t __next_bkt
|
|
|
2186 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
|
|
|
2187 __n);
|
|
|
2188 if (__next_bkt != __prev_bkt)
|
|
|
2189 __new_buckets[__next_bkt] = __prev_p;
|
|
|
2190 }
|
|
|
2191 __check_bucket = false;
|
|
|
2192 }
|
|
|
2193
|
|
|
2194 if (!__new_buckets[__bkt])
|
|
|
2195 {
|
|
|
2196 __p->_M_nxt = _M_before_begin._M_nxt;
|
|
|
2197 _M_before_begin._M_nxt = __p;
|
|
|
2198 __new_buckets[__bkt] = &_M_before_begin;
|
|
|
2199 if (__p->_M_nxt)
|
|
|
2200 __new_buckets[__bbegin_bkt] = __p;
|
|
|
2201 __bbegin_bkt = __bkt;
|
|
|
2202 }
|
|
|
2203 else
|
|
|
2204 {
|
|
|
2205 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
|
|
|
2206 __new_buckets[__bkt]->_M_nxt = __p;
|
|
|
2207 }
|
|
|
2208 }
|
|
|
2209 __prev_p = __p;
|
|
|
2210 __prev_bkt = __bkt;
|
|
|
2211 __p = __next;
|
|
|
2212 }
|
|
|
2213
|
|
|
2214 if (__check_bucket && __prev_p->_M_nxt)
|
|
|
2215 {
|
|
|
2216 std::size_t __next_bkt
|
|
|
2217 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
|
|
|
2218 if (__next_bkt != __prev_bkt)
|
|
|
2219 __new_buckets[__next_bkt] = __prev_p;
|
|
|
2220 }
|
|
|
2221
|
|
|
2222 _M_deallocate_buckets();
|
|
|
2223 _M_bucket_count = __n;
|
|
|
2224 _M_buckets = __new_buckets;
|
|
|
2225 }
|
|
|
2226
|
|
|
2227 #if __cplusplus > 201402L
|
|
|
2228 template<typename, typename, typename> class _Hash_merge_helper { };
|
|
|
2229 #endif // C++17
|
|
|
2230
|
|
|
2231 _GLIBCXX_END_NAMESPACE_VERSION
|
|
|
2232 } // namespace std
|
|
|
2233
|
|
|
2234 #endif // _HASHTABLE_H
|
