diff options
author | Patrick Simianer <simianer@cl.uni-heidelberg.de> | 2012-05-31 13:57:24 +0200 |
---|---|---|
committer | Patrick Simianer <simianer@cl.uni-heidelberg.de> | 2012-05-31 13:57:24 +0200 |
commit | 6f6601111710aa67eee5169e5b7d89102cc33bb8 (patch) | |
tree | 0872544abd6bc76162f3f80eb3920999afbf2c34 /klm/util/probing_hash_table.hh | |
parent | 8cee8b565a9c56a7732365e9563f52ff3c4ff7fd (diff) | |
parent | 090a64e73f94a6a35e5364a9d416dcf75c0a2938 (diff) |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'klm/util/probing_hash_table.hh')
-rw-r--r-- | klm/util/probing_hash_table.hh | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/klm/util/probing_hash_table.hh b/klm/util/probing_hash_table.hh index f466cebc..3354b68e 100644 --- a/klm/util/probing_hash_table.hh +++ b/klm/util/probing_hash_table.hh @@ -78,12 +78,33 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry } } + // Return true if the value was found (and not inserted). This is consistent with Find but the opposite if hash_map! + template <class T> bool FindOrInsert(const T &t, MutableIterator &out) { +#ifdef DEBUG + assert(initialized_); +#endif + for (MutableIterator i(begin_ + (hash_(t.GetKey()) % buckets_));;) { + Key got(i->GetKey()); + if (equal_(got, t.GetKey())) { out = i; return true; } + if (equal_(got, invalid_)) { + UTIL_THROW_IF(++entries_ >= buckets_, ProbingSizeException, "Hash table with " << buckets_ << " buckets is full."); + *i = t; + out = i; + return false; + } + if (++i == end_) i = begin_; + } + } + void FinishedInserting() {} void LoadedBinary() {} // Don't change anything related to GetKey, template <class Key> bool UnsafeMutableFind(const Key key, MutableIterator &out) { +#ifdef DEBUG + assert(initialized_); +#endif for (MutableIterator i(begin_ + (hash_(key) % buckets_));;) { Key got(i->GetKey()); if (equal_(got, key)) { out = i; return true; } |