From 89238977fc9d8f8d9a6421b0d4f35afc200f08e7 Mon Sep 17 00:00:00 2001
From: Kenneth Heafield <kenlm@kheafield.com>
Date: Tue, 28 Feb 2012 17:23:55 -0500
Subject: Subject: where's my kenlm update?? From: Chris Dyer
 <cdyer@cs.cmu.edu>

---
 klm/util/probing_hash_table.hh | 33 +++++++++++++++++++--------------
 1 file changed, 19 insertions(+), 14 deletions(-)

(limited to 'klm/util/probing_hash_table.hh')

diff --git a/klm/util/probing_hash_table.hh b/klm/util/probing_hash_table.hh
index 8122d69c..f466cebc 100644
--- a/klm/util/probing_hash_table.hh
+++ b/klm/util/probing_hash_table.hh
@@ -18,27 +18,33 @@ class ProbingSizeException : public Exception {
     ~ProbingSizeException() throw() {}
 };
 
+// std::identity is an SGI extension :-(
+struct IdentityHash {
+  template <class T> T operator()(T arg) const { return arg; }
+};
+
 /* Non-standard hash table
  * Buckets must be set at the beginning and must be greater than maximum number
- * of elements, else an infinite loop happens.
+ * of elements, else it throws ProbingSizeException.
  * Memory management and initialization is externalized to make it easier to
  * serialize these to disk and load them quickly.
  * Uses linear probing to find value.
  * Only insert and lookup operations.  
  */
 
-template <class PackingT, class HashT, class EqualT = std::equal_to<typename PackingT::Key> > class ProbingHashTable {
+template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key> > class ProbingHashTable {
   public:
-    typedef PackingT Packing;
-    typedef typename Packing::Key Key;
-    typedef typename Packing::MutableIterator MutableIterator;
-    typedef typename Packing::ConstIterator ConstIterator;
-
+    typedef EntryT Entry;
+    typedef typename Entry::Key Key;
+    typedef const Entry *ConstIterator;
+    typedef Entry *MutableIterator;
     typedef HashT Hash;
     typedef EqualT Equal;
 
+  public:
     static std::size_t Size(std::size_t entries, float multiplier) {
-      return std::max(entries + 1, static_cast<std::size_t>(multiplier * static_cast<float>(entries))) * Packing::kBytes;
+      std::size_t buckets = std::max(entries + 1, static_cast<std::size_t>(multiplier * static_cast<float>(entries)));
+      return buckets * sizeof(Entry);
     }
 
     // Must be assigned to later.  
@@ -49,9 +55,9 @@ template <class PackingT, class HashT, class EqualT = std::equal_to<typename Pac
     {}
 
     ProbingHashTable(void *start, std::size_t allocated, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal())
-      : begin_(Packing::FromVoid(start)),
-        buckets_(allocated / Packing::kBytes),
-        end_(begin_ + (allocated / Packing::kBytes)),
+      : begin_(reinterpret_cast<MutableIterator>(start)),
+        buckets_(allocated / sizeof(Entry)),
+        end_(begin_ + buckets_),
         invalid_(invalid),
         hash_(hash_func),
         equal_(equal_func),
@@ -62,11 +68,10 @@ template <class PackingT, class HashT, class EqualT = std::equal_to<typename Pac
     {}
 
     template <class T> MutableIterator Insert(const T &t) {
-      if (++entries_ >= buckets_)
-        UTIL_THROW(ProbingSizeException, "Hash table with " << buckets_ << " buckets is full.");
 #ifdef DEBUG
       assert(initialized_);
 #endif
+      UTIL_THROW_IF(++entries_ >= buckets_, ProbingSizeException, "Hash table with " << buckets_ << " buckets is full.");
       for (MutableIterator i(begin_ + (hash_(t.GetKey()) % buckets_));;) {
         if (equal_(i->GetKey(), invalid_)) { *i = t; return i; }
         if (++i == end_) { i = begin_; }
@@ -84,7 +89,7 @@ template <class PackingT, class HashT, class EqualT = std::equal_to<typename Pac
         if (equal_(got, key)) { out = i; return true; }
         if (equal_(got, invalid_)) return false;
         if (++i == end_) i = begin_;
-      }    
+      }   
     }
 
     template <class Key> bool Find(const Key key, ConstIterator &out) const {
-- 
cgit v1.2.3