96 #ifndef _SPARSEHASHTABLE_H_ 97 #define _SPARSEHASHTABLE_H_ 99 #ifndef SPARSEHASH_STAT_UPDATE 100 #define SPARSEHASH_STAT_UPDATE(x) ((void) 0) 107 #define JUMP_(key, num_probes) ( num_probes ) 109 #include <stk_util/util/sparseconfig.h> 116 #include <stk_util/util/hashtable-common.h> 117 #include <stk_util/util/sparsetable> 119 _START_GOOGLE_NAMESPACE_
121 using STL_NAMESPACE::pair;
127 static const u_int16_t DEFAULT_GROUP_SIZE = 48;
146 template <
class Value,
class Key,
class HashFcn,
147 class ExtractKey,
class SetKey,
class EqualKey,
class Alloc>
148 class sparse_hashtable;
150 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
151 struct sparse_hashtable_iterator;
153 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
154 struct sparse_hashtable_const_iterator;
158 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
159 struct sparse_hashtable_iterator {
161 typedef typename A::template rebind<V>::other value_alloc_type;
164 typedef sparse_hashtable_iterator<V,K,HF,ExK,SetK,EqK,A> iterator;
165 typedef sparse_hashtable_const_iterator<V,K,HF,ExK,SetK,EqK,A> const_iterator;
166 typedef typename sparsetable<V,DEFAULT_GROUP_SIZE,A>::nonempty_iterator
169 typedef STL_NAMESPACE::forward_iterator_tag iterator_category;
170 typedef V value_type;
171 typedef typename value_alloc_type::difference_type difference_type;
172 typedef typename value_alloc_type::size_type size_type;
173 typedef typename value_alloc_type::reference reference;
174 typedef typename value_alloc_type::pointer pointer;
177 sparse_hashtable_iterator(
const sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *h,
178 st_iterator it, st_iterator it_end)
179 : ht(h), pos(it), end(it_end) { advance_past_deleted(); }
180 sparse_hashtable_iterator() { }
185 reference operator*()
const {
return *pos; }
186 pointer operator->()
const {
return &(operator*()); }
190 void advance_past_deleted() {
191 while ( pos != end && ht->test_deleted(*
this) )
194 iterator& operator++() {
195 assert(pos != end); ++pos; advance_past_deleted();
return *
this;
197 iterator operator++(
int) { iterator tmp(*
this); ++*
this;
return tmp; }
200 bool operator==(
const iterator& it)
const {
return pos == it.pos; }
201 bool operator!=(
const iterator& it)
const {
return pos != it.pos; }
205 const sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *ht;
206 st_iterator pos, end;
210 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
211 struct sparse_hashtable_const_iterator {
213 typedef typename A::template rebind<V>::other value_alloc_type;
216 typedef sparse_hashtable_iterator<V,K,HF,ExK,SetK,EqK,A> iterator;
217 typedef sparse_hashtable_const_iterator<V,K,HF,ExK,SetK,EqK,A> const_iterator;
218 typedef typename sparsetable<V,DEFAULT_GROUP_SIZE,A>::const_nonempty_iterator
221 typedef STL_NAMESPACE::forward_iterator_tag iterator_category;
222 typedef V value_type;
223 typedef typename value_alloc_type::difference_type difference_type;
224 typedef typename value_alloc_type::size_type size_type;
225 typedef typename value_alloc_type::const_reference reference;
226 typedef typename value_alloc_type::const_pointer pointer;
229 sparse_hashtable_const_iterator(
const sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *h,
230 st_iterator it, st_iterator it_end)
231 : ht(h), pos(it), end(it_end) { advance_past_deleted(); }
233 sparse_hashtable_const_iterator() { }
234 sparse_hashtable_const_iterator(
const iterator &it)
235 : ht(it.ht), pos(it.pos), end(it.end) { }
240 reference operator*()
const {
return *pos; }
241 pointer operator->()
const {
return &(operator*()); }
245 void advance_past_deleted() {
246 while ( pos != end && ht->test_deleted(*
this) )
249 const_iterator& operator++() {
250 assert(pos != end); ++pos; advance_past_deleted();
return *
this;
252 const_iterator operator++(
int) { const_iterator tmp(*
this); ++*
this;
return tmp; }
255 bool operator==(
const const_iterator& it)
const {
return pos == it.pos; }
256 bool operator!=(
const const_iterator& it)
const {
return pos != it.pos; }
260 const sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *ht;
261 st_iterator pos, end;
265 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
266 struct sparse_hashtable_destructive_iterator {
268 typedef typename A::template rebind<V>::other value_alloc_type;
271 typedef sparse_hashtable_destructive_iterator<V,K,HF,ExK,SetK,EqK,A> iterator;
272 typedef typename sparsetable<V,DEFAULT_GROUP_SIZE,A>::destructive_iterator
275 typedef STL_NAMESPACE::forward_iterator_tag iterator_category;
276 typedef V value_type;
277 typedef typename value_alloc_type::difference_type difference_type;
278 typedef typename value_alloc_type::size_type size_type;
279 typedef typename value_alloc_type::reference reference;
280 typedef typename value_alloc_type::pointer pointer;
283 sparse_hashtable_destructive_iterator(
const 284 sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *h,
285 st_iterator it, st_iterator it_end)
286 : ht(h), pos(it), end(it_end) { advance_past_deleted(); }
287 sparse_hashtable_destructive_iterator() { }
292 reference operator*()
const {
return *pos; }
293 pointer operator->()
const {
return &(operator*()); }
297 void advance_past_deleted() {
298 while ( pos != end && ht->test_deleted(*
this) )
301 iterator& operator++() {
302 assert(pos != end); ++pos; advance_past_deleted();
return *
this;
304 iterator operator++(
int) { iterator tmp(*
this); ++*
this;
return tmp; }
307 bool operator==(
const iterator& it)
const {
return pos == it.pos; }
308 bool operator!=(
const iterator& it)
const {
return pos != it.pos; }
312 const sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> *ht;
313 st_iterator pos, end;
317 template <
class Value,
class Key,
class HashFcn,
318 class ExtractKey,
class SetKey,
class EqualKey,
class Alloc>
319 class sparse_hashtable {
321 typedef typename Alloc::template rebind<Value>::other value_alloc_type;
324 typedef Key key_type;
325 typedef Value value_type;
326 typedef HashFcn hasher;
327 typedef EqualKey key_equal;
328 typedef Alloc allocator_type;
330 typedef typename value_alloc_type::size_type size_type;
331 typedef typename value_alloc_type::difference_type difference_type;
332 typedef typename value_alloc_type::reference reference;
333 typedef typename value_alloc_type::const_reference const_reference;
334 typedef typename value_alloc_type::pointer pointer;
335 typedef typename value_alloc_type::const_pointer const_pointer;
336 typedef sparse_hashtable_iterator<Value, Key, HashFcn, ExtractKey,
337 SetKey, EqualKey, Alloc>
340 typedef sparse_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey,
341 SetKey, EqualKey, Alloc>
344 typedef sparse_hashtable_destructive_iterator<Value, Key, HashFcn, ExtractKey,
345 SetKey, EqualKey, Alloc>
346 destructive_iterator;
349 typedef iterator local_iterator;
350 typedef const_iterator const_local_iterator;
355 static const int HT_OCCUPANCY_PCT;
360 static const int HT_EMPTY_PCT;
366 static const size_type HT_MIN_BUCKETS = 4;
371 static const size_type HT_DEFAULT_STARTING_BUCKETS = 32;
374 iterator begin() {
return iterator(
this, table.nonempty_begin(),
375 table.nonempty_end()); }
376 iterator end() {
return iterator(
this, table.nonempty_end(),
377 table.nonempty_end()); }
378 const_iterator begin()
const {
return const_iterator(
this,
379 table.nonempty_begin(),
380 table.nonempty_end()); }
381 const_iterator end()
const {
return const_iterator(
this,
382 table.nonempty_end(),
383 table.nonempty_end()); }
390 local_iterator begin(size_type i) {
392 return local_iterator(
this, table.get_iter(i), table.nonempty_end());
394 return local_iterator(
this, table.nonempty_end(), table.nonempty_end());
396 local_iterator end(size_type i) {
397 local_iterator it = begin(i);
398 if (table.test(i) && !test_deleted(i))
402 const_local_iterator begin(size_type i)
const {
404 return const_local_iterator(
this, table.get_iter(i),
405 table.nonempty_end());
407 return const_local_iterator(
this, table.nonempty_end(),
408 table.nonempty_end());
410 const_local_iterator end(size_type i)
const {
411 const_local_iterator it = begin(i);
412 if (table.test(i) && !test_deleted(i))
418 destructive_iterator destructive_begin() {
419 return destructive_iterator(
this, table.destructive_begin(),
420 table.destructive_end());
422 destructive_iterator destructive_end() {
423 return destructive_iterator(
this, table.destructive_end(),
424 table.destructive_end());
429 hasher hash_funct()
const {
return settings; }
430 key_equal key_eq()
const {
return key_info; }
431 allocator_type get_allocator()
const {
return table.get_allocator(); }
434 int num_table_copies()
const {
return settings.num_ht_copies(); }
442 void set_value(pointer dst, const_reference src) {
444 new(dst) value_type(src);
451 enum MoveDontCopyT {MoveDontCopy, MoveDontGrow};
460 void squash_deleted() {
462 sparse_hashtable tmp(MoveDontGrow, *
this);
465 assert(num_deleted == 0);
468 bool test_deleted_key(
const key_type& key)
const {
472 assert(settings.use_deleted() || num_deleted == 0);
473 return num_deleted > 0 && equals(key_info.delkey, key);
477 void set_deleted_key(
const key_type &key) {
480 settings.set_use_deleted(
true);
481 key_info.delkey = key;
483 void clear_deleted_key() {
485 settings.set_use_deleted(
false);
487 key_type deleted_key()
const {
488 assert(settings.use_deleted()
489 &&
"Must set deleted key before calling deleted_key");
490 return key_info.delkey;
495 bool test_deleted(size_type bucknum)
const {
496 if (num_deleted == 0 || !table.test(bucknum))
return false;
497 return test_deleted_key(get_key(table.unsafe_get(bucknum)));
499 bool test_deleted(
const iterator &it)
const {
500 if (!settings.use_deleted())
return false;
501 return test_deleted_key(get_key(*it));
503 bool test_deleted(
const const_iterator &it)
const {
504 if (!settings.use_deleted())
return false;
505 return test_deleted_key(get_key(*it));
507 bool test_deleted(
const destructive_iterator &it)
const {
508 if (!settings.use_deleted())
return false;
509 return test_deleted_key(get_key(*it));
515 bool set_deleted(iterator &it) {
516 assert(settings.use_deleted());
517 bool retval = !test_deleted(it);
519 set_key(&(*it), key_info.delkey);
523 bool clear_deleted(iterator &it) {
524 assert(settings.use_deleted());
526 return test_deleted(it);
534 bool set_deleted(const_iterator &it) {
535 assert(settings.use_deleted());
536 bool retval = !test_deleted(it);
537 set_key(const_cast<pointer>(&(*it)), key_info.delkey);
541 bool clear_deleted(const_iterator &it) {
542 assert(settings.use_deleted());
543 return test_deleted(it);
548 size_type size()
const {
return table.num_nonempty() - num_deleted; }
549 size_type max_size()
const {
return table.max_size(); }
550 bool empty()
const {
return size() == 0; }
551 size_type bucket_count()
const {
return table.size(); }
552 size_type max_bucket_count()
const {
return max_size(); }
555 size_type bucket_size(size_type i)
const {
556 return begin(i) == end(i) ? 0 : 1;
561 static const size_type ILLEGAL_BUCKET = size_type(-1);
566 bool maybe_shrink() {
567 assert(table.num_nonempty() >= num_deleted);
568 assert((bucket_count() & (bucket_count()-1)) == 0);
569 assert(bucket_count() >= HT_MIN_BUCKETS);
577 const size_type num_remain = table.num_nonempty() - num_deleted;
578 const size_type shrink_threshold = settings.shrink_threshold();
579 if (shrink_threshold > 0 && num_remain < shrink_threshold &&
580 bucket_count() > HT_DEFAULT_STARTING_BUCKETS) {
581 const float shrink_factor = settings.shrink_factor();
582 size_type sz = bucket_count() / 2;
583 while (sz > HT_DEFAULT_STARTING_BUCKETS &&
584 num_remain < static_cast<size_type>(sz * shrink_factor)) {
587 sparse_hashtable tmp(MoveDontCopy, *
this, sz);
591 settings.set_consider_shrink(
false);
598 bool resize_delta(size_type delta) {
599 bool did_resize =
false;
600 if ( settings.consider_shrink() ) {
601 if ( maybe_shrink() )
604 if (table.num_nonempty() >=
605 (STL_NAMESPACE::numeric_limits<size_type>::max)() - delta)
606 throw std::length_error(
"resize overflow");
607 if ( bucket_count() >= HT_MIN_BUCKETS &&
608 (table.num_nonempty() + delta) <= settings.enlarge_threshold() )
617 const size_type needed_size =
618 settings.min_buckets(table.num_nonempty() + delta, 0);
619 if ( needed_size <= bucket_count() )
622 size_type resize_to =
623 settings.min_buckets(table.num_nonempty() - num_deleted + delta,
625 if (resize_to < needed_size &&
626 resize_to < (STL_NAMESPACE::numeric_limits<size_type>::max)() / 2) {
634 const size_type target =
635 static_cast<size_type
>(settings.shrink_size(resize_to*2));
636 if (table.num_nonempty() - num_deleted + delta >= target) {
642 sparse_hashtable tmp(MoveDontCopy, *
this, resize_to);
648 void copy_from(
const sparse_hashtable &ht, size_type min_buckets_wanted) {
652 const size_type resize_to =
653 settings.min_buckets(ht.size(), min_buckets_wanted);
654 if ( resize_to > bucket_count() ) {
655 table.resize(resize_to);
656 settings.reset_thresholds(bucket_count());
662 assert((bucket_count() & (bucket_count()-1)) == 0);
663 for ( const_iterator it = ht.begin(); it != ht.end(); ++it ) {
664 size_type num_probes = 0;
666 const size_type bucket_count_minus_one = bucket_count() - 1;
667 for (bucknum = hash(get_key(*it)) & bucket_count_minus_one;
669 bucknum = (bucknum + JUMP_(key, num_probes)) & bucket_count_minus_one) {
671 assert(num_probes < bucket_count()
672 &&
"Hashtable is full: an error in key_equal<> or hash<>");
674 table.set(bucknum, *it);
676 settings.inc_num_ht_copies();
682 void move_from(MoveDontCopyT mover, sparse_hashtable &ht,
683 size_type min_buckets_wanted) {
688 if ( mover == MoveDontGrow )
689 resize_to = ht.bucket_count();
691 resize_to = settings.min_buckets(ht.size(), min_buckets_wanted);
692 if ( resize_to > bucket_count() ) {
693 table.resize(resize_to);
694 settings.reset_thresholds(bucket_count());
700 assert( (bucket_count() & (bucket_count()-1)) == 0);
702 for ( destructive_iterator it = ht.destructive_begin();
703 it != ht.destructive_end(); ++it ) {
704 size_type num_probes = 0;
706 for ( bucknum = hash(get_key(*it)) & (bucket_count()-1);
708 bucknum = (bucknum + JUMP_(key, num_probes)) & (bucket_count()-1) ) {
710 assert(num_probes < bucket_count()
711 &&
"Hashtable is full: an error in key_equal<> or hash<>");
713 table.set(bucknum, *it);
715 settings.inc_num_ht_copies();
724 void resize(size_type req_elements) {
725 if ( settings.consider_shrink() || req_elements == 0 )
727 if ( req_elements > table.num_nonempty() )
728 resize_delta(req_elements - table.num_nonempty());
735 void get_resizing_parameters(
float* shrink,
float* grow)
const {
736 *shrink = settings.shrink_factor();
737 *grow = settings.enlarge_factor();
739 void set_resizing_parameters(
float shrink,
float grow) {
740 settings.set_resizing_parameters(shrink, grow);
741 settings.reset_thresholds(bucket_count());
748 explicit sparse_hashtable(size_type expected_max_items_in_table = 0,
749 const HashFcn& hf = HashFcn(),
750 const EqualKey& eql = EqualKey(),
751 const ExtractKey& ext = ExtractKey(),
752 const SetKey&
set = SetKey(),
753 const Alloc& alloc = Alloc())
755 key_info(ext, set, eql),
757 table((expected_max_items_in_table == 0
758 ? HT_DEFAULT_STARTING_BUCKETS
759 : settings.min_buckets(expected_max_items_in_table, 0)),
761 settings.reset_thresholds(bucket_count());
768 sparse_hashtable(
const sparse_hashtable& ht,
769 size_type min_buckets_wanted = HT_DEFAULT_STARTING_BUCKETS)
770 : settings(ht.settings),
771 key_info(ht.key_info),
773 table(0, ht.get_allocator()) {
774 settings.reset_thresholds(bucket_count());
775 copy_from(ht, min_buckets_wanted);
777 sparse_hashtable(MoveDontCopyT mover, sparse_hashtable& ht,
778 size_type min_buckets_wanted = HT_DEFAULT_STARTING_BUCKETS)
779 : settings(ht.settings),
780 key_info(ht.key_info),
782 table(0, ht.get_allocator()) {
783 settings.reset_thresholds(bucket_count());
784 move_from(mover, ht, min_buckets_wanted);
787 sparse_hashtable& operator= (
const sparse_hashtable& ht) {
788 if (&ht ==
this)
return *
this;
789 settings = ht.settings;
790 key_info = ht.key_info;
791 num_deleted = ht.num_deleted;
793 copy_from(ht, HT_MIN_BUCKETS);
799 void swap(sparse_hashtable& ht) {
800 STL_NAMESPACE::swap(settings, ht.settings);
801 STL_NAMESPACE::swap(key_info, ht.key_info);
802 STL_NAMESPACE::swap(num_deleted, ht.num_deleted);
803 table.swap(ht.table);
808 if (!empty() || (num_deleted != 0)) {
811 settings.reset_thresholds(bucket_count());
822 pair<size_type, size_type> find_position(
const key_type &key)
const {
823 size_type num_probes = 0;
824 const size_type bucket_count_minus_one = bucket_count() - 1;
825 size_type bucknum = hash(key) & bucket_count_minus_one;
826 size_type insert_pos = ILLEGAL_BUCKET;
827 SPARSEHASH_STAT_UPDATE(total_lookups += 1);
829 if ( !table.test(bucknum) ) {
830 SPARSEHASH_STAT_UPDATE(total_probes += num_probes);
831 if ( insert_pos == ILLEGAL_BUCKET )
832 return pair<size_type,size_type>(ILLEGAL_BUCKET, bucknum);
834 return pair<size_type,size_type>(ILLEGAL_BUCKET, insert_pos);
836 }
else if ( test_deleted(bucknum) ) {
837 if ( insert_pos == ILLEGAL_BUCKET )
838 insert_pos = bucknum;
840 }
else if ( equals(key, get_key(table.unsafe_get(bucknum))) ) {
841 SPARSEHASH_STAT_UPDATE(total_probes += num_probes);
842 return pair<size_type,size_type>(bucknum, ILLEGAL_BUCKET);
845 bucknum = (bucknum + JUMP_(key, num_probes)) & bucket_count_minus_one;
846 assert(num_probes < bucket_count()
847 &&
"Hashtable is full: an error in key_equal<> or hash<>");
852 iterator
find(
const key_type& key) {
853 if ( size() == 0 )
return end();
854 pair<size_type, size_type> pos = find_position(key);
855 if ( pos.first == ILLEGAL_BUCKET )
858 return iterator(
this, table.get_iter(pos.first), table.nonempty_end());
861 const_iterator
find(
const key_type& key)
const {
862 if ( size() == 0 )
return end();
863 pair<size_type, size_type> pos = find_position(key);
864 if ( pos.first == ILLEGAL_BUCKET )
867 return const_iterator(
this,
868 table.get_iter(pos.first), table.nonempty_end());
873 size_type bucket(
const key_type& key)
const {
874 pair<size_type, size_type> pos = find_position(key);
875 return pos.first == ILLEGAL_BUCKET ? pos.second : pos.first;
879 size_type
count(
const key_type &key)
const {
880 pair<size_type, size_type> pos = find_position(key);
881 return pos.first == ILLEGAL_BUCKET ? 0 : 1;
885 pair<iterator,iterator>
equal_range(
const key_type& key) {
886 iterator pos =
find(key);
888 return pair<iterator,iterator>(pos, pos);
890 const iterator startpos = pos++;
891 return pair<iterator,iterator>(startpos, pos);
894 pair<const_iterator,const_iterator>
equal_range(
const key_type& key)
const {
895 const_iterator pos =
find(key);
897 return pair<const_iterator,const_iterator>(pos, pos);
899 const const_iterator startpos = pos++;
900 return pair<const_iterator,const_iterator>(startpos, pos);
908 iterator insert_at(const_reference obj, size_type pos) {
909 if (size() >= max_size())
910 throw std::length_error(
"insert overflow");
911 if ( test_deleted(pos) ) {
913 assert(num_deleted > 0);
917 return iterator(
this, table.get_iter(pos), table.nonempty_end());
921 pair<iterator, bool> insert_noresize(const_reference obj) {
923 assert((!settings.use_deleted() || !equals(get_key(obj), key_info.delkey))
924 &&
"Inserting the deleted key");
925 const pair<size_type,size_type> pos = find_position(get_key(obj));
926 if ( pos.first != ILLEGAL_BUCKET) {
927 return pair<iterator,bool>(iterator(
this, table.get_iter(pos.first),
928 table.nonempty_end()),
931 return pair<iterator,bool>(insert_at(obj, pos.second),
true);
937 template <
class ForwardIterator>
938 void insert(ForwardIterator f, ForwardIterator l, STL_NAMESPACE::forward_iterator_tag) {
939 size_t dist = STL_NAMESPACE::distance(f, l);
940 if (dist >= (std::numeric_limits<size_type>::max)())
941 throw std::length_error(
"insert-range overflow");
942 resize_delta(static_cast<size_type>(dist));
943 for ( ; dist > 0; --dist, ++f) {
949 template <
class InputIterator>
950 void insert(InputIterator f, InputIterator l, STL_NAMESPACE::input_iterator_tag) {
957 pair<iterator, bool>
insert(const_reference obj) {
959 return insert_noresize(obj);
963 template <
class InputIterator>
964 void insert(InputIterator f, InputIterator l) {
966 insert(f, l,
typename STL_NAMESPACE::iterator_traits<InputIterator>::iterator_category());
971 template <
class DefaultValue>
972 value_type& find_or_insert(
const key_type& key) {
974 assert((!settings.use_deleted() || !equals(key, key_info.delkey))
975 &&
"Inserting the deleted key");
976 const pair<size_type,size_type> pos = find_position(key);
977 DefaultValue default_value;
978 if ( pos.first != ILLEGAL_BUCKET) {
979 return *table.get_iter(pos.first);
980 }
else if (resize_delta(1)) {
982 return *insert_noresize(default_value(key)).first;
984 return *insert_at(default_value(key), pos.second);
989 size_type erase(
const key_type& key) {
991 assert((!settings.use_deleted() || !equals(key, key_info.delkey))
992 &&
"Erasing the deleted key");
993 assert(!settings.use_deleted() || !equals(key, key_info.delkey));
994 const_iterator pos =
find(key);
995 if ( pos != end() ) {
996 assert(!test_deleted(pos));
1000 settings.set_consider_shrink(
true);
1008 void erase(iterator pos) {
1009 if ( pos == end() )
return;
1010 if ( set_deleted(pos) ) {
1013 settings.set_consider_shrink(
true);
1017 void erase(iterator f, iterator l) {
1018 for ( ; f != l; ++f) {
1019 if ( set_deleted(f) )
1023 settings.set_consider_shrink(
true);
1031 void erase(const_iterator pos) {
1032 if ( pos == end() )
return;
1033 if ( set_deleted(pos) ) {
1036 settings.set_consider_shrink(
true);
1039 void erase(const_iterator f, const_iterator l) {
1040 for ( ; f != l; ++f) {
1041 if ( set_deleted(f) )
1045 settings.set_consider_shrink(
true);
1050 bool operator==(
const sparse_hashtable& ht)
const {
1051 if (size() != ht.size()) {
1053 }
else if (
this == &ht) {
1058 for ( const_iterator it = begin(); it != end(); ++it ) {
1059 const_iterator it2 = ht.find(get_key(*it));
1060 if ((it2 == ht.end()) || (*it != *it2)) {
1067 bool operator!=(
const sparse_hashtable& ht)
const {
1068 return !(*
this == ht);
1078 bool write_metadata(FILE *fp) {
1080 return table.write_metadata(fp);
1083 bool read_metadata(FILE *fp) {
1085 bool result = table.read_metadata(fp);
1086 settings.reset_thresholds(bucket_count());
1091 bool write_nopointer_data(FILE *fp) {
1092 return table.write_nopointer_data(fp);
1096 bool read_nopointer_data(FILE *fp) {
1097 return table.read_nopointer_data(fp);
1102 typedef sparsetable<value_type, DEFAULT_GROUP_SIZE, value_alloc_type> Table;
1109 sh_hashtable_settings<key_type, hasher, size_type, HT_MIN_BUCKETS> {
1110 explicit Settings(
const hasher& hf)
1111 : sh_hashtable_settings<key_type, hasher, size_type, HT_MIN_BUCKETS>(
1112 hf, HT_OCCUPANCY_PCT / 100.0f, HT_EMPTY_PCT / 100.0f) {}
1117 class KeyInfo :
public ExtractKey,
public SetKey,
public key_equal {
1119 KeyInfo(
const ExtractKey& ek,
const SetKey& sk,
const key_equal& eq)
1125 typename ExtractKey::result_type get_key(const_reference v)
const {
1126 return ExtractKey::operator()(v);
1128 void set_key(pointer v,
const key_type& k)
const {
1129 SetKey::operator()(v, k);
1131 bool equals(
const key_type& a,
const key_type& b)
const {
1132 return key_equal::operator()(a, b);
1137 typename remove_const<key_type>::type delkey;
1141 size_type hash(
const key_type& v)
const {
1142 return settings.hash(v);
1144 bool equals(
const key_type& a,
const key_type& b)
const {
1145 return key_info.equals(a, b);
1147 typename ExtractKey::result_type get_key(const_reference v)
const {
1148 return key_info.get_key(v);
1150 void set_key(pointer v,
const key_type& k)
const {
1151 key_info.set_key(v, k);
1158 size_type num_deleted;
1164 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
1165 inline void swap(sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> &x,
1166 sparse_hashtable<V,K,HF,ExK,SetK,EqK,A> &y) {
1172 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
1173 const typename sparse_hashtable<V,K,HF,ExK,SetK,EqK,A>::size_type
1174 sparse_hashtable<V,K,HF,ExK,SetK,EqK,A>::ILLEGAL_BUCKET;
1178 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
1179 const int sparse_hashtable<V,K,HF,ExK,SetK,EqK,A>::HT_OCCUPANCY_PCT = 80;
1183 template <
class V,
class K,
class HF,
class ExK,
class SetK,
class EqK,
class A>
1184 const int sparse_hashtable<V,K,HF,ExK,SetK,EqK,A>::HT_EMPTY_PCT
1185 =
static_cast<int>(0.4 *
1186 sparse_hashtable<V,K,HF,ExK,SetK,EqK,A>::HT_OCCUPANCY_PCT);
1188 _END_GOOGLE_NAMESPACE_
pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first, ForwardIterator last, const T &value)
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)