X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/1df5f87f1309a8daa30dabdee855f48ae40d14ab..6fe7ccc865dc7d7541b93c5bcaf6368d2c98a174:/wtf/HashMap.h?ds=inline diff --git a/wtf/HashMap.h b/wtf/HashMap.h deleted file mode 100644 index 7731546..0000000 --- a/wtf/HashMap.h +++ /dev/null @@ -1,411 +0,0 @@ -/* - * Copyright (C) 2005, 2006, 2007, 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_HashMap_h -#define WTF_HashMap_h - -#include "HashTable.h" - -namespace WTF { - - template struct PairFirstExtractor; - - template::Hash, - typename KeyTraitsArg = HashTraits, typename MappedTraitsArg = HashTraits > - class HashMap { - WTF_MAKE_FAST_ALLOCATED; - private: - typedef KeyTraitsArg KeyTraits; - typedef MappedTraitsArg MappedTraits; - typedef PairHashTraits ValueTraits; - - public: - typedef typename KeyTraits::TraitType KeyType; - typedef typename MappedTraits::TraitType MappedType; - typedef typename ValueTraits::TraitType ValueType; - - private: - typedef HashArg HashFunctions; - - typedef HashTable, - HashFunctions, ValueTraits, KeyTraits> HashTableType; - - public: - typedef HashTableIteratorAdapter iterator; - typedef HashTableConstIteratorAdapter const_iterator; - - void swap(HashMap&); - - int size() const; - int capacity() const; - bool isEmpty() const; - - // iterators iterate over pairs of keys and values - iterator begin(); - iterator end(); - const_iterator begin() const; - const_iterator end() const; - - iterator find(const KeyType&); - const_iterator find(const KeyType&) const; - bool contains(const KeyType&) const; - MappedType get(const KeyType&) const; - - // replaces value but not key if key is already present - // return value is a pair of the iterator to the key location, - // and a boolean that's true if a new value was actually added - pair set(const KeyType&, const MappedType&); - - // does nothing if key is already present - // return value is a pair of the iterator to the key location, - // and a boolean that's true if a new value was actually added - pair add(const KeyType&, const MappedType&); - - void remove(const KeyType&); - void remove(iterator); - void clear(); - - MappedType take(const KeyType&); // efficient combination of get with remove - - // An alternate version of find() that finds the object by hashing and comparing - // with some other type, to avoid the cost of type conversion. HashTranslator - // must have the following function members: - // static unsigned hash(const T&); - // static bool equal(const ValueType&, const T&); - template iterator find(const T&); - template const_iterator find(const T&) const; - template bool contains(const T&) const; - - // An alternate version of add() that finds the object by hashing and comparing - // with some other type, to avoid the cost of type conversion if the object is already - // in the table. HashTranslator must have the following function members: - // static unsigned hash(const T&); - // static bool equal(const ValueType&, const T&); - // static translate(ValueType&, const T&, unsigned hashCode); - template pair add(const T&, const MappedType&); - - void checkConsistency() const; - - private: - pair inlineAdd(const KeyType&, const MappedType&); - - HashTableType m_impl; - }; - - template struct PairFirstExtractor { - static const typename PairType::first_type& extract(const PairType& p) { return p.first; } - }; - - template - struct HashMapTranslator { - typedef typename ValueType::first_type KeyType; - typedef typename ValueType::second_type MappedType; - - static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); } - static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); } - static void translate(ValueType& location, const KeyType& key, const MappedType& mapped) - { - location.first = key; - location.second = mapped; - } - }; - - template - struct HashMapTranslatorAdapter { - typedef typename ValueType::first_type KeyType; - typedef typename ValueType::second_type MappedType; - - static unsigned hash(const T& key) { return Translator::hash(key); } - static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); } - static void translate(ValueType& location, const T& key, const MappedType& mapped, unsigned hashCode) - { - Translator::translate(location.first, key, hashCode); - location.second = mapped; - } - }; - - template - inline void HashMap::swap(HashMap& other) - { - m_impl.swap(other.m_impl); - } - - template - inline int HashMap::size() const - { - return m_impl.size(); - } - - template - inline int HashMap::capacity() const - { - return m_impl.capacity(); - } - - template - inline bool HashMap::isEmpty() const - { - return m_impl.isEmpty(); - } - - template - inline typename HashMap::iterator HashMap::begin() - { - return m_impl.begin(); - } - - template - inline typename HashMap::iterator HashMap::end() - { - return m_impl.end(); - } - - template - inline typename HashMap::const_iterator HashMap::begin() const - { - return m_impl.begin(); - } - - template - inline typename HashMap::const_iterator HashMap::end() const - { - return m_impl.end(); - } - - template - inline typename HashMap::iterator HashMap::find(const KeyType& key) - { - return m_impl.find(key); - } - - template - inline typename HashMap::const_iterator HashMap::find(const KeyType& key) const - { - return m_impl.find(key); - } - - template - inline bool HashMap::contains(const KeyType& key) const - { - return m_impl.contains(key); - } - - template - template - inline typename HashMap::iterator - HashMap::find(const TYPE& value) - { - typedef HashMapTranslatorAdapter Adapter; - return m_impl.template find(value); - } - - template - template - inline typename HashMap::const_iterator - HashMap::find(const TYPE& value) const - { - typedef HashMapTranslatorAdapter Adapter; - return m_impl.template find(value); - } - - template - template - inline bool - HashMap::contains(const TYPE& value) const - { - typedef HashMapTranslatorAdapter Adapter; - return m_impl.template contains(value); - } - - template - inline pair::iterator, bool> - HashMap::inlineAdd(const KeyType& key, const MappedType& mapped) - { - typedef HashMapTranslator TranslatorType; - return m_impl.template add(key, mapped); - } - - template - pair::iterator, bool> - HashMap::set(const KeyType& key, const MappedType& mapped) - { - pair result = inlineAdd(key, mapped); - if (!result.second) { - // add call above didn't change anything, so set the mapped value - result.first->second = mapped; - } - return result; - } - - template - template - pair::iterator, bool> - HashMap::add(const TYPE& key, const MappedType& value) - { - typedef HashMapTranslatorAdapter Adapter; - return m_impl.template addPassingHashCode(key, value); - } - - template - pair::iterator, bool> - HashMap::add(const KeyType& key, const MappedType& mapped) - { - return inlineAdd(key, mapped); - } - - template - typename HashMap::MappedType - HashMap::get(const KeyType& key) const - { - ValueType* entry = const_cast(m_impl).lookup(key); - if (!entry) - return MappedTraits::emptyValue(); - return entry->second; - } - - template - inline void HashMap::remove(iterator it) - { - if (it.m_impl == m_impl.end()) - return; - m_impl.internalCheckTableConsistency(); - m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); - } - - template - inline void HashMap::remove(const KeyType& key) - { - remove(find(key)); - } - - template - inline void HashMap::clear() - { - m_impl.clear(); - } - - template - typename HashMap::MappedType - HashMap::take(const KeyType& key) - { - // This can probably be made more efficient to avoid ref/deref churn. - iterator it = find(key); - if (it == end()) - return MappedTraits::emptyValue(); - typename HashMap::MappedType result = it->second; - remove(it); - return result; - } - - template - inline void HashMap::checkConsistency() const - { - m_impl.checkTableConsistency(); - } - - - template - bool operator==(const HashMap& a, const HashMap& b) - { - if (a.size() != b.size()) - return false; - - typedef typename HashMap::const_iterator const_iterator; - - const_iterator end = a.end(); - const_iterator notFound = b.end(); - for (const_iterator it = a.begin(); it != end; ++it) { - const_iterator bPos = b.find(it->first); - if (bPos == notFound || it->second != bPos->second) - return false; - } - - return true; - } - - template - inline bool operator!=(const HashMap& a, const HashMap& b) - { - return !(a == b); - } - - template - void deleteAllPairSeconds(HashTableType& collection) - { - typedef typename HashTableType::const_iterator iterator; - iterator end = collection.end(); - for (iterator it = collection.begin(); it != end; ++it) - delete it->second; - } - - template - inline void deleteAllValues(const HashMap& collection) - { - deleteAllPairSeconds::MappedType>(collection); - } - - template - void deleteAllPairFirsts(HashTableType& collection) - { - typedef typename HashTableType::const_iterator iterator; - iterator end = collection.end(); - for (iterator it = collection.begin(); it != end; ++it) - delete it->first; - } - - template - inline void deleteAllKeys(const HashMap& collection) - { - deleteAllPairFirsts::KeyType>(collection); - } - - template - inline void copyKeysToVector(const HashMap& collection, Y& vector) - { - typedef typename HashMap::const_iterator::Keys iterator; - - vector.resize(collection.size()); - - iterator it = collection.begin().keys(); - iterator end = collection.end().keys(); - for (unsigned i = 0; it != end; ++it, ++i) - vector[i] = *it; - } - - template - inline void copyValuesToVector(const HashMap& collection, Y& vector) - { - typedef typename HashMap::const_iterator::Values iterator; - - vector.resize(collection.size()); - - iterator it = collection.begin().values(); - iterator end = collection.end().values(); - for (unsigned i = 0; it != end; ++it, ++i) - vector[i] = *it; - } - -} // namespace WTF - -using WTF::HashMap; - -#include "RefPtrHashMap.h" - -#endif /* WTF_HashMap_h */