API tools faq
paste
Advertisement
Guest User

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

a guest
Oct 2nd, 2012
724
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.24 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!