1 // -*- mode: c++; c-basic-offset: 4 -*-

     2 /*

     3  * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Library General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Library General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Library General Public License

    16  * along with this library; see the file COPYING.LIB.  If not, write to

    17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    18  * Boston, MA 02110-1301, USA.

    19  *

    20  */

    21 

    22 #ifndef WTF_ListHashSet_h

    23 #define WTF_ListHashSet_h

    24 

    25 #include "Assertions.h"

    26 #include "HashSet.h"

    27 #include "OwnPtr.h"

    28 

    29 namespace WTF {

    30 

    31     // ListHashSet: Just like HashSet, this class provides a Set

    32     // interface - a collection of unique objects with O(1) insertion,

    33     // removal and test for containership. However, it also has an

    34     // order - iterating it will always give back values in the order

    35     // in which they are added.

    36 

    37     // In theory it would be possible to add prepend, insertAfter, insertBefore,

    38     // and an append that moves the element to the end even if already present,

    39     // but unclear yet if these are needed.

    40 

    41     template<typename Value, typename HashFunctions> class ListHashSet;

    42 

    43     template<typename T> struct IdentityExtractor;

    44 

    45     template<typename Value, typename HashFunctions>

    46     void deleteAllValues(const ListHashSet<Value, HashFunctions>&);

    47 

    48     template<typename ValueArg, typename HashArg> class ListHashSetIterator;

    49     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;

    50 

    51     template<typename ValueArg> struct ListHashSetNode;

    52     template<typename ValueArg> struct ListHashSetNodeAllocator;

    53     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;

    54 

    55     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {

    56     private:

    57         typedef ListHashSetNode<ValueArg> Node;

    58         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

    59 

    60         typedef HashTraits<Node*> NodeTraits;

    61         typedef ListHashSetNodeHashFunctions<ValueArg, HashArg> NodeHash;

    62 

    63         typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;

    64 

    65         typedef HashArg HashFunctions;

    66 

    67     public:

    68         typedef ValueArg ValueType;

    69         typedef ListHashSetIterator<ValueType, HashArg> iterator;

    70         typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;

    71 

    72         friend class ListHashSetConstIterator<ValueType, HashArg>;

    73 

    74         ListHashSet();

    75         ListHashSet(const ListHashSet&);

    76         ListHashSet& operator=(const ListHashSet&);

    77         ~ListHashSet();

    78 

    79         ListHashSet& swap(ListHashSet&);

    80 

    81         int size() const;

    82         int capacity() const;

    83         bool isEmpty() const;

    84 

    85         iterator begin();

    86         iterator end();

    87         const_iterator begin() const;

    88         const_iterator end() const;

    89 

    90         iterator find(const ValueType&);

    91         const_iterator find(const ValueType&) const;

    92         bool contains(const ValueType&) const;

    93 

    94         // the return value is a pair of an interator to the new value's location, 

    95         // and a bool that is true if an new entry was added

    96         pair<iterator, bool> add(const ValueType&);

    97 

    98         void remove(const ValueType&);

    99         void remove(iterator);

   100         void clear();

   101 

   102     private:

   103         void unlinkAndDelete(Node*);

   104         void appendNode(Node*);

   105         void deleteAllNodes();

   106         iterator makeIterator(Node*);

   107         const_iterator makeConstIterator(Node*) const;

   108 

   109         friend void deleteAllValues<>(const ListHashSet&);

   110 

   111         ImplType m_impl;

   112         Node* m_head;

   113         Node* m_tail;

   114         OwnPtr<NodeAllocator> m_allocator;

   115     };

   116 

   117     template<typename ValueArg> struct ListHashSetNodeAllocator {

   118         typedef ListHashSetNode<ValueArg> Node;

   119         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

   120 

   121         ListHashSetNodeAllocator() 

   122             : m_freeList(pool())

   123             , m_isDoneWithInitialFreeList(false)

   124         { 

   125             memset(m_pool.pool, 0, sizeof(m_pool.pool));

   126         }

   127 

   128         Node* allocate()

   129         { 

   130             Node* result = m_freeList;

   131 

   132             if (!result)

   133                 return static_cast<Node*>(fastMalloc(sizeof(Node)));

   134 

   135             ASSERT(!result->m_isAllocated);

   136 

   137             Node* next = result->m_next;

   138             ASSERT(!next || !next->m_isAllocated);

   139             if (!next && !m_isDoneWithInitialFreeList) {

   140                 next = result + 1;

   141                 if (next == pastPool()) {

   142                     m_isDoneWithInitialFreeList = true;

   143                     next = 0;

   144                 } else {

   145                     ASSERT(inPool(next));

   146                     ASSERT(!next->m_isAllocated);

   147                 }

   148             }

   149             m_freeList = next;

   150 

   151             return result;

   152         }

   153 

   154         void deallocate(Node* node) 

   155         {

   156             if (inPool(node)) {

   157 #ifndef NDEBUG

   158                 node->m_isAllocated = false;

   159 #endif

   160                 node->m_next = m_freeList;

   161                 m_freeList = node;

   162                 return;

   163             }

   164 

   165             fastFree(node);

   166         }

   167 

   168     private:

   169         Node* pool() { return reinterpret_cast<Node*>(m_pool.pool); }

   170         Node* pastPool() { return pool() + m_poolSize; }

   171 

   172         bool inPool(Node* node)

   173         {

   174             return node >= pool() && node < pastPool();

   175         }

   176 

   177         Node* m_freeList;

   178         bool m_isDoneWithInitialFreeList;

   179         static const size_t m_poolSize = 256;

   180         union {

   181             char pool[sizeof(Node) * m_poolSize];

   182             double forAlignment;

   183         } m_pool;

   184     };

   185 

   186     template<typename ValueArg> struct ListHashSetNode {

   187         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

   188 

   189         ListHashSetNode(ValueArg value)

   190             : m_value(value)

   191             , m_prev(0)

   192             , m_next(0)

   193 #ifndef NDEBUG

   194             , m_isAllocated(true)

   195 #endif

   196         {

   197         }

   198 

   199         void* operator new(size_t, NodeAllocator* allocator)

   200         {

   201             return allocator->allocate();

   202         }

   203         void destroy(NodeAllocator* allocator)

   204         {

   205             this->~ListHashSetNode();

   206             allocator->deallocate(this);

   207         }

   208 

   209         ValueArg m_value;

   210         ListHashSetNode* m_prev;

   211         ListHashSetNode* m_next;

   212 

   213 #ifndef NDEBUG

   214         bool m_isAllocated;

   215 #endif

   216     };

   217 

   218     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions {

   219         typedef ListHashSetNode<ValueArg> Node;

   220         

   221         static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }

   222         static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }

   223     };

   224 

   225     template<typename ValueArg, typename HashArg> class ListHashSetIterator {

   226     private:

   227         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;

   228         typedef ListHashSetIterator<ValueArg, HashArg> iterator;

   229         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;

   230         typedef ListHashSetNode<ValueArg> Node;

   231         typedef ValueArg ValueType;

   232         typedef ValueType& ReferenceType;

   233         typedef ValueType* PointerType;

   234 

   235         friend class ListHashSet<ValueArg, HashArg>;

   236 

   237         ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }

   238 

   239     public:

   240         ListHashSetIterator() { }

   241 

   242         // default copy, assignment and destructor are OK

   243 

   244         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }

   245         ReferenceType operator*() const { return *get(); }

   246         PointerType operator->() const { return get(); }

   247 

   248         iterator& operator++() { ++m_iterator; return *this; }

   249 

   250         // postfix ++ intentionally omitted

   251 

   252         iterator& operator--() { --m_iterator; return *this; }

   253 

   254         // postfix -- intentionally omitted

   255 

   256         // Comparison.

   257         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }

   258         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }

   259 

   260         operator const_iterator() const { return m_iterator; }

   261 

   262     private:

   263         Node* node() { return m_iterator.node(); }

   264 

   265         const_iterator m_iterator;

   266     };

   267 

   268     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {

   269     private:

   270         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;

   271         typedef ListHashSetIterator<ValueArg, HashArg> iterator;

   272         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;

   273         typedef ListHashSetNode<ValueArg> Node;

   274         typedef ValueArg ValueType;

   275         typedef const ValueType& ReferenceType;

   276         typedef const ValueType* PointerType;

   277 

   278         friend class ListHashSet<ValueArg, HashArg>;

   279         friend class ListHashSetIterator<ValueArg, HashArg>;

   280 

   281         ListHashSetConstIterator(const ListHashSetType* set, Node* position)

   282             : m_set(set)

   283             , m_position(position)

   284         {

   285         }

   286 

   287     public:

   288         ListHashSetConstIterator()

   289         {

   290         }

   291 

   292         PointerType get() const

   293         {

   294             return &m_position->m_value;

   295         }

   296         ReferenceType operator*() const { return *get(); }

   297         PointerType operator->() const { return get(); }

   298 

   299         const_iterator& operator++()

   300         {

   301             ASSERT(m_position != 0);

   302             m_position = m_position->m_next;

   303             return *this;

   304         }

   305 

   306         // postfix ++ intentionally omitted

   307 

   308         const_iterator& operator--()

   309         {

   310             ASSERT(m_position != m_set->m_head);

   311             m_position = m_position->m_prev;

   312             return *this;

   313         }

   314 

   315         // postfix -- intentionally omitted

   316 

   317         // Comparison.

   318         bool operator==(const const_iterator& other) const

   319         {

   320             return m_position == other.m_position;

   321         }

   322         bool operator!=(const const_iterator& other) const

   323         {

   324             return m_position != other.m_position;

   325         }

   326 

   327     private:

   328         Node* node() { return m_position; }

   329 

   330         const ListHashSetType* m_set;

   331         Node* m_position;

   332     };

   333 

   334 

   335     template<typename ValueType, typename HashFunctions>

   336     struct ListHashSetTranslator {

   337     private:

   338         typedef ListHashSetNode<ValueType> Node;

   339         typedef ListHashSetNodeAllocator<ValueType> NodeAllocator;

   340     public:

   341         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }

   342         static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }

   343         static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator, unsigned)

   344         {

   345             location = new (allocator) Node(key);

   346         }

   347     };

   348 

   349     template<typename T, typename U>

   350     inline ListHashSet<T, U>::ListHashSet()

   351         : m_head(0)

   352         , m_tail(0)

   353         , m_allocator(new NodeAllocator)

   354     {

   355     }

   356 

   357     template<typename T, typename U>

   358     inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)

   359         : m_head(0)

   360         , m_tail(0)

   361         , m_allocator(new NodeAllocator)

   362     {

   363         const_iterator end = other.end();

   364         for (const_iterator it = other.begin(); it != end; ++it)

   365             add(*it);

   366     }

   367 

   368     template<typename T, typename U>

   369     inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)

   370     {

   371         ListHashSet tmp(other);

   372         swap(tmp);

   373         return *this;

   374     }

   375 

   376     template<typename T, typename U>

   377     inline ListHashSet<T, U>& ListHashSet<T, U>::swap(ListHashSet& other)

   378     {

   379         m_impl.swap(other.m_impl);

   380         std::swap(m_head, other.m_head);

   381         std::swap(m_tail, other.m_tail);

   382         m_allocator.swap(other.m_allocator);

   383         return *this;

   384     }

   385 

   386     template<typename T, typename U>

   387     inline ListHashSet<T, U>::~ListHashSet()

   388     {

   389         deleteAllNodes();

   390     }

   391 

   392     template<typename T, typename U>

   393     inline int ListHashSet<T, U>::size() const

   394     {

   395         return m_impl.size(); 

   396     }

   397 

   398     template<typename T, typename U>

   399     inline int ListHashSet<T, U>::capacity() const

   400     {

   401         return m_impl.capacity(); 

   402     }

   403 

   404     template<typename T, typename U>

   405     inline bool ListHashSet<T, U>::isEmpty() const

   406     {

   407         return m_impl.isEmpty(); 

   408     }

   409 

   410     template<typename T, typename U>

   411     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::begin()

   412     {

   413         return makeIterator(m_head); 

   414     }

   415 

   416     template<typename T, typename U>

   417     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::end()

   418     {

   419         return makeIterator(0);

   420     }

   421 

   422     template<typename T, typename U>

   423     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::begin() const

   424     {

   425         return makeConstIterator(m_head); 

   426     }

   427 

   428     template<typename T, typename U>

   429     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::end() const

   430     {

   431         return makeConstIterator(0); 

   432     }

   433 

   434     template<typename T, typename U>

   435     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::find(const ValueType& value)

   436     {

   437         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;

   438         typename ImplType::iterator it ( m_impl.template find<ValueType, Translator>(value) );

   439         if (it == m_impl.end())

   440             return end();

   441         return makeIterator(*it); 

   442     }

   443 

   444     template<typename T, typename U>

   445     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::find(const ValueType& value) const

   446     {

   447         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;

   448         typename ImplType::const_iterator it;

   449         it = m_impl.template find<ValueType, Translator>(value);

   450         if (it == m_impl.end())

   451             return end();

   452         return makeConstIterator(*it);

   453     }

   454 

   455     template<typename T, typename U>

   456     inline bool ListHashSet<T, U>::contains(const ValueType& value) const

   457     {

   458         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;

   459         return m_impl.template contains<ValueType, Translator>(value);

   460     }

   461 

   462     template<typename T, typename U>

   463     pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::add(const ValueType &value)

   464     {

   465         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;

   466         pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());

   467         if (result.second)

   468             appendNode(*result.first);

   469         return std::make_pair(makeIterator(*result.first), result.second);

   470     }

   471 

   472     template<typename T, typename U>

   473     inline void ListHashSet<T, U>::remove(iterator it)

   474     {

   475         if (it == end())

   476             return;

   477         m_impl.remove(it.node());

   478         unlinkAndDelete(it.node());

   479     }

   480 

   481     template<typename T, typename U>

   482     inline void ListHashSet<T, U>::remove(const ValueType& value)

   483     {

   484         remove(find(value));

   485     }

   486 

   487     template<typename T, typename U>

   488     inline void ListHashSet<T, U>::clear()

   489     {

   490         deleteAllNodes();

   491         m_impl.clear(); 

   492         m_head = 0;

   493         m_tail = 0;

   494     }

   495 

   496     template<typename T, typename U>

   497     void ListHashSet<T, U>::unlinkAndDelete(Node* node)

   498     {

   499         if (!node->m_prev) {

   500             ASSERT(node == m_head);

   501             m_head = node->m_next;

   502         } else {

   503             ASSERT(node != m_head);

   504             node->m_prev->m_next = node->m_next;

   505         }

   506 

   507         if (!node->m_next) {

   508             ASSERT(node == m_tail);

   509             m_tail = node->m_prev;

   510         } else {

   511             ASSERT(node != m_tail);

   512             node->m_next->m_prev = node->m_prev;

   513         }

   514 

   515         node->destroy(m_allocator.get());

   516     }

   517 

   518     template<typename T, typename U>

   519     void ListHashSet<T, U>::appendNode(Node* node)

   520     {

   521         node->m_prev = m_tail;

   522         node->m_next = 0;

   523 

   524         if (m_tail) {

   525             ASSERT(m_head);

   526             m_tail->m_next = node;

   527         } else {

   528             ASSERT(!m_head);

   529             m_head = node;

   530         }

   531 

   532         m_tail = node;

   533     }

   534 

   535     template<typename T, typename U>

   536     void ListHashSet<T, U>::deleteAllNodes()

   537     {

   538         if (!m_head)

   539             return;

   540 

   541         for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)

   542             node->destroy(m_allocator.get());

   543     }

   544 

   545     template<typename T, typename U>

   546     inline ListHashSetIterator<T, U> ListHashSet<T, U>::makeIterator(Node* position) 

   547     {

   548         return ListHashSetIterator<T, U>(this, position); 

   549     }

   550 

   551     template<typename T, typename U>

   552     inline ListHashSetConstIterator<T, U> ListHashSet<T, U>::makeConstIterator(Node* position) const

   553     { 

   554         return ListHashSetConstIterator<T, U>(this, position); 

   555     }

   556 

   557     template<bool, typename ValueType, typename HashTableType>

   558     void deleteAllValues(HashTableType& collection)

   559     {

   560         typedef typename HashTableType::const_iterator iterator;

   561         iterator end = collection.end();

   562         for (iterator it = collection.begin(); it != end; ++it)

   563             delete (*it)->m_value;

   564     }

   565 

   566     template<typename T, typename U>

   567     inline void deleteAllValues(const ListHashSet<T, U>& collection)

   568     {

   569         deleteAllValues<true, typename ListHashSet<T, U>::ValueType>(collection.m_impl);

   570     }

   571 

   572 } // namespace WTF

   573 

   574 using WTF::ListHashSet;

   575 

   576 #endif /* WTF_ListHashSet_h */