runtime/WeakGCMap.h

   1 /*
   2  * Copyright (C) 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef WeakGCMap_h
  27 #define WeakGCMap_h
  28
  29 #include "Weak.h"
  30 #include "WeakInlines.h"
  31 #include <wtf/HashMap.h>
  32
  33 namespace JSC {
  34
  35 // A HashMap with Weak<JSCell> values, which automatically removes values once they're garbage collected.
  36
  37 template<typename KeyArg, typename ValueArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
  38     typename KeyTraitsArg = HashTraits<KeyArg>>
  39 class WeakGCMap {
  40     WTF_MAKE_FAST_ALLOCATED;
  41     typedef Weak<ValueArg> ValueType;
  42     typedef HashMap<KeyArg, ValueType, HashArg, KeyTraitsArg> HashMapType;
  43
  44 public:
  45     typedef typename HashMapType::KeyType KeyType;
  46     typedef typename HashMapType::AddResult AddResult;
  47     typedef typename HashMapType::iterator iterator;
  48     typedef typename HashMapType::const_iterator const_iterator;
  49
  50     WeakGCMap()
  51         : m_gcThreshold(minGCThreshold)
  52     {
  53     }
  54
  55     ValueArg* get(const KeyType& key) const
  56     {
  57         return m_map.get(key);
  58     }
  59
  60     AddResult set(const KeyType& key, ValueType value)
  61     {
  62         gcMapIfNeeded();
  63         return m_map.set(key, WTF::move(value));
  64     }
  65
  66     ALWAYS_INLINE AddResult add(const KeyType& key, ValueType value)
  67     {
  68         gcMapIfNeeded();
  69         AddResult addResult = m_map.fastAdd(key, nullptr);
  70         if (!addResult.iterator->value) { // New value or found a zombie value.
  71             addResult.isNewEntry = true;
  72             addResult.iterator->value = WTF::move(value);
  73         }
  74         return addResult;
  75     }
  76
  77     bool remove(const KeyType& key)
  78     {
  79         return m_map.remove(key);
  80     }
  81
  82     void clear()
  83     {
  84         m_map.clear();
  85     }
  86
  87     iterator find(const KeyType& key)
  88     {
  89         iterator it = m_map.find(key);
  90         iterator end = m_map.end();
  91         if (it != end && !it->value) // Found a zombie value.
  92             return end;
  93         return it;
  94     }
  95
  96     const_iterator find(const KeyType& key) const
  97     {
  98         return const_cast<WeakGCMap*>(this)->find(key);
  99     }
 100
 101     bool contains(const KeyType& key) const
 102     {
 103         return find(key) != m_map.end();
 104     }
 105
 106 private:
 107     static const int minGCThreshold = 3;
 108
 109     NEVER_INLINE void gcMap()
 110     {
 111         Vector<KeyType, 4> zombies;
 112
 113         for (iterator it = m_map.begin(), end = m_map.end(); it != end; ++it) {
 114             if (!it->value)
 115                 zombies.append(it->key);
 116         }
 117
 118         for (size_t i = 0; i < zombies.size(); ++i)
 119             m_map.remove(zombies[i]);
 120     }
 121
 122     void gcMapIfNeeded()
 123     {
 124         if (m_map.size() < m_gcThreshold)
 125             return;
 126
 127         gcMap();
 128         m_gcThreshold = std::max(minGCThreshold, m_map.size() * 2 - 1);
 129     }
 130
 131     HashMapType m_map;
 132     int m_gcThreshold;
 133 };
 134
 135 template<typename KeyArg, typename RawMappedArg, typename HashArg, typename KeyTraitsArg>
 136 const int WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg>::minGCThreshold;
 137
 138 } // namespace JSC
 139
 140 #endif // WeakGCMap_h