Advertisement
Guest User

qt\src\3rdparty\webkit\Source\JavaScriptCore\wtf\HashSet.h

a guest
Oct 2nd, 2012
702
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.24 KB | None | 0 0
  1. /*
  2.  * Copyright (C) 2005, 2006, 2007, 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_HashSet_h
  22. #define WTF_HashSet_h
  23.  
  24. #include "FastAllocBase.h"
  25. #include "HashTable.h"
  26.  
  27. namespace WTF {
  28.  
  29.     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
  30.     template<typename Value, typename HashFunctions, typename Traits>
  31.     void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
  32.     template<typename Value, typename HashFunctions, typename Traits>
  33.     void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
  34.  
  35.     template<typename T> struct IdentityExtractor;
  36.  
  37.     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
  38.         typename TraitsArg = HashTraits<ValueArg> > class HashSet {
  39.         WTF_MAKE_FAST_ALLOCATED;
  40.     private:
  41.         typedef HashArg HashFunctions;
  42.         typedef TraitsArg ValueTraits;
  43.  
  44.     public:
  45.         typedef typename ValueTraits::TraitType ValueType;
  46.  
  47.     private:
  48.         typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
  49.             HashFunctions, ValueTraits, ValueTraits> HashTableType;
  50.  
  51.     public:
  52.         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
  53.         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
  54.  
  55.         void swap(HashSet&);
  56.  
  57.         int size() const;
  58.         int capacity() const;
  59.         bool isEmpty() const;
  60.  
  61.         iterator begin() const;
  62.         iterator end() const;
  63.  
  64.         iterator find(const ValueType&) const;
  65.         bool contains(const ValueType&) const;
  66.  
  67.         // An alternate version of find() that finds the object by hashing and comparing
  68.         // with some other type, to avoid the cost of type conversion. HashTranslator
  69.         // must have the following function members:
  70.         //   static unsigned hash(const T&);
  71.         //   static bool equal(const ValueType&, const T&);
  72.         template<typename T, typename HashTranslator> iterator find(const T&) const;
  73.         template<typename T, typename HashTranslator> bool contains(const T&) const;
  74.  
  75.         // The return value is a pair of an interator to the new value's location,
  76.         // and a bool that is true if an new entry was added.
  77.         pair<iterator, bool> add(const ValueType&);
  78.  
  79.         // An alternate version of add() that finds the object by hashing and comparing
  80.         // with some other type, to avoid the cost of type conversion if the object is already
  81.         // in the table. HashTranslator must have the following function members:
  82.         //   static unsigned hash(const T&);
  83.         //   static bool equal(const ValueType&, const T&);
  84.         //   static translate(ValueType&, const T&, unsigned hashCode);
  85.         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
  86.  
  87.         void remove(const ValueType&);
  88.         void remove(iterator);
  89.         void clear();
  90.  
  91.     private:
  92.         friend void deleteAllValues<>(const HashSet&);
  93.         friend void fastDeleteAllValues<>(const HashSet&);
  94.  
  95.         HashTableType m_impl;
  96.     };
  97.  
  98.     template<typename T> struct IdentityExtractor {
  99.         static const T& extract(const T& t) { return t; }
  100.     };
  101.  
  102.     template<typename ValueType, typename ValueTraits, typename T, typename Translator>
  103.     struct HashSetTranslatorAdapter {
  104.         static unsigned hash(const T& key) { return Translator::hash(key); }
  105.         static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
  106.         static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
  107.         {
  108.             Translator::translate(location, key, hashCode);
  109.         }
  110.     };
  111.  
  112.     template<typename T, typename U, typename V>
  113.     inline void HashSet<T, U, V>::swap(HashSet& other)
  114.     {
  115.         m_impl.swap(other.m_impl);
  116.     }
  117.  
  118.     template<typename T, typename U, typename V>
  119.     inline int HashSet<T, U, V>::size() const
  120.     {
  121.         return m_impl.size();
  122.     }
  123.  
  124.     template<typename T, typename U, typename V>
  125.     inline int HashSet<T, U, V>::capacity() const
  126.     {
  127.         return m_impl.capacity();
  128.     }
  129.  
  130.     template<typename T, typename U, typename V>
  131.     inline bool HashSet<T, U, V>::isEmpty() const
  132.     {
  133.         return m_impl.isEmpty();
  134.     }
  135.  
  136.     template<typename T, typename U, typename V>
  137.     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const
  138.     {
  139.         return m_impl.begin();
  140.     }
  141.  
  142.     template<typename T, typename U, typename V>
  143.     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const
  144.     {
  145.         return m_impl.end();
  146.     }
  147.  
  148.     template<typename T, typename U, typename V>
  149.     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value) const
  150.     {
  151.         return m_impl.find(value);
  152.     }
  153.  
  154.     template<typename T, typename U, typename V>
  155.     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
  156.     {
  157.         return m_impl.contains(value);
  158.     }
  159.  
  160.     template<typename Value, typename HashFunctions, typename Traits>
  161.     template<typename T, typename HashTranslator>
  162.     typename HashSet<Value, HashFunctions, Traits>::iterator
  163.     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
  164.     {
  165.         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
  166.         return m_impl.template find<T, Adapter>(value);
  167.     }
  168.  
  169.     template<typename Value, typename HashFunctions, typename Traits>
  170.     template<typename T, typename HashTranslator>
  171.     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
  172.     {
  173.         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
  174.         return m_impl.template contains<T, Adapter>(value);
  175.     }
  176.  
  177.     template<typename T, typename U, typename V>
  178.     inline pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
  179.     {
  180.         //return m_impl.add(value);
  181.        
  182.         typedef typename HashSet<T, U, V>::iterator iter_type;
  183.         auto& temp = m_impl.add(value);
  184.         return make_pair((iter_type)temp.first, temp.second);      
  185.        
  186.         //auto p= m_impl.add(value);
  187.         //return make_pair(typename HashSet<T,U,V>::const_iterator(p.first), p.second);    
  188.     }
  189.  
  190.     template<typename Value, typename HashFunctions, typename Traits>
  191.     template<typename T, typename HashTranslator>
  192.     inline pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
  193.     HashSet<Value, HashFunctions, Traits>::add(const T& value)
  194.     {
  195.         //typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
  196.         //return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
  197.        
  198.         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
  199.         typedef typename HashSet<Value, HashFunctions, Traits>::iterator iter_type;
  200.         auto& temp = m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
  201.         return make_pair((iter_type)temp.first, temp.second);      
  202.        
  203.         //typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
  204.         //auto p = m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
  205.         //return make_pair(typename HashSet<Value, HashFunctions, Traits>::iterator(p.first), p.second);       
  206.     }
  207.  
  208.     template<typename T, typename U, typename V>
  209.     inline void HashSet<T, U, V>::remove(iterator it)
  210.     {
  211.         if (it.m_impl == m_impl.end())
  212.             return;
  213.         m_impl.internalCheckTableConsistency();
  214.         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
  215.     }
  216.  
  217.     template<typename T, typename U, typename V>
  218.     inline void HashSet<T, U, V>::remove(const ValueType& value)
  219.     {
  220.         remove(find(value));
  221.     }
  222.  
  223.     template<typename T, typename U, typename V>
  224.     inline void HashSet<T, U, V>::clear()
  225.     {
  226.         m_impl.clear();
  227.     }
  228.  
  229.     template<typename ValueType, typename HashTableType>
  230.     void deleteAllValues(HashTableType& collection)
  231.     {
  232.         typedef typename HashTableType::const_iterator iterator;
  233.         iterator end = collection.end();
  234.         for (iterator it = collection.begin(); it != end; ++it)
  235.             delete *it;
  236.     }
  237.  
  238.     template<typename T, typename U, typename V>
  239.     inline void deleteAllValues(const HashSet<T, U, V>& collection)
  240.     {
  241.         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
  242.     }
  243.  
  244.     template<typename ValueType, typename HashTableType>
  245.     void fastDeleteAllValues(HashTableType& collection)
  246.     {
  247.         typedef typename HashTableType::const_iterator iterator;
  248.         iterator end = collection.end();
  249.         for (iterator it = collection.begin(); it != end; ++it)
  250.             fastDelete(*it);
  251.     }
  252.  
  253.     template<typename T, typename U, typename V>
  254.     inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)
  255.     {
  256.         fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
  257.     }
  258.    
  259.     template<typename T, typename U, typename V, typename W>
  260.     inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
  261.     {
  262.         typedef typename HashSet<T, U, V>::const_iterator iterator;
  263.        
  264.         vector.resize(collection.size());
  265.        
  266.         iterator it = collection.begin();
  267.         iterator end = collection.end();
  268.         for (unsigned i = 0; it != end; ++it, ++i)
  269.             vector[i] = *it;
  270.     }  
  271.  
  272. } // namespace WTF
  273.  
  274. using WTF::HashSet;
  275.  
  276. #endif /* WTF_HashSet_h */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement