Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/moses-smt/mosesdecoder.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/util/probing_hash_table.hh
diff options
context:
space:
mode:
Diffstat (limited to 'util/probing_hash_table.hh')
-rw-r--r--util/probing_hash_table.hh125
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();
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-01 04:31:13 +0300