Add a force_insert method to the hash_table. It is faster as it skips the presence check and avoid equality compare.

It allows duplicates and should hence be used carefully.
At least resize will be faster as it it can safely be used there.

3 files changed, 71 insertions, 3 deletions

diff --git a/vespalib/src/tests/stllike/hashtable_test.cpp b/vespalib/src/tests/stllike/hashtable_test.cpp
index 877a5dddcb5..99884c78dfb 100644
--- a/vespalib/src/tests/stllike/hashtable_test.cpp
+++ b/vespalib/src/tests/stllike/hashtable_test.cpp
@@ -73,6 +73,48 @@ TEST("require that hashtable<int> can be copied") {
     EXPECT_EQUAL(42, *table2.find(42));
 }
 
+TEST("require that you can insert duplicates") {
+    using Pair = std::pair<int, vespalib::string>;
+    using Map = hashtable<int, Pair, vespalib::hash<int>, std::equal_to<int>, First<int, Pair>>;
+
+    Map m(1);
+    EXPECT_EQUAL(0u, m.size());
+    EXPECT_EQUAL(8u, m.capacity());
+    auto res = m.insert(Pair(1, "1"));
+    EXPECT_TRUE(res.second);
+    EXPECT_EQUAL(1u, m.size());
+    EXPECT_EQUAL(8u, m.capacity());
+    res = m.insert(Pair(1, "1.2"));
+    EXPECT_FALSE(res.second);
+    auto found = m.find(1);
+    ASSERT_TRUE(found != m.end());
+    EXPECT_EQUAL(found->second, "1");
+
+    m.force_insert(Pair(1, "1.2"));
+    EXPECT_EQUAL(2u, m.size());
+    EXPECT_EQUAL(8u, m.capacity());
+    m.force_insert(Pair(1, "1.3"));
+    EXPECT_EQUAL(3u, m.size());
+    EXPECT_EQUAL(16u, m.capacity());
+    found = m.find(1);
+    ASSERT_TRUE(found != m.end());
+    EXPECT_EQUAL(found->second, "1");
+
+    m.erase(1);
+    EXPECT_EQUAL(2u, m.size());
+    EXPECT_EQUAL(16u, m.capacity());
+    found = m.find(1);
+    ASSERT_TRUE(found != m.end());
+    EXPECT_EQUAL(found->second, "1.3");
+
+    m.erase(1);
+    EXPECT_EQUAL(1u, m.size());
+    EXPECT_EQUAL(16u, m.capacity());
+    found = m.find(1);
+    ASSERT_TRUE(found != m.end());
+    EXPECT_EQUAL(found->second, "1.2");
+}
+
 template<typename To, typename Vector>
 struct FirstInVector : std::unary_function<To, Vector> {
     To &operator()(Vector& v) const { return v[0]; }
diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h
index eb01a91c308..8c9d36e86ad 100644
--- a/vespalib/src/vespa/vespalib/stllike/hashtable.h
+++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h
@@ -246,6 +246,9 @@ public:
     insert_result insert(V && node) {
         return insertInternal(std::forward<V>(node));
     }
+    // This will insert unconditionally, without checking presence, and might cause duplicates.
+    // Use at you own risk.
+    void force_insert(Value && value);
     
     /// This gives faster iteration than can be achieved by the iterators.
     template <typename Func>
@@ -274,10 +277,10 @@ public:
     size_t getMemoryUsed() const;
 
 protected:
-    /// These two methods are only for the ones that know what they are doing.
-    /// valid input here are stuff returned from iterator.getInternalIndex.
     template <typename V>
     insert_result insertInternal(V && node);
+    /// These two methods are only for the ones that know what they are doing.
+    /// valid input here are stuff returned from iterator.getInternalIndex.
     Value & getByInternalIndex(size_t index)             { return _nodes[index].getValue(); }
     const Value & getByInternalIndex(size_t index) const { return _nodes[index].getValue(); }
     template <typename MoveHandler>
diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
index 57f05ca6542..15510d608da 100644
--- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
+++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
@@ -180,6 +180,29 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && n
     }
 }
 
+
+template <typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator>
+void
+hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::force_insert(Value && value)
+{
+    const next_t h = hash(_keyExtractor(value));
+    if ( ! _nodes[h].valid() ) {
+        _nodes[h] = std::move(value);
+        _count++;
+    } else {
+        if (_nodes.size() < _nodes.capacity()) {
+            const next_t p(_nodes[h].getNext());
+            const next_t newIdx(_nodes.size());
+            _nodes[h].setNext(newIdx);
+            new (_nodes.push_back_fast()) Node(std::move(value), p);
+            _count++;
+        } else {
+            resize(_nodes.capacity()*2);
+            force_insert(std::move(value));
+        }
+    }
+}
+
 template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator >
 template<typename MoveHandler>
 void
@@ -261,7 +284,7 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::move(NodeStore && old
 {
     for (auto & entry : oldStore) {
         if (entry.valid()) {
-            insert(std::move(entry.getValue()));
+            force_insert(std::move(entry.getValue()));
         }
     }
 }