(Concept patch) Simplify WTF::HashTable::add() return value for size and performance

Source/wtf/HashTable.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008 David Levin <levin@chromium.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 188 matching lines @@
     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } };
     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
 
     template<typename HashFunctions> class IdentityHashTranslator {
     public:
         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
         template<typename T, typename U> static void translate(T& location, const U&, const T& value) { location = value; }
     };
 
-    template<typename IteratorType> struct HashTableAddResult {
-        HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { }
-        IteratorType iterator;
+    template<typename ValueType> struct HashTableAddResult {
+        HashTableAddResult(ValueType* iterator, bool isNewEntry) : iterator(iterator), isNewEntry(isNewEntry) { }

[Erik Corry, 2014/02/04 14:27:15]

If this is no longer an iterator, should it be called 'iterator'?

[eseidel, 2014/02/05 22:17:20]

No. :)  But presumably Daniel did this to minimize changes?  I would call this
value or addedValue or something.

+        ValueType* iterator;
         bool isNewEntry;
     };
 
     template<typename Value, typename Extractor, typename KeyTraits>
     struct HashTableHelper {
         static bool isEmptyBucket(const Value& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
         static bool isDeletedBucket(const Value& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
         static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
     };
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTable {
     public:
         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
         typedef Traits ValueTraits;
         typedef Key KeyType;
         typedef typename KeyTraits::PeekInType KeyPeekInType;
         typedef typename KeyTraits::PassInType KeyPassInType;
         typedef Value ValueType;
         typedef typename Traits::PeekInType ValuePeekInType;
         typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
-        typedef HashTableAddResult<iterator> AddResult;
+        typedef HashTableAddResult<ValueType> AddResult;
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         struct Stats {
             Stats()
                 : numAccesses(0)
                 , numRehashes(0)
                 , numRemoves(0)
                 , numReinserts(0)
                 , maxCollisions(0)
                 , numCollisions(0)
@@ skipping 436 matching lines @@
         ValueType* entry;
         while (1) {
             entry = table + i;
 
             // we count on the compiler to optimize out this branch
             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                 if (isEmptyBucket(*entry))
                     break;
 
                 if (HashTranslator::equal(Extractor::extract(*entry), key))
-                    return AddResult(makeKnownGoodIterator(entry), false);
+                    return AddResult(entry, false);
 
                 if (isDeletedBucket(*entry))
                     deletedEntry = entry;
             } else {
                 if (isEmptyBucket(*entry))
                     break;
 
                 if (isDeletedBucket(*entry))
                     deletedEntry = entry;
                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
-                    return AddResult(makeKnownGoodIterator(entry), false);
+                    return AddResult(entry, false);
             }
 #if DUMP_HASHTABLE_STATS
             ++probeCount;
             HashTableStats::recordCollisionAtCount(probeCount);
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
             ++perTableProbeCount;
             m_stats->recordCollisionAtCount(perTableProbeCount);
 #endif
@@ skipping 12 matching lines @@
         HashTranslator::translate(*entry, key, extra);
 
         ++m_keyCount;
 
         if (shouldExpand()) {
             // FIXME: This makes an extra copy on expand. Probably not that bad since
             // expand is rare, but would be better to have a version of expand that can
             // follow a pivot entry and return the new position.
             typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extractor::extract(*entry);
             expand();
-            AddResult result(find(enteredKey), true);
-            ASSERT(result.iterator != end());
+            iterator findResult = find(enteredKey);
+            ASSERT(findResult != end());
+            ValueType* resultValue = findResult.get();
+            AddResult result(resultValue, true);
             return result;
         }
 
-        return AddResult(makeKnownGoodIterator(entry), true);
+        return AddResult(entry, true);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T, typename Extra>
     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
     {
         if (!m_table)
             expand();
 
         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
 
         ValueType* entry = lookupResult.first.first;
         bool found = lookupResult.first.second;
         unsigned h = lookupResult.second;
 
         if (found)
-            return AddResult(makeKnownGoodIterator(entry), false);
+            return AddResult(entry, false);
 
         if (isDeletedBucket(*entry)) {
             initializeBucket(*entry);
             --m_deletedCount;
         }
 
         HashTranslator::translate(*entry, key, extra, h);
         ++m_keyCount;
         if (shouldExpand()) {
             // FIXME: This makes an extra copy on expand. Probably not that bad since
             // expand is rare, but would be better to have a version of expand that can
             // follow a pivot entry and return the new position.
             typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extractor::extract(*entry);
             expand();
-            AddResult result(find(enteredKey), true);
-            ASSERT(result.iterator != end());
+            iterator findResult = find(enteredKey);
+            ASSERT(findResult != end());
+            ValueType* resultValue = findResult.get();
+            AddResult result(resultValue, true);
             return result;
         }
 
-        return AddResult(makeKnownGoodIterator(entry), true);
+        return AddResult(entry, true);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::reinsert(ValueType& entry)
     {
         ASSERT(m_table);
         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numReinserts);
@@ skipping 373 matching lines @@
     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
 } // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif // WTF_HashTable_h