1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5// ==++==
6//
7
8//
9
10//
11// ==--==
12
13/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
14XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
15XX XX
16XX hashtable<K,V,H,P,A,KO> XX
17XX XX
18XX Implemented using a vector of list iterators begin and end whose range XX
19XX is a single bucket. A chain of buckets is maintained in a linked list XX
20XX (doubly) for holding the key-value pairs. XX
21XX XX
22XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
23XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
24*/
25
26#pragma once
27
28#include "hash.h"
29#include "functional.h"
30#include "allocator.h"
31#include "vector.h"
32#include "list.h"
33#include "pair.h"
34
35namespace jitstd
36{
37
38static const float kflDefaultLoadFactor = 3.0f;
39
40template <typename Key,
41 typename Value = Key,
42 typename Hash = jitstd::hash<Key>,
43 typename Pred = jitstd::equal_to<Key>,
44 typename Alloc = jitstd::allocator<Value>,
45 typename KeyOf = jitstd::identity<Value>>
46class hashtable
47{
48public:
49 typedef Key key_type;
50 typedef Value value_type;
51 typedef Hash hasher;
52 typedef Pred key_equal;
53 typedef Alloc allocator_type;
54 typedef typename allocator_type::pointer pointer;
55 typedef typename allocator_type::const_pointer const_pointer;
56 typedef typename allocator_type::reference reference;
57 typedef typename allocator_type::const_reference const_reference;
58 typedef size_t size_type;
59 typedef ptrdiff_t difference_type;
60 typedef typename list<Value, Alloc>::iterator iterator;
61 typedef typename list<Value, Alloc>::reverse_iterator reverse_iterator;
62 typedef typename list<Value, Alloc>::const_iterator const_iterator;
63 typedef typename list<Value, Alloc>::iterator local_iterator;
64
65protected:
66 hashtable();
67
68 typedef pair<iterator, iterator> BucketEntry;
69 typedef vector<BucketEntry, typename Alloc::template rebind<BucketEntry>::allocator> Buckets;
70 typedef list<Value, typename Alloc::template rebind<Value>::allocator> Elements;
71
72protected:
73 explicit hashtable(size_type,
74 const allocator_type& a,
75 const KeyOf& keyOf = KeyOf());
76
77 hashtable(size_type n,
78 const hasher& hf,
79 const key_equal& eq,
80 const allocator_type& a,
81 const KeyOf& keyOf = KeyOf());
82
83 template<typename InputIterator>
84 hashtable(
85 InputIterator f, InputIterator l,
86 size_type n,
87 const hasher& hf,
88 const key_equal& eq,
89 const allocator_type& a,
90 const KeyOf& keyOf = KeyOf());
91
92 explicit hashtable(const allocator_type& a, const KeyOf& keyOf = KeyOf());
93
94 hashtable(const hashtable& other);
95
96 ~hashtable();
97
98public:
99 hashtable& operator=(const hashtable& other);
100
101 allocator_type get_allocator() const;
102
103 bool empty() const;
104
105 size_type size() const;
106 size_type max_size() const;
107
108 iterator begin();
109 iterator end();
110
111 // Even though we have an unordered set and there is no concept of forward and
112 // reverse, rbegin will just return the first element inserted. This is not in STL.
113 reverse_iterator rbegin();
114 reverse_iterator rend();
115
116 const_iterator begin() const;
117 const_iterator end() const;
118 const_iterator cbegin() const;
119 const_iterator cend() const;
120 local_iterator begin(size_type size);
121 local_iterator end(size_type size);
122
123 pair<iterator, bool> insert(const value_type& value);
124 iterator insert(const_iterator, const value_type& value);
125 template<typename InputIterator>
126 void insert(InputIterator first, InputIterator last);
127
128 iterator erase(iterator position);
129 size_type erase(const key_type& key);
130 iterator erase(iterator first, iterator last);
131
132 void clear();
133 void swap(hashtable& table);
134
135 hasher hash_function() const;
136 key_equal key_eq() const;
137
138 const_iterator find(const key_type& key) const;
139 iterator find(const key_type& key);
140
141 size_type count(const key_type& key) const;
142
143 size_type bucket_count() const;
144 size_type max_bucket_count() const;
145
146 size_type bucket_size(size_type size) const;
147 size_type bucket(const key_type& key) const;
148
149 float load_factor() const;
150 float max_load_factor() const;
151 void max_load_factor(float);
152
153 void rehash(size_type);
154
155protected:
156 template <typename Compare>
157 iterator find(const key_type&, const Compare& comp);
158
159 // helpers
160 bool check_load();
161 void copy_helper(const hashtable& other);
162 size_type hash_helper(const key_type& value, size_type buckets) const;
163 pair<iterator, bool> insert_helper(const value_type& value, Buckets& buckets, Elements& elements, bool fRehashing);
164 iterator erase_helper(const_iterator position);
165 void dump_helper();
166 void debug_check();
167
168private:
169
170 // member objects
171 Hash m_hasher;
172 Alloc m_allocator;
173 Pred m_pred;
174
175 Buckets m_buckets;
176 Elements m_elements;
177 size_type m_nSize;
178 KeyOf m_keyOf;
179
180 // metadata
181 float m_flMaxLoadFactor;
182};
183
184} // end of namespace jitstd
185
186
187namespace jitstd
188{
189
190template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
191void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::dump_helper()
192{
193 for (size_type i = 0; i < m_buckets.size(); ++i)
194 {
195 printf("\n");
196 printf("--------------=BEGIN=--------------\n");
197 printf("Load factor = %f\n", load_factor());
198 printf("-----------------------------------\n");
199 printf("Bucket number = %d %p %p\n", i, *((ptrdiff_t*)&(m_buckets[i].first)), *((ptrdiff_t*)&(m_buckets[i].second)));
200 printf("-----------------------------------\n");
201 for (typename Elements::iterator value = (m_buckets[i]).first; value != (m_buckets[i]).second; ++value)
202 {
203 printf("%d, ", *((ptrdiff_t*)&value), *value);
204 }
205 printf("-----------------------------------\n");
206 }
207}
208
209// We can't leave this permanently enabled -- it makes algorithms cubic, and causes tests to time out.
210// Enable when/if you have reason to believe there's a problem in hashtable.
211#define JITSTD_DO_HASHTABLE_DEBUGCHECK 0
212
213template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
214void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::debug_check()
215{
216#if JITSTD_DO_HASHTABLE_DEBUGCHECK
217 for (iterator iter = m_elements.begin(); iter != m_elements.end(); ++iter)
218 {
219 size_type nHash = hash_helper(m_keyOf(*iter), m_buckets.size());
220 BucketEntry& entry = m_buckets[nHash];
221 iterator iter2 = entry.first;
222 bool present = false;
223 while (iter2 != entry.second)
224 {
225 if (iter2 == iter)
226 {
227 present = true;
228 }
229 iter2++;
230 }
231 if (!present)
232 {
233 present = false;
234 }
235 assert(present);
236 }
237#endif
238}
239
240template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
241template <typename Compare>
242typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
243hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::find(const key_type& key, const Compare& comp)
244{
245 if (empty())
246 {
247 return end();
248 }
249 size_type nHash = hash_helper(key, m_buckets.size());
250 BucketEntry& entry = m_buckets[nHash];
251 for (iterator i = entry.first; i != entry.second; ++i)
252 {
253 if (comp(m_keyOf(*i), key))
254 {
255 return i;
256 }
257 }
258 return end();
259}
260
261template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
262bool hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::check_load()
263{
264 float flLoadFactor = load_factor();
265 if (flLoadFactor > m_flMaxLoadFactor)
266 {
267 rehash(m_buckets.size());
268 return true;
269 }
270 return false;
271}
272
273template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
274typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
275hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::erase_helper(const_iterator position)
276{
277 const Key& key = m_keyOf(*position);
278 size_type nHash = hash_helper(key, m_buckets.size());
279 BucketEntry& entry = m_buckets[nHash];
280 iterator eraseNext = end();
281 for (iterator first = entry.first; first != entry.second; ++first)
282 {
283 if (m_pred(m_keyOf(*first), key))
284 {
285 if (first == entry.first)
286 {
287 if (first != m_elements.begin())
288 {
289 iterator update = first;
290 update--;
291 size_type nUpdateHash = hash_helper(m_keyOf(*update), m_buckets.size());
292 if (nUpdateHash != nHash)
293 {
294 BucketEntry& updateEntry = m_buckets[nUpdateHash];
295 if (updateEntry.second == first)
296 {
297 updateEntry.second = first;
298 updateEntry.second++;
299 }
300 if (updateEntry.first == first)
301 {
302 updateEntry.first = first;
303 updateEntry.first++;
304 }
305 }
306 }
307 entry.first = m_elements.erase(first);
308 eraseNext = entry.first;
309 }
310 else
311 {
312 eraseNext = m_elements.erase(first);
313 }
314
315 --m_nSize;
316#ifdef DEBUG
317 debug_check();
318#endif
319 return eraseNext;
320 }
321 }
322 return end();
323}
324
325template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
326pair<typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator, bool>
327hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::insert_helper(
328 const Value& value, Buckets& buckets, Elements& elements, bool fRehashing)
329{
330 const Key& key = m_keyOf(value);
331 size_t nHash = hash_helper(key, buckets.size());
332 BucketEntry& entry = buckets[nHash];
333
334 iterator ret;
335 if (entry.first == entry.second)
336 {
337 entry.first = elements.insert(elements.begin(), value);
338 entry.second = entry.first;
339 entry.second++; // end iterator is one past always.
340 ret = entry.first;
341 }
342 else
343 {
344 for (iterator first = entry.first; first != entry.second; ++first)
345 {
346 if (m_pred(m_keyOf(*first), key))
347 {
348 return pair<iterator, bool>(first, false);
349 }
350 }
351 iterator firstNext = entry.first;
352 firstNext++;
353 ret = elements.insert(firstNext, value);
354 if (entry.second == entry.first)
355 {
356 entry.second = firstNext;
357 }
358 }
359 bool fRehashed = false;
360 if (!fRehashing)
361 {
362 m_nSize += 1;
363 fRehashed = check_load();
364 }
365
366#ifdef DEBUG
367 debug_check();
368#endif
369
370 return pair<iterator, bool>(fRehashed ? find(key, m_pred) : ret, true);
371}
372
373template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
374typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
375 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hash_helper(
376 const key_type& key, size_type buckets) const
377{
378 return m_hasher(key) % buckets;
379}
380
381template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
382void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::rehash(size_type n)
383{
384 size_type nCurBuckets = m_buckets.size();
385 float flLoadFactor = load_factor();
386 if (nCurBuckets >= n && flLoadFactor <= m_flMaxLoadFactor)
387 {
388 return;
389 }
390
391 size_type nBuckets = max(nCurBuckets, 1);
392 if (flLoadFactor > m_flMaxLoadFactor)
393 {
394 nBuckets *= 2;
395 }
396
397 if (nBuckets < n)
398 {
399 nBuckets = n;
400 }
401
402 Buckets buckets(m_allocator);
403 Elements elements(m_allocator);
404
405 buckets.resize(nBuckets, BucketEntry(m_elements.end(), m_elements.end())); // both equal means empty.
406 for (typename Elements::iterator iter = m_elements.begin(); iter != m_elements.end(); ++iter)
407 {
408 (void) insert_helper(*iter, buckets, elements, true);
409 }
410 m_buckets.swap(buckets);
411 m_elements.swap(elements);
412}
413
414template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
415hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hashtable(
416 size_type n,
417 allocator_type const& allocator,
418 const KeyOf& keyOf)
419 : m_allocator(allocator)
420 , m_buckets(Alloc::template rebind<hashtable::BucketEntry>::allocator(allocator))
421 , m_elements(allocator)
422 , m_flMaxLoadFactor(kflDefaultLoadFactor)
423 , m_nSize(0)
424 , m_keyOf(keyOf)
425{
426 rehash(n);
427}
428
429template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
430hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hashtable(
431 size_type n,
432 hasher const& hf,
433 key_equal const& eq,
434 allocator_type const& allocator,
435 const KeyOf& keyOf)
436 : m_hasher(hf)
437 , m_pred(eq)
438 , m_allocator(allocator)
439 , m_buckets(Alloc::template rebind<BucketEntry>::allocator(allocator))
440 , m_elements(allocator)
441 , m_flMaxLoadFactor(kflDefaultLoadFactor)
442 , m_nSize(0)
443 , m_keyOf(keyOf)
444{
445 rehash(n);
446}
447
448template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
449template<typename InputIterator>
450hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hashtable(
451 InputIterator f, InputIterator l,
452 size_type n,
453 const hasher& hf,
454 const key_equal& eq,
455 const allocator_type& allocator,
456 const KeyOf& keyOf)
457 : m_hasher(hf)
458 , m_pred(eq)
459 , m_allocator(allocator)
460 , m_buckets(Alloc::template rebind<BucketEntry>::allocator(allocator))
461 , m_elements(allocator)
462 , m_flMaxLoadFactor(kflDefaultLoadFactor)
463 , m_nSize(0)
464 , m_keyOf(keyOf)
465{
466 rehash(n);
467 insert(this->first, this->last);
468}
469
470template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
471hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hashtable(const allocator_type& allocator, const KeyOf& keyOf)
472 : m_allocator(allocator)
473 , m_buckets(Alloc::template rebind<BucketEntry>::allocator(allocator))
474 , m_elements(allocator)
475 , m_flMaxLoadFactor(kflDefaultLoadFactor)
476 , m_nSize(0)
477 , m_keyOf(keyOf)
478{
479}
480
481template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
482void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::copy_helper(const hashtable& other)
483{
484 m_buckets.clear();
485 m_elements.clear();
486 m_nSize = 0;
487
488 rehash(other.m_buckets.size());
489 for (const_iterator i = other.m_elements.begin(); i != other.m_elements.end(); ++i)
490 {
491 insert_helper(*i, m_buckets, m_elements, false);
492 }
493 m_nSize = other.m_nSize;
494}
495
496template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
497hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hashtable(const hashtable& other)
498 : m_hasher(other.m_hasher)
499 , m_pred(other.m_pred)
500 , m_allocator(other.m_allocator)
501 , m_flMaxLoadFactor(other.m_flMaxLoadFactor)
502 , m_keyOf(other.m_keyOf)
503 , m_elements(other.m_allocator)
504 , m_buckets(other.m_allocator)
505{
506 copy_helper(other);
507}
508
509template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
510hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::~hashtable()
511{
512}
513
514template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
515hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>&
516 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::operator=(hashtable const& other)
517{
518 m_hasher = other.m_hasher;
519 m_pred = other.m_pred;
520 m_allocator = other.m_allocator;
521 m_flMaxLoadFactor = other.m_flMaxLoadFactor;
522 m_keyOf = other.m_keyOf;
523 copy_helper(other);
524 return *this;
525}
526
527template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
528typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::allocator_type
529 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::get_allocator() const
530{
531 return m_allocator;
532}
533
534template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
535bool hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::empty() const
536{
537 return m_nSize == 0;
538}
539
540template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
541typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
542 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size() const
543{
544 return m_nSize;
545}
546
547template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
548typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
549 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::max_size() const
550{
551 return ((size_type)(-1)) >> 1;
552}
553
554template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
555typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
556hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::begin()
557{
558 return m_elements.begin();
559}
560
561template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
562typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::reverse_iterator
563hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::rbegin()
564{
565 return m_elements.rbegin();
566}
567
568template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
569typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
570hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::end()
571{
572 return m_elements.end();
573}
574
575template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
576typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::reverse_iterator
577hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::rend()
578{
579 return m_elements.rend();
580}
581
582template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
583typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::const_iterator
584hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::begin() const
585{
586 return m_elements.begin();
587}
588
589template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
590typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::const_iterator
591hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::end() const
592{
593 return m_elements.end();
594}
595
596template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
597typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::const_iterator
598hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::cbegin() const
599{
600 return m_elements.begin();
601}
602
603template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
604typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::const_iterator
605hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::cend() const
606{
607 return m_elements.end();
608}
609
610template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
611jitstd::pair<typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator, bool>
612 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::insert(const Value& val)
613{
614 // Allocate some space first.
615 rehash(2);
616 return insert_helper(val, m_buckets, m_elements, false);
617}
618
619template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
620typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
621 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::insert(const_iterator position, const Value& value)
622{
623 // Allocate some space first.
624 rehash(2);
625
626 // We will not use the hint here, we can consider doing this later.
627 return insert_helper(this->val, m_buckets, m_elements, false).first;
628}
629
630template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
631template<typename InputIterator>
632void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::insert(InputIterator first, InputIterator last)
633{
634 // Allocate some space first.
635 rehash(2);
636 while (first != last)
637 {
638 (void) insert_helper(*first, m_buckets, m_elements, false);
639 ++first;
640 }
641}
642
643template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
644typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
645 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::erase(iterator position)
646{
647 return erase_helper(position);
648}
649
650template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
651typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
652 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::erase(const key_type& key)
653{
654 iterator iter = erase_helper(find(key));
655 return iter == end() ? 0 : 1;
656}
657
658template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
659typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
660 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::erase(iterator first, iterator last)
661{
662 iterator iter = end();
663 while (first != last)
664 {
665 iter = erase_helper(find(m_keyOf(*first)));
666 ++first;
667 }
668 return iter;
669}
670
671template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
672void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::clear()
673{
674 m_buckets.clear();
675 m_elements.clear();
676}
677
678template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
679void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::swap(hashtable& set)
680{
681 std::swap(set.m_buckets, m_buckets);
682 std::swap(set.m_elements, m_elements);
683 std::swap(set.m_flLoadFactor, this->m_flLoadFactor);
684 std::swap(set.m_flMaxLoadFactor, this->m_flMaxLoadFactor);
685 std::swap(set.m_keyOf, this->m_keyOf);
686}
687
688
689template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
690typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hasher
691 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::hash_function() const
692{
693 return m_hasher;
694}
695
696template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
697typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::key_equal
698 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::key_eq() const
699{
700 return m_pred;
701}
702
703template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
704typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::const_iterator
705 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::find(const key_type& key) const
706{
707 if (empty())
708 {
709 return end();
710 }
711 size_type nHash = hash_helper(key, m_buckets.size());
712 BucketEntry& entry = m_buckets[nHash];
713 for (iterator i = entry.first; i != entry.second; ++i)
714 {
715 if (m_pred(m_keyOf(*i), key))
716 {
717 return i;
718 }
719 }
720 return end();
721}
722
723template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
724typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::iterator
725 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::find(const key_type& key)
726{
727 if (empty())
728 {
729 return end();
730 }
731 size_type nHash = hash_helper(key, m_buckets.size());
732 BucketEntry& entry = m_buckets[nHash];
733 for (iterator i = entry.first; i != entry.second; ++i)
734 {
735 if (m_pred(m_keyOf(*i), key))
736 {
737 return i;
738 }
739 }
740 return end();
741}
742
743
744template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
745typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
746 hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::count(const key_type& key) const
747{
748 size_type nCount = 0;
749 size_type nHash = hash_helper(key, m_buckets.size());
750 BucketEntry& bucket = m_buckets[nHash];
751 for (iterator i = bucket.first; i != bucket.second; ++i)
752 {
753 if (m_pred(m_keyOf(*i), key))
754 {
755 ++nCount;
756 }
757 }
758 return nCount;
759}
760
761template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
762typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
763hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::bucket_count() const
764{
765 return m_buckets.size();
766}
767
768template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
769typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
770hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::max_bucket_count() const
771{
772 return m_buckets.size();
773}
774
775template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
776typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
777hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::bucket_size(size_type size) const
778{
779 rehash(size);
780}
781
782template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
783typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::size_type
784hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::bucket(const key_type& key) const
785{
786 return hash_helper(key, m_buckets.size());
787}
788
789template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
790typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::local_iterator
791hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::begin(size_type size)
792{
793 return m_buckets[size].first;
794}
795
796template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
797typename hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::local_iterator
798hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::end(size_type size)
799{
800 return m_buckets[size].second;
801}
802
803template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
804float hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::load_factor() const
805{
806 return m_nSize ? (((float) m_nSize) / m_buckets.size()) : 0;
807}
808
809template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
810float hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::max_load_factor() const
811{
812 return m_flMaxLoadFactor;
813}
814
815template <typename Key, typename Value, typename Hash, typename Pred, typename Alloc, typename KeyOf>
816void hashtable<Key, Value, Hash, Pred, Alloc, KeyOf>::max_load_factor(float flLoadFactor)
817{
818 m_flMaxLoadFactor = flLoadFactor;
819 rehash(m_buckets.size());
820}
821
822} // end of namespace jitstd.
823