wtf/ListHashSet.h

   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         void 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         static const bool safeToCompareToEmptyOrDeleted = false;
 224     };
 225
 226     template<typename ValueArg, typename HashArg> class ListHashSetIterator {
 227     private:
 228         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
 229         typedef ListHashSetIterator<ValueArg, HashArg> iterator;
 230         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
 231         typedef ListHashSetNode<ValueArg> Node;
 232         typedef ValueArg ValueType;
 233         typedef ValueType& ReferenceType;
 234         typedef ValueType* PointerType;
 235
 236         friend class ListHashSet<ValueArg, HashArg>;
 237
 238         ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
 239
 240     public:
 241         ListHashSetIterator() { }
 242
 243         // default copy, assignment and destructor are OK
 244
 245         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
 246         ReferenceType operator*() const { return *get(); }
 247         PointerType operator->() const { return get(); }
 248
 249         iterator& operator++() { ++m_iterator; return *this; }
 250
 251         // postfix ++ intentionally omitted
 252
 253         iterator& operator--() { --m_iterator; return *this; }
 254
 255         // postfix -- intentionally omitted
 256
 257         // Comparison.
 258         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
 259         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
 260
 261         operator const_iterator() const { return m_iterator; }
 262
 263     private:
 264         Node* node() { return m_iterator.node(); }
 265
 266         const_iterator m_iterator;
 267     };
 268
 269     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {
 270     private:
 271         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
 272         typedef ListHashSetIterator<ValueArg, HashArg> iterator;
 273         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
 274         typedef ListHashSetNode<ValueArg> Node;
 275         typedef ValueArg ValueType;
 276         typedef const ValueType& ReferenceType;
 277         typedef const ValueType* PointerType;
 278
 279         friend class ListHashSet<ValueArg, HashArg>;
 280         friend class ListHashSetIterator<ValueArg, HashArg>;
 281
 282         ListHashSetConstIterator(const ListHashSetType* set, Node* position)
 283             : m_set(set)
 284             , m_position(position)
 285         {
 286         }
 287
 288     public:
 289         ListHashSetConstIterator()
 290         {
 291         }
 292
 293         PointerType get() const
 294         {
 295             return &m_position->m_value;
 296         }
 297         ReferenceType operator*() const { return *get(); }
 298         PointerType operator->() const { return get(); }
 299
 300         const_iterator& operator++()
 301         {
 302             ASSERT(m_position != 0);
 303             m_position = m_position->m_next;
 304             return *this;
 305         }
 306
 307         // postfix ++ intentionally omitted
 308
 309         const_iterator& operator--()
 310         {
 311             ASSERT(m_position != m_set->m_head);
 312             m_position = m_position->m_prev;
 313             return *this;
 314         }
 315
 316         // postfix -- intentionally omitted
 317
 318         // Comparison.
 319         bool operator==(const const_iterator& other) const
 320         {
 321             return m_position == other.m_position;
 322         }
 323         bool operator!=(const const_iterator& other) const
 324         {
 325             return m_position != other.m_position;
 326         }
 327
 328     private:
 329         Node* node() { return m_position; }
 330
 331         const ListHashSetType* m_set;
 332         Node* m_position;
 333     };
 334
 335
 336     template<typename ValueType, typename HashFunctions>
 337     struct ListHashSetTranslator {
 338     private:
 339         typedef ListHashSetNode<ValueType> Node;
 340         typedef ListHashSetNodeAllocator<ValueType> NodeAllocator;
 341     public:
 342         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
 343         static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
 344         static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
 345         {
 346             location = new (allocator) Node(key);
 347         }
 348     };
 349
 350     template<typename T, typename U>
 351     inline ListHashSet<T, U>::ListHashSet()
 352         : m_head(0)
 353         , m_tail(0)
 354         , m_allocator(new NodeAllocator)
 355     {
 356     }
 357
 358     template<typename T, typename U>
 359     inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
 360         : m_head(0)
 361         , m_tail(0)
 362         , m_allocator(new NodeAllocator)
 363     {
 364         const_iterator end = other.end();
 365         for (const_iterator it = other.begin(); it != end; ++it)
 366             add(*it);
 367     }
 368
 369     template<typename T, typename U>
 370     inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
 371     {
 372         ListHashSet tmp(other);
 373         swap(tmp);
 374         return *this;
 375     }
 376
 377     template<typename T, typename U>
 378     inline void ListHashSet<T, U>::swap(ListHashSet& other)
 379     {
 380         m_impl.swap(other.m_impl);
 381         std::swap(m_head, other.m_head);
 382         std::swap(m_tail, other.m_tail);
 383         m_allocator.swap(other.m_allocator);
 384         return *this;
 385     }
 386
 387     template<typename T, typename U>
 388     inline ListHashSet<T, U>::~ListHashSet()
 389     {
 390         deleteAllNodes();
 391     }
 392
 393     template<typename T, typename U>
 394     inline int ListHashSet<T, U>::size() const
 395     {
 396         return m_impl.size();
 397     }
 398
 399     template<typename T, typename U>
 400     inline int ListHashSet<T, U>::capacity() const
 401     {
 402         return m_impl.capacity();
 403     }
 404
 405     template<typename T, typename U>
 406     inline bool ListHashSet<T, U>::isEmpty() const
 407     {
 408         return m_impl.isEmpty();
 409     }
 410
 411     template<typename T, typename U>
 412     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::begin()
 413     {
 414         return makeIterator(m_head);
 415     }
 416
 417     template<typename T, typename U>
 418     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::end()
 419     {
 420         return makeIterator(0);
 421     }
 422
 423     template<typename T, typename U>
 424     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::begin() const
 425     {
 426         return makeConstIterator(m_head);
 427     }
 428
 429     template<typename T, typename U>
 430     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::end() const
 431     {
 432         return makeConstIterator(0);
 433     }
 434
 435     template<typename T, typename U>
 436     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::find(const ValueType& value)
 437     {
 438         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 439         typename ImplType::iterator it = m_impl.template find<ValueType, Translator>(value);
 440         if (it == m_impl.end())
 441             return end();
 442         return makeIterator(*it);
 443     }
 444
 445     template<typename T, typename U>
 446     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::find(const ValueType& value) const
 447     {
 448         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 449         typename ImplType::const_iterator 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 */