From 40736c5763bf61337c8c14e16d8587db021a87d4 Mon Sep 17 00:00:00 2001 From: Simon Hausmann Date: Fri, 6 Jan 2012 14:44:00 +0100 Subject: Imported WebKit commit 2ea9d364d0f6efa8fa64acf19f451504c59be0e4 (http://svn.webkit.org/repository/webkit/trunk@104285) --- Source/JavaScriptCore/wtf/HashCountedSet.h | 228 +++++++++++++++++++++++++++++ 1 file changed, 228 insertions(+) create mode 100644 Source/JavaScriptCore/wtf/HashCountedSet.h (limited to 'Source/JavaScriptCore/wtf/HashCountedSet.h') diff --git a/Source/JavaScriptCore/wtf/HashCountedSet.h b/Source/JavaScriptCore/wtf/HashCountedSet.h new file mode 100644 index 000000000..b97d8c8fd --- /dev/null +++ b/Source/JavaScriptCore/wtf/HashCountedSet.h @@ -0,0 +1,228 @@ +/* + * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public License + * along with this library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + * Boston, MA 02110-1301, USA. + * + */ + +#ifndef WTF_HashCountedSet_h +#define WTF_HashCountedSet_h + +#include "Assertions.h" +#include "HashMap.h" +#include "Vector.h" + +namespace WTF { + + template::Hash, + typename Traits = HashTraits > class HashCountedSet { + WTF_MAKE_FAST_ALLOCATED; + private: + typedef HashMap ImplType; + public: + typedef Value ValueType; + typedef typename ImplType::iterator iterator; + typedef typename ImplType::const_iterator const_iterator; + + HashCountedSet() {} + + int size() const; + int capacity() const; + bool isEmpty() const; + + // Iterators iterate over pairs of values and counts. + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + iterator find(const ValueType&); + const_iterator find(const ValueType&) const; + bool contains(const ValueType&) const; + unsigned count(const ValueType&) const; + + // Increases the count if an equal value is already present + // the return value is a pair of an interator to the new value's + // location, and a bool that is true if an new entry was added. + std::pair add(const ValueType&); + + // Reduces the count of the value, and removes it if count + // goes down to zero, returns true if the value is removed. + bool remove(const ValueType&); + bool remove(iterator); + + // Removes the value, regardless of its count. + void removeAll(iterator); + void removeAll(const ValueType&); + + // Clears the whole set. + void clear(); + + private: + ImplType m_impl; + }; + + template + inline int HashCountedSet::size() const + { + return m_impl.size(); + } + + template + inline int HashCountedSet::capacity() const + { + return m_impl.capacity(); + } + + template + inline bool HashCountedSet::isEmpty() const + { + return size() == 0; + } + + template + inline typename HashCountedSet::iterator HashCountedSet::begin() + { + return m_impl.begin(); + } + + template + inline typename HashCountedSet::iterator HashCountedSet::end() + { + return m_impl.end(); + } + + template + inline typename HashCountedSet::const_iterator HashCountedSet::begin() const + { + return m_impl.begin(); + } + + template + inline typename HashCountedSet::const_iterator HashCountedSet::end() const + { + return m_impl.end(); + } + + template + inline typename HashCountedSet::iterator HashCountedSet::find(const ValueType& value) + { + return m_impl.find(value); + } + + template + inline typename HashCountedSet::const_iterator HashCountedSet::find(const ValueType& value) const + { + return m_impl.find(value); + } + + template + inline bool HashCountedSet::contains(const ValueType& value) const + { + return m_impl.contains(value); + } + + template + inline unsigned HashCountedSet::count(const ValueType& value) const + { + return m_impl.get(value); + } + + template + inline std::pair::iterator, bool> HashCountedSet::add(const ValueType &value) + { + pair result = m_impl.add(value, 0); + ++result.first->second; + return result; + } + + template + inline bool HashCountedSet::remove(const ValueType& value) + { + return remove(find(value)); + } + + template + inline bool HashCountedSet::remove(iterator it) + { + if (it == end()) + return false; + + unsigned oldVal = it->second; + ASSERT(oldVal); + unsigned newVal = oldVal - 1; + if (newVal) { + it->second = newVal; + return false; + } + + m_impl.remove(it); + return true; + } + + template + inline void HashCountedSet::removeAll(const ValueType& value) + { + removeAll(find(value)); + } + + template + inline void HashCountedSet::removeAll(iterator it) + { + if (it == end()) + return; + + m_impl.remove(it); + } + + template + inline void HashCountedSet::clear() + { + m_impl.clear(); + } + + template + inline void copyToVector(const HashCountedSet& collection, VectorType& vector) + { + typedef typename HashCountedSet::const_iterator iterator; + + vector.resize(collection.size()); + + iterator it = collection.begin(); + iterator end = collection.end(); + for (unsigned i = 0; it != end; ++it, ++i) + vector[i] = *it; + } + + template + inline void copyToVector(const HashCountedSet& collection, Vector& vector) + { + typedef typename HashCountedSet::const_iterator iterator; + + vector.resize(collection.size()); + + iterator it = collection.begin(); + iterator end = collection.end(); + for (unsigned i = 0; it != end; ++it, ++i) + vector[i] = (*it).first; + } + + +} // namespace khtml + +using WTF::HashCountedSet; + +#endif /* WTF_HashCountedSet_h */ -- cgit v1.2.1