1 /*
2 * Copyright (c) 1994
3 * Hewlett-Packard Company
4 *
5 * Copyright (c) 1996,1997
6 * Silicon Graphics Computer Systems, Inc.
7 *
8 * Copyright (c) 1997
9 * Moscow Center for SPARC Technology
10 *
11 * Copyright (c) 1999
12 * Boris Fomitchev
13 *
14 * This material is provided "as is", with absolutely no warranty expressed
15 * or implied. Any use is at your own risk.
16 *
17 * Permission to use or copy this software for any purpose is hereby granted
18 * without fee, provided the above notices are retained on all copies.
19 * Permission to modify the code and to distribute modified code is granted,
20 * provided the above notices are retained, and a notice that the code was
21 * modified is included with the above copyright notice.
22 *
23 */
24 #ifndef _STLP_HASHTABLE_C
25 #define _STLP_HASHTABLE_C
26
27 #ifndef _STLP_INTERNAL_HASHTABLE_H
28 # include <stl/_hashtable.h>
29 #endif
30
31 _STLP_BEGIN_NAMESPACE
32
33 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
34
35 _STLP_MOVE_TO_PRIV_NAMESPACE
36
37 # define __PRIME_LIST_BODY { \
38 7ul, 23ul, \
39 53ul, 97ul, 193ul, 389ul, 769ul, \
40 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \
41 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \
42 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \
43 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\
44 1610612741ul, 3221225473ul, 4294967291ul \
45 }
46
47 template <class _Dummy>
48 size_t _STLP_CALL
_S_max_nb_buckets()49 _Stl_prime<_Dummy>::_S_max_nb_buckets() {
50 const size_t _list[] = __PRIME_LIST_BODY;
51 # ifndef __MWERKS__
52 return _list[(sizeof(_list)/sizeof(_list[0])) - 1];
53 # else
54 return _list[30/sizeof(size_t) - 1]; // stupid MWERKS!
55 # endif
56 }
57
58 template <class _Dummy>
59 size_t _STLP_CALL
_S_next_size(size_t __n)60 _Stl_prime<_Dummy>::_S_next_size(size_t __n) {
61 static const size_t _list[] = __PRIME_LIST_BODY;
62 const size_t* __first = _list;
63 # ifndef __MWERKS__
64 const size_t* __last = _list + (sizeof(_list)/sizeof(_list[0]));
65 # else
66 const size_t* __last = _list + (30/sizeof(size_t)); // stupid MWERKS
67 # endif
68 const size_t* pos = __lower_bound(__first, __last, __n,
69 __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
70 return (pos == __last ? *(__last - 1) : *pos);
71 }
72
73 # undef __PRIME_LIST_BODY
74
75 _STLP_MOVE_TO_STD_NAMESPACE
76
77 #endif
78
79 #if defined (_STLP_DEBUG)
80 # define hashtable _STLP_NON_DBG_NAME(hashtable)
81 _STLP_MOVE_TO_PRIV_NAMESPACE
82 #endif
83
84 // fbp: these defines are for outline methods definitions.
85 // needed to definitions to be portable. Should not be used in method bodies.
86
87 #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
88 # define __size_type__ size_t
89 # define size_type size_t
90 # define value_type _Val
91 # define key_type _Key
92 # define __reference__ _Val&
93
94 # define __iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
95 _Key, _HF, _ExK, _EqK, _All>
96 # define __const_iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
97 _Key, _HF, _ExK, _EqK, _All>
98 #else
99 # define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
100 # define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
101 # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
102 # define __const_iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
103 #endif
104
105 /*
106 * This method is too difficult to implement for hashtable that do not
107 * require a sorted operation on the stored type.
108 template <class _Val, class _Key, class _HF,
109 class _Traits, class _ExK, class _EqK, class _All>
110 bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
111 const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
112 const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
113 return __ht1._M_buckets == __ht2._M_buckets &&
114 __ht1._M_elems == __ht2._M_elems;
115 }
116 */
117
118 /* Returns the iterator before the first iterator of the bucket __n and set
119 * __n to the first previous bucket having the same first iterator as bucket
120 * __n.
121 */
122 template <class _Val, class _Key, class _HF,
123 class _Traits, class _ExK, class _EqK, class _All>
124 __iterator__
125 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_M_before_begin(size_type & __n)126 ::_M_before_begin(size_type &__n) const {
127 return _S_before_begin(_M_elems, _M_buckets, __n);
128 }
129
130 template <class _Val, class _Key, class _HF,
131 class _Traits, class _ExK, class _EqK, class _All>
132 __iterator__
133 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_S_before_begin(const _ElemsCont & __elems,const _BucketVector & __buckets,size_type & __n)134 ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
135 size_type &__n) {
136 _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
137 typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
138
139 _ElemsIte __pos(*__bpos);
140 if (__pos == __mutable_elems.begin()) {
141 __n = 0;
142 return __mutable_elems.before_begin();
143 }
144
145 typename _BucketVector::const_iterator __bcur(__bpos);
146 _BucketType *__pos_node = __pos._M_node;
147 for (--__bcur; __pos_node == *__bcur; --__bcur);
148
149 __n = __bcur - __buckets.begin() + 1;
150 _ElemsIte __cur(*__bcur);
151 _ElemsIte __prev = __cur++;
152 for (; __cur != __pos; ++__prev, ++__cur);
153 return __prev;
154 }
155
156
157 template <class _Val, class _Key, class _HF,
158 class _Traits, class _ExK, class _EqK, class _All>
159 __iterator__
160 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_M_insert_noresize(size_type __n,const value_type & __obj)161 ::_M_insert_noresize(size_type __n, const value_type& __obj) {
162 //We always insert this element as 1st in the bucket to not break
163 //the elements order as equal elements must be kept next to each other.
164 size_type __prev = __n;
165 _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
166
167 fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
168 _M_elems.insert_after(__pos, __obj)._M_node);
169 ++_M_num_elements;
170 return iterator(_ElemsIte(_M_buckets[__n]));
171 }
172
173 template <class _Val, class _Key, class _HF,
174 class _Traits, class _ExK, class _EqK, class _All>
175 pair<__iterator__, bool>
176 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
insert_unique_noresize(const value_type & __obj)177 ::insert_unique_noresize(const value_type& __obj) {
178 const size_type __n = _M_bkt_num(__obj);
179 _ElemsIte __cur(_M_buckets[__n]);
180 _ElemsIte __last(_M_buckets[__n + 1]);
181
182 if (__cur != __last) {
183 for (; __cur != __last; ++__cur) {
184 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
185 //We check that equivalent keys have equals hash code as otherwise, on resize,
186 //equivalent value might not be in the same bucket
187 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
188 return pair<iterator, bool>(iterator(__cur), false);
189 }
190 }
191 /* Here we do not rely on the _M_insert_noresize method as we know
192 * that we cannot break element orders, elements are unique, and
193 * insertion after the first bucket element is faster than what is
194 * done in _M_insert_noresize.
195 */
196 __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
197 ++_M_num_elements;
198 return pair<iterator, bool>(iterator(__cur), true);
199 }
200
201 return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
202 }
203
204 template <class _Val, class _Key, class _HF,
205 class _Traits, class _ExK, class _EqK, class _All>
206 __iterator__
207 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
insert_equal_noresize(const value_type & __obj)208 ::insert_equal_noresize(const value_type& __obj) {
209 const size_type __n = _M_bkt_num(__obj);
210 {
211 _ElemsIte __cur(_M_buckets[__n]);
212 _ElemsIte __last(_M_buckets[__n + 1]);
213
214 for (; __cur != __last; ++__cur) {
215 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
216 //We check that equivalent keys have equals hash code as otherwise, on resize,
217 //equivalent value might not be in the same bucket
218 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
219 ++_M_num_elements;
220 return _M_elems.insert_after(__cur, __obj);
221 }
222 }
223 }
224
225 return _M_insert_noresize(__n, __obj);
226 }
227
228 template <class _Val, class _Key, class _HF,
229 class _Traits, class _ExK, class _EqK, class _All>
230 __reference__
231 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_M_insert(const value_type & __obj)232 ::_M_insert(const value_type& __obj) {
233 resize(_M_num_elements + 1);
234 return *insert_unique_noresize(__obj).first;
235 }
236
237 /*
238 template <class _Val, class _Key, class _HF,
239 class _Traits, class _ExK, class _EqK, class _All>
240 __reference__
241 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
242 ::find_or_insert(const value_type& __obj) {
243 _Node* __first = _M_find(_M_get_key(__obj));
244 if (__first)
245 return __first->_M_val;
246 else
247 return _M_insert(__obj);
248 }
249 */
250
251 template <class _Val, class _Key, class _HF,
252 class _Traits, class _ExK, class _EqK, class _All>
253 __size_type__
254 hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
erase(const key_type & __key)255 ::erase(const key_type& __key) {
256 const size_type __n = _M_bkt_num_key(__key);
257
258 _ElemsIte __cur(_M_buckets[__n]);
259 _ElemsIte __last(_M_buckets[__n + 1]);
260 if (__cur == __last)
261 return 0;
262
263 size_type __erased = 0;
264 if (_M_equals(_M_get_key(*__cur), __key)) {
265 //We look for the pos before __cur:
266 size_type __prev_b = __n;
267 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
268 do {
269 __cur = _M_elems.erase_after(__prev);
270 ++__erased;
271 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
272 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
273 }
274 else {
275 _ElemsIte __prev = __cur++;
276 for (; __cur != __last; ++__prev, ++__cur) {
277 if (_M_equals(_M_get_key(*__cur), __key)) {
278 do {
279 __cur = _M_elems.erase_after(__prev);
280 ++__erased;
281 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
282 break;
283 }
284 }
285 }
286
287 _M_num_elements -= __erased;
288 return __erased;
289 }
290
291 template <class _Val, class _Key, class _HF,
292 class _Traits, class _ExK, class _EqK, class _All>
293 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
erase(const_iterator __it)294 ::erase(const_iterator __it) {
295 const size_type __n = _M_bkt_num(*__it);
296 _ElemsIte __cur(_M_buckets[__n]);
297
298 if (__cur == __it._M_ite) {
299 size_type __prev_b = __n;
300 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
301 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
302 _M_elems.erase_after(__prev)._M_node);
303 --_M_num_elements;
304 }
305 else {
306 _ElemsIte __prev = __cur++;
307 _ElemsIte __last(_M_buckets[__n + 1]);
308 for (; __cur != __last; ++__prev, ++__cur) {
309 if (__cur == __it._M_ite) {
310 _M_elems.erase_after(__prev);
311 --_M_num_elements;
312 break;
313 }
314 }
315 }
316 }
317
318 template <class _Val, class _Key, class _HF,
319 class _Traits, class _ExK, class _EqK, class _All>
320 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
erase(const_iterator __first,const_iterator __last)321 ::erase(const_iterator __first, const_iterator __last) {
322 if (__first == __last)
323 return;
324 size_type __f_bucket = _M_bkt_num(*__first);
325 size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
326
327 _ElemsIte __cur(_M_buckets[__f_bucket]);
328 _ElemsIte __prev;
329 if (__cur == __first._M_ite) {
330 __prev = _M_before_begin(__f_bucket)._M_ite;
331 }
332 else {
333 _ElemsIte __last(_M_buckets[++__f_bucket]);
334 __prev = __cur++;
335 for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
336 }
337 //We do not use the slist::erase_after method taking a range to count the
338 //number of erased elements:
339 while (__cur != __last._M_ite) {
340 __cur = _M_elems.erase_after(__prev);
341 --_M_num_elements;
342 }
343 fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
344 }
345
346 template <class _Val, class _Key, class _HF,
347 class _Traits, class _ExK, class _EqK, class _All>
348 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
rehash(size_type __num_buckets_hint)349 ::rehash(size_type __num_buckets_hint) {
350 if ((bucket_count() >= __num_buckets_hint) &&
351 (max_load_factor() > load_factor()))
352 return;
353
354 //Here if max_load_factor is lower than 1.0 the resulting value might not be representable
355 //as a size_type. The result concerning the respect of the max_load_factor will then be
356 //undefined.
357 __num_buckets_hint = (max) (__num_buckets_hint, (size_type)((float)size() / max_load_factor()));
358 size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
359 _M_rehash(__num_buckets);
360 }
361
362 template <class _Val, class _Key, class _HF,
363 class _Traits, class _ExK, class _EqK, class _All>
364 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
resize(size_type __num_elements_hint)365 ::resize(size_type __num_elements_hint) {
366 if (((float)__num_elements_hint / (float)bucket_count() <= max_load_factor()) &&
367 (max_load_factor() >= load_factor())) {
368 return;
369 }
370
371 size_type __num_buckets_hint = (size_type)((float)(max) (__num_elements_hint, size()) / max_load_factor());
372 size_type __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
373 #if defined (_STLP_DEBUG)
374 _M_check();
375 #endif
376 _M_rehash(__num_buckets);
377 }
378
379 template <class _Val, class _Key, class _HF,
380 class _Traits, class _ExK, class _EqK, class _All>
381 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_M_rehash(size_type __num_buckets)382 ::_M_rehash(size_type __num_buckets) {
383 _ElemsCont __tmp_elems(_M_elems.get_allocator());
384 _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
385 _ElemsIte __cur, __last(_M_elems.end());
386 while (!_M_elems.empty()) {
387 __cur = _M_elems.begin();
388 size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
389 _ElemsIte __ite(__cur), __before_ite(__cur);
390 for (++__ite;
391 __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
392 ++__ite, ++__before_ite);
393 size_type __prev_bucket = __new_bucket;
394 _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
395 __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
396 fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
397 }
398 _M_elems.swap(__tmp_elems);
399 _M_buckets.swap(__tmp);
400 }
401
402 #if defined (_STLP_DEBUG)
403 template <class _Val, class _Key, class _HF,
404 class _Traits, class _ExK, class _EqK, class _All>
_M_check()405 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_check() const {
406 //We check that hash code of stored keys haven't change and also that equivalent
407 //relation hasn't been modified
408 size_t __num_buckets = bucket_count();
409 for (size_t __b = 0; __b < __num_buckets; ++__b) {
410 _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
411 _ElemsIte __fst(__cur), __snd(__cur);
412 for (; __cur != __last; ++__cur) {
413 _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
414 _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
415 if (__fst != __snd)
416 ++__fst;
417 if (__snd != __cur)
418 ++__snd;
419 }
420 }
421 }
422 #endif
423
424 template <class _Val, class _Key, class _HF,
425 class _Traits, class _ExK, class _EqK, class _All>
clear()426 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::clear() {
427 _M_elems.clear();
428 _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
429 _M_num_elements = 0;
430 }
431
432 template <class _Val, class _Key, class _HF,
433 class _Traits, class _ExK, class _EqK, class _All>
434 void hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> & __ht)435 ::_M_copy_from(const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht) {
436 _M_elems.clear();
437 _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
438 _M_buckets.resize(__ht._M_buckets.size());
439 _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
440 _ElemsIte __dst(_M_elems.begin());
441 typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
442 __src_end_b(__ht._M_buckets.end());
443 typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
444 for (; __src != __src_end; ++__src, ++__dst) {
445 for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
446 if (*__src_b == __src._M_node) {
447 *__dst_b = __dst._M_node;
448 }
449 else
450 break;
451 }
452 }
453 fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
454 _M_num_elements = __ht._M_num_elements;
455 _M_max_load_factor = __ht._M_max_load_factor;
456 }
457
458 #undef __iterator__
459 #undef const_iterator
460 #undef __size_type__
461 #undef __reference__
462 #undef size_type
463 #undef value_type
464 #undef key_type
465 #undef __stl_num_primes
466
467 #if defined (_STLP_DEBUG)
468 # undef hashtable
469 _STLP_MOVE_TO_STD_NAMESPACE
470 #endif
471
472 _STLP_END_NAMESPACE
473
474 #endif /* _STLP_HASHTABLE_C */
475
476 // Local Variables:
477 // mode:C++
478 // End:
479