#ifndef WeakGCMap_h
#define WeakGCMap_h
-#include "Collector.h"
+#include <heap/Weak.h>
+#include <heap/WeakInlines.h>
#include <wtf/HashMap.h>
namespace JSC {
-class JSCell;
+// A HashMap with Weak<JSCell> values, which automatically removes values once they're garbage collected.
-// A HashMap whose get() function returns emptyValue() for cells awaiting destruction.
-template<typename KeyType, typename MappedType>
-class WeakGCMap : public FastAllocBase {
- /*
- Invariants:
- * A value enters the WeakGCMap marked. (Guaranteed by set().)
- * A value that becomes unmarked leaves the WeakGCMap before being recycled. (Guaranteed by the value's destructor removing it from the WeakGCMap.)
- * A value that becomes unmarked leaves the WeakGCMap before becoming marked again. (Guaranteed by all destructors running before the mark phase begins.)
- * During the mark phase, all values in the WeakGCMap are valid. (Guaranteed by all destructors running before the mark phase begins.)
- */
+template<typename KeyArg, typename RawMappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
+ typename KeyTraitsArg = HashTraits<KeyArg> >
+class WeakGCMap : public HashMap<KeyArg, Weak<RawMappedArg>, HashArg, KeyTraitsArg> {
+ typedef Weak<RawMappedArg> MappedType;
+ typedef HashMap<KeyArg, MappedType, HashArg, KeyTraitsArg> Base;
+ typedef WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg> Self;
+ typedef HashTraits<MappedType> MappedTraits;
+ typedef typename MappedTraits::PassInType MappedPassInType;
public:
- typedef typename HashMap<KeyType, MappedType>::iterator iterator;
- typedef typename HashMap<KeyType, MappedType>::const_iterator const_iterator;
-
- bool isEmpty() { return m_map.isEmpty(); }
+ typedef typename Base::KeyType KeyType;
+ typedef typename Base::AddResult AddResult;
+ typedef typename Base::iterator iterator;
+ typedef typename Base::const_iterator const_iterator;
+ using Base::begin;
+ using Base::end;
+ using Base::size;
+ using Base::remove;
+
+ WeakGCMap()
+ : m_gcThreshold(minGCThreshold)
+ {
+ }
- MappedType get(const KeyType& key) const;
- pair<iterator, bool> set(const KeyType&, const MappedType&);
- MappedType take(const KeyType& key);
+ AddResult set(const KeyType& key, MappedPassInType value)
+ {
+ gcMapIfNeeded();
+ return Base::set(key, value);
+ }
- // These unchecked functions provide access to a value even if the value's
- // mark bit is not set. This is used, among other things, to retrieve values
- // during the GC mark phase, which begins by clearing all mark bits.
+ AddResult add(const KeyType& key, MappedPassInType value)
+ {
+ gcMapIfNeeded();
+ AddResult addResult = Base::add(key, nullptr);
+ if (!addResult.iterator->value) { // New value or found a zombie value.
+ addResult.isNewEntry = true;
+ addResult.iterator->value = value;
+ }
+ return addResult;
+ }
- MappedType uncheckedGet(const KeyType& key) const { return m_map.get(key); }
- bool uncheckedRemove(const KeyType&, const MappedType&);
+ iterator find(const KeyType& key)
+ {
+ iterator it = Base::find(key);
+ iterator end = Base::end();
+ if (it != end && !it->value) // Found a zombie value.
+ return end;
+ return it;
+ }
- iterator uncheckedBegin() { return m_map.begin(); }
- iterator uncheckedEnd() { return m_map.end(); }
+ const_iterator find(const KeyType& key) const
+ {
+ return const_cast<Self*>(this)->find(key);
+ }
- const_iterator uncheckedBegin() const { return m_map.begin(); }
- const_iterator uncheckedEnd() const { return m_map.end(); }
+ bool contains(const KeyType& key) const
+ {
+ return find(key) != end();
+ }
private:
- HashMap<KeyType, MappedType> m_map;
-};
+ static const int minGCThreshold = 3;
+
+ void gcMap()
+ {
+ Vector<KeyType, 4> zombies;
+ iterator end = this->end();
+ for (iterator it = begin(); it != end; ++it) {
+ if (!it->value)
+ zombies.append(it->key);
+ }
+ for (size_t i = 0; i < zombies.size(); ++i)
+ remove(zombies[i]);
+ }
+
+ void gcMapIfNeeded()
+ {
+ if (size() < m_gcThreshold)
+ return;
-template<typename KeyType, typename MappedType>
-inline MappedType WeakGCMap<KeyType, MappedType>::get(const KeyType& key) const
-{
- MappedType result = m_map.get(key);
- if (result == HashTraits<MappedType>::emptyValue())
- return result;
- if (!Heap::isCellMarked(result))
- return HashTraits<MappedType>::emptyValue();
- return result;
-}
-
-template<typename KeyType, typename MappedType>
-MappedType WeakGCMap<KeyType, MappedType>::take(const KeyType& key)
-{
- MappedType result = m_map.take(key);
- if (result == HashTraits<MappedType>::emptyValue())
- return result;
- if (!Heap::isCellMarked(result))
- return HashTraits<MappedType>::emptyValue();
- return result;
-}
-
-template<typename KeyType, typename MappedType>
-pair<typename HashMap<KeyType, MappedType>::iterator, bool> WeakGCMap<KeyType, MappedType>::set(const KeyType& key, const MappedType& value)
-{
- Heap::markCell(value); // If value is newly allocated, it's not marked, so mark it now.
- pair<iterator, bool> result = m_map.add(key, value);
- if (!result.second) { // pre-existing entry
- result.second = !Heap::isCellMarked(result.first->second);
- result.first->second = value;
+ gcMap();
+ m_gcThreshold = std::max(minGCThreshold, size() * 2 - 1);
}
- return result;
-}
-
-template<typename KeyType, typename MappedType>
-bool WeakGCMap<KeyType, MappedType>::uncheckedRemove(const KeyType& key, const MappedType& value)
-{
- iterator it = m_map.find(key);
- if (it == m_map.end())
- return false;
- if (it->second != value)
- return false;
- m_map.remove(it);
- return true;
-}
+
+ int m_gcThreshold;
+};
+
+template<typename KeyArg, typename RawMappedArg, typename HashArg, typename KeyTraitsArg>
+const int WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg>::minGCThreshold;
} // namespace JSC
projects / apple / javascriptcore.git / blobdiff