Save 100-300 KB footprint by not force inlining HashTable functions

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 51 matching lines @@
     ++m_stats->numAccesses;                              \
     int perTableProbeCount = 0
 #else
 #define UPDATE_PROBE_COUNTS() do { } while (0)
 #define UPDATE_ACCESS_COUNTS() do { } while (0)
 #endif
 #endif
 
 namespace WTF {
 
+// Custom secondary hash function.
+unsigned doubleHash(unsigned key);
+
 #if DUMP_HASHTABLE_STATS
 
     struct HashTableStats {
         // The following variables are all atomically incremented when modified.
         static int numAccesses;
         static int numRehashes;
         static int numRemoves;
         static int numReinserts;
 
         // The following variables are only modified in the recordCollisionAtCount method within a mutex.
@@ skipping 157 matching lines @@
 
         operator const_iterator() const { return m_iterator; }
 
     private:
         const_iterator m_iterator;
     };
 
     using std::swap;
 
     // Work around MSVC's standard library, whose swap for pairs does not swap by component.
-    template<typename T> inline void hashTableSwap(T& a, T& b)
+    template<typename T> void hashTableSwap(T& a, T& b)
     {
         swap(a, b);
     }
 
-    template<typename T, typename U> inline void hashTableSwap(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b)
+    template<typename T, typename U> void hashTableSwap(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b)
     {
         swap(a.key, b.key);
         swap(a.value, b.value);
     }
 
     template<typename T, typename Allocator, bool useSwap> struct Mover;
     template<typename T, typename Allocator> struct Mover<T, Allocator, true> {
         static void move(T& from, T& to)
         {
             // A swap operation should not normally allocate, but it may do so
@@ skipping 334 matching lines @@
     // This is done at compile time to initialize the HashTraits.
     template<unsigned size>
     struct HashTableCapacityForSize {
         static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
         COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
         COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
     };
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
-    inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
+    HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
         : m_table(0)
         , m_tableSize(0)
         , m_keyCount(0)
         , m_deletedCount(0)
         , m_queueFlag(false)
 #if ENABLE(ASSERT)
         , m_modifications(0)
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         , m_stats(adoptPtr(new Stats))
 #endif
     {
     }
 
-    inline unsigned doubleHash(unsigned key)
-    {
-        key = ~key + (key >> 23);
-        key ^= (key << 12);
-        key ^= (key >> 7);
-        key ^= (key << 2);
-        key ^= (key >> 20);
-        return key;
-    }
-
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
-    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
+    Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
     {
         return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator, T>(key));
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
-    inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
+    const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
     {
         ASSERT((HashTableKeyChecker<HashTranslator, KeyTraits, HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key)));
         const ValueType* table = m_table;
         if (!table)
             return 0;
 
         size_t k = 0;
         size_t sizeMask = tableSizeMask();
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
@@ skipping 18 matching lines @@
             }
             UPDATE_PROBE_COUNTS();
             if (!k)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
     {
         ASSERT(m_table);
         registerModification();
 
         ValueType* table = m_table;
         size_t k = 0;
         size_t sizeMask = tableSizeMask();
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
@@ skipping 21 matching lines @@
             }
             UPDATE_PROBE_COUNTS();
             if (!k)
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
     {
         ASSERT(m_table);
         registerModification();
 
         ValueType* table = m_table;
         size_t k = 0;
         size_t sizeMask = tableSizeMask();
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
@@ skipping 39 matching lines @@
         template<typename Traits, typename Value> static void initialize(Value& bucket)
         {
             // This initializes the bucket without copying the empty value.
             // That makes it possible to use this with types that don't support copying.
             // The memset to 0 looks like a slow operation but is optimized by the compilers.
             memset(&bucket, 0, sizeof(bucket));
         }
     };
 
     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>::initializeBucket(ValueType& bucket)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
     {
         // For hash maps the key and value cannot be initialied simultaneously,
         // and it would be wrong to have a GC when only one was initialized and
         // the other still contained garbage (eg. from a previous use of the
         // same slot). Therefore we forbid allocation (and thus GC) while the
         // slot is initalized to an empty value.
         Allocator::enterNoAllocationScope();
         HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
         Allocator::leaveNoAllocationScope();
     }
@@ skipping 111 matching lines @@
         ++m_stats->numReinserts;
 #endif
         Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
         Mover<ValueType, Allocator, Traits::needsDestruction>::move(entry, *newEntry);
 
         return newEntry;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template <typename HashTranslator, typename T>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key)
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key)
     {
         ValueType* entry = lookup<HashTranslator>(key);
         if (!entry)
             return end();
 
         return makeKnownGoodIterator(entry);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template <typename HashTranslator, typename T>
-    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key) const
+    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key) const
     {
         ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
         if (!entry)
             return end();
 
         return makeKnownGoodConstIterator(entry);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template <typename HashTranslator, typename T>
@@ skipping 15 matching lines @@
 
         deleteBucket(*pos);
         ++m_deletedCount;
         --m_keyCount;
 
         if (shouldShrink())
             shrink();
     }
 
     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>::remove(iterator it)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(iterator it)
     {
         if (it == end())
             return;
 
         remove(const_cast<ValueType*>(it.m_iterator.m_position));
     }
 
     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>::remove(const_iterator it)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(const_iterator it)
     {
         if (it == end())
             return;
 
         remove(const_cast<ValueType*>(it.m_position));
     }
 
     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>::remove(KeyPeekInType key)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(KeyPeekInType key)
     {
         remove(find(key));
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::allocateTable(unsigned size)
     {
         typedef typename Allocator::template HashTableBackingHelper<HashTable>::Type HashTableBacking;
 
         size_t allocSize = size * sizeof(ValueType);
@@ skipping 324 matching lines @@
         operator HashTableConstIteratorAdapter<HashTableType, Traits>()
         {
             typename HashTableType::const_iterator i = m_impl;
             return i;
         }
 
         typename HashTableType::iterator m_impl;
     };
 
     template<typename T, typename U>
-    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl == b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     {
         return a.m_impl == b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
     // All 4 combinations of ==, != and Const,non const.
     template<typename T, typename U>
-    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     {
         return a.m_impl == b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+    bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl == b.m_impl;
     }
 
     template<typename T, typename U>
-    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+    bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
     template<typename Collection1, typename Collection2>
-    inline void removeAll(Collection1& collection, const Collection2& toBeRemoved)
+    void removeAll(Collection1& collection, const Collection2& toBeRemoved)
     {
         if (collection.isEmpty() || toBeRemoved.isEmpty())
             return;
         typedef typename Collection2::const_iterator CollectionIterator;
         CollectionIterator end(toBeRemoved.end());
         for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
             collection.remove(*it);
     }
 
 } // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif // WTF_HashTable_h