AK: Allow HashMap to be used with non-default-constructible values.

Solve this by adding find() overloads to HashTable and SinglyLinkedList
that take a templated functor for comparing the values.

This allows HashMap to call HashTable::find() without having to create
a temporary Entry for use as the table key. :^)

3 files changed, 67 insertions, 51 deletions

diff --git a/AK/HashMap.h b/AK/HashMap.h
index d6fed82763..208bc18c49 100644
--- a/AK/HashMap.h
+++ b/AK/HashMap.h
@@ -37,7 +37,12 @@ public:
 
     void set(const K& key, const V& value) { m_table.set({ key, value }); }
     void set(const K& key, V&& value) { m_table.set({ key, move(value) }); }
-    void remove(const K& key) { m_table.remove({ key, V() }); }
+    void remove(const K& key)
+    {
+        auto it = find(key);
+        if (it != end())
+            m_table.remove(it);
+    }
     void remove_one_randomly() { m_table.remove(m_table.begin()); }
 
     typedef HashTable<Entry, EntryTraits> HashTableType;
@@ -46,11 +51,11 @@ public:
 
     IteratorType begin() { return m_table.begin(); }
     IteratorType end() { return m_table.end(); }
-    IteratorType find(const K& key) { return m_table.find({ key, V() }); }
+    IteratorType find(const K& key) { return m_table.find(Traits<K>::hash(key), [&](auto& entry) { return key == entry.key; }); }
 
     ConstIteratorType begin() const { return m_table.begin(); }
     ConstIteratorType end() const { return m_table.end(); }
-    ConstIteratorType find(const K& key) const { return m_table.find({ key, V() }); }
+    ConstIteratorType find(const K& key) const { return m_table.find(Traits<K>::hash(key), [&](auto& entry) { return key == entry.key; }); }
 
     void ensure_capacity(int capacity) { m_table.ensure_capacity(capacity); }
 
diff --git a/AK/HashTable.h b/AK/HashTable.h
index 0e10730e6a..185f9cc7c9 100644
--- a/AK/HashTable.h
+++ b/AK/HashTable.h
@@ -146,8 +146,42 @@ public:
     ConstIterator begin() const { return ConstIterator(*this, is_empty()); }
     ConstIterator end() const { return ConstIterator(*this, true); }
 
-    Iterator find(const T&);
-    ConstIterator find(const T&) const;
+
+    template<typename Finder>
+    Iterator find(unsigned hash, Finder finder)
+    {
+        if (is_empty())
+            return end();
+        int bucket_index;
+        auto& bucket = lookup_with_hash(hash, &bucket_index);
+        auto bucket_iterator = bucket.find(finder);
+        if (bucket_iterator != bucket.end())
+            return Iterator(*this, false, bucket_iterator, bucket_index);
+        return end();
+    }
+
+    template<typename Finder>
+    ConstIterator find(unsigned hash, Finder finder) const
+    {
+        if (is_empty())
+            return end();
+        int bucket_index;
+        auto& bucket = lookup_with_hash(hash, &bucket_index);
+        auto bucket_iterator = bucket.find(finder);
+        if (bucket_iterator != bucket.end())
+            return ConstIterator(*this, false, bucket_iterator, bucket_index);
+        return end();
+    }
+
+    Iterator find(const T& value)
+    {
+        return find(TraitsForT::hash(value), [&](auto& other) { return TraitsForT::equals(value, other); });
+    }
+
+    ConstIterator find(const T& value) const
+    {
+        return find(TraitsForT::hash(value), [&](auto& other) { return TraitsForT::equals(value, other); });
+    }
 
     void remove(const T& value)
     {
@@ -161,6 +195,21 @@ public:
 private:
     Bucket& lookup(const T&, int* bucket_index = nullptr);
     const Bucket& lookup(const T&, int* bucket_index = nullptr) const;
+
+    Bucket& lookup_with_hash(unsigned hash, int* bucket_index)
+    {
+        if (bucket_index)
+            *bucket_index = hash % m_capacity;
+        return m_buckets[hash % m_capacity];
+    }
+
+    const Bucket& lookup_with_hash(unsigned hash, int* bucket_index) const
+    {
+        if (bucket_index)
+            *bucket_index = hash % m_capacity;
+        return m_buckets[hash % m_capacity];
+    }
+
     void rehash(int capacity);
     void insert(const T&);
     void insert(T&&);
@@ -274,32 +323,6 @@ bool HashTable<T, TraitsForT>::contains(const T& value) const
 }
 
 template<typename T, typename TraitsForT>
-auto HashTable<T, TraitsForT>::find(const T& value) -> Iterator
-{
-    if (is_empty())
-        return end();
-    int bucket_index;
-    auto& bucket = lookup(value, &bucket_index);
-    auto bucket_iterator = bucket.template find<TraitsForT>(value);
-    if (bucket_iterator != bucket.end())
-        return Iterator(*this, false, bucket_iterator, bucket_index);
-    return end();
-}
-
-template<typename T, typename TraitsForT>
-auto HashTable<T, TraitsForT>::find(const T& value) const -> ConstIterator
-{
-    if (is_empty())
-        return end();
-    int bucket_index;
-    const auto& bucket = lookup(value, &bucket_index);
-    auto bucket_iterator = bucket.template find<TraitsForT>(value);
-    if (bucket_iterator != bucket.end())
-        return ConstIterator(*this, false, bucket_iterator, bucket_index);
-    return end();
-}
-
-template<typename T, typename TraitsForT>
 void HashTable<T, TraitsForT>::remove(Iterator it)
 {
     ASSERT(!is_empty());
diff --git a/AK/SinglyLinkedList.h b/AK/SinglyLinkedList.h
index 59b2f1665a..1760cdbb81 100644
--- a/AK/SinglyLinkedList.h
+++ b/AK/SinglyLinkedList.h
@@ -147,50 +147,38 @@ public:
     ConstIterator begin() const { return ConstIterator(m_head); }
     ConstIterator end() const { return ConstIterator::universal_end(); }
 
-    ConstIterator find(const T& value) const
+    template<typename Finder>
+    ConstIterator find(Finder finder) const
     {
         Node* prev = nullptr;
         for (auto* node = m_head; node; node = node->next) {
-            if (node->value == value)
+            if (finder(node->value))
                 return ConstIterator(node, prev);
             prev = node;
         }
         return end();
     }
 
-    Iterator find(const T& value)
+    template<typename Finder>
+    Iterator find(Finder finder)
     {
         Node* prev = nullptr;
         for (auto* node = m_head; node; node = node->next) {
-            if (node->value == value)
+            if (finder(node->value))
                 return Iterator(node, prev);
             prev = node;
         }
         return end();
     }
 
-    template<typename Traits>
     ConstIterator find(const T& value) const
     {
-        Node* prev = nullptr;
-        for (auto* node = m_head; node; node = node->next) {
-            if (Traits::equals(node->value, value))
-                return ConstIterator(node, prev);
-            prev = node;
-        }
-        return end();
+        return find([&](auto& other) { return value == other; });
     }
 
-    template<typename Traits>
     Iterator find(const T& value)
     {
-        Node* prev = nullptr;
-        for (auto* node = m_head; node; node = node->next) {
-            if (Traits::equals(node->value, value))
-                return Iterator(node, prev);
-            prev = node;
-        }
-        return end();
+        return find([&](auto& other) { return value == other; });
     }
 
     void remove(Iterator iterator)