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 <heap/Weak.h>
  30 #include <heap/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 RawMappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
  38     typename KeyTraitsArg = HashTraits<KeyArg> >
  39 class WeakGCMap : public HashMap<KeyArg, Weak<RawMappedArg>, HashArg, KeyTraitsArg> {
  40     typedef Weak<RawMappedArg> MappedType;
  41     typedef HashMap<KeyArg, MappedType, HashArg, KeyTraitsArg> Base;
  42     typedef WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg> Self;
  43     typedef HashTraits<MappedType> MappedTraits;
  44     typedef typename MappedTraits::PassInType MappedPassInType;
  45
  46 public:
  47     typedef typename Base::KeyType KeyType;
  48     typedef typename Base::AddResult AddResult;
  49     typedef typename Base::iterator iterator;
  50     typedef typename Base::const_iterator const_iterator;
  51     using Base::begin;
  52     using Base::end;
  53     using Base::size;
  54     using Base::remove;
  55
  56     WeakGCMap()
  57         : m_gcThreshold(minGCThreshold)
  58     {
  59     }
  60
  61     AddResult set(const KeyType& key, MappedPassInType value)
  62     {
  63         gcMapIfNeeded();
  64         return Base::set(key, value);
  65     }
  66
  67     AddResult add(const KeyType& key, MappedPassInType value)
  68     {
  69         gcMapIfNeeded();
  70         AddResult addResult = Base::add(key, nullptr);
  71         if (!addResult.iterator->value) { // New value or found a zombie value.
  72             addResult.isNewEntry = true;
  73             addResult.iterator->value = value;
  74         }
  75         return addResult;
  76     }
  77
  78     iterator find(const KeyType& key)
  79     {
  80         iterator it = Base::find(key);
  81         iterator end = Base::end();
  82         if (it != end && !it->value) // Found a zombie value.
  83             return end;
  84         return it;
  85     }
  86
  87     const_iterator find(const KeyType& key) const
  88     {
  89         return const_cast<Self*>(this)->find(key);
  90     }
  91
  92     bool contains(const KeyType& key) const
  93     {
  94         return find(key) != end();
  95     }
  96
  97 private:
  98     static const int minGCThreshold = 3;
  99
 100     void gcMap()
 101     {
 102         Vector<KeyType, 4> zombies;
 103         iterator end = this->end();
 104         for (iterator it = begin(); it != end; ++it) {
 105             if (!it->value)
 106                 zombies.append(it->key);
 107         }
 108         for (size_t i = 0; i < zombies.size(); ++i)
 109             remove(zombies[i]);
 110     }
 111
 112     void gcMapIfNeeded()
 113     {
 114         if (size() < m_gcThreshold)
 115             return;
 116
 117         gcMap();
 118         m_gcThreshold = std::max(minGCThreshold, size() * 2 - 1);
 119     }
 120
 121     int m_gcThreshold;
 122 };
 123
 124 template<typename KeyArg, typename RawMappedArg, typename HashArg, typename KeyTraitsArg>
 125 const int WeakGCMap<KeyArg, RawMappedArg, HashArg, KeyTraitsArg>::minGCThreshold;
 126
 127 } // namespace JSC
 128
 129 #endif // WeakGCMap_h