WeakGCMap.h revision d0825bca7fe65beaee391d30da42e937db621564 
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 "Collector.h"
30#include <wtf/HashMap.h>
31
32namespace JSC {
33
34class JSCell;
35
36// A HashMap whose get() function returns emptyValue() for cells awaiting destruction.
37template<typename KeyType, typename MappedType>
38class WeakGCMap : public FastAllocBase {
39    /*
40    Invariants:
41        * A value enters the WeakGCMap marked. (Guaranteed by set().)
42        * A value that becomes unmarked leaves the WeakGCMap before being recycled. (Guaranteed by the value's destructor removing it from the WeakGCMap.)
43        * A value that becomes unmarked leaves the WeakGCMap before becoming marked again. (Guaranteed by all destructors running before the mark phase begins.)
44        * During the mark phase, all values in the WeakGCMap are valid. (Guaranteed by all destructors running before the mark phase begins.)
45    */
46
47public:
48    typedef typename HashMap<KeyType, MappedType>::iterator iterator;
49    typedef typename HashMap<KeyType, MappedType>::const_iterator const_iterator;
50
51    bool isEmpty() { return m_map.isEmpty(); }
52
53    MappedType get(const KeyType& key) const;
54    pair<iterator, bool> set(const KeyType&, const MappedType&);
55    MappedType take(const KeyType& key);
56
57    // These unchecked functions provide access to a value even if the value's
58    // mark bit is not set. This is used, among other things, to retrieve values
59    // during the GC mark phase, which begins by clearing all mark bits.
60
61    MappedType uncheckedGet(const KeyType& key) const { return m_map.get(key); }
62    bool uncheckedRemove(const KeyType&, const MappedType&);
63
64    iterator uncheckedBegin() { return m_map.begin(); }
65    iterator uncheckedEnd() { return m_map.end(); }
66
67    const_iterator uncheckedBegin() const { return m_map.begin(); }
68    const_iterator uncheckedEnd() const { return m_map.end(); }
69
70private:
71    HashMap<KeyType, MappedType> m_map;
72};
73
74template<typename KeyType, typename MappedType>
75inline MappedType WeakGCMap<KeyType, MappedType>::get(const KeyType& key) const
76{
77    MappedType result = m_map.get(key);
78    if (result == HashTraits<MappedType>::emptyValue())
79        return result;
80    if (!Heap::isCellMarked(result))
81        return HashTraits<MappedType>::emptyValue();
82    return result;
83}
84
85template<typename KeyType, typename MappedType>
86MappedType WeakGCMap<KeyType, MappedType>::take(const KeyType& key)
87{
88    MappedType result = m_map.take(key);
89    if (result == HashTraits<MappedType>::emptyValue())
90        return result;
91    if (!Heap::isCellMarked(result))
92        return HashTraits<MappedType>::emptyValue();
93    return result;
94}
95
96template<typename KeyType, typename MappedType>
97pair<typename HashMap<KeyType, MappedType>::iterator, bool> WeakGCMap<KeyType, MappedType>::set(const KeyType& key, const MappedType& value)
98{
99    Heap::markCell(value); // If value is newly allocated, it's not marked, so mark it now.
100    pair<iterator, bool> result = m_map.add(key, value);
101    if (!result.second) { // pre-existing entry
102        result.second = !Heap::isCellMarked(result.first->second);
103        result.first->second = value;
104    }
105    return result;
106}
107
108template<typename KeyType, typename MappedType>
109bool WeakGCMap<KeyType, MappedType>::uncheckedRemove(const KeyType& key, const MappedType& value)
110{
111    iterator it = m_map.find(key);
112    if (it == m_map.end())
113        return false;
114    if (it->second != value)
115        return false;
116    m_map.remove(it);
117    return true;
118}
119
120} // namespace JSC
121
122#endif // WeakGCMap_h
123