|
|
|
1 |
|
// xhash internal header |
2 |
|
#pragma once |
3 |
|
#ifndef _XHASH_ |
4 |
|
#define _XHASH_ |
5 |
|
#ifndef RC_INVOKED |
6 |
|
|
7 |
|
#include <cstring> |
8 |
|
#include <cwchar> |
9 |
|
#include <functional> |
10 |
|
#include <list> |
11 |
|
#include <vector> |
12 |
|
|
13 |
|
#ifdef _MSC_VER |
14 |
|
#pragma pack(push,_CRT_PACKING) |
15 |
|
#pragma warning(push,3) |
16 |
|
#pragma warning(disable: 4127) |
17 |
|
#endif /* _MSC_VER */ |
18 |
|
|
19 |
|
|
20 |
|
#ifndef _HAS_INCREMENTAL_HASH |
21 |
|
#define _HAS_INCREMENTAL_HASH 0 /* 1 for slow growth, 0 for rapid */ |
22 |
|
#endif /* _HAS_INCREMENTAL_HASH */ |
23 |
|
|
24 |
|
#if _HAS_TRADITIONAL_STL |
25 |
|
#ifdef _HAS_STLPORT_EMULATION |
26 |
|
#undef _HAS_STLPORT_EMULATION |
27 |
|
#endif |
28 |
|
#define _HAS_STLPORT_EMULATION 1 |
29 |
|
#endif /* _HAS_TRADITIONAL_STL */ |
30 |
|
|
31 |
|
|
32 |
|
// TEMPLATE FUNCTION hash_value |
33 |
|
#define _HASH_SEED (size_t)0xdeadbeef |
34 |
|
|
35 |
|
/* |
36 |
|
We start off by defining a specialisation of hash_value for stdext. |
37 |
|
This will work for stdext::hash_map<std::string, ... |
38 |
|
If the user is using std::hash_map, we pull the specialisation into std |
39 |
|
as well. |
40 |
|
|
41 |
|
This comes at the top of our file before everything else to ensure we |
42 |
|
only pull in this one specialisation. |
43 |
|
*/ |
44 |
|
|
45 |
|
_STDEXT_BEGIN |
46 |
|
|
47 |
|
#if _HAS_ITERATOR_DEBUGGING |
48 |
|
using std::_Debug_message; |
49 |
|
using std::_Debug_range; |
50 |
|
#endif |
51 |
|
|
52 |
|
template <class _InIt> |
53 |
|
inline size_t _Hash_value(_InIt _Begin, _InIt _End) |
54 |
|
{ // hash range of elements |
55 |
|
size_t _Val = 2166136261U; |
56 |
|
while(_Begin != _End) |
57 |
|
_Val = 16777619U * _Val ^ (size_t)*_Begin++; |
58 |
|
return (_Val); |
59 |
|
} |
60 |
|
|
61 |
|
template<class _Elem, |
62 |
|
class _Traits, |
63 |
|
class _Alloc> inline |
64 |
|
size_t hash_value(const _STD basic_string<_Elem, _Traits, _Alloc>& _Str) |
65 |
|
{ // hash string to size_t value |
66 |
|
const _Elem *_Ptr = _Str.c_str(); |
67 |
|
|
68 |
|
return (_Hash_value(_Ptr, _Ptr + _Str.size())); |
69 |
|
} |
70 |
|
|
71 |
|
|
72 |
|
template<class _Kty> inline |
73 |
|
size_t hash_value(const _Kty& _Keyval) |
74 |
|
{ // hash _Keyval to size_t value one-to-one |
75 |
|
return ((size_t)_Keyval ^ _HASH_SEED); |
76 |
|
} |
77 |
|
|
78 |
|
inline size_t hash_value(_In_z_ const char *_Str) |
79 |
|
{ // hash NTBS to size_t value |
80 |
|
return (_Hash_value(_Str, _Str + ::strlen(_Str))); |
81 |
|
} |
82 |
|
|
83 |
|
inline size_t hash_value(_In_z_ const wchar_t *_Str) |
84 |
|
{ // hash NTWCS to size_t value |
85 |
|
return (_Hash_value(_Str, _Str + ::wcslen(_Str))); |
86 |
|
} |
87 |
|
|
88 |
|
|
89 |
|
#if _HAS_TRADITIONAL_STL |
90 |
|
// TEMPLATE CLASS hash for STLport |
91 |
|
template<class _Kty> |
92 |
|
class hash |
93 |
|
{ // traits class for hash function |
94 |
|
public: |
95 |
|
size_t operator()(const _Kty& _Keyval) const |
96 |
|
{ // hash _Keyval to size_t value by pseudorandomizing transform |
97 |
|
ldiv_t _Qrem = ldiv((size_t)hash_value(_Keyval), 127773); |
98 |
|
_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot; |
99 |
|
if (_Qrem.rem < 0) |
100 |
|
_Qrem.rem += 2147483647; |
101 |
|
return ((size_t)_Qrem.rem); |
102 |
|
} |
103 |
|
}; |
104 |
|
#endif /* _HAS_TRADITIONAL_STL */ |
105 |
|
|
106 |
|
template<class _Kty, |
107 |
|
class _Pr = _STD less<_Kty> > |
108 |
|
class hash_compare |
109 |
|
{ // traits class for hash containers |
110 |
|
public: |
111 |
|
enum |
112 |
|
{ // parameters for hash table |
113 |
|
bucket_size = 4, // 0 < bucket_size |
114 |
|
min_buckets = 8}; // min_buckets = 2 ^^ N, 0 < N |
115 |
|
|
116 |
|
hash_compare() |
117 |
|
: comp() |
118 |
|
{ // construct with default comparator |
119 |
|
} |
120 |
|
|
121 |
|
hash_compare(_Pr _Pred) |
122 |
|
: comp(_Pred) |
123 |
|
{ // construct with _Pred comparator |
124 |
|
} |
125 |
|
|
126 |
|
size_t operator()(const _Kty& _Keyval) const |
127 |
|
{ // hash _Keyval to size_t value by pseudorandomizing transform |
128 |
|
long _Quot = (long)(hash_value(_Keyval) & LONG_MAX); |
129 |
|
ldiv_t _Qrem = ldiv(_Quot, 127773); |
130 |
|
|
131 |
|
_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot; |
132 |
|
if (_Qrem.rem < 0) |
133 |
|
_Qrem.rem += LONG_MAX; |
134 |
|
return ((size_t)_Qrem.rem); |
135 |
|
} |
136 |
|
|
137 |
|
bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const |
138 |
|
{ // test if _Keyval1 ordered before _Keyval2 |
139 |
|
return (comp(_Keyval1, _Keyval2)); |
140 |
|
} |
141 |
|
|
142 |
|
protected: |
143 |
|
_Pr comp; // the comparator object |
144 |
|
}; |
145 |
|
|
146 |
|
// TEMPLATE CLASS _Hash_compare |
147 |
|
template<class _Kty, |
148 |
|
class _Hasher, |
149 |
|
class _Keyeq> |
150 |
|
class _Hash_compare |
151 |
|
{ // traits class for hash containers |
152 |
|
public: |
153 |
|
typedef _Hasher hasher; |
154 |
|
enum |
155 |
|
{ // parameters for hash table |
156 |
|
bucket_size = 4, // 0 < bucket_size |
157 |
|
min_buckets = 8}; // min_buckets = 2 ^^ N, 0 < N |
158 |
|
|
159 |
|
_Hash_compare() |
160 |
|
{ // construct with default hasher and equality comparator |
161 |
|
} |
162 |
|
|
163 |
|
_Hash_compare(hasher _Hasharg) |
164 |
|
: _Hashobj(_Hasharg) |
165 |
|
{ // construct with hasher and default equality comparator |
166 |
|
} |
167 |
|
|
168 |
|
_Hash_compare(hasher _Hasharg, _Keyeq _Keyeqarg) |
169 |
|
: _Hashobj(_Hasharg), _Keyeqobj(_Keyeqarg) |
170 |
|
{ // construct with hasher and equality comparator |
171 |
|
} |
172 |
|
|
173 |
|
size_t operator()(const _Kty& _Keyval) const |
174 |
|
{ // hash _Keyval to size_t value |
175 |
|
return ((size_t)_Hashobj(_Keyval)); |
176 |
|
} |
177 |
|
|
178 |
|
bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const |
179 |
|
{ // test if _Keyval1 NOT equal to _Keyval2 |
180 |
|
return (!_Keyeqobj(_Keyval1, _Keyval2)); |
181 |
|
} |
182 |
|
|
183 |
|
hasher _Hashobj; // the hash object |
184 |
|
_Keyeq _Keyeqobj; // the equality comparator object |
185 |
|
}; |
186 |
|
|
187 |
|
// TEMPLATE CLASS _Hash |
188 |
|
template<class _Traits> |
189 |
|
class _Hash |
190 |
|
: public _Traits // traits serves as base class |
191 |
|
{ // hash table -- list with vector of iterators for quick access |
192 |
|
public: |
193 |
|
typedef _Hash<_Traits> _Myt; |
194 |
|
typedef typename _Traits::key_type key_type; |
195 |
|
typedef typename _Traits::key_compare key_compare; |
196 |
|
typedef typename _Traits::value_compare value_compare; |
197 |
|
enum |
198 |
|
{ // hoist constants from key_compare |
199 |
|
_Bucket_size = key_compare::bucket_size, |
200 |
|
min_buckets = key_compare::min_buckets, |
201 |
|
_Multi = _Traits::_Multi}; |
202 |
|
typedef _STD list<typename _Traits::value_type, |
203 |
|
typename _Traits::allocator_type> _Mylist; |
204 |
|
|
205 |
|
typedef typename _Mylist::allocator_type allocator_type; |
206 |
|
typedef typename _Mylist::size_type size_type; |
207 |
|
typedef typename _Mylist::difference_type difference_type; |
208 |
|
typedef typename _Mylist::pointer pointer; |
209 |
|
typedef typename _Mylist::const_pointer const_pointer; |
210 |
|
typedef typename _Mylist::reference reference; |
211 |
|
typedef typename _Mylist::const_reference const_reference; |
212 |
|
|
213 |
|
#if _HAS_IMMUTABLE_SETS |
214 |
|
typedef typename _Mylist::iterator _Myiterator; |
215 |
|
typedef typename _Traits::_ITptr _ITptr; |
216 |
|
typedef typename _Traits::_IReft _IReft; |
217 |
|
|
218 |
|
// CLASS iterator |
219 |
|
class iterator |
220 |
|
: public _Myiterator |
221 |
|
{ // possibly non-mutable iterator |
222 |
|
public: |
223 |
|
typedef _ITptr pointer; |
224 |
|
typedef _IReft reference; |
225 |
|
|
226 |
|
iterator() |
227 |
|
{ // construct default iterator |
228 |
|
} |
229 |
|
|
230 |
|
iterator(const _Myiterator& _Iter) |
231 |
|
: _Myiterator(_Iter) |
232 |
|
{ // construct from _Myiterator |
233 |
|
} |
234 |
|
|
235 |
|
_IReft operator*() const |
236 |
|
{ // change to const_reference |
237 |
|
return ((_IReft)**(_Myiterator *)this); |
238 |
|
} |
239 |
|
|
240 |
|
_ITptr operator->() const |
241 |
|
{ // change to const_pointer |
242 |
|
return ((_ITptr)&**(_Myiterator *)this); |
243 |
|
} |
244 |
|
}; |
245 |
|
|
246 |
|
#else /* _HAS_IMMUTABLE_SETS */ |
247 |
|
typedef typename _Mylist::iterator _Myiterator; |
248 |
|
typedef typename _Mylist::iterator iterator; |
249 |
|
#endif /* _HAS_IMMUTABLE_SETS */ |
250 |
|
|
251 |
|
typedef typename _Mylist::const_iterator const_iterator; |
252 |
|
|
253 |
|
#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING |
254 |
|
|
255 |
|
// _List_position is used to keep a pointer to a certain position in the list. |
256 |
|
// List iterators can easily be converted to _List_position, and you can get |
257 |
|
// the correctly parented iterator from a _List_position calling _Get_iter() or |
258 |
|
// the helper function _Get_iter_from_vec() below. |
259 |
|
struct _List_position |
260 |
|
{ |
261 |
|
public: |
262 |
|
_List_position() |
263 |
|
: _Mypos() |
264 |
|
{ |
265 |
|
} |
266 |
|
|
267 |
|
_List_position(iterator _Iter) |
268 |
|
: _Mypos(_Iter._Mynode(), (_Mylist*)_Iter._Getmycont()) |
269 |
|
{ |
270 |
|
} |
271 |
|
|
272 |
|
_List_position(const_iterator _Iter) |
273 |
|
: _Mypos(_Iter._Mynode(), (_Mylist*)_Iter._Getmycont()) |
274 |
|
{ |
275 |
|
} |
276 |
|
|
277 |
|
// default copy constructor and assignment operator |
278 |
|
|
279 |
|
iterator _Get_iter(const _Mylist &_List) const |
280 |
|
{ |
281 |
|
// reparent the iterator |
282 |
|
return (_Myiterator(_Mypos._Mynode(), &_List)); |
283 |
|
} |
284 |
|
|
285 |
|
bool operator==(const _List_position &_Right) const |
286 |
|
{ |
287 |
|
return (_Mypos._Mynode() == _Right._Mypos._Mynode()); |
288 |
|
} |
289 |
|
|
290 |
|
bool operator!=(const _List_position &_Right) const |
291 |
|
{ |
292 |
|
return (!(*this == _Right)); |
293 |
|
} |
294 |
|
|
295 |
|
bool operator==(const const_iterator &_Right) const |
296 |
|
{ |
297 |
|
return (_Mypos._Mynode() == _Right._Mynode()); |
298 |
|
} |
299 |
|
|
300 |
|
bool operator!=(const const_iterator &_Right) const |
301 |
|
{ |
302 |
|
return (!(*this == _Right)); |
303 |
|
} |
517 |
|
{ // set new load factor |
518 |
|
if (_Newmax != _Newmax // may detect a NaN |
519 |
|
|| _Newmax < 0) |
520 |
|
_THROW(_STD out_of_range, "invalid hash load factor"); |
521 |
|
|
522 |
|
_Max_bucket_size = _Newmax; |
523 |
|
} |
524 |
|
|
525 |
|
void rehash(size_type _Buckets) |
526 |
|
{ // rebuild table with at least _Buckets buckets |
527 |
|
size_type _Maxsize = _Vec.max_size() / 2; |
528 |
|
size_type _Newsize = min_buckets; |
529 |
|
|
530 |
|
for (; _Newsize < _Buckets && _Newsize < _Maxsize; ) |
531 |
|
_Newsize *= 2; // double until big enough |
532 |
|
if (_Newsize < _Buckets) |
533 |
|
_THROW(_STD out_of_range, "invalid hash bucket count"); |
534 |
|
for (float _Size = (float)size(); |
535 |
|
max_load_factor() < _Size / _Newsize && _Newsize < _Maxsize; ) |
536 |
|
_Newsize *= 2; // double until load factor okay |
537 |
|
|
538 |
|
_Init(_Newsize); |
539 |
|
_Reinsert(); |
540 |
|
} |
541 |
|
// ADDED WITH TR1 -- END |
542 |
|
|
543 |
|
_Pairib insert(const value_type& _Val) |
544 |
|
{ // try to insert node with value _Val |
545 |
|
return (_Insert(_Val, end())); |
546 |
|
} |
547 |
|
|
548 |
|
iterator insert(const_iterator, const value_type& _Val) |
549 |
|
{ // try to insert node with value _Val, ignore hint |
550 |
|
return (insert(_Val).first); |
551 |
|
} |
552 |
|
|
553 |
|
template<class _Iter> |
554 |
|
void insert(_Iter _First, _Iter _Last) |
555 |
|
{ // insert [_First, _Last) one at a time |
556 |
|
_List.insert(begin(), _First, _Last); |
557 |
|
_Reinsert(); |
558 |
|
} |
559 |
|
|
560 |
|
|
561 |
|
iterator erase(const_iterator _Where) |
562 |
|
{ // erase element at _Where |
563 |
|
size_type _Bucket = _Hashval(this->_Kfn(*_Where)); |
564 |
|
for (; _Vec[_Bucket] == _Where; --_Bucket) |
565 |
|
{ // update end iterators if erasing first |
566 |
|
#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING |
567 |
|
iterator _Vec_iter = _Get_iter_from_vec(_Vec[_Bucket]); |
568 |
|
++_Vec_iter; |
569 |
|
_Vec[_Bucket] = _Vec_iter; |
570 |
|
#else |
571 |
|
++_Vec[_Bucket]; |
572 |
|
#endif |
573 |
|
if (_Bucket == 0) |
574 |
|
break; |
575 |
|
} |
576 |
|
return (_List.erase(_Where)); |
577 |
|
} |
578 |
|
|
579 |
|
iterator erase(const_iterator _First, const_iterator _Last) |
580 |
|
{ // erase [_First, _Last) |
581 |
|
_DEBUG_RANGE(_First, _Last); |
582 |
|
if (_First == begin() && _Last == end()) |
583 |
|
{ // erase all |
584 |
|
clear(); |
585 |
|
return (begin()); |
586 |
|
} |
587 |
|
else |
588 |
|
{ // partial erase, one at a time |
589 |
|
while (_First != _Last) |
590 |
|
erase(_First++); |
591 |
|
return (_List._Make_iter(_First)); |
592 |
|
} |
593 |
|
} |
594 |
|
|
595 |
|
size_type erase(const key_type& _Keyval) |
596 |
|
{ // erase and count all that match _Keyval |
597 |
|
_Pairii _Where = equal_range(_Keyval); |
598 |
|
size_type _Num = 0; |
599 |
|
_Distance(_Where.first, _Where.second, _Num); |
600 |
|
erase(_Where.first, _Where.second); |
601 |
|
return (_Num); |
602 |
|
} |
603 |
|
|
604 |
|
void erase(const key_type *_First, |
605 |
|
const key_type *_Last) |
606 |
|
{ // erase all that match array of keys [_First, _Last) |
607 |
|
_DEBUG_RANGE(_First, _Last); |
608 |
|
for (; _First != _Last; ++_First) |
609 |
|
erase(*_First); |
610 |
|
} |
611 |
|
|
612 |
|
void clear() |
613 |
|
{ // erase all |
614 |
|
_List.clear(); |
615 |
|
_Init(); |
616 |
|
} |
617 |
|
|
618 |
|
iterator find(const key_type& _Keyval) |
619 |
|
{ // find an element in mutable hash table that matches _Keyval |
620 |
|
return (lower_bound(_Keyval)); |
621 |
|
} |
622 |
|
|
623 |
|
const_iterator find(const key_type& _Keyval) const |
624 |
|
{ // find an element in nonmutable hash table that matches _Keyval |
625 |
|
return (lower_bound(_Keyval)); |
626 |
|
} |
627 |
|
|
628 |
|
size_type count(const key_type& _Keyval) const |
629 |
|
{ // count all elements that match _Keyval |
630 |
|
_Paircc _Ans = equal_range(_Keyval); |
631 |
|
size_type _Num = 0; |
632 |
|
_Distance(_Ans.first, _Ans.second, _Num); |
633 |
|
return (_Num); |
634 |
|
} |
635 |
|
|
636 |
|
iterator lower_bound(const key_type& _Keyval) |
637 |
|
{ // find leftmost not less than _Keyval in mutable hash table |
638 |
|
size_type _Bucket = _Hashval(_Keyval); |
639 |
|
iterator _Where; |
640 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where) |
641 |
|
if (!this->comp(this->_Kfn(*_Where), _Keyval)) |
642 |
|
return (this->comp(_Keyval, |
643 |
|
this->_Kfn(*_Where)) ? end() : _Where); |
644 |
|
return (end()); |
645 |
|
} |
646 |
|
|
647 |
|
const_iterator lower_bound(const key_type& _Keyval) const |
648 |
|
{ // find leftmost not less than _Keyval in nonmutable hash table |
649 |
|
size_type _Bucket = _Hashval(_Keyval); |
650 |
|
const_iterator _Where; |
651 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where) |
652 |
|
if (!this->comp(this->_Kfn(*_Where), _Keyval)) |
653 |
|
return (this->comp(_Keyval, |
654 |
|
this->_Kfn(*_Where)) ? end() : _Where); |
655 |
|
return (end()); |
656 |
|
} |
657 |
|
|
658 |
|
iterator upper_bound(const key_type& _Keyval) |
659 |
|
{ // find leftmost not greater than _Keyval in mutable hash table |
660 |
|
size_type _Bucket = _Hashval(_Keyval); |
661 |
|
iterator _Where; |
662 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket + 1]); _Vec[_Bucket] != _Where; ) |
663 |
|
if (!this->comp(_Keyval, this->_Kfn(*--_Where))) |
664 |
|
return (this->comp(this->_Kfn(*_Where), |
665 |
|
_Keyval) ? end() : (iterator)++_Where); |
666 |
|
return (end()); |
667 |
|
} |
668 |
|
|
669 |
|
const_iterator upper_bound(const key_type& _Keyval) const |
670 |
|
{ // find leftmost not greater than _Keyval in nonmutable hash table |
671 |
|
size_type _Bucket = _Hashval(_Keyval); |
672 |
|
const_iterator _Where; |
673 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket + 1]); _Vec[_Bucket] != _Where; ) |
674 |
|
if (!this->comp(_Keyval, this->_Kfn(*--_Where))) |
675 |
|
return (this->comp(this->_Kfn(*_Where), |
676 |
|
_Keyval) ? end() : (const_iterator)++_Where); |
677 |
|
return (end()); |
678 |
|
} |
679 |
|
|
680 |
|
_Pairii equal_range(const key_type& _Keyval) |
681 |
|
{ // find range equivalent to _Keyval in mutable hash table |
682 |
|
size_type _Bucket = _Hashval(_Keyval); |
683 |
|
iterator _First, _Where; |
684 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where) |
685 |
|
if (!this->comp(this->_Kfn(*_Where), _Keyval)) |
686 |
|
{ // found _First, look for end of range |
687 |
|
for (_First = _Where; _Vec[_Bucket + 1] != _Where; ++_Where) |
688 |
|
if (this->comp(_Keyval, this->_Kfn(*_Where))) |
689 |
|
break; |
690 |
|
if (_First == _Where) |
691 |
|
break; |
692 |
|
return (_Pairii(_First, _Where)); |
693 |
|
} |
694 |
|
return (_Pairii(end(), end())); |
695 |
|
} |
696 |
|
|
697 |
|
_Paircc equal_range(const key_type& _Keyval) const |
698 |
|
{ // find range equivalent to _Keyval in nonmutable hash table |
699 |
|
size_type _Bucket = _Hashval(_Keyval); |
700 |
|
iterator _First, _Where; |
701 |
|
for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where) |
702 |
|
if (!this->comp(this->_Kfn(*_Where), _Keyval)) |
703 |
|
{ // found _First, look for end of range |
704 |
|
for (_First = _Where; _Vec[_Bucket + 1] != _Where; ++_Where) |
705 |
|
if (this->comp(_Keyval, this->_Kfn(*_Where))) |
706 |
|
break; |
707 |
|
if (_First == _Where) |
708 |
|
break; |
709 |
|
return (_Paircc(_First, _Where)); |
710 |
|
} |
711 |
|
return (_Paircc(end(), end())); |
712 |
|
} |
713 |
|
|
714 |
|
void swap(_Myt& _Right) |
715 |
|
{ // exchange contents with _Right |
716 |
|
if (this != &_Right) |
717 |
|
{ // different, worth swapping |
718 |
|
_STD _Swap_adl(this->comp, _Right.comp); |
719 |
|
this->_List.swap(_Right._List); |
720 |
|
this->_Vec.swap(_Right._Vec); |
721 |
|
_STD swap(this->_Mask, _Right._Mask); |
722 |
|
_STD swap(this->_Maxidx, _Right._Maxidx); |
723 |
|
_STD swap(this->_Max_bucket_size, _Right._Max_bucket_size); |
724 |
|
} |
725 |
|
} |
726 |
|
|
727 |
|
#if _HAS_TRADITIONAL_STL |
728 |
|
size_type elems_in_bucket(size_type _Bucket) const |
729 |
|
{ // return number of elements in bucket |
730 |
|
return (bucket_size(_Bucket)); |
731 |
|
} |
732 |
|
#endif /* _HAS_TRADITIONAL_STL */ |
733 |
|
|
734 |
|
protected: |
735 |
|
void _Copy(const _Myt& _Right) |
736 |
|
{ // copy entire hash table |
737 |
|
_Vec.resize(_Right._Vec.size(), end()); |
738 |
|
_Mask = _Right._Mask; |
739 |
|
_Maxidx = _Right._Maxidx; |
740 |
|
_Max_bucket_size = _Right._Max_bucket_size; |
741 |
|
_List.clear(); |
742 |
|
|
743 |
|
_TRY_BEGIN |
744 |
|
_List.insert(end(), _Right._List.begin(), _Right._List.end()); |
745 |
|
this->comp = _Right.comp; |
746 |
|
_CATCH_ALL |
747 |
|
_List.clear(); // list or compare copy failed, bail out |
748 |
|
fill(_Vec.begin(), _Vec.end(), end()); |
749 |
|
_RERAISE; |
750 |
|
_CATCH_END |
751 |
|
|
752 |
|
iterator _Whereto = begin(); |
753 |
|
const_iterator _Wherefrom = _Right.begin(); |
754 |
|
for (size_type _Bucket = 0; _Bucket < _Vec.size(); ) |
755 |
|
if (_Right._Vec[_Bucket] == _Wherefrom) |
756 |
|
_Vec[_Bucket] = _Whereto, ++_Bucket; |
757 |
|
else |
758 |
|
++_Whereto, ++_Wherefrom; |
759 |
|
} |
760 |
|
|
761 |
|
void _Grow() |
762 |
|
{ // grow hash table by one bucket |
763 |
|
iterator _Plist; |
764 |
|
|
765 |
|
if (_Vec.size() - 1 <= _Maxidx) |
766 |
|
{ // table full, double its size |
767 |
|
_Mask = ((_Vec.size() - 1) << 1) - 1; |
768 |
|
_Vec.resize(_Mask + 2, end()); |
769 |
|
} |
770 |
|
else if (_Mask < _Maxidx) |
771 |
|
_Mask = (_Mask << 1) + 1; |
772 |
|
|
773 |
|
size_type _Bucket = _Maxidx - (_Mask >> 1) - 1; |
774 |
|
for (_Plist = _Get_iter_from_vec(_Vec[_Bucket]); |
775 |
|
_Plist != _Get_iter_from_vec(_Vec[_Bucket + 1]); ) |
776 |
|
{ // split old bucket |
777 |
|
size_type _Newbucket = |
778 |
|
this->comp(this->_Kfn(*_Plist)) & _Mask; |
779 |
|
if (_Newbucket == _Bucket) |
780 |
|
++_Plist; // leave element in old bucket |
781 |
|
|
782 |
|
#if _HAS_ITERATOR_DEBUGGING |
783 |
|
else if (_Newbucket != _Maxidx) |
784 |
|
_DEBUG_ERROR("bad hash function"); |
785 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
786 |
|
|
787 |
|
else |
788 |
|
{ // move element to new bucket |
789 |
|
size_type _Idx; |
790 |
|
iterator _Pnext = _Plist; |
791 |
|
if (++_Pnext != end()) |
792 |
|
{ // not at end, move it |
793 |
|
for (_Idx = _Bucket; _Plist == _Get_iter_from_vec(_Vec[_Idx]); --_Idx) |
794 |
|
{ // update end iterators if moving first |
795 |
|
_Vec[_Idx] = _Pnext; |
796 |
|
if (_Idx == 0) |
797 |
|
break; |
798 |
|
} |
799 |
|
_List._Splice(end(), _List, _Plist, _Pnext, 0); |
800 |
|
_Plist = --end(); |
801 |
|
_Vec[_Maxidx + 1] = end(); |
802 |
|
} |
803 |
|
|
804 |
|
for (_Idx = _Maxidx; _Bucket < _Idx; --_Idx) |
805 |
|
{ // update end iterators if new bucket filled |
806 |
|
if (_Get_iter_from_vec(_Vec[_Idx]) != end()) |
807 |
|
break; |
808 |
|
_Vec[_Idx] = _Plist; |
809 |
|
} |
810 |
|
|
811 |
|
if (_Pnext == end()) |
812 |
|
break; |
813 |
|
else |
814 |
|
_Plist = _Pnext; |
815 |
|
} |
816 |
|
} |
817 |
|
++_Maxidx; // open new bucket for hash lookup |
818 |
|
} |
819 |
|
|
820 |
|
size_type _Hashval(const key_type& _Keyval) const |
821 |
|
{ // return hash value, masked and wrapped to current table size |
822 |
|
size_type _Num = this->comp(_Keyval) & _Mask; |
823 |
|
if (_Maxidx <= _Num) |
824 |
|
_Num -= (_Mask >> 1) + 1; |
825 |
|
return (_Num); |
826 |
|
} |
827 |
|
|
828 |
|
void _Init(size_type _Buckets = min_buckets) |
829 |
|
{ // initialize hash table with _Buckets buckets, leave list alone |
830 |
|
_Vec.assign(_Buckets + 1, end()); |
831 |
|
_Mask = _Buckets - 1; |
832 |
|
_Maxidx = _Buckets; |
833 |
|
} |
834 |
|
|
835 |
|
_Pairib _Insert(const value_type& _Val, iterator _Where) |
836 |
|
{ // try to insert (possibly existing) node with value _Val |
837 |
|
size_type _Bucket = _Hashval(this->_Kfn(_Val)); |
838 |
|
iterator _Plist = _Get_iter_from_vec(_Vec[_Bucket + 1]); |
839 |
|
|
840 |
|
for (; _Plist != _Get_iter_from_vec(_Vec[_Bucket]); ) |
841 |
|
if (this->comp(this->_Kfn(_Val), this->_Kfn(*--_Plist))) |
842 |
|
; // still too high in bucket list |
843 |
|
else if (_Multi |
844 |
|
|| this->comp(this->_Kfn(*_Plist), this->_Kfn(_Val))) |
845 |
|
{ // found insertion point, back up to it |
846 |
|
++_Plist; |
847 |
|
break; |
848 |
|
} |
849 |
|
else |
850 |
|
{ // discard new list element and return existing |
851 |
|
if (_Where != end()) |
852 |
|
_List.erase(_Where); |
853 |
|
return (_Pairib(_Plist, false)); |
854 |
|
} |
855 |
|
|
856 |
|
if (_Where != end()) |
857 |
|
_List.splice(_Plist, _List, _Where); // move element into place |
858 |
|
else |
859 |
|
_Where = _List.insert(_Plist, _Val); // insert new element |
860 |
|
for (; _Plist == _Get_iter_from_vec(_Vec[_Bucket]); --_Bucket) |
861 |
|
{ // update end iterators if new first bucket element |
862 |
|
_Vec[_Bucket] = _Where; |
863 |
|
if (_Bucket == 0) |
864 |
|
break; |
865 |
|
} |
866 |
|
|
867 |
|
if (max_load_factor() < load_factor()) |
868 |
|
#if _HAS_INCREMENTAL_HASH |
869 |
|
_Grow(); // too dense, need to grow hash table |
870 |
|
|
871 |
|
#else /* _HAS_INCREMENTAL_HASH */ |
872 |
|
{ // rehash to bigger table |
873 |
|
size_type _Maxsize = _Vec.max_size() / 2; |
874 |
|
size_type _Newsize = bucket_count(); |
875 |
|
|
876 |
|
for (int _Idx = 0; _Idx < 3 && _Newsize < _Maxsize; ++_Idx) |
877 |
|
_Newsize *= 2; // multiply safely by 8 |
878 |
|
_Init(_Newsize); |
879 |
|
_Reinsert(); |
880 |
|
} |
881 |
|
#endif /* _HAS_INCREMENTAL_HASH */ |
882 |
|
|
883 |
|
return (_Pairib(_Where, true)); // return iterator for new element |
884 |
|
} |
885 |
|
|
886 |
|
void _Reinsert() |
887 |
|
{ // insert elements at beginning of list into table |
888 |
|
iterator _First; |
889 |
|
for (; (_First = _List.begin()) != _Get_iter_from_vec(_Vec[0]); ) |
890 |
|
_Insert(*_First, _First); |
891 |
|
} |
892 |
|
|
893 |
|
_Mylist _List; // the list of elements, must initialize before _Vec |
894 |
|
_Myvec _Vec; // the vector of list iterators |
895 |
|
size_type _Mask; // the key mask |
896 |
|
size_type _Maxidx; // current maximum key value |
897 |
|
float _Max_bucket_size; // current maximum bucket size |
898 |
|
}; |
899 |
|
|
900 |
|
// _Hash TEMPLATE OPERATORS |
901 |
|
template<class _Ty> inline |
902 |
|
bool operator==(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
903 |
|
{ // test for hash table equality |
904 |
|
return (_Left.size() == _Right.size() |
905 |
|
&& equal(_Left.begin(), _Left.end(), _Right.begin())); |
906 |
|
} |
907 |
|
|
908 |
|
template<class _Ty> inline |
909 |
|
bool operator!=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
910 |
|
{ // test for hash table inequality |
911 |
|
return (!(_Left == _Right)); |
912 |
|
} |
913 |
|
|
914 |
|
template<class _Ty> inline |
915 |
|
bool operator<(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
916 |
|
{ // test if _Left < _Right for hash tables |
917 |
|
return (lexicographical_compare(_Left.begin(), _Left.end(), |
918 |
|
_Right.begin(), _Right.end())); |
919 |
|
} |
920 |
|
|
921 |
|
template<class _Ty> inline |
922 |
|
bool operator>(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
923 |
|
{ // test if _Left > _Right for hash tables |
924 |
|
return (_Right < _Left); |
925 |
|
} |
926 |
|
|
927 |
|
template<class _Ty> inline |
928 |
|
bool operator<=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
929 |
|
{ // test if _Left <= _Right for hash tables |
930 |
|
return (!(_Right < _Left)); |
931 |
|
} |
932 |
|
|
933 |
|
template<class _Ty> inline |
934 |
|
bool operator>=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right) |
935 |
|
{ // test if _Left >= _Right for hash tables |
936 |
|
return (!(_Left < _Right)); |
937 |
|
} |
938 |
|
_STDEXT_END |
939 |
|
|
940 |
|
_STD_BEGIN |
941 |
|
|
942 |
|
// _Hash implements a performant swap |
943 |
|
template <class _Traits> |
944 |
|
class _Move_operation_category<_STDEXT _Hash<_Traits> > |
945 |
|
{ |
946 |
|
public: |
947 |
|
typedef _Swap_move_tag _Move_cat; |
948 |
|
}; |
949 |
|
|
950 |
|
_STD_END |
951 |
|
|
952 |
|
#ifdef _MSC_VER |
953 |
|
#pragma warning(default: 4127) |
954 |
|
#pragma warning(pop) |
955 |
|
#pragma pack(pop) |
956 |
|
#endif /* _MSC_VER */ |
957 |
|
|
958 |
|
#endif /* RC_INVOKED */ |
959 |
|
#endif /* _XHASH_ */ |
960 |
|
|
961 |
|
/* |
962 |
|
* Copyright (c) 1992-2008 by P.J. Plauger. ALL RIGHTS RESERVED. |
963 |
|
* Consult your license regarding permissions and restrictions. |
964 |
|
V5.05:0009 */ |
965 |
|
|
966 |
|
|
967 |
|
|
|
|
|