summaryrefslogtreecommitdiff
path: root/klm/util/probing_hash_table.hh
diff options
context:
space:
mode:
authorKenneth Heafield <github@kheafield.com>2013-06-18 11:34:20 -0700
committerKenneth Heafield <github@kheafield.com>2013-06-18 11:34:20 -0700
commit8dc383a74c12d44ab3f51947575ed5828653f4f1 (patch)
tree30371d17e6c2daf3837068b2617e357ad6b37d89 /klm/util/probing_hash_table.hh
parent354787aa16539702802b9ea075c4bd8a72071035 (diff)
lazy dd880b4 including kenlm 6eef0f1
Diffstat (limited to 'klm/util/probing_hash_table.hh')
-rw-r--r--klm/util/probing_hash_table.hh23
1 files changed, 22 insertions, 1 deletions
diff --git a/klm/util/probing_hash_table.hh b/klm/util/probing_hash_table.hh
index 57866ff9..51a2944d 100644
--- a/klm/util/probing_hash_table.hh
+++ b/klm/util/probing_hash_table.hh
@@ -109,9 +109,20 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
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(begin_ + (hash_(key) % buckets_));;) {
+ 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 {
#ifdef DEBUG
assert(initialized_);
@@ -124,6 +135,16 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
}
}
+ // Like Find but we're sure it must be there.
+ template <class Key> ConstIterator MustFind(const Key key) const {
+ for (ConstIterator i(begin_ + (hash_(key) % buckets_));;) {
+ Key got(i->GetKey());
+ if (equal_(got, key)) { return i; }
+ assert(!equal_(got, invalid_));
+ if (++i == end_) i = begin_;
+ }
+ }
+
void Clear() {
Entry invalid;
invalid.SetKey(invalid_);