1/*
2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB.  If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20
21#ifndef WTF_HashCountedSet_h
22#define WTF_HashCountedSet_h
23
24#include "wtf/Assertions.h"
25#include "wtf/HashMap.h"
26#include "wtf/Vector.h"
27
28namespace WTF {
29
30    // An unordered hash set that keeps track of how many times you added an
31    // item to the set. The iterators have fields ->key and ->value that return
32    // the set members and their counts, respectively.
33    template<
34        typename Value,
35        typename HashFunctions = typename DefaultHash<Value>::Hash,
36        typename Traits = HashTraits<Value>,
37        typename Allocator = DefaultAllocator > class HashCountedSet {
38        WTF_USE_ALLOCATOR(HashCountedSet, Allocator);
39    private:
40        typedef HashMap<Value, unsigned, HashFunctions, Traits, HashTraits<unsigned>, Allocator> ImplType;
41    public:
42        typedef Value ValueType;
43        typedef typename ImplType::iterator iterator;
44        typedef typename ImplType::const_iterator const_iterator;
45        typedef typename ImplType::AddResult AddResult;
46
47        HashCountedSet() {}
48
49        void swap(HashCountedSet& other) { m_impl.swap(other.m_impl); }
50
51        unsigned size() const { return m_impl.size(); }
52        unsigned capacity() const { return m_impl.capacity(); }
53        bool isEmpty() const { return m_impl.isEmpty(); }
54
55        // Iterators iterate over pairs of values (called key) and counts (called value).
56        iterator begin() { return m_impl.begin(); }
57        iterator end() { return m_impl.end(); }
58        const_iterator begin() const { return m_impl.begin(); }
59        const_iterator end() const { return m_impl.end(); }
60
61        iterator find(const ValueType& value) { return m_impl.find(value); }
62        const_iterator find(const ValueType& value) const { return m_impl.find(value); }
63        bool contains(const ValueType& value ) const { return m_impl.contains(value); }
64        unsigned count(const ValueType& value ) const { return m_impl.get(value); }
65
66        // Increases the count if an equal value is already present
67        // the return value is a pair of an iterator to the new value's
68        // location, and a bool that is true if an new entry was added.
69        AddResult add(const ValueType&);
70
71        // Reduces the count of the value, and removes it if count
72        // goes down to zero, returns true if the value is removed.
73        bool remove(const ValueType& value) { return remove(find(value)); }
74        bool remove(iterator);
75
76        // Removes the value, regardless of its count.
77        void removeAll(const ValueType& value) { removeAll(find(value)); }
78        void removeAll(iterator);
79
80        // Clears the whole set.
81        void clear() { m_impl.clear(); }
82
83        void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); }
84
85    private:
86        ImplType m_impl;
87    };
88
89    template<typename T, typename U, typename V, typename W>
90    inline typename HashCountedSet<T, U, V, W>::AddResult HashCountedSet<T, U, V, W>::add(const ValueType& value)
91    {
92        AddResult result = m_impl.add(value, 0);
93        ++result.storedValue->value;
94        return result;
95    }
96
97    template<typename T, typename U, typename V, typename W>
98    inline bool HashCountedSet<T, U, V, W>::remove(iterator it)
99    {
100        if (it == end())
101            return false;
102
103        unsigned oldVal = it->value;
104        ASSERT(oldVal);
105        unsigned newVal = oldVal - 1;
106        if (newVal) {
107            it->value = newVal;
108            return false;
109        }
110
111        m_impl.remove(it);
112        return true;
113    }
114
115    template<typename T, typename U, typename V, typename W>
116    inline void HashCountedSet<T, U, V, W>::removeAll(iterator it)
117    {
118        if (it == end())
119            return;
120
121        m_impl.remove(it);
122    }
123
124    template<typename T, typename U, typename V, typename W, typename VectorType>
125    inline void copyToVector(const HashCountedSet<T, U, V, W>& collection, VectorType& vector)
126    {
127        typedef typename HashCountedSet<T, U, V, W>::const_iterator iterator;
128
129        vector.resize(collection.size());
130
131        iterator it = collection.begin();
132        iterator end = collection.end();
133        for (unsigned i = 0; it != end; ++it, ++i)
134            vector[i] = *it;
135    }
136
137    template<typename Value, typename HashFunctions, typename Traits, typename Allocator, size_t inlineCapacity, typename VectorAllocator>
138    inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits, Allocator>& collection, Vector<Value, inlineCapacity, VectorAllocator>& vector)
139    {
140        typedef typename HashCountedSet<Value, HashFunctions, Traits, Allocator>::const_iterator iterator;
141
142        vector.resize(collection.size());
143
144        iterator it = collection.begin();
145        iterator end = collection.end();
146        for (unsigned i = 0; it != end; ++it, ++i)
147            vector[i] = (*it).key;
148    }
149
150#if !ENABLE(OILPAN)
151    template<typename T, typename U, typename V>
152    struct NeedsTracing<HashCountedSet<T, U, V> > {
153        static const bool value = false;
154    };
155#endif
156
157} // namespace WTF
158
159using WTF::HashCountedSet;
160
161#endif /* WTF_HashCountedSet_h */
162