wtf/ListHashSet.h

   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_ListHashSet_h
  22 #define WTF_ListHashSet_h
  23
  24 #include "Assertions.h"
  25 #include "HashSet.h"
  26 #include "OwnPtr.h"
  27
  28 namespace WTF {
  29
  30     // ListHashSet: Just like HashSet, this class provides a Set
  31     // interface - a collection of unique objects with O(1) insertion,
  32     // removal and test for containership. However, it also has an
  33     // order - iterating it will always give back values in the order
  34     // in which they are added.
  35
  36     // In theory it would be possible to add prepend, insertAfter
  37     // and an append that moves the element to the end even if already present,
  38     // but unclear yet if these are needed.
  39
  40     template<typename Value, typename HashFunctions> class ListHashSet;
  41
  42     template<typename T> struct IdentityExtractor;
  43
  44     template<typename Value, typename HashFunctions>
  45     void deleteAllValues(const ListHashSet<Value, HashFunctions>&);
  46
  47     template<typename ValueArg, typename HashArg> class ListHashSetIterator;
  48     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;
  49
  50     template<typename ValueArg> struct ListHashSetNode;
  51     template<typename ValueArg> struct ListHashSetNodeAllocator;
  52     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;
  53
  54     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
  55     private:
  56         typedef ListHashSetNode<ValueArg> Node;
  57         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
  58
  59         typedef HashTraits<Node*> NodeTraits;
  60         typedef ListHashSetNodeHashFunctions<ValueArg, HashArg> NodeHash;
  61
  62         typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
  63         typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
  64         typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;
  65
  66         typedef HashArg HashFunctions;
  67
  68     public:
  69         typedef ValueArg ValueType;
  70         typedef ListHashSetIterator<ValueType, HashArg> iterator;
  71         typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;
  72
  73         friend class ListHashSetConstIterator<ValueType, HashArg>;
  74
  75         ListHashSet();
  76         ListHashSet(const ListHashSet&);
  77         ListHashSet& operator=(const ListHashSet&);
  78         ~ListHashSet();
  79
  80         void swap(ListHashSet&);
  81
  82         int size() const;
  83         int capacity() const;
  84         bool isEmpty() const;
  85
  86         iterator begin();
  87         iterator end();
  88         const_iterator begin() const;
  89         const_iterator end() const;
  90
  91         iterator find(const ValueType&);
  92         const_iterator find(const ValueType&) const;
  93         bool contains(const ValueType&) const;
  94
  95         // the return value is a pair of an iterator to the new value's location,
  96         // and a bool that is true if an new entry was added
  97         pair<iterator, bool> add(const ValueType&);
  98
  99         pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue);
 100         pair<iterator, bool> insertBefore(iterator it, const ValueType&);
 101
 102         void remove(const ValueType&);
 103         void remove(iterator);
 104         void clear();
 105
 106     private:
 107         void unlinkAndDelete(Node*);
 108         void appendNode(Node*);
 109         void insertNodeBefore(Node* beforeNode, Node* newNode);
 110         void deleteAllNodes();
 111         iterator makeIterator(Node*);
 112         const_iterator makeConstIterator(Node*) const;
 113
 114         friend void deleteAllValues<>(const ListHashSet&);
 115
 116         ImplType m_impl;
 117         Node* m_head;
 118         Node* m_tail;
 119         OwnPtr<NodeAllocator> m_allocator;
 120     };
 121
 122     template<typename ValueArg> struct ListHashSetNodeAllocator {
 123         typedef ListHashSetNode<ValueArg> Node;
 124         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
 125
 126         ListHashSetNodeAllocator()
 127             : m_freeList(pool())
 128             , m_isDoneWithInitialFreeList(false)
 129         {
 130             memset(m_pool.pool, 0, sizeof(m_pool.pool));
 131         }
 132
 133         Node* allocate()
 134         {
 135             Node* result = m_freeList;
 136
 137             if (!result)
 138                 return static_cast<Node*>(fastMalloc(sizeof(Node)));
 139
 140             ASSERT(!result->m_isAllocated);
 141
 142             Node* next = result->m_next;
 143             ASSERT(!next || !next->m_isAllocated);
 144             if (!next && !m_isDoneWithInitialFreeList) {
 145                 next = result + 1;
 146                 if (next == pastPool()) {
 147                     m_isDoneWithInitialFreeList = true;
 148                     next = 0;
 149                 } else {
 150                     ASSERT(inPool(next));
 151                     ASSERT(!next->m_isAllocated);
 152                 }
 153             }
 154             m_freeList = next;
 155
 156             return result;
 157         }
 158
 159         void deallocate(Node* node)
 160         {
 161             if (inPool(node)) {
 162 #ifndef NDEBUG
 163                 node->m_isAllocated = false;
 164 #endif
 165                 node->m_next = m_freeList;
 166                 m_freeList = node;
 167                 return;
 168             }
 169
 170             fastFree(node);
 171         }
 172
 173     private:
 174         Node* pool() { return reinterpret_cast<Node*>(m_pool.pool); }
 175         Node* pastPool() { return pool() + m_poolSize; }
 176
 177         bool inPool(Node* node)
 178         {
 179             return node >= pool() && node < pastPool();
 180         }
 181
 182         Node* m_freeList;
 183         bool m_isDoneWithInitialFreeList;
 184         static const size_t m_poolSize = 256;
 185         union {
 186             char pool[sizeof(Node) * m_poolSize];
 187             double forAlignment;
 188         } m_pool;
 189     };
 190
 191     template<typename ValueArg> struct ListHashSetNode {
 192         typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;
 193
 194         ListHashSetNode(ValueArg value)
 195             : m_value(value)
 196             , m_prev(0)
 197             , m_next(0)
 198 #ifndef NDEBUG
 199             , m_isAllocated(true)
 200 #endif
 201         {
 202         }
 203
 204         void* operator new(size_t, NodeAllocator* allocator)
 205         {
 206             return allocator->allocate();
 207         }
 208         void destroy(NodeAllocator* allocator)
 209         {
 210             this->~ListHashSetNode();
 211             allocator->deallocate(this);
 212         }
 213
 214         ValueArg m_value;
 215         ListHashSetNode* m_prev;
 216         ListHashSetNode* m_next;
 217
 218 #ifndef NDEBUG
 219         bool m_isAllocated;
 220 #endif
 221     };
 222
 223     template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions {
 224         typedef ListHashSetNode<ValueArg> Node;
 225
 226         static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
 227         static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
 228         static const bool safeToCompareToEmptyOrDeleted = false;
 229     };
 230
 231     template<typename ValueArg, typename HashArg> class ListHashSetIterator {
 232     private:
 233         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
 234         typedef ListHashSetIterator<ValueArg, HashArg> iterator;
 235         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
 236         typedef ListHashSetNode<ValueArg> Node;
 237         typedef ValueArg ValueType;
 238         typedef ValueType& ReferenceType;
 239         typedef ValueType* PointerType;
 240
 241         friend class ListHashSet<ValueArg, HashArg>;
 242
 243         ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
 244
 245     public:
 246         ListHashSetIterator() { }
 247
 248         // default copy, assignment and destructor are OK
 249
 250         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
 251         ReferenceType operator*() const { return *get(); }
 252         PointerType operator->() const { return get(); }
 253
 254         iterator& operator++() { ++m_iterator; return *this; }
 255
 256         // postfix ++ intentionally omitted
 257
 258         iterator& operator--() { --m_iterator; return *this; }
 259
 260         // postfix -- intentionally omitted
 261
 262         // Comparison.
 263         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
 264         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
 265
 266         operator const_iterator() const { return m_iterator; }
 267
 268     private:
 269         Node* node() { return m_iterator.node(); }
 270
 271         const_iterator m_iterator;
 272     };
 273
 274     template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {
 275     private:
 276         typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
 277         typedef ListHashSetIterator<ValueArg, HashArg> iterator;
 278         typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
 279         typedef ListHashSetNode<ValueArg> Node;
 280         typedef ValueArg ValueType;
 281         typedef const ValueType& ReferenceType;
 282         typedef const ValueType* PointerType;
 283
 284         friend class ListHashSet<ValueArg, HashArg>;
 285         friend class ListHashSetIterator<ValueArg, HashArg>;
 286
 287         ListHashSetConstIterator(const ListHashSetType* set, Node* position)
 288             : m_set(set)
 289             , m_position(position)
 290         {
 291         }
 292
 293     public:
 294         ListHashSetConstIterator()
 295         {
 296         }
 297
 298         PointerType get() const
 299         {
 300             return &m_position->m_value;
 301         }
 302         ReferenceType operator*() const { return *get(); }
 303         PointerType operator->() const { return get(); }
 304
 305         const_iterator& operator++()
 306         {
 307             ASSERT(m_position != 0);
 308             m_position = m_position->m_next;
 309             return *this;
 310         }
 311
 312         // postfix ++ intentionally omitted
 313
 314         const_iterator& operator--()
 315         {
 316             ASSERT(m_position != m_set->m_head);
 317             if (!m_position)
 318                 m_position = m_set->m_tail;
 319             else
 320                 m_position = m_position->m_prev;
 321             return *this;
 322         }
 323
 324         // postfix -- intentionally omitted
 325
 326         // Comparison.
 327         bool operator==(const const_iterator& other) const
 328         {
 329             return m_position == other.m_position;
 330         }
 331         bool operator!=(const const_iterator& other) const
 332         {
 333             return m_position != other.m_position;
 334         }
 335
 336     private:
 337         Node* node() { return m_position; }
 338
 339         const ListHashSetType* m_set;
 340         Node* m_position;
 341     };
 342
 343
 344     template<typename ValueType, typename HashFunctions>
 345     struct ListHashSetTranslator {
 346     private:
 347         typedef ListHashSetNode<ValueType> Node;
 348         typedef ListHashSetNodeAllocator<ValueType> NodeAllocator;
 349     public:
 350         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
 351         static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
 352         static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
 353         {
 354             location = new (allocator) Node(key);
 355         }
 356     };
 357
 358     template<typename T, typename U>
 359     inline ListHashSet<T, U>::ListHashSet()
 360         : m_head(0)
 361         , m_tail(0)
 362         , m_allocator(new NodeAllocator)
 363     {
 364     }
 365
 366     template<typename T, typename U>
 367     inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
 368         : m_head(0)
 369         , m_tail(0)
 370         , m_allocator(new NodeAllocator)
 371     {
 372         const_iterator end = other.end();
 373         for (const_iterator it = other.begin(); it != end; ++it)
 374             add(*it);
 375     }
 376
 377     template<typename T, typename U>
 378     inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
 379     {
 380         ListHashSet tmp(other);
 381         swap(tmp);
 382         return *this;
 383     }
 384
 385     template<typename T, typename U>
 386     inline void ListHashSet<T, U>::swap(ListHashSet& other)
 387     {
 388         m_impl.swap(other.m_impl);
 389         std::swap(m_head, other.m_head);
 390         std::swap(m_tail, other.m_tail);
 391         m_allocator.swap(other.m_allocator);
 392     }
 393
 394     template<typename T, typename U>
 395     inline ListHashSet<T, U>::~ListHashSet()
 396     {
 397         deleteAllNodes();
 398     }
 399
 400     template<typename T, typename U>
 401     inline int ListHashSet<T, U>::size() const
 402     {
 403         return m_impl.size();
 404     }
 405
 406     template<typename T, typename U>
 407     inline int ListHashSet<T, U>::capacity() const
 408     {
 409         return m_impl.capacity();
 410     }
 411
 412     template<typename T, typename U>
 413     inline bool ListHashSet<T, U>::isEmpty() const
 414     {
 415         return m_impl.isEmpty();
 416     }
 417
 418     template<typename T, typename U>
 419     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::begin()
 420     {
 421         return makeIterator(m_head);
 422     }
 423
 424     template<typename T, typename U>
 425     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::end()
 426     {
 427         return makeIterator(0);
 428     }
 429
 430     template<typename T, typename U>
 431     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::begin() const
 432     {
 433         return makeConstIterator(m_head);
 434     }
 435
 436     template<typename T, typename U>
 437     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::end() const
 438     {
 439         return makeConstIterator(0);
 440     }
 441
 442     template<typename T, typename U>
 443     inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::find(const ValueType& value)
 444     {
 445         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 446         ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value);
 447         if (it == m_impl.end())
 448             return end();
 449         return makeIterator(*it);
 450     }
 451
 452     template<typename T, typename U>
 453     inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::find(const ValueType& value) const
 454     {
 455         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 456         ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value);
 457         if (it == m_impl.end())
 458             return end();
 459         return makeConstIterator(*it);
 460     }
 461
 462     template<typename T, typename U>
 463     inline bool ListHashSet<T, U>::contains(const ValueType& value) const
 464     {
 465         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 466         return m_impl.template contains<ValueType, Translator>(value);
 467     }
 468
 469     template<typename T, typename U>
 470     pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::add(const ValueType &value)
 471     {
 472         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 473         pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());
 474         if (result.second)
 475             appendNode(*result.first);
 476         return std::make_pair(makeIterator(*result.first), result.second);
 477     }
 478
 479     template<typename T, typename U>
 480     pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::insertBefore(iterator it, const ValueType& newValue)
 481     {
 482         typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
 483         pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get());
 484         if (result.second)
 485             insertNodeBefore(it.node(), *result.first);
 486         return std::make_pair(makeIterator(*result.first), result.second);
 487
 488     }
 489
 490     template<typename T, typename U>
 491     pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
 492     {
 493         return insertBefore(find(beforeValue), newValue);
 494     }
 495
 496     template<typename T, typename U>
 497     inline void ListHashSet<T, U>::remove(iterator it)
 498     {
 499         if (it == end())
 500             return;
 501         m_impl.remove(it.node());
 502         unlinkAndDelete(it.node());
 503     }
 504
 505     template<typename T, typename U>
 506     inline void ListHashSet<T, U>::remove(const ValueType& value)
 507     {
 508         remove(find(value));
 509     }
 510
 511     template<typename T, typename U>
 512     inline void ListHashSet<T, U>::clear()
 513     {
 514         deleteAllNodes();
 515         m_impl.clear();
 516         m_head = 0;
 517         m_tail = 0;
 518     }
 519
 520     template<typename T, typename U>
 521     void ListHashSet<T, U>::unlinkAndDelete(Node* node)
 522     {
 523         if (!node->m_prev) {
 524             ASSERT(node == m_head);
 525             m_head = node->m_next;
 526         } else {
 527             ASSERT(node != m_head);
 528             node->m_prev->m_next = node->m_next;
 529         }
 530
 531         if (!node->m_next) {
 532             ASSERT(node == m_tail);
 533             m_tail = node->m_prev;
 534         } else {
 535             ASSERT(node != m_tail);
 536             node->m_next->m_prev = node->m_prev;
 537         }
 538
 539         node->destroy(m_allocator.get());
 540     }
 541
 542     template<typename T, typename U>
 543     void ListHashSet<T, U>::appendNode(Node* node)
 544     {
 545         node->m_prev = m_tail;
 546         node->m_next = 0;
 547
 548         if (m_tail) {
 549             ASSERT(m_head);
 550             m_tail->m_next = node;
 551         } else {
 552             ASSERT(!m_head);
 553             m_head = node;
 554         }
 555
 556         m_tail = node;
 557     }
 558
 559     template<typename T, typename U>
 560     void ListHashSet<T, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
 561     {
 562         if (!beforeNode)
 563             return appendNode(newNode);
 564
 565         newNode->m_next = beforeNode;
 566         newNode->m_prev = beforeNode->m_prev;
 567         if (beforeNode->m_prev)
 568             beforeNode->m_prev->m_next = newNode;
 569         beforeNode->m_prev = newNode;
 570
 571         if (!newNode->m_prev)
 572             m_head = newNode;
 573     }
 574
 575     template<typename T, typename U>
 576     void ListHashSet<T, U>::deleteAllNodes()
 577     {
 578         if (!m_head)
 579             return;
 580
 581         for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
 582             node->destroy(m_allocator.get());
 583     }
 584
 585     template<typename T, typename U>
 586     inline ListHashSetIterator<T, U> ListHashSet<T, U>::makeIterator(Node* position)
 587     {
 588         return ListHashSetIterator<T, U>(this, position);
 589     }
 590
 591     template<typename T, typename U>
 592     inline ListHashSetConstIterator<T, U> ListHashSet<T, U>::makeConstIterator(Node* position) const
 593     {
 594         return ListHashSetConstIterator<T, U>(this, position);
 595     }
 596
 597     template<bool, typename ValueType, typename HashTableType>
 598     void deleteAllValues(HashTableType& collection)
 599     {
 600         typedef typename HashTableType::const_iterator iterator;
 601         iterator end = collection.end();
 602         for (iterator it = collection.begin(); it != end; ++it)
 603             delete (*it)->m_value;
 604     }
 605
 606     template<typename T, typename U>
 607     inline void deleteAllValues(const ListHashSet<T, U>& collection)
 608     {
 609         deleteAllValues<true, typename ListHashSet<T, U>::ValueType>(collection.m_impl);
 610     }
 611
 612 } // namespace WTF
 613
 614 using WTF::ListHashSet;
 615
 616 #endif /* WTF_ListHashSet_h */