Make sure all destructors are called in HeapHashMap and HeapHashSet

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 223 matching lines @@
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTable : public HashTableDestructorBase<HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>, Allocator::isGarbageCollected> {
     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 Extractor ExtractorType;
+        typedef KeyTraits KeyTraitsType;
         typedef typename Traits::PeekInType ValuePeekInType;
         typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
         typedef HashTableAddResult<ValueType> AddResult;
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         struct Stats {
             Stats()
                 : numAccesses(0)
                 , numRehashes(0)
                 , numRemoves(0)
@@ skipping 35 matching lines @@
             }
         };
 #endif
 
         HashTable();
         void finalize()
         {
             ASSERT(!Allocator::isGarbageCollected);
             if (LIKELY(!m_table))
                 return;
-            deallocateTable(m_table, m_tableSize);
+            deleteAllBucketsAndDeallocate(m_table, m_tableSize);
             m_table = 0;
         }
 
         HashTable(const HashTable&);
         void swap(HashTable&);
         HashTable& operator=(const HashTable&);
 
         // When the hash table is empty, just return the same iterator for end as for begin.
         // This is more efficient because we don't have to skip all the empty and deleted
         // buckets, and iterating an empty table is a common case that's worth optimizing.
@@ skipping 34 matching lines @@
         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
         static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
 
         ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType>(key); }
         template<typename HashTranslator, typename T> ValueType* lookup(const T&);
 
         void trace(typename Allocator::Visitor*);
 
     private:
         static ValueType* allocateTable(unsigned size);
-        static void deallocateTable(ValueType* table, unsigned size);
+        static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size);
 
         typedef std::pair<ValueType*, bool> LookupType;
         typedef std::pair<LookupType, unsigned> FullLookupType;
 
         LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
         template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
         template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
 
         void remove(ValueType*);
 
@@ skipping 512 matching lines @@
 
     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)
     {
         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<Key, Value, Extractor, Traits, KeyTraits>::Type HashTableBacking;
+        typedef typename Allocator::template HashTableBackingHelper<HashTable>::Type HashTableBacking;
 
         size_t allocSize = size * sizeof(ValueType);
         ValueType* result;
         if (Traits::emptyValueIsZero) {
             result = Allocator::template zeroedBackingMalloc<ValueType*, HashTableBacking>(allocSize);
         } else {
             result = Allocator::template backingMalloc<ValueType*, HashTableBacking>(allocSize);
             for (unsigned i = 0; i < size; i++)
                 initializeBucket(result[i]);
         }
         return result;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
-    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::deallocateTable(ValueType* table, unsigned size)
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::deleteAllBucketsAndDeallocate(ValueType* table, unsigned size)
     {
-        if (Allocator::isGarbageCollected)
-            return;
         if (Traits::needsDestruction) {
             for (unsigned i = 0; i < size; ++i) {
-                if (!isDeletedBucket(table[i]))
-                    table[i].~ValueType();
+                // This code is called when the hash table is cleared or
+                // resized. We have allocated a new backing store and we need
+                // to run the destructors on the old backing store, as it is
+                // being freed. If we are GCing we need to both call the
+                // destructor and mark the bucket as deleted, otherwise the
+                // destructor gets called again when the GC finds the backing
+                // store. With the default allocator it's enough to call the
+                // destructor, since we will free the memory explicitly and
+                // we won't see the memory with the bucket again.
+                if (!isEmptyOrDeletedBucket(table[i])) {
+                    if (Allocator::isGarbageCollected)
+                        deleteBucket(table[i]);
+                    else
+                        table[i].~ValueType();
+                }
             }
         }
         Allocator::backingFree(table);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::expand()
     {
         unsigned newSize;
         if (!m_tableSize) {
@@ skipping 27 matching lines @@
         m_table = allocateTable(newTableSize);
         m_tableSize = newTableSize;
         m_tableSizeMask = newTableSize - 1;
 
         for (unsigned i = 0; i != oldTableSize; ++i)
             if (!isEmptyOrDeletedBucket(oldTable[i]))
                 reinsert(oldTable[i]);
 
         m_deletedCount = 0;
 
-        deallocateTable(oldTable, oldTableSize);
+        deleteAllBucketsAndDeallocate(oldTable, oldTableSize);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::clear()
     {
         if (!m_table)
             return;
 
-        deallocateTable(m_table, m_tableSize);
+        deleteAllBucketsAndDeallocate(m_table, m_tableSize);
         m_table = 0;
         m_tableSize = 0;
         m_tableSizeMask = 0;
         m_keyCount = 0;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable(const HashTable& other)
         : m_table(0)
         , m_tableSize(0)
@@ skipping 189 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