1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file bits/hashtable.h
26 * This is an internal header file, included by other library headers.
27 * You should not attempt to use it directly.
31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
35 #include <bits/hashtable_policy.h>
39 // Class template _Hashtable, class definition.
41 // Meaning of class template _Hashtable's template parameters
43 // _Key and _Value: arbitrary CopyConstructible types.
45 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
46 // value type is Value. As a conforming extension, we allow for
47 // value type != Value.
49 // _ExtractKey: function object that takes a object of type Value
50 // and returns a value of type _Key.
52 // _Equal: function object that takes two objects of type k and returns
53 // a bool-like value that is true if the two objects are considered equal.
55 // _H1: the hash function. A unary function object with argument type
56 // Key and result type size_t. Return values should be distributed
57 // over the entire range [0, numeric_limits<size_t>:::max()].
59 // _H2: the range-hashing function (in the terminology of Tavori and
60 // Dreizin). A binary function object whose argument types and result
61 // type are all size_t. Given arguments r and N, the return value is
62 // in the range [0, N).
64 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
65 // whose argument types are _Key and size_t and whose result type is
66 // size_t. Given arguments k and N, the return value is in the range
67 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
68 // than the default, _H1 and _H2 are ignored.
70 // _RehashPolicy: Policy class with three members, all of which govern
71 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
72 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
73 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
74 // determines whether, if the current bucket count is n_bkt and the
75 // current element count is n_elt, we need to increase the bucket
76 // count. If so, returns make_pair(true, n), where n is the new
77 // bucket count. If not, returns make_pair(false, <anything>).
79 // ??? Right now it is hard-wired that the number of buckets never
80 // shrinks. Should we allow _RehashPolicy to change that?
82 // __cache_hash_code: bool. true if we store the value of the hash
83 // function along with the value. This is a time-space tradeoff.
84 // Storing it may improve lookup speed by reducing the number of times
85 // we need to call the Equal function.
87 // __constant_iterators: bool. true if iterator and const_iterator are
88 // both constant iterator types. This is true for unordered_set and
89 // unordered_multiset, false for unordered_map and unordered_multimap.
91 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
92 // is always at most one, false if it may be an arbitrary number. This
93 // true for unordered_set and unordered_map, false for unordered_multiset
94 // and unordered_multimap.
96 template<typename _Key
, typename _Value
, typename _Allocator
,
97 typename _ExtractKey
, typename _Equal
,
98 typename _H1
, typename _H2
, typename _Hash
,
99 typename _RehashPolicy
,
100 bool __cache_hash_code
,
101 bool __constant_iterators
,
104 : public __detail::_Rehash_base
<_RehashPolicy
,
105 _Hashtable
<_Key
, _Value
, _Allocator
,
107 _Equal
, _H1
, _H2
, _Hash
,
110 __constant_iterators
,
112 public __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
113 _H1
, _H2
, _Hash
, __cache_hash_code
>,
114 public __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __unique_keys
,
115 _Hashtable
<_Key
, _Value
, _Allocator
,
117 _Equal
, _H1
, _H2
, _Hash
,
120 __constant_iterators
,
122 public __detail::_Equality_base
<_ExtractKey
, __unique_keys
,
123 _Hashtable
<_Key
, _Value
, _Allocator
,
125 _Equal
, _H1
, _H2
, _Hash
,
128 __constant_iterators
,
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::pointer pointer
;
139 typedef typename
_Allocator::const_pointer const_pointer
;
140 typedef typename
_Allocator::reference reference
;
141 typedef typename
_Allocator::const_reference const_reference
;
143 typedef std::size_t size_type
;
144 typedef std::ptrdiff_t difference_type
;
145 typedef __detail::_Node_iterator
<value_type
, __constant_iterators
,
148 typedef __detail::_Node_const_iterator
<value_type
,
149 __constant_iterators
,
151 const_local_iterator
;
153 typedef __detail::_Hashtable_iterator
<value_type
, __constant_iterators
,
156 typedef __detail::_Hashtable_const_iterator
<value_type
,
157 __constant_iterators
,
161 template<typename _Key2
, typename _Value2
, typename _Ex2
, bool __unique2
,
162 typename _Hashtable2
>
163 friend struct __detail::_Map_base
;
166 typedef __detail::_Hash_node
<_Value
, __cache_hash_code
> _Node
;
167 typedef typename
_Allocator::template rebind
<_Node
>::other
168 _Node_allocator_type
;
169 typedef typename
_Allocator::template rebind
<_Node
*>::other
170 _Bucket_allocator_type
;
172 typedef typename
_Allocator::template rebind
<_Value
>::other
173 _Value_allocator_type
;
175 _Node_allocator_type _M_node_allocator
;
177 size_type _M_bucket_count
;
178 size_type _M_begin_bucket_index
; // First non-empty bucket.
179 size_type _M_element_count
;
180 _RehashPolicy _M_rehash_policy
;
182 template<typename
... _Args
>
184 _M_allocate_node(_Args
&&... __args
);
187 _M_deallocate_node(_Node
* __n
);
190 _M_deallocate_nodes(_Node
**, size_type
);
193 _M_allocate_buckets(size_type __n
);
196 _M_deallocate_buckets(_Node
**, size_type __n
);
199 // Constructor, destructor, assignment, swap
200 _Hashtable(size_type __bucket_hint
,
201 const _H1
&, const _H2
&, const _Hash
&,
202 const _Equal
&, const _ExtractKey
&,
203 const allocator_type
&);
205 template<typename _InputIterator
>
206 _Hashtable(_InputIterator __first
, _InputIterator __last
,
207 size_type __bucket_hint
,
208 const _H1
&, const _H2
&, const _Hash
&,
209 const _Equal
&, const _ExtractKey
&,
210 const allocator_type
&);
212 _Hashtable(const _Hashtable
&);
214 _Hashtable(_Hashtable
&&);
217 operator=(const _Hashtable
& __ht
)
219 _Hashtable
__tmp(__ht
);
225 operator=(_Hashtable
&& __ht
)
236 void swap(_Hashtable
&);
238 // Basic container operations
241 { return iterator(_M_buckets
+ _M_begin_bucket_index
); }
245 { return const_iterator(_M_buckets
+ _M_begin_bucket_index
); }
249 { return iterator(_M_buckets
+ _M_bucket_count
); }
253 { return const_iterator(_M_buckets
+ _M_bucket_count
); }
257 { return const_iterator(_M_buckets
+ _M_begin_bucket_index
); }
261 { return const_iterator(_M_buckets
+ _M_bucket_count
); }
265 { return _M_element_count
; }
269 { return size() == 0; }
272 get_allocator() const
273 { return allocator_type(_M_node_allocator
); }
277 { return _M_node_allocator
.max_size(); }
282 { return this->_M_eq
; }
284 // hash_function, if present, comes from _Hash_code_base.
289 { return _M_bucket_count
; }
292 max_bucket_count() const
293 { return max_size(); }
296 bucket_size(size_type __n
) const
297 { return std::distance(begin(__n
), end(__n
)); }
300 bucket(const key_type
& __k
) const
302 return this->_M_bucket_index(__k
, this->_M_hash_code(__k
),
308 { return local_iterator(_M_buckets
[__n
]); }
312 { return local_iterator(0); }
315 begin(size_type __n
) const
316 { return const_local_iterator(_M_buckets
[__n
]); }
320 { return const_local_iterator(0); }
324 cbegin(size_type __n
) const
325 { return const_local_iterator(_M_buckets
[__n
]); }
328 cend(size_type
) const
329 { return const_local_iterator(0); }
334 return static_cast<float>(size()) / static_cast<float>(bucket_count());
337 // max_load_factor, if present, comes from _Rehash_base.
339 // Generalization of max_load_factor. Extension, not found in TR1. Only
340 // useful if _RehashPolicy is something other than the default.
342 __rehash_policy() const
343 { return _M_rehash_policy
; }
346 __rehash_policy(const _RehashPolicy
&);
350 find(const key_type
& __k
);
353 find(const key_type
& __k
) const;
356 count(const key_type
& __k
) const;
358 std::pair
<iterator
, iterator
>
359 equal_range(const key_type
& __k
);
361 std::pair
<const_iterator
, const_iterator
>
362 equal_range(const key_type
& __k
) const;
365 // Find and insert helper functions and types
367 _M_find_node(_Node
*, const key_type
&,
368 typename
_Hashtable::_Hash_code_type
) const;
370 template<typename _Pair
>
372 _M_insert_bucket(_Pair
&&, size_type
,
373 typename
_Hashtable::_Hash_code_type
);
375 template<typename _Pair
>
376 std::pair
<iterator
, bool>
377 _M_insert(_Pair
&&, std::true_type
);
379 template<typename _Pair
>
381 _M_insert(_Pair
&&, std::false_type
);
383 typedef typename
std::conditional
<__unique_keys
,
384 std::pair
<iterator
, bool>,
388 typedef typename
std::conditional
<__unique_keys
,
389 std::_Select1st
<_Insert_Return_Type
>,
390 std::_Identity
<_Insert_Return_Type
>
397 insert(const value_type
& __v
)
398 { return _M_insert(__v
, std::integral_constant
<bool, __unique_keys
>()); }
401 insert(const_iterator
, const value_type
& __v
)
402 { return _Insert_Conv_Type()(insert(__v
)); }
405 insert(value_type
&& __v
)
406 { return _M_insert(std::move(__v
),
407 std::integral_constant
<bool, __unique_keys
>()); }
410 insert(const_iterator
, value_type
&& __v
)
411 { return _Insert_Conv_Type()(insert(std::move(__v
))); }
413 template<typename _Pair
, typename
= typename
414 std::enable_if
<!__constant_iterators
415 && std::is_convertible
<_Pair
,
416 value_type
>::value
>::type
>
419 { return _M_insert(std::forward
<_Pair
>(__v
),
420 std::integral_constant
<bool, __unique_keys
>()); }
422 template<typename _Pair
, typename
= typename
423 std::enable_if
<!__constant_iterators
424 && std::is_convertible
<_Pair
,
425 value_type
>::value
>::type
>
427 insert(const_iterator
, _Pair
&& __v
)
428 { return _Insert_Conv_Type()(insert(std::forward
<_Pair
>(__v
))); }
430 template<typename _InputIterator
>
432 insert(_InputIterator __first
, _InputIterator __last
);
435 insert(initializer_list
<value_type
> __l
)
436 { this->insert(__l
.begin(), __l
.end()); }
439 erase(const_iterator
);
442 erase(const key_type
&);
445 erase(const_iterator
, const_iterator
);
450 // Set number of buckets to be appropriate for container of n element.
451 void rehash(size_type __n
);
454 // reserve, if present, comes from _Rehash_base.
457 // Unconditionally change size of bucket array to n.
458 void _M_rehash(size_type __n
);
462 // Definitions of class template _Hashtable's out-of-line member functions.
463 template<typename _Key
, typename _Value
,
464 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
465 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
466 bool __chc
, bool __cit
, bool __uk
>
467 template<typename
... _Args
>
468 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
469 _H1
, _H2
, _Hash
, _RehashPolicy
,
470 __chc
, __cit
, __uk
>::_Node
*
471 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
472 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
473 _M_allocate_node(_Args
&&... __args
)
475 _Node
* __n
= _M_node_allocator
.allocate(1);
478 _M_node_allocator
.construct(__n
, std::forward
<_Args
>(__args
)...);
484 _M_node_allocator
.deallocate(__n
, 1);
485 __throw_exception_again
;
489 template<typename _Key
, typename _Value
,
490 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
491 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
492 bool __chc
, bool __cit
, bool __uk
>
494 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
495 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
496 _M_deallocate_node(_Node
* __n
)
498 _M_node_allocator
.destroy(__n
);
499 _M_node_allocator
.deallocate(__n
, 1);
502 template<typename _Key
, typename _Value
,
503 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
504 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
505 bool __chc
, bool __cit
, bool __uk
>
507 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
508 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
509 _M_deallocate_nodes(_Node
** __array
, size_type __n
)
511 for (size_type __i
= 0; __i
< __n
; ++__i
)
513 _Node
* __p
= __array
[__i
];
518 _M_deallocate_node(__tmp
);
524 template<typename _Key
, typename _Value
,
525 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
526 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
527 bool __chc
, bool __cit
, bool __uk
>
528 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
529 _H1
, _H2
, _Hash
, _RehashPolicy
,
530 __chc
, __cit
, __uk
>::_Node
**
531 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
532 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
533 _M_allocate_buckets(size_type __n
)
535 _Bucket_allocator_type
__alloc(_M_node_allocator
);
537 // We allocate one extra bucket to hold a sentinel, an arbitrary
538 // non-null pointer. Iterator increment relies on this.
539 _Node
** __p
= __alloc
.allocate(__n
+ 1);
540 std::fill(__p
, __p
+ __n
, (_Node
*) 0);
541 __p
[__n
] = reinterpret_cast<_Node
*>(0x1000);
545 template<typename _Key
, typename _Value
,
546 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
547 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
548 bool __chc
, bool __cit
, bool __uk
>
550 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
551 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
552 _M_deallocate_buckets(_Node
** __p
, size_type __n
)
554 _Bucket_allocator_type
__alloc(_M_node_allocator
);
555 __alloc
.deallocate(__p
, __n
+ 1);
558 template<typename _Key
, typename _Value
,
559 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
560 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
561 bool __chc
, bool __cit
, bool __uk
>
562 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
563 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
564 _Hashtable(size_type __bucket_hint
,
565 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
566 const _Equal
& __eq
, const _ExtractKey
& __exk
,
567 const allocator_type
& __a
)
568 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
569 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
570 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
572 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
573 _M_node_allocator(__a
),
578 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
579 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
580 _M_begin_bucket_index
= _M_bucket_count
;
583 template<typename _Key
, typename _Value
,
584 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
585 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
586 bool __chc
, bool __cit
, bool __uk
>
587 template<typename _InputIterator
>
588 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
589 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
590 _Hashtable(_InputIterator __f
, _InputIterator __l
,
591 size_type __bucket_hint
,
592 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
593 const _Equal
& __eq
, const _ExtractKey
& __exk
,
594 const allocator_type
& __a
)
595 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
596 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
597 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
599 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
600 _M_node_allocator(__a
),
605 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
607 _M_bkt_for_elements(__detail::
610 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
611 _M_begin_bucket_index
= _M_bucket_count
;
614 for (; __f
!= __l
; ++__f
)
620 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
621 __throw_exception_again
;
625 template<typename _Key
, typename _Value
,
626 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
627 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
628 bool __chc
, bool __cit
, bool __uk
>
629 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
630 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
631 _Hashtable(const _Hashtable
& __ht
)
632 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
633 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
634 _H1
, _H2
, _Hash
, __chc
>(__ht
),
635 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
636 _M_node_allocator(__ht
._M_node_allocator
),
637 _M_bucket_count(__ht
._M_bucket_count
),
638 _M_begin_bucket_index(__ht
._M_begin_bucket_index
),
639 _M_element_count(__ht
._M_element_count
),
640 _M_rehash_policy(__ht
._M_rehash_policy
)
642 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
645 for (size_type __i
= 0; __i
< __ht
._M_bucket_count
; ++__i
)
647 _Node
* __n
= __ht
._M_buckets
[__i
];
648 _Node
** __tail
= _M_buckets
+ __i
;
651 *__tail
= _M_allocate_node(__n
->_M_v
);
652 this->_M_copy_code(*__tail
, __n
);
653 __tail
= &((*__tail
)->_M_next
);
661 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
662 __throw_exception_again
;
666 template<typename _Key
, typename _Value
,
667 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
668 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
669 bool __chc
, bool __cit
, bool __uk
>
670 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
671 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
672 _Hashtable(_Hashtable
&& __ht
)
673 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
674 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
675 _H1
, _H2
, _Hash
, __chc
>(__ht
),
676 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
677 _M_node_allocator(__ht
._M_node_allocator
),
678 _M_buckets(__ht
._M_buckets
),
679 _M_bucket_count(__ht
._M_bucket_count
),
680 _M_begin_bucket_index(__ht
._M_begin_bucket_index
),
681 _M_element_count(__ht
._M_element_count
),
682 _M_rehash_policy(__ht
._M_rehash_policy
)
684 size_type __n_bkt
= __ht
._M_rehash_policy
._M_next_bkt(0);
685 __ht
._M_buckets
= __ht
._M_allocate_buckets(__n_bkt
);
686 __ht
._M_bucket_count
= __n_bkt
;
687 __ht
._M_begin_bucket_index
= __ht
._M_bucket_count
;
688 __ht
._M_element_count
= 0;
689 __ht
._M_rehash_policy
= _RehashPolicy();
692 template<typename _Key
, typename _Value
,
693 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
694 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
695 bool __chc
, bool __cit
, bool __uk
>
696 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
697 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
701 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
704 template<typename _Key
, typename _Value
,
705 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
706 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
707 bool __chc
, bool __cit
, bool __uk
>
709 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
710 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
711 swap(_Hashtable
& __x
)
713 // The only base class with member variables is hash_code_base. We
714 // define _Hash_code_base::_M_swap because different specializations
715 // have different members.
716 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
717 _H1
, _H2
, _Hash
, __chc
>::_M_swap(__x
);
719 // _GLIBCXX_RESOLVE_LIB_DEFECTS
720 // 431. Swapping containers with unequal allocators.
721 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
722 __x
._M_node_allocator
);
724 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
725 std::swap(_M_buckets
, __x
._M_buckets
);
726 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
727 std::swap(_M_begin_bucket_index
, __x
._M_begin_bucket_index
);
728 std::swap(_M_element_count
, __x
._M_element_count
);
731 template<typename _Key
, typename _Value
,
732 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
733 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
734 bool __chc
, bool __cit
, bool __uk
>
736 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
737 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
738 __rehash_policy(const _RehashPolicy
& __pol
)
740 _M_rehash_policy
= __pol
;
741 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
742 if (__n_bkt
> _M_bucket_count
)
746 template<typename _Key
, typename _Value
,
747 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
748 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
749 bool __chc
, bool __cit
, bool __uk
>
750 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
751 _H1
, _H2
, _Hash
, _RehashPolicy
,
752 __chc
, __cit
, __uk
>::iterator
753 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
754 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
755 find(const key_type
& __k
)
757 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
758 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
759 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
760 return __p
? iterator(__p
, _M_buckets
+ __n
) : this->end();
763 template<typename _Key
, typename _Value
,
764 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
765 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
766 bool __chc
, bool __cit
, bool __uk
>
767 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
768 _H1
, _H2
, _Hash
, _RehashPolicy
,
769 __chc
, __cit
, __uk
>::const_iterator
770 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
771 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
772 find(const key_type
& __k
) const
774 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
775 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
776 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
777 return __p
? const_iterator(__p
, _M_buckets
+ __n
) : this->end();
780 template<typename _Key
, typename _Value
,
781 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
782 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
783 bool __chc
, bool __cit
, bool __uk
>
784 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
785 _H1
, _H2
, _Hash
, _RehashPolicy
,
786 __chc
, __cit
, __uk
>::size_type
787 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
788 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
789 count(const key_type
& __k
) const
791 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
792 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
793 std::size_t __result
= 0;
794 for (_Node
* __p
= _M_buckets
[__n
]; __p
; __p
= __p
->_M_next
)
795 if (this->_M_compare(__k
, __code
, __p
))
800 template<typename _Key
, typename _Value
,
801 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
802 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
803 bool __chc
, bool __cit
, bool __uk
>
804 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
805 _ExtractKey
, _Equal
, _H1
,
806 _H2
, _Hash
, _RehashPolicy
,
807 __chc
, __cit
, __uk
>::iterator
,
808 typename _Hashtable
<_Key
, _Value
, _Allocator
,
809 _ExtractKey
, _Equal
, _H1
,
810 _H2
, _Hash
, _RehashPolicy
,
811 __chc
, __cit
, __uk
>::iterator
>
812 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
813 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
814 equal_range(const key_type
& __k
)
816 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
817 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
818 _Node
** __head
= _M_buckets
+ __n
;
819 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
823 _Node
* __p1
= __p
->_M_next
;
824 for (; __p1
; __p1
= __p1
->_M_next
)
825 if (!this->_M_compare(__k
, __code
, __p1
))
828 iterator
__first(__p
, __head
);
829 iterator
__last(__p1
, __head
);
831 __last
._M_incr_bucket();
832 return std::make_pair(__first
, __last
);
835 return std::make_pair(this->end(), this->end());
838 template<typename _Key
, typename _Value
,
839 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
840 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
841 bool __chc
, bool __cit
, bool __uk
>
842 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
843 _ExtractKey
, _Equal
, _H1
,
844 _H2
, _Hash
, _RehashPolicy
,
845 __chc
, __cit
, __uk
>::const_iterator
,
846 typename _Hashtable
<_Key
, _Value
, _Allocator
,
847 _ExtractKey
, _Equal
, _H1
,
848 _H2
, _Hash
, _RehashPolicy
,
849 __chc
, __cit
, __uk
>::const_iterator
>
850 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
851 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
852 equal_range(const key_type
& __k
) const
854 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
855 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
856 _Node
** __head
= _M_buckets
+ __n
;
857 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
861 _Node
* __p1
= __p
->_M_next
;
862 for (; __p1
; __p1
= __p1
->_M_next
)
863 if (!this->_M_compare(__k
, __code
, __p1
))
866 const_iterator
__first(__p
, __head
);
867 const_iterator
__last(__p1
, __head
);
869 __last
._M_incr_bucket();
870 return std::make_pair(__first
, __last
);
873 return std::make_pair(this->end(), this->end());
876 // Find the node whose key compares equal to k, beginning the search
877 // at p (usually the head of a bucket). Return nil if no node is found.
878 template<typename _Key
, typename _Value
,
879 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
880 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
881 bool __chc
, bool __cit
, bool __uk
>
882 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
883 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
884 __chc
, __cit
, __uk
>::_Node
*
885 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
886 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
887 _M_find_node(_Node
* __p
, const key_type
& __k
,
888 typename
_Hashtable::_Hash_code_type __code
) const
890 for (; __p
; __p
= __p
->_M_next
)
891 if (this->_M_compare(__k
, __code
, __p
))
896 // Insert v in bucket n (assumes no element with its key already present).
897 template<typename _Key
, typename _Value
,
898 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
899 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
900 bool __chc
, bool __cit
, bool __uk
>
901 template<typename _Pair
>
902 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
903 _H1
, _H2
, _Hash
, _RehashPolicy
,
904 __chc
, __cit
, __uk
>::iterator
905 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
906 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
907 _M_insert_bucket(_Pair
&& __v
, size_type __n
,
908 typename
_Hashtable::_Hash_code_type __code
)
910 std::pair
<bool, std::size_t> __do_rehash
911 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
912 _M_element_count
, 1);
914 if (__do_rehash
.first
)
916 const key_type
& __k
= this->_M_extract(__v
);
917 __n
= this->_M_bucket_index(__k
, __code
, __do_rehash
.second
);
920 // Allocate the new node before doing the rehash so that we don't
921 // do a rehash if the allocation throws.
922 _Node
* __new_node
= _M_allocate_node(std::forward
<_Pair
>(__v
));
926 if (__do_rehash
.first
)
927 _M_rehash(__do_rehash
.second
);
929 __new_node
->_M_next
= _M_buckets
[__n
];
930 this->_M_store_code(__new_node
, __code
);
931 _M_buckets
[__n
] = __new_node
;
933 if (__n
< _M_begin_bucket_index
)
934 _M_begin_bucket_index
= __n
;
935 return iterator(__new_node
, _M_buckets
+ __n
);
939 _M_deallocate_node(__new_node
);
940 __throw_exception_again
;
944 // Insert v if no element with its key is already present.
945 template<typename _Key
, typename _Value
,
946 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
947 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
948 bool __chc
, bool __cit
, bool __uk
>
949 template<typename _Pair
>
950 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
951 _ExtractKey
, _Equal
, _H1
,
952 _H2
, _Hash
, _RehashPolicy
,
953 __chc
, __cit
, __uk
>::iterator
, bool>
954 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
955 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
956 _M_insert(_Pair
&& __v
, std::true_type
)
958 const key_type
& __k
= this->_M_extract(__v
);
959 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
960 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
962 if (_Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
))
963 return std::make_pair(iterator(__p
, _M_buckets
+ __n
), false);
964 return std::make_pair(_M_insert_bucket(std::forward
<_Pair
>(__v
),
968 // Insert v unconditionally.
969 template<typename _Key
, typename _Value
,
970 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
971 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
972 bool __chc
, bool __cit
, bool __uk
>
973 template<typename _Pair
>
974 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
975 _H1
, _H2
, _Hash
, _RehashPolicy
,
976 __chc
, __cit
, __uk
>::iterator
977 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
978 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
979 _M_insert(_Pair
&& __v
, std::false_type
)
981 std::pair
<bool, std::size_t> __do_rehash
982 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
983 _M_element_count
, 1);
984 if (__do_rehash
.first
)
985 _M_rehash(__do_rehash
.second
);
987 const key_type
& __k
= this->_M_extract(__v
);
988 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
989 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
991 // First find the node, avoid leaking new_node if compare throws.
992 _Node
* __prev
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
993 _Node
* __new_node
= _M_allocate_node(std::forward
<_Pair
>(__v
));
997 __new_node
->_M_next
= __prev
->_M_next
;
998 __prev
->_M_next
= __new_node
;
1002 __new_node
->_M_next
= _M_buckets
[__n
];
1003 _M_buckets
[__n
] = __new_node
;
1004 if (__n
< _M_begin_bucket_index
)
1005 _M_begin_bucket_index
= __n
;
1007 this->_M_store_code(__new_node
, __code
);
1010 return iterator(__new_node
, _M_buckets
+ __n
);
1013 template<typename _Key
, typename _Value
,
1014 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1015 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1016 bool __chc
, bool __cit
, bool __uk
>
1017 template<typename _InputIterator
>
1019 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1020 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1021 insert(_InputIterator __first
, _InputIterator __last
)
1023 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
1024 std::pair
<bool, std::size_t> __do_rehash
1025 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1026 _M_element_count
, __n_elt
);
1027 if (__do_rehash
.first
)
1028 _M_rehash(__do_rehash
.second
);
1030 for (; __first
!= __last
; ++__first
)
1031 this->insert(*__first
);
1034 template<typename _Key
, typename _Value
,
1035 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1036 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1037 bool __chc
, bool __cit
, bool __uk
>
1038 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1039 _H1
, _H2
, _Hash
, _RehashPolicy
,
1040 __chc
, __cit
, __uk
>::iterator
1041 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1042 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1043 erase(const_iterator __it
)
1045 iterator
__result(__it
._M_cur_node
, __it
._M_cur_bucket
);
1048 _Node
* __cur
= *__it
._M_cur_bucket
;
1049 if (__cur
== __it
._M_cur_node
)
1051 *__it
._M_cur_bucket
= __cur
->_M_next
;
1053 // If _M_begin_bucket_index no longer indexes the first non-empty
1054 // bucket - its single node is being erased - update it.
1055 if (!_M_buckets
[_M_begin_bucket_index
])
1056 _M_begin_bucket_index
= __result
._M_cur_bucket
- _M_buckets
;
1060 _Node
* __next
= __cur
->_M_next
;
1061 while (__next
!= __it
._M_cur_node
)
1064 __next
= __cur
->_M_next
;
1066 __cur
->_M_next
= __next
->_M_next
;
1069 _M_deallocate_node(__it
._M_cur_node
);
1075 template<typename _Key
, typename _Value
,
1076 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1077 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1078 bool __chc
, bool __cit
, bool __uk
>
1079 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1080 _H1
, _H2
, _Hash
, _RehashPolicy
,
1081 __chc
, __cit
, __uk
>::size_type
1082 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1083 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1084 erase(const key_type
& __k
)
1086 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1087 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
1088 size_type __result
= 0;
1090 _Node
** __slot
= _M_buckets
+ __n
;
1091 while (*__slot
&& !this->_M_compare(__k
, __code
, *__slot
))
1092 __slot
= &((*__slot
)->_M_next
);
1094 _Node
** __saved_slot
= 0;
1095 while (*__slot
&& this->_M_compare(__k
, __code
, *__slot
))
1097 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1098 // 526. Is it undefined if a function in the standard changes
1100 if (std::__addressof(this->_M_extract((*__slot
)->_M_v
))
1101 != std::__addressof(__k
))
1103 _Node
* __p
= *__slot
;
1104 *__slot
= __p
->_M_next
;
1105 _M_deallocate_node(__p
);
1111 __saved_slot
= __slot
;
1112 __slot
= &((*__slot
)->_M_next
);
1118 _Node
* __p
= *__saved_slot
;
1119 *__saved_slot
= __p
->_M_next
;
1120 _M_deallocate_node(__p
);
1125 // If the entire bucket indexed by _M_begin_bucket_index has been
1126 // erased look forward for the first non-empty bucket.
1127 if (!_M_buckets
[_M_begin_bucket_index
])
1129 if (!_M_element_count
)
1130 _M_begin_bucket_index
= _M_bucket_count
;
1133 ++_M_begin_bucket_index
;
1134 while (!_M_buckets
[_M_begin_bucket_index
])
1135 ++_M_begin_bucket_index
;
1142 // ??? This could be optimized by taking advantage of the bucket
1143 // structure, but it's not clear that it's worth doing. It probably
1144 // wouldn't even be an optimization unless the load factor is large.
1145 template<typename _Key
, typename _Value
,
1146 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1147 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1148 bool __chc
, bool __cit
, bool __uk
>
1149 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1150 _H1
, _H2
, _Hash
, _RehashPolicy
,
1151 __chc
, __cit
, __uk
>::iterator
1152 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1153 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1154 erase(const_iterator __first
, const_iterator __last
)
1156 while (__first
!= __last
)
1157 __first
= this->erase(__first
);
1158 return iterator(__last
._M_cur_node
, __last
._M_cur_bucket
);
1161 template<typename _Key
, typename _Value
,
1162 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1163 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1164 bool __chc
, bool __cit
, bool __uk
>
1166 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1167 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1170 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1171 _M_element_count
= 0;
1172 _M_begin_bucket_index
= _M_bucket_count
;
1175 template<typename _Key
, typename _Value
,
1176 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1177 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1178 bool __chc
, bool __cit
, bool __uk
>
1180 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1181 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1182 rehash(size_type __n
)
1184 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1185 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1189 template<typename _Key
, typename _Value
,
1190 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1191 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1192 bool __chc
, bool __cit
, bool __uk
>
1194 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1195 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1196 _M_rehash(size_type __n
)
1198 _Node
** __new_array
= _M_allocate_buckets(__n
);
1201 _M_begin_bucket_index
= __n
;
1202 for (size_type __i
= 0; __i
< _M_bucket_count
; ++__i
)
1203 while (_Node
* __p
= _M_buckets
[__i
])
1205 std::size_t __new_index
= this->_M_bucket_index(__p
, __n
);
1206 _M_buckets
[__i
] = __p
->_M_next
;
1207 __p
->_M_next
= __new_array
[__new_index
];
1208 __new_array
[__new_index
] = __p
;
1209 if (__new_index
< _M_begin_bucket_index
)
1210 _M_begin_bucket_index
= __new_index
;
1212 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1213 _M_bucket_count
= __n
;
1214 _M_buckets
= __new_array
;
1218 // A failure here means that a hash function threw an exception.
1219 // We can't restore the previous state without calling the hash
1220 // function again, so the only sensible recovery is to delete
1222 _M_deallocate_nodes(__new_array
, __n
);
1223 _M_deallocate_buckets(__new_array
, __n
);
1224 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1225 _M_element_count
= 0;
1226 _M_begin_bucket_index
= _M_bucket_count
;
1227 __throw_exception_again
;
1232 #endif // _HASHTABLE_H