diff options
Diffstat (limited to 'util/probing_hash_table.hh')
-rw-r--r-- | util/probing_hash_table.hh | 125 |
1 files changed, 94 insertions, 31 deletions
diff --git a/util/probing_hash_table.hh b/util/probing_hash_table.hh index f32b64ea3..53fbbe996 100644 --- a/util/probing_hash_table.hh +++ b/util/probing_hash_table.hh @@ -26,6 +26,65 @@ struct IdentityHash { template <class T> T operator()(T arg) const { return arg; } }; +class DivMod { + public: + explicit DivMod(std::size_t buckets) : buckets_(buckets) {} + + static std::size_t RoundBuckets(std::size_t from) { + return from; + } + + template <class It> It Ideal(It begin, uint64_t hash) const { + return begin + (hash % buckets_); + } + + template <class BaseIt, class OutIt> void Next(BaseIt begin, BaseIt end, OutIt &it) const { + if (++it == end) it = begin; + } + + void Double() { + buckets_ *= 2; + } + + private: + std::size_t buckets_; +}; + +class Power2Mod { + public: + explicit Power2Mod(std::size_t buckets) { + UTIL_THROW_IF(!buckets || (((buckets - 1) & buckets)), ProbingSizeException, "Size " << buckets << " is not a power of 2."); + mask_ = buckets - 1; + } + + // Round up to next power of 2. + static std::size_t RoundBuckets(std::size_t from) { + --from; + from |= from >> 1; + from |= from >> 2; + from |= from >> 4; + from |= from >> 8; + from |= from >> 16; + from |= from >> 32; + return from + 1; + } + + template <class It> It Ideal(It begin, uint64_t hash) const { + return begin + (hash & mask_); + } + + template <class BaseIt, class OutIt> void Next(BaseIt begin, BaseIt /*end*/, OutIt &it) const { + it = begin + ((it - begin + 1) & mask_); + } + + void Double() { + mask_ = (mask_ << 1) | 1; + } + + private: + std::size_t mask_; +}; + template <class EntryT, class HashT, class EqualT> class AutoProbing; /* Non-standard hash table @@ -36,7 +95,7 @@ template <class EntryT, class HashT, class EqualT> class AutoProbing; * Uses linear probing to find value. * Only insert and lookup operations. */ -template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key> > class ProbingHashTable { +template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key>, class ModT = DivMod> class ProbingHashTable { public: typedef EntryT Entry; typedef typename Entry::Key Key; @@ -44,14 +103,15 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry typedef Entry *MutableIterator; typedef HashT Hash; typedef EqualT Equal; + typedef ModT Mod; static uint64_t Size(uint64_t entries, float multiplier) { - uint64_t buckets = std::max(entries + 1, static_cast<uint64_t>(multiplier * static_cast<float>(entries))); + uint64_t buckets = Mod::RoundBuckets(std::max(entries + 1, static_cast<uint64_t>(multiplier * static_cast<float>(entries)))); return buckets * sizeof(Entry); } // Must be assigned to later. - ProbingHashTable() : entries_(0) + ProbingHashTable() : mod_(1), entries_(0) #ifdef DEBUG , initialized_(false) #endif @@ -59,11 +119,12 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry ProbingHashTable(void *start, std::size_t allocated, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal()) : begin_(reinterpret_cast<MutableIterator>(start)), - buckets_(allocated / sizeof(Entry)), - end_(begin_ + buckets_), + end_(begin_ + allocated / sizeof(Entry)), + buckets_(end_ - begin_), invalid_(invalid), hash_(hash_func), equal_(equal_func), + mod_(end_ - begin_), entries_(0) #ifdef DEBUG , initialized_(true) @@ -75,6 +136,13 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry end_ = begin_ + buckets_; } + MutableIterator Ideal(const Key key) { + return mod_.Ideal(begin_, hash_(key)); + } + ConstIterator Ideal(const Key key) const { + return mod_.Ideal(begin_, hash_(key)); + } + template <class T> MutableIterator Insert(const T &t) { #ifdef DEBUG assert(initialized_); @@ -83,12 +151,12 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry return UncheckedInsert(t); } - // Return true if the value was found (and not inserted). This is consistent with Find but the opposite if hash_map! + // Return true if the value was found (and not inserted). This is consistent with Find but the opposite of hash_map! template <class T> bool FindOrInsert(const T &t, MutableIterator &out) { #ifdef DEBUG assert(initialized_); #endif - for (MutableIterator i = Ideal(t.GetKey());;) { + for (MutableIterator i = Ideal(t.GetKey());;mod_.Next(begin_, end_, i)) { Key got(i->GetKey()); if (equal_(got, t.GetKey())) { out = i; return true; } if (equal_(got, invalid_)) { @@ -97,7 +165,6 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry out = i; return false; } - if (++i == end_) i = begin_; } } @@ -108,44 +175,45 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry #ifdef DEBUG assert(initialized_); #endif - for (MutableIterator i(Ideal(key));;) { + for (MutableIterator i(Ideal(key));; mod_.Next(begin_, end_, i)) { Key got(i->GetKey()); if (equal_(got, key)) { out = i; return true; } if (equal_(got, invalid_)) return false; - if (++i == end_) i = begin_; } } // Like UnsafeMutableFind, but the key must be there. template <class Key> MutableIterator UnsafeMutableMustFind(const Key key) { - for (MutableIterator i(Ideal(key));;) { + for (MutableIterator i(Ideal(key));; mod_.Next(begin_, end_, i)) { Key got(i->GetKey()); if (equal_(got, key)) { return i; } assert(!equal_(got, invalid_)); - if (++i == end_) i = begin_; } } - - template <class Key> bool Find(const Key key, ConstIterator &out) const { + // Iterator is both input and output. + template <class Key> bool FindFromIdeal(const Key key, ConstIterator &i) const { #ifdef DEBUG assert(initialized_); #endif - for (ConstIterator i(Ideal(key));;) { + for (;; mod_.Next(begin_, end_, i)) { Key got(i->GetKey()); - if (equal_(got, key)) { out = i; return true; } + if (equal_(got, key)) return true; if (equal_(got, invalid_)) return false; - if (++i == end_) i = begin_; } } + template <class Key> bool Find(const Key key, ConstIterator &out) const { + out = Ideal(key); + return FindFromIdeal(key, out); + } + // Like Find but we're sure it must be there. template <class Key> ConstIterator MustFind(const Key key) const { - for (ConstIterator i(Ideal(key));;) { + for (ConstIterator i(Ideal(key));; mod_.Next(begin_, end_, i)) { Key got(i->GetKey()); if (equal_(got, key)) { return i; } assert(!equal_(got, invalid_)); - if (++i == end_) i = begin_; } } @@ -174,6 +242,7 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry MutableIterator old_end = begin_ + buckets_; buckets_ *= 2; end_ = begin_ + buckets_; + mod_.Double(); if (clear_new) { Entry invalid; invalid.SetKey(invalid_); @@ -230,26 +299,20 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry private: friend class AutoProbing<Entry, Hash, Equal>; - MutableIterator Ideal(const Key key) { - return begin_ + (hash_(key) % buckets_); - } - ConstIterator Ideal(const Key key) const { - return begin_ + (hash_(key) % buckets_); - } - template <class T> MutableIterator UncheckedInsert(const T &t) { - for (MutableIterator i(Ideal(t.GetKey()));;) { + for (MutableIterator i(Ideal(t.GetKey()));; mod_.Next(begin_, end_, i)) { if (equal_(i->GetKey(), invalid_)) { *i = t; return i; } - if (++i == end_) { i = begin_; } } } MutableIterator begin_; - std::size_t buckets_; MutableIterator end_; + std::size_t buckets_; Key invalid_; Hash hash_; Equal equal_; + Mod mod_; + std::size_t entries_; #ifdef DEBUG bool initialized_; @@ -259,7 +322,7 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry // Resizable linear probing hash table. This owns the memory. template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key> > class AutoProbing { private: - typedef ProbingHashTable<EntryT, HashT, EqualT> Backend; + typedef ProbingHashTable<EntryT, HashT, EqualT, Power2Mod> Backend; public: static std::size_t MemUsage(std::size_t size, float multiplier = 1.5) { return Backend::Size(size, multiplier); @@ -272,7 +335,7 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry typedef HashT Hash; typedef EqualT Equal; - AutoProbing(std::size_t initial_size = 10, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal()) : + AutoProbing(std::size_t initial_size = 5, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal()) : allocated_(Backend::Size(initial_size, 1.5)), mem_(util::MallocOrThrow(allocated_)), backend_(mem_.get(), allocated_, invalid, hash_func, equal_func) { threshold_ = initial_size * 1.2; Clear(); |