|
111
|
1 // TR1 hashtable.h header -*- C++ -*-
|
|
|
2
|
|
145
|
3 // Copyright (C) 2007-2020 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 tr1/hashtable.h
|
|
|
26 * This is an internal header file, included by other library headers.
|
|
|
27 * Do not attempt to use it directly.
|
|
|
28 * @headername{tr1/unordered_set, tr1/unordered_map}
|
|
|
29 */
|
|
|
30
|
|
|
31 #ifndef _GLIBCXX_TR1_HASHTABLE_H
|
|
|
32 #define _GLIBCXX_TR1_HASHTABLE_H 1
|
|
|
33
|
|
|
34 #pragma GCC system_header
|
|
|
35
|
|
|
36 #include <tr1/hashtable_policy.h>
|
|
145
|
37 #include <ext/alloc_traits.h>
|
|
111
|
38
|
|
|
39 namespace std _GLIBCXX_VISIBILITY(default)
|
|
|
40 {
|
|
|
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
|
|
42
|
|
|
43 namespace tr1
|
|
|
44 {
|
|
|
45 // Class template _Hashtable, class definition.
|
|
|
46
|
|
|
47 // Meaning of class template _Hashtable's template parameters
|
|
|
48
|
|
|
49 // _Key and _Value: arbitrary CopyConstructible types.
|
|
|
50
|
|
|
51 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
|
|
|
52 // value type is Value. As a conforming extension, we allow for
|
|
|
53 // value type != Value.
|
|
|
54
|
|
|
55 // _ExtractKey: function object that takes a object of type Value
|
|
|
56 // and returns a value of type _Key.
|
|
|
57
|
|
|
58 // _Equal: function object that takes two objects of type k and returns
|
|
|
59 // a bool-like value that is true if the two objects are considered equal.
|
|
|
60
|
|
|
61 // _H1: the hash function. A unary function object with argument type
|
|
|
62 // Key and result type size_t. Return values should be distributed
|
|
|
63 // over the entire range [0, numeric_limits<size_t>:::max()].
|
|
|
64
|
|
|
65 // _H2: the range-hashing function (in the terminology of Tavori and
|
|
|
66 // Dreizin). A binary function object whose argument types and result
|
|
|
67 // type are all size_t. Given arguments r and N, the return value is
|
|
|
68 // in the range [0, N).
|
|
|
69
|
|
|
70 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
|
|
|
71 // whose argument types are _Key and size_t and whose result type is
|
|
|
72 // size_t. Given arguments k and N, the return value is in the range
|
|
|
73 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
|
|
|
74 // than the default, _H1 and _H2 are ignored.
|
|
|
75
|
|
|
76 // _RehashPolicy: Policy class with three members, all of which govern
|
|
|
77 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
|
|
|
78 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
|
|
|
79 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
|
|
|
80 // determines whether, if the current bucket count is n_bkt and the
|
|
|
81 // current element count is n_elt, we need to increase the bucket
|
|
|
82 // count. If so, returns make_pair(true, n), where n is the new
|
|
|
83 // bucket count. If not, returns make_pair(false, <anything>).
|
|
|
84
|
|
|
85 // ??? Right now it is hard-wired that the number of buckets never
|
|
|
86 // shrinks. Should we allow _RehashPolicy to change that?
|
|
|
87
|
|
|
88 // __cache_hash_code: bool. true if we store the value of the hash
|
|
|
89 // function along with the value. This is a time-space tradeoff.
|
|
|
90 // Storing it may improve lookup speed by reducing the number of times
|
|
|
91 // we need to call the Equal function.
|
|
|
92
|
|
|
93 // __constant_iterators: bool. true if iterator and const_iterator are
|
|
|
94 // both constant iterator types. This is true for unordered_set and
|
|
|
95 // unordered_multiset, false for unordered_map and unordered_multimap.
|
|
|
96
|
|
|
97 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
|
|
|
98 // is always at most one, false if it may be an arbitrary number. This
|
|
|
99 // true for unordered_set and unordered_map, false for unordered_multiset
|
|
|
100 // and unordered_multimap.
|
|
|
101
|
|
|
102 template<typename _Key, typename _Value, typename _Allocator,
|
|
|
103 typename _ExtractKey, typename _Equal,
|
|
|
104 typename _H1, typename _H2, typename _Hash,
|
|
|
105 typename _RehashPolicy,
|
|
|
106 bool __cache_hash_code,
|
|
|
107 bool __constant_iterators,
|
|
|
108 bool __unique_keys>
|
|
|
109 class _Hashtable
|
|
|
110 : public __detail::_Rehash_base<_RehashPolicy,
|
|
|
111 _Hashtable<_Key, _Value, _Allocator,
|
|
|
112 _ExtractKey,
|
|
|
113 _Equal, _H1, _H2, _Hash,
|
|
|
114 _RehashPolicy,
|
|
|
115 __cache_hash_code,
|
|
|
116 __constant_iterators,
|
|
|
117 __unique_keys> >,
|
|
|
118 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
119 _H1, _H2, _Hash, __cache_hash_code>,
|
|
|
120 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
|
|
|
121 _Hashtable<_Key, _Value, _Allocator,
|
|
|
122 _ExtractKey,
|
|
|
123 _Equal, _H1, _H2, _Hash,
|
|
|
124 _RehashPolicy,
|
|
|
125 __cache_hash_code,
|
|
|
126 __constant_iterators,
|
|
|
127 __unique_keys> >
|
|
|
128 {
|
|
145
|
129 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
|
|
|
130
|
|
111
|
131 public:
|
|
|
132 typedef _Allocator allocator_type;
|
|
|
133 typedef _Value value_type;
|
|
|
134 typedef _Key key_type;
|
|
|
135 typedef _Equal key_equal;
|
|
|
136 // mapped_type, if present, comes from _Map_base.
|
|
|
137 // hasher, if present, comes from _Hash_code_base.
|
|
|
138 typedef typename _Allocator::difference_type difference_type;
|
|
|
139 typedef typename _Allocator::size_type size_type;
|
|
145
|
140 typedef typename _Alloc_traits::pointer pointer;
|
|
|
141 typedef typename _Alloc_traits::const_pointer const_pointer;
|
|
|
142 typedef typename _Alloc_traits::reference reference;
|
|
|
143 typedef typename _Alloc_traits::const_reference const_reference;
|
|
111
|
144
|
|
|
145 typedef __detail::_Node_iterator<value_type, __constant_iterators,
|
|
|
146 __cache_hash_code>
|
|
|
147 local_iterator;
|
|
|
148 typedef __detail::_Node_const_iterator<value_type,
|
|
|
149 __constant_iterators,
|
|
|
150 __cache_hash_code>
|
|
|
151 const_local_iterator;
|
|
|
152
|
|
|
153 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
|
|
|
154 __cache_hash_code>
|
|
|
155 iterator;
|
|
|
156 typedef __detail::_Hashtable_const_iterator<value_type,
|
|
|
157 __constant_iterators,
|
|
|
158 __cache_hash_code>
|
|
|
159 const_iterator;
|
|
|
160
|
|
|
161 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
|
|
|
162 typename _Hashtable2>
|
|
|
163 friend struct __detail::_Map_base;
|
|
|
164
|
|
|
165 private:
|
|
|
166 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
|
|
145
|
167 typedef typename _Alloc_traits::template rebind<_Node>::other
|
|
|
168 _Node_allocator_type;
|
|
|
169 typedef typename _Alloc_traits::template rebind<_Node*>::other
|
|
|
170 _Bucket_allocator_type;
|
|
111
|
171
|
|
145
|
172 typedef typename _Alloc_traits::template rebind<_Value>::other
|
|
|
173 _Value_allocator_type;
|
|
111
|
174
|
|
|
175 _Node_allocator_type _M_node_allocator;
|
|
|
176 _Node** _M_buckets;
|
|
|
177 size_type _M_bucket_count;
|
|
|
178 size_type _M_element_count;
|
|
|
179 _RehashPolicy _M_rehash_policy;
|
|
|
180
|
|
|
181 _Node*
|
|
|
182 _M_allocate_node(const value_type& __v);
|
|
|
183
|
|
|
184 void
|
|
|
185 _M_deallocate_node(_Node* __n);
|
|
|
186
|
|
|
187 void
|
|
|
188 _M_deallocate_nodes(_Node**, size_type);
|
|
|
189
|
|
|
190 _Node**
|
|
|
191 _M_allocate_buckets(size_type __n);
|
|
|
192
|
|
|
193 void
|
|
|
194 _M_deallocate_buckets(_Node**, size_type __n);
|
|
|
195
|
|
|
196 public:
|
|
|
197 // Constructor, destructor, assignment, swap
|
|
|
198 _Hashtable(size_type __bucket_hint,
|
|
|
199 const _H1&, const _H2&, const _Hash&,
|
|
|
200 const _Equal&, const _ExtractKey&,
|
|
|
201 const allocator_type&);
|
|
|
202
|
|
|
203 template<typename _InputIterator>
|
|
|
204 _Hashtable(_InputIterator __first, _InputIterator __last,
|
|
|
205 size_type __bucket_hint,
|
|
|
206 const _H1&, const _H2&, const _Hash&,
|
|
|
207 const _Equal&, const _ExtractKey&,
|
|
|
208 const allocator_type&);
|
|
|
209
|
|
|
210 _Hashtable(const _Hashtable&);
|
|
|
211
|
|
|
212 _Hashtable&
|
|
|
213 operator=(const _Hashtable&);
|
|
|
214
|
|
|
215 ~_Hashtable();
|
|
|
216
|
|
|
217 void swap(_Hashtable&);
|
|
|
218
|
|
|
219 // Basic container operations
|
|
|
220 iterator
|
|
|
221 begin()
|
|
|
222 {
|
|
|
223 iterator __i(_M_buckets);
|
|
|
224 if (!__i._M_cur_node)
|
|
|
225 __i._M_incr_bucket();
|
|
|
226 return __i;
|
|
|
227 }
|
|
|
228
|
|
|
229 const_iterator
|
|
|
230 begin() const
|
|
|
231 {
|
|
|
232 const_iterator __i(_M_buckets);
|
|
|
233 if (!__i._M_cur_node)
|
|
|
234 __i._M_incr_bucket();
|
|
|
235 return __i;
|
|
|
236 }
|
|
|
237
|
|
|
238 iterator
|
|
|
239 end()
|
|
|
240 { return iterator(_M_buckets + _M_bucket_count); }
|
|
|
241
|
|
|
242 const_iterator
|
|
|
243 end() const
|
|
|
244 { return const_iterator(_M_buckets + _M_bucket_count); }
|
|
|
245
|
|
|
246 size_type
|
|
|
247 size() const
|
|
|
248 { return _M_element_count; }
|
|
|
249
|
|
145
|
250 _GLIBCXX_NODISCARD bool
|
|
111
|
251 empty() const
|
|
|
252 { return size() == 0; }
|
|
|
253
|
|
|
254 allocator_type
|
|
|
255 get_allocator() const
|
|
|
256 { return allocator_type(_M_node_allocator); }
|
|
|
257
|
|
|
258 _Value_allocator_type
|
|
|
259 _M_get_Value_allocator() const
|
|
|
260 { return _Value_allocator_type(_M_node_allocator); }
|
|
|
261
|
|
|
262 size_type
|
|
|
263 max_size() const
|
|
145
|
264 {
|
|
|
265 typedef __gnu_cxx::__alloc_traits<_Node_allocator_type> _Traits;
|
|
|
266 return _Traits::max_size(_M_node_allocator);
|
|
|
267 }
|
|
111
|
268
|
|
|
269 // Observers
|
|
|
270 key_equal
|
|
|
271 key_eq() const
|
|
|
272 { return this->_M_eq; }
|
|
|
273
|
|
|
274 // hash_function, if present, comes from _Hash_code_base.
|
|
|
275
|
|
|
276 // Bucket operations
|
|
|
277 size_type
|
|
|
278 bucket_count() const
|
|
|
279 { return _M_bucket_count; }
|
|
|
280
|
|
|
281 size_type
|
|
|
282 max_bucket_count() const
|
|
|
283 { return max_size(); }
|
|
|
284
|
|
|
285 size_type
|
|
|
286 bucket_size(size_type __n) const
|
|
|
287 { return std::distance(begin(__n), end(__n)); }
|
|
|
288
|
|
|
289 size_type
|
|
|
290 bucket(const key_type& __k) const
|
|
|
291 {
|
|
|
292 return this->_M_bucket_index(__k, this->_M_hash_code(__k),
|
|
|
293 bucket_count());
|
|
|
294 }
|
|
|
295
|
|
|
296 local_iterator
|
|
|
297 begin(size_type __n)
|
|
|
298 { return local_iterator(_M_buckets[__n]); }
|
|
|
299
|
|
|
300 local_iterator
|
|
|
301 end(size_type)
|
|
|
302 { return local_iterator(0); }
|
|
|
303
|
|
|
304 const_local_iterator
|
|
|
305 begin(size_type __n) const
|
|
|
306 { return const_local_iterator(_M_buckets[__n]); }
|
|
|
307
|
|
|
308 const_local_iterator
|
|
|
309 end(size_type) const
|
|
|
310 { return const_local_iterator(0); }
|
|
|
311
|
|
|
312 float
|
|
|
313 load_factor() const
|
|
|
314 {
|
|
|
315 return static_cast<float>(size()) / static_cast<float>(bucket_count());
|
|
|
316 }
|
|
|
317
|
|
|
318 // max_load_factor, if present, comes from _Rehash_base.
|
|
|
319
|
|
|
320 // Generalization of max_load_factor. Extension, not found in TR1. Only
|
|
|
321 // useful if _RehashPolicy is something other than the default.
|
|
|
322 const _RehashPolicy&
|
|
|
323 __rehash_policy() const
|
|
|
324 { return _M_rehash_policy; }
|
|
|
325
|
|
|
326 void
|
|
|
327 __rehash_policy(const _RehashPolicy&);
|
|
|
328
|
|
|
329 // Lookup.
|
|
|
330 iterator
|
|
|
331 find(const key_type& __k);
|
|
|
332
|
|
|
333 const_iterator
|
|
|
334 find(const key_type& __k) const;
|
|
|
335
|
|
|
336 size_type
|
|
|
337 count(const key_type& __k) const;
|
|
|
338
|
|
|
339 std::pair<iterator, iterator>
|
|
|
340 equal_range(const key_type& __k);
|
|
|
341
|
|
|
342 std::pair<const_iterator, const_iterator>
|
|
|
343 equal_range(const key_type& __k) const;
|
|
|
344
|
|
|
345 private: // Find, insert and erase helper functions
|
|
|
346 // ??? This dispatching is a workaround for the fact that we don't
|
|
|
347 // have partial specialization of member templates; it would be
|
|
|
348 // better to just specialize insert on __unique_keys. There may be a
|
|
|
349 // cleaner workaround.
|
|
|
350 typedef typename __gnu_cxx::__conditional_type<__unique_keys,
|
|
|
351 std::pair<iterator, bool>, iterator>::__type
|
|
|
352 _Insert_Return_Type;
|
|
|
353
|
|
|
354 typedef typename __gnu_cxx::__conditional_type<__unique_keys,
|
|
|
355 std::_Select1st<_Insert_Return_Type>,
|
|
|
356 std::_Identity<_Insert_Return_Type>
|
|
|
357 >::__type
|
|
|
358 _Insert_Conv_Type;
|
|
|
359
|
|
|
360 _Node*
|
|
|
361 _M_find_node(_Node*, const key_type&,
|
|
|
362 typename _Hashtable::_Hash_code_type) const;
|
|
|
363
|
|
|
364 iterator
|
|
|
365 _M_insert_bucket(const value_type&, size_type,
|
|
|
366 typename _Hashtable::_Hash_code_type);
|
|
|
367
|
|
|
368 std::pair<iterator, bool>
|
|
|
369 _M_insert(const value_type&, std::tr1::true_type);
|
|
|
370
|
|
|
371 iterator
|
|
|
372 _M_insert(const value_type&, std::tr1::false_type);
|
|
|
373
|
|
|
374 void
|
|
|
375 _M_erase_node(_Node*, _Node**);
|
|
|
376
|
|
|
377 public:
|
|
|
378 // Insert and erase
|
|
|
379 _Insert_Return_Type
|
|
|
380 insert(const value_type& __v)
|
|
|
381 { return _M_insert(__v, std::tr1::integral_constant<bool,
|
|
|
382 __unique_keys>()); }
|
|
|
383
|
|
|
384 iterator
|
|
|
385 insert(iterator, const value_type& __v)
|
|
|
386 { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
|
|
|
387
|
|
|
388 const_iterator
|
|
|
389 insert(const_iterator, const value_type& __v)
|
|
|
390 { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }
|
|
|
391
|
|
|
392 template<typename _InputIterator>
|
|
|
393 void
|
|
|
394 insert(_InputIterator __first, _InputIterator __last);
|
|
|
395
|
|
|
396 iterator
|
|
|
397 erase(iterator);
|
|
|
398
|
|
|
399 const_iterator
|
|
|
400 erase(const_iterator);
|
|
|
401
|
|
|
402 size_type
|
|
|
403 erase(const key_type&);
|
|
|
404
|
|
|
405 iterator
|
|
|
406 erase(iterator, iterator);
|
|
|
407
|
|
|
408 const_iterator
|
|
|
409 erase(const_iterator, const_iterator);
|
|
|
410
|
|
|
411 void
|
|
|
412 clear();
|
|
|
413
|
|
|
414 // Set number of buckets to be appropriate for container of n element.
|
|
|
415 void rehash(size_type __n);
|
|
|
416
|
|
|
417 private:
|
|
|
418 // Unconditionally change size of bucket array to n.
|
|
|
419 void _M_rehash(size_type __n);
|
|
|
420 };
|
|
|
421
|
|
|
422
|
|
|
423 // Definitions of class template _Hashtable's out-of-line member functions.
|
|
|
424 template<typename _Key, typename _Value,
|
|
|
425 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
426 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
427 bool __chc, bool __cit, bool __uk>
|
|
|
428 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
429 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
430 __chc, __cit, __uk>::_Node*
|
|
|
431 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
432 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
433 _M_allocate_node(const value_type& __v)
|
|
|
434 {
|
|
|
435 _Node* __n = _M_node_allocator.allocate(1);
|
|
|
436 __try
|
|
|
437 {
|
|
145
|
438 _Value_allocator_type __a = _M_get_Value_allocator();
|
|
|
439 typedef __gnu_cxx::__alloc_traits<_Value_allocator_type> _Traits;
|
|
|
440 _Traits::construct(__a, &__n->_M_v, __v);
|
|
111
|
441 __n->_M_next = 0;
|
|
|
442 return __n;
|
|
|
443 }
|
|
|
444 __catch(...)
|
|
|
445 {
|
|
|
446 _M_node_allocator.deallocate(__n, 1);
|
|
|
447 __throw_exception_again;
|
|
|
448 }
|
|
|
449 }
|
|
|
450
|
|
|
451 template<typename _Key, typename _Value,
|
|
|
452 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
453 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
454 bool __chc, bool __cit, bool __uk>
|
|
|
455 void
|
|
|
456 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
457 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
458 _M_deallocate_node(_Node* __n)
|
|
|
459 {
|
|
145
|
460 _Value_allocator_type __a = _M_get_Value_allocator();
|
|
|
461 typedef __gnu_cxx::__alloc_traits<_Value_allocator_type> _Traits;
|
|
|
462 _Traits::destroy(__a, &__n->_M_v);
|
|
111
|
463 _M_node_allocator.deallocate(__n, 1);
|
|
|
464 }
|
|
|
465
|
|
|
466 template<typename _Key, typename _Value,
|
|
|
467 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
468 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
469 bool __chc, bool __cit, bool __uk>
|
|
|
470 void
|
|
|
471 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
472 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
473 _M_deallocate_nodes(_Node** __array, size_type __n)
|
|
|
474 {
|
|
|
475 for (size_type __i = 0; __i < __n; ++__i)
|
|
|
476 {
|
|
|
477 _Node* __p = __array[__i];
|
|
|
478 while (__p)
|
|
|
479 {
|
|
|
480 _Node* __tmp = __p;
|
|
|
481 __p = __p->_M_next;
|
|
|
482 _M_deallocate_node(__tmp);
|
|
|
483 }
|
|
|
484 __array[__i] = 0;
|
|
|
485 }
|
|
|
486 }
|
|
|
487
|
|
|
488 template<typename _Key, typename _Value,
|
|
|
489 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
490 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
491 bool __chc, bool __cit, bool __uk>
|
|
|
492 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
493 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
494 __chc, __cit, __uk>::_Node**
|
|
|
495 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
496 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
497 _M_allocate_buckets(size_type __n)
|
|
|
498 {
|
|
|
499 _Bucket_allocator_type __alloc(_M_node_allocator);
|
|
|
500
|
|
|
501 // We allocate one extra bucket to hold a sentinel, an arbitrary
|
|
|
502 // non-null pointer. Iterator increment relies on this.
|
|
|
503 _Node** __p = __alloc.allocate(__n + 1);
|
|
|
504 std::fill(__p, __p + __n, (_Node*) 0);
|
|
|
505 __p[__n] = reinterpret_cast<_Node*>(0x1000);
|
|
|
506 return __p;
|
|
|
507 }
|
|
|
508
|
|
|
509 template<typename _Key, typename _Value,
|
|
|
510 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
511 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
512 bool __chc, bool __cit, bool __uk>
|
|
|
513 void
|
|
|
514 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
515 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
516 _M_deallocate_buckets(_Node** __p, size_type __n)
|
|
|
517 {
|
|
|
518 _Bucket_allocator_type __alloc(_M_node_allocator);
|
|
|
519 __alloc.deallocate(__p, __n + 1);
|
|
|
520 }
|
|
|
521
|
|
|
522 template<typename _Key, typename _Value,
|
|
|
523 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
524 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
525 bool __chc, bool __cit, bool __uk>
|
|
|
526 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
527 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
528 _Hashtable(size_type __bucket_hint,
|
|
|
529 const _H1& __h1, const _H2& __h2, const _Hash& __h,
|
|
|
530 const _Equal& __eq, const _ExtractKey& __exk,
|
|
|
531 const allocator_type& __a)
|
|
|
532 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
|
|
|
533 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
534 _H1, _H2, _Hash, __chc>(__exk, __eq,
|
|
|
535 __h1, __h2, __h),
|
|
|
536 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
|
|
|
537 _M_node_allocator(__a),
|
|
|
538 _M_bucket_count(0),
|
|
|
539 _M_element_count(0),
|
|
|
540 _M_rehash_policy()
|
|
|
541 {
|
|
|
542 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
|
|
|
543 _M_buckets = _M_allocate_buckets(_M_bucket_count);
|
|
|
544 }
|
|
|
545
|
|
|
546 template<typename _Key, typename _Value,
|
|
|
547 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
548 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
549 bool __chc, bool __cit, bool __uk>
|
|
|
550 template<typename _InputIterator>
|
|
|
551 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
552 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
553 _Hashtable(_InputIterator __f, _InputIterator __l,
|
|
|
554 size_type __bucket_hint,
|
|
|
555 const _H1& __h1, const _H2& __h2, const _Hash& __h,
|
|
|
556 const _Equal& __eq, const _ExtractKey& __exk,
|
|
|
557 const allocator_type& __a)
|
|
|
558 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
|
|
|
559 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
560 _H1, _H2, _Hash, __chc>(__exk, __eq,
|
|
|
561 __h1, __h2, __h),
|
|
|
562 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
|
|
|
563 _M_node_allocator(__a),
|
|
|
564 _M_bucket_count(0),
|
|
|
565 _M_element_count(0),
|
|
|
566 _M_rehash_policy()
|
|
|
567 {
|
|
|
568 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
|
|
|
569 _M_rehash_policy.
|
|
|
570 _M_bkt_for_elements(__detail::
|
|
|
571 __distance_fw(__f,
|
|
|
572 __l)));
|
|
|
573 _M_buckets = _M_allocate_buckets(_M_bucket_count);
|
|
|
574 __try
|
|
|
575 {
|
|
|
576 for (; __f != __l; ++__f)
|
|
|
577 this->insert(*__f);
|
|
|
578 }
|
|
|
579 __catch(...)
|
|
|
580 {
|
|
|
581 clear();
|
|
|
582 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
|
|
|
583 __throw_exception_again;
|
|
|
584 }
|
|
|
585 }
|
|
|
586
|
|
|
587 template<typename _Key, typename _Value,
|
|
|
588 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
589 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
590 bool __chc, bool __cit, bool __uk>
|
|
|
591 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
592 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
593 _Hashtable(const _Hashtable& __ht)
|
|
|
594 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
|
|
|
595 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
596 _H1, _H2, _Hash, __chc>(__ht),
|
|
|
597 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
|
|
|
598 _M_node_allocator(__ht._M_node_allocator),
|
|
|
599 _M_bucket_count(__ht._M_bucket_count),
|
|
|
600 _M_element_count(__ht._M_element_count),
|
|
|
601 _M_rehash_policy(__ht._M_rehash_policy)
|
|
|
602 {
|
|
|
603 _M_buckets = _M_allocate_buckets(_M_bucket_count);
|
|
|
604 __try
|
|
|
605 {
|
|
|
606 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
|
|
|
607 {
|
|
|
608 _Node* __n = __ht._M_buckets[__i];
|
|
|
609 _Node** __tail = _M_buckets + __i;
|
|
|
610 while (__n)
|
|
|
611 {
|
|
|
612 *__tail = _M_allocate_node(__n->_M_v);
|
|
|
613 this->_M_copy_code(*__tail, __n);
|
|
|
614 __tail = &((*__tail)->_M_next);
|
|
|
615 __n = __n->_M_next;
|
|
|
616 }
|
|
|
617 }
|
|
|
618 }
|
|
|
619 __catch(...)
|
|
|
620 {
|
|
|
621 clear();
|
|
|
622 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
|
|
|
623 __throw_exception_again;
|
|
|
624 }
|
|
|
625 }
|
|
|
626
|
|
|
627 template<typename _Key, typename _Value,
|
|
|
628 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
629 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
630 bool __chc, bool __cit, bool __uk>
|
|
|
631 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
632 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>&
|
|
|
633 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
634 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
635 operator=(const _Hashtable& __ht)
|
|
|
636 {
|
|
|
637 _Hashtable __tmp(__ht);
|
|
|
638 this->swap(__tmp);
|
|
|
639 return *this;
|
|
|
640 }
|
|
|
641
|
|
|
642 template<typename _Key, typename _Value,
|
|
|
643 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
644 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
645 bool __chc, bool __cit, bool __uk>
|
|
|
646 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
647 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
648 ~_Hashtable()
|
|
|
649 {
|
|
|
650 clear();
|
|
|
651 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
|
|
|
652 }
|
|
|
653
|
|
|
654 template<typename _Key, typename _Value,
|
|
|
655 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
656 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
657 bool __chc, bool __cit, bool __uk>
|
|
|
658 void
|
|
|
659 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
660 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
661 swap(_Hashtable& __x)
|
|
|
662 {
|
|
|
663 // The only base class with member variables is hash_code_base. We
|
|
|
664 // define _Hash_code_base::_M_swap because different specializations
|
|
|
665 // have different members.
|
|
|
666 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
|
|
|
667 _H1, _H2, _Hash, __chc>::_M_swap(__x);
|
|
|
668
|
|
|
669 // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|
|
670 // 431. Swapping containers with unequal allocators.
|
|
|
671 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
|
|
|
672 __x._M_node_allocator);
|
|
|
673
|
|
|
674 std::swap(_M_rehash_policy, __x._M_rehash_policy);
|
|
|
675 std::swap(_M_buckets, __x._M_buckets);
|
|
|
676 std::swap(_M_bucket_count, __x._M_bucket_count);
|
|
|
677 std::swap(_M_element_count, __x._M_element_count);
|
|
|
678 }
|
|
|
679
|
|
|
680 template<typename _Key, typename _Value,
|
|
|
681 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
682 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
683 bool __chc, bool __cit, bool __uk>
|
|
|
684 void
|
|
|
685 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
686 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
687 __rehash_policy(const _RehashPolicy& __pol)
|
|
|
688 {
|
|
|
689 _M_rehash_policy = __pol;
|
|
|
690 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
|
|
|
691 if (__n_bkt > _M_bucket_count)
|
|
|
692 _M_rehash(__n_bkt);
|
|
|
693 }
|
|
|
694
|
|
|
695 template<typename _Key, typename _Value,
|
|
|
696 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
697 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
698 bool __chc, bool __cit, bool __uk>
|
|
|
699 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
700 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
701 __chc, __cit, __uk>::iterator
|
|
|
702 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
703 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
704 find(const key_type& __k)
|
|
|
705 {
|
|
|
706 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
707 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
708 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
|
|
|
709 return __p ? iterator(__p, _M_buckets + __n) : this->end();
|
|
|
710 }
|
|
|
711
|
|
|
712 template<typename _Key, typename _Value,
|
|
|
713 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
714 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
715 bool __chc, bool __cit, bool __uk>
|
|
|
716 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
717 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
718 __chc, __cit, __uk>::const_iterator
|
|
|
719 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
720 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
721 find(const key_type& __k) const
|
|
|
722 {
|
|
|
723 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
724 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
725 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
|
|
|
726 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
|
|
|
727 }
|
|
|
728
|
|
|
729 template<typename _Key, typename _Value,
|
|
|
730 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
731 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
732 bool __chc, bool __cit, bool __uk>
|
|
|
733 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
734 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
735 __chc, __cit, __uk>::size_type
|
|
|
736 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
737 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
738 count(const key_type& __k) const
|
|
|
739 {
|
|
|
740 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
741 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
742 std::size_t __result = 0;
|
|
|
743 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
|
|
|
744 if (this->_M_compare(__k, __code, __p))
|
|
|
745 ++__result;
|
|
|
746 return __result;
|
|
|
747 }
|
|
|
748
|
|
|
749 template<typename _Key, typename _Value,
|
|
|
750 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
751 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
752 bool __chc, bool __cit, bool __uk>
|
|
|
753 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
|
|
|
754 _ExtractKey, _Equal, _H1,
|
|
|
755 _H2, _Hash, _RehashPolicy,
|
|
|
756 __chc, __cit, __uk>::iterator,
|
|
|
757 typename _Hashtable<_Key, _Value, _Allocator,
|
|
|
758 _ExtractKey, _Equal, _H1,
|
|
|
759 _H2, _Hash, _RehashPolicy,
|
|
|
760 __chc, __cit, __uk>::iterator>
|
|
|
761 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
762 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
763 equal_range(const key_type& __k)
|
|
|
764 {
|
|
|
765 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
766 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
767 _Node** __head = _M_buckets + __n;
|
|
|
768 _Node* __p = _M_find_node(*__head, __k, __code);
|
|
|
769
|
|
|
770 if (__p)
|
|
|
771 {
|
|
|
772 _Node* __p1 = __p->_M_next;
|
|
|
773 for (; __p1; __p1 = __p1->_M_next)
|
|
|
774 if (!this->_M_compare(__k, __code, __p1))
|
|
|
775 break;
|
|
|
776
|
|
|
777 iterator __first(__p, __head);
|
|
|
778 iterator __last(__p1, __head);
|
|
|
779 if (!__p1)
|
|
|
780 __last._M_incr_bucket();
|
|
|
781 return std::make_pair(__first, __last);
|
|
|
782 }
|
|
|
783 else
|
|
|
784 return std::make_pair(this->end(), this->end());
|
|
|
785 }
|
|
|
786
|
|
|
787 template<typename _Key, typename _Value,
|
|
|
788 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
789 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
790 bool __chc, bool __cit, bool __uk>
|
|
|
791 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
|
|
|
792 _ExtractKey, _Equal, _H1,
|
|
|
793 _H2, _Hash, _RehashPolicy,
|
|
|
794 __chc, __cit, __uk>::const_iterator,
|
|
|
795 typename _Hashtable<_Key, _Value, _Allocator,
|
|
|
796 _ExtractKey, _Equal, _H1,
|
|
|
797 _H2, _Hash, _RehashPolicy,
|
|
|
798 __chc, __cit, __uk>::const_iterator>
|
|
|
799 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
800 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
801 equal_range(const key_type& __k) const
|
|
|
802 {
|
|
|
803 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
804 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
805 _Node** __head = _M_buckets + __n;
|
|
|
806 _Node* __p = _M_find_node(*__head, __k, __code);
|
|
|
807
|
|
|
808 if (__p)
|
|
|
809 {
|
|
|
810 _Node* __p1 = __p->_M_next;
|
|
|
811 for (; __p1; __p1 = __p1->_M_next)
|
|
|
812 if (!this->_M_compare(__k, __code, __p1))
|
|
|
813 break;
|
|
|
814
|
|
|
815 const_iterator __first(__p, __head);
|
|
|
816 const_iterator __last(__p1, __head);
|
|
|
817 if (!__p1)
|
|
|
818 __last._M_incr_bucket();
|
|
|
819 return std::make_pair(__first, __last);
|
|
|
820 }
|
|
|
821 else
|
|
|
822 return std::make_pair(this->end(), this->end());
|
|
|
823 }
|
|
|
824
|
|
|
825 // Find the node whose key compares equal to k, beginning the search
|
|
|
826 // at p (usually the head of a bucket). Return zero if no node is found.
|
|
|
827 template<typename _Key, typename _Value,
|
|
|
828 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
829 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
830 bool __chc, bool __cit, bool __uk>
|
|
|
831 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
|
|
|
832 _Equal, _H1, _H2, _Hash, _RehashPolicy,
|
|
|
833 __chc, __cit, __uk>::_Node*
|
|
|
834 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
835 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
836 _M_find_node(_Node* __p, const key_type& __k,
|
|
|
837 typename _Hashtable::_Hash_code_type __code) const
|
|
|
838 {
|
|
|
839 for (; __p; __p = __p->_M_next)
|
|
|
840 if (this->_M_compare(__k, __code, __p))
|
|
|
841 return __p;
|
|
|
842 return 0;
|
|
|
843 }
|
|
|
844
|
|
|
845 // Insert v in bucket n (assumes no element with its key already present).
|
|
|
846 template<typename _Key, typename _Value,
|
|
|
847 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
848 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
849 bool __chc, bool __cit, bool __uk>
|
|
|
850 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
851 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
852 __chc, __cit, __uk>::iterator
|
|
|
853 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
854 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
855 _M_insert_bucket(const value_type& __v, size_type __n,
|
|
|
856 typename _Hashtable::_Hash_code_type __code)
|
|
|
857 {
|
|
|
858 std::pair<bool, std::size_t> __do_rehash
|
|
|
859 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
|
|
|
860 _M_element_count, 1);
|
|
|
861
|
|
|
862 // Allocate the new node before doing the rehash so that we don't
|
|
|
863 // do a rehash if the allocation throws.
|
|
|
864 _Node* __new_node = _M_allocate_node(__v);
|
|
|
865
|
|
|
866 __try
|
|
|
867 {
|
|
|
868 if (__do_rehash.first)
|
|
|
869 {
|
|
|
870 const key_type& __k = this->_M_extract(__v);
|
|
|
871 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
|
|
|
872 _M_rehash(__do_rehash.second);
|
|
|
873 }
|
|
|
874
|
|
|
875 __new_node->_M_next = _M_buckets[__n];
|
|
|
876 this->_M_store_code(__new_node, __code);
|
|
|
877 _M_buckets[__n] = __new_node;
|
|
|
878 ++_M_element_count;
|
|
|
879 return iterator(__new_node, _M_buckets + __n);
|
|
|
880 }
|
|
|
881 __catch(...)
|
|
|
882 {
|
|
|
883 _M_deallocate_node(__new_node);
|
|
|
884 __throw_exception_again;
|
|
|
885 }
|
|
|
886 }
|
|
|
887
|
|
|
888 // Insert v if no element with its key is already present.
|
|
|
889 template<typename _Key, typename _Value,
|
|
|
890 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
891 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
892 bool __chc, bool __cit, bool __uk>
|
|
|
893 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
|
|
|
894 _ExtractKey, _Equal, _H1,
|
|
|
895 _H2, _Hash, _RehashPolicy,
|
|
|
896 __chc, __cit, __uk>::iterator, bool>
|
|
|
897 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
898 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
899 _M_insert(const value_type& __v, std::tr1::true_type)
|
|
|
900 {
|
|
|
901 const key_type& __k = this->_M_extract(__v);
|
|
|
902 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
903 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
904
|
|
|
905 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
|
|
|
906 return std::make_pair(iterator(__p, _M_buckets + __n), false);
|
|
|
907 return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
|
|
|
908 }
|
|
|
909
|
|
|
910 // Insert v unconditionally.
|
|
|
911 template<typename _Key, typename _Value,
|
|
|
912 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
913 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
914 bool __chc, bool __cit, bool __uk>
|
|
|
915 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
916 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
917 __chc, __cit, __uk>::iterator
|
|
|
918 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
919 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
920 _M_insert(const value_type& __v, std::tr1::false_type)
|
|
|
921 {
|
|
|
922 std::pair<bool, std::size_t> __do_rehash
|
|
|
923 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
|
|
|
924 _M_element_count, 1);
|
|
|
925 if (__do_rehash.first)
|
|
|
926 _M_rehash(__do_rehash.second);
|
|
|
927
|
|
|
928 const key_type& __k = this->_M_extract(__v);
|
|
|
929 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
930 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
931
|
|
|
932 // First find the node, avoid leaking new_node if compare throws.
|
|
|
933 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
|
|
|
934 _Node* __new_node = _M_allocate_node(__v);
|
|
|
935
|
|
|
936 if (__prev)
|
|
|
937 {
|
|
|
938 __new_node->_M_next = __prev->_M_next;
|
|
|
939 __prev->_M_next = __new_node;
|
|
|
940 }
|
|
|
941 else
|
|
|
942 {
|
|
|
943 __new_node->_M_next = _M_buckets[__n];
|
|
|
944 _M_buckets[__n] = __new_node;
|
|
|
945 }
|
|
|
946 this->_M_store_code(__new_node, __code);
|
|
|
947
|
|
|
948 ++_M_element_count;
|
|
|
949 return iterator(__new_node, _M_buckets + __n);
|
|
|
950 }
|
|
|
951
|
|
|
952 // For erase(iterator) and erase(const_iterator).
|
|
|
953 template<typename _Key, typename _Value,
|
|
|
954 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
955 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
956 bool __chc, bool __cit, bool __uk>
|
|
|
957 void
|
|
|
958 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
959 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
960 _M_erase_node(_Node* __p, _Node** __b)
|
|
|
961 {
|
|
|
962 _Node* __cur = *__b;
|
|
|
963 if (__cur == __p)
|
|
|
964 *__b = __cur->_M_next;
|
|
|
965 else
|
|
|
966 {
|
|
|
967 _Node* __next = __cur->_M_next;
|
|
|
968 while (__next != __p)
|
|
|
969 {
|
|
|
970 __cur = __next;
|
|
|
971 __next = __cur->_M_next;
|
|
|
972 }
|
|
|
973 __cur->_M_next = __next->_M_next;
|
|
|
974 }
|
|
|
975
|
|
|
976 _M_deallocate_node(__p);
|
|
|
977 --_M_element_count;
|
|
|
978 }
|
|
|
979
|
|
|
980 template<typename _Key, typename _Value,
|
|
|
981 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
982 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
983 bool __chc, bool __cit, bool __uk>
|
|
|
984 template<typename _InputIterator>
|
|
|
985 void
|
|
|
986 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
987 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
988 insert(_InputIterator __first, _InputIterator __last)
|
|
|
989 {
|
|
|
990 size_type __n_elt = __detail::__distance_fw(__first, __last);
|
|
|
991 std::pair<bool, std::size_t> __do_rehash
|
|
|
992 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
|
|
|
993 _M_element_count, __n_elt);
|
|
|
994 if (__do_rehash.first)
|
|
|
995 _M_rehash(__do_rehash.second);
|
|
|
996
|
|
|
997 for (; __first != __last; ++__first)
|
|
|
998 this->insert(*__first);
|
|
|
999 }
|
|
|
1000
|
|
|
1001 template<typename _Key, typename _Value,
|
|
|
1002 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1003 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1004 bool __chc, bool __cit, bool __uk>
|
|
|
1005 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1006 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
1007 __chc, __cit, __uk>::iterator
|
|
|
1008 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1009 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1010 erase(iterator __it)
|
|
|
1011 {
|
|
|
1012 iterator __result = __it;
|
|
|
1013 ++__result;
|
|
|
1014 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
|
|
|
1015 return __result;
|
|
|
1016 }
|
|
|
1017
|
|
|
1018 template<typename _Key, typename _Value,
|
|
|
1019 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1020 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1021 bool __chc, bool __cit, bool __uk>
|
|
|
1022 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1023 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
1024 __chc, __cit, __uk>::const_iterator
|
|
|
1025 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1026 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1027 erase(const_iterator __it)
|
|
|
1028 {
|
|
|
1029 const_iterator __result = __it;
|
|
|
1030 ++__result;
|
|
|
1031 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
|
|
|
1032 return __result;
|
|
|
1033 }
|
|
|
1034
|
|
|
1035 template<typename _Key, typename _Value,
|
|
|
1036 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1037 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1038 bool __chc, bool __cit, bool __uk>
|
|
|
1039 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1040 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
1041 __chc, __cit, __uk>::size_type
|
|
|
1042 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1043 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1044 erase(const key_type& __k)
|
|
|
1045 {
|
|
|
1046 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
|
|
|
1047 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
|
|
|
1048 size_type __result = 0;
|
|
|
1049
|
|
|
1050 _Node** __slot = _M_buckets + __n;
|
|
|
1051 while (*__slot && !this->_M_compare(__k, __code, *__slot))
|
|
|
1052 __slot = &((*__slot)->_M_next);
|
|
|
1053
|
|
|
1054 _Node** __saved_slot = 0;
|
|
|
1055 while (*__slot && this->_M_compare(__k, __code, *__slot))
|
|
|
1056 {
|
|
|
1057 // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
|
|
1058 // 526. Is it undefined if a function in the standard changes
|
|
|
1059 // in parameters?
|
|
|
1060 if (&this->_M_extract((*__slot)->_M_v) != &__k)
|
|
|
1061 {
|
|
|
1062 _Node* __p = *__slot;
|
|
|
1063 *__slot = __p->_M_next;
|
|
|
1064 _M_deallocate_node(__p);
|
|
|
1065 --_M_element_count;
|
|
|
1066 ++__result;
|
|
|
1067 }
|
|
|
1068 else
|
|
|
1069 {
|
|
|
1070 __saved_slot = __slot;
|
|
|
1071 __slot = &((*__slot)->_M_next);
|
|
|
1072 }
|
|
|
1073 }
|
|
|
1074
|
|
|
1075 if (__saved_slot)
|
|
|
1076 {
|
|
|
1077 _Node* __p = *__saved_slot;
|
|
|
1078 *__saved_slot = __p->_M_next;
|
|
|
1079 _M_deallocate_node(__p);
|
|
|
1080 --_M_element_count;
|
|
|
1081 ++__result;
|
|
|
1082 }
|
|
|
1083
|
|
|
1084 return __result;
|
|
|
1085 }
|
|
|
1086
|
|
|
1087 // ??? This could be optimized by taking advantage of the bucket
|
|
|
1088 // structure, but it's not clear that it's worth doing. It probably
|
|
|
1089 // wouldn't even be an optimization unless the load factor is large.
|
|
|
1090 template<typename _Key, typename _Value,
|
|
|
1091 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1092 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1093 bool __chc, bool __cit, bool __uk>
|
|
|
1094 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1095 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
1096 __chc, __cit, __uk>::iterator
|
|
|
1097 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1098 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1099 erase(iterator __first, iterator __last)
|
|
|
1100 {
|
|
|
1101 while (__first != __last)
|
|
|
1102 __first = this->erase(__first);
|
|
|
1103 return __last;
|
|
|
1104 }
|
|
|
1105
|
|
|
1106 template<typename _Key, typename _Value,
|
|
|
1107 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1108 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1109 bool __chc, bool __cit, bool __uk>
|
|
|
1110 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1111 _H1, _H2, _Hash, _RehashPolicy,
|
|
|
1112 __chc, __cit, __uk>::const_iterator
|
|
|
1113 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1114 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1115 erase(const_iterator __first, const_iterator __last)
|
|
|
1116 {
|
|
|
1117 while (__first != __last)
|
|
|
1118 __first = this->erase(__first);
|
|
|
1119 return __last;
|
|
|
1120 }
|
|
|
1121
|
|
|
1122 template<typename _Key, typename _Value,
|
|
|
1123 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1124 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1125 bool __chc, bool __cit, bool __uk>
|
|
|
1126 void
|
|
|
1127 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1128 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1129 clear()
|
|
|
1130 {
|
|
|
1131 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
|
|
|
1132 _M_element_count = 0;
|
|
|
1133 }
|
|
|
1134
|
|
|
1135 template<typename _Key, typename _Value,
|
|
|
1136 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1137 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1138 bool __chc, bool __cit, bool __uk>
|
|
|
1139 void
|
|
|
1140 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1141 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1142 rehash(size_type __n)
|
|
|
1143 {
|
|
|
1144 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
|
|
|
1145 _M_rehash_policy._M_bkt_for_elements(_M_element_count
|
|
|
1146 + 1)));
|
|
|
1147 }
|
|
|
1148
|
|
|
1149 template<typename _Key, typename _Value,
|
|
|
1150 typename _Allocator, typename _ExtractKey, typename _Equal,
|
|
|
1151 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
|
|
|
1152 bool __chc, bool __cit, bool __uk>
|
|
|
1153 void
|
|
|
1154 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
|
|
|
1155 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
|
|
|
1156 _M_rehash(size_type __n)
|
|
|
1157 {
|
|
|
1158 _Node** __new_array = _M_allocate_buckets(__n);
|
|
|
1159 __try
|
|
|
1160 {
|
|
|
1161 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
|
|
|
1162 while (_Node* __p = _M_buckets[__i])
|
|
|
1163 {
|
|
|
1164 std::size_t __new_index = this->_M_bucket_index(__p, __n);
|
|
|
1165 _M_buckets[__i] = __p->_M_next;
|
|
|
1166 __p->_M_next = __new_array[__new_index];
|
|
|
1167 __new_array[__new_index] = __p;
|
|
|
1168 }
|
|
|
1169 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
|
|
|
1170 _M_bucket_count = __n;
|
|
|
1171 _M_buckets = __new_array;
|
|
|
1172 }
|
|
|
1173 __catch(...)
|
|
|
1174 {
|
|
|
1175 // A failure here means that a hash function threw an exception.
|
|
|
1176 // We can't restore the previous state without calling the hash
|
|
|
1177 // function again, so the only sensible recovery is to delete
|
|
|
1178 // everything.
|
|
|
1179 _M_deallocate_nodes(__new_array, __n);
|
|
|
1180 _M_deallocate_buckets(__new_array, __n);
|
|
|
1181 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
|
|
|
1182 _M_element_count = 0;
|
|
|
1183 __throw_exception_again;
|
|
|
1184 }
|
|
|
1185 }
|
|
|
1186 } // namespace tr1
|
|
|
1187
|
|
|
1188 _GLIBCXX_END_NAMESPACE_VERSION
|
|
|
1189 } // namespace std
|
|
|
1190
|
|
|
1191 #endif // _GLIBCXX_TR1_HASHTABLE_H
|
