1/* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012, 2013 Apple Inc. All rights reserved. 3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> 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 <wtf/HashSet.h> 26#include <wtf/OwnPtr.h> 27#include <wtf/PassOwnPtr.h> 28 29namespace 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// Unlike iteration of most WTF Hash data structures, iteration is 38// guaranteed safe against mutation of the ListHashSet, except for 39// removal of the item currently pointed to by a given iterator. 40 41template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet; 42 43template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator; 44template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator; 45 46template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode; 47template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator; 48 49template<typename HashArg> struct ListHashSetNodeHashFunctions; 50template<typename HashArg> struct ListHashSetTranslator; 51 52template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet { 53 WTF_MAKE_FAST_ALLOCATED; 54private: 55 typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 56 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 57 58 typedef HashTraits<Node*> NodeTraits; 59 typedef ListHashSetNodeHashFunctions<HashArg> NodeHash; 60 typedef ListHashSetTranslator<HashArg> BaseTranslator; 61 62 typedef HashArg HashFunctions; 63 64public: 65 typedef ValueArg ValueType; 66 67 typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator; 68 typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator; 69 friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>; 70 71 typedef std::reverse_iterator<iterator> reverse_iterator; 72 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 73 74 typedef HashTableAddResult<iterator> AddResult; 75 76 ListHashSet(); 77 ListHashSet(const ListHashSet&); 78 ListHashSet& operator=(const ListHashSet&); 79 ~ListHashSet(); 80 81 void swap(ListHashSet&); 82 83 int size() const; 84 int capacity() const; 85 bool isEmpty() const; 86 87 iterator begin() { return makeIterator(m_head); } 88 iterator end() { return makeIterator(nullptr); } 89 const_iterator begin() const { return makeConstIterator(m_head); } 90 const_iterator end() const { return makeConstIterator(nullptr); } 91 92 reverse_iterator rbegin() { return reverse_iterator(end()); } 93 reverse_iterator rend() { return reverse_iterator(begin()); } 94 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 95 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 96 97 ValueType& first(); 98 const ValueType& first() const; 99 void removeFirst(); 100 ValueType takeFirst(); 101 102 ValueType& last(); 103 const ValueType& last() const; 104 void removeLast(); 105 ValueType takeLast(); 106 107 iterator find(const ValueType&); 108 const_iterator find(const ValueType&) const; 109 bool contains(const ValueType&) const; 110 111 // An alternate version of find() that finds the object by hashing and comparing 112 // with some other type, to avoid the cost of type conversion. 113 // The HashTranslator interface is defined in HashSet. 114 // FIXME: We should reverse the order of the template arguments so that callers 115 // can just pass the translator let the compiler deduce T. 116 template<typename T, typename HashTranslator> iterator find(const T&); 117 template<typename T, typename HashTranslator> const_iterator find(const T&) const; 118 template<typename T, typename HashTranslator> bool contains(const T&) const; 119 120 // The return value of add is a pair of an iterator to the new value's location, 121 // and a bool that is true if an new entry was added. 122 AddResult add(const ValueType&); 123 AddResult add(ValueType&&); 124 125 // Add the value to the end of the collection. If the value was already in 126 // the list, it is moved to the end. 127 AddResult appendOrMoveToLast(const ValueType&); 128 AddResult appendOrMoveToLast(ValueType&&); 129 130 // Add the value to the beginning of the collection. If the value was already in 131 // the list, it is moved to the beginning. 132 AddResult prependOrMoveToFirst(const ValueType&); 133 AddResult prependOrMoveToFirst(ValueType&&); 134 135 AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue); 136 AddResult insertBefore(const ValueType& beforeValue, ValueType&& newValue); 137 AddResult insertBefore(iterator, const ValueType&); 138 AddResult insertBefore(iterator, ValueType&&); 139 140 bool remove(const ValueType&); 141 bool remove(iterator); 142 void clear(); 143 144private: 145 void unlink(Node*); 146 void unlinkAndDelete(Node*); 147 void appendNode(Node*); 148 void prependNode(Node*); 149 void insertNodeBefore(Node* beforeNode, Node* newNode); 150 void deleteAllNodes(); 151 152 iterator makeIterator(Node*); 153 const_iterator makeConstIterator(Node*) const; 154 155 HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> m_impl; 156 Node* m_head; 157 Node* m_tail; 158 std::unique_ptr<NodeAllocator> m_allocator; 159}; 160 161template<typename ValueArg, size_t inlineCapacity> class ListHashSetNodeAllocator { 162 WTF_MAKE_FAST_ALLOCATED; 163 164public: 165 typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 166 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 167 168 ListHashSetNodeAllocator() 169 : m_freeList(pool()) 170 , m_isDoneWithInitialFreeList(false) 171 { 172 memset(m_pool.pool, 0, sizeof(m_pool.pool)); 173 } 174 175 Node* allocate() 176 { 177 Node* result = m_freeList; 178 179 if (!result) 180 return static_cast<Node*>(fastMalloc(sizeof(Node))); 181 182 ASSERT(!result->m_isAllocated); 183 184 Node* next = result->m_next; 185 ASSERT(!next || !next->m_isAllocated); 186 if (!next && !m_isDoneWithInitialFreeList) { 187 next = result + 1; 188 if (next == pastPool()) { 189 m_isDoneWithInitialFreeList = true; 190 next = 0; 191 } else { 192 ASSERT(inPool(next)); 193 ASSERT(!next->m_isAllocated); 194 } 195 } 196 m_freeList = next; 197 198 return result; 199 } 200 201 void deallocate(Node* node) 202 { 203 if (inPool(node)) { 204#ifndef NDEBUG 205 node->m_isAllocated = false; 206#endif 207 node->m_next = m_freeList; 208 m_freeList = node; 209 return; 210 } 211 212 fastFree(node); 213 } 214 215private: 216 Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); } 217 Node* pastPool() { return pool() + m_poolSize; } 218 bool inPool(Node* node) 219 { 220 return node >= pool() && node < pastPool(); 221 } 222 223 Node* m_freeList; 224 bool m_isDoneWithInitialFreeList; 225 static const size_t m_poolSize = inlineCapacity; 226 union { 227 char pool[sizeof(Node) * m_poolSize]; 228 double forAlignment; 229 } m_pool; 230}; 231 232template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode { 233 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator; 234 235 template<typename T> 236 ListHashSetNode(T&& value) 237 : m_value(std::forward<T>(value)) 238 , m_prev(0) 239 , m_next(0) 240#ifndef NDEBUG 241 , m_isAllocated(true) 242#endif 243 { 244 } 245 246 void* operator new(size_t, NodeAllocator* allocator) 247 { 248 return allocator->allocate(); 249 } 250 void destroy(NodeAllocator* allocator) 251 { 252 this->~ListHashSetNode(); 253 allocator->deallocate(this); 254 } 255 256 ValueArg m_value; 257 ListHashSetNode* m_prev; 258 ListHashSetNode* m_next; 259 260#ifndef NDEBUG 261 bool m_isAllocated; 262#endif 263}; 264 265template<typename HashArg> struct ListHashSetNodeHashFunctions { 266 template<typename T> static unsigned hash(const T& key) { return HashArg::hash(key->m_value); } 267 template<typename T> static bool equal(const T& a, const T& b) { return HashArg::equal(a->m_value, b->m_value); } 268 static const bool safeToCompareToEmptyOrDeleted = false; 269}; 270 271template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator { 272private: 273 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 274 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 275 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 276 typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 277 typedef ValueArg ValueType; 278 279 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 280 281 ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { } 282 283public: 284 typedef ptrdiff_t difference_type; 285 typedef ValueType value_type; 286 typedef ValueType* pointer; 287 typedef ValueType& reference; 288 typedef std::bidirectional_iterator_tag iterator_category; 289 290 ListHashSetIterator() { } 291 292 // default copy, assignment and destructor are OK 293 294 ValueType* get() const { return const_cast<ValueType*>(m_iterator.get()); } 295 ValueType& operator*() const { return *get(); } 296 ValueType* operator->() const { return get(); } 297 298 iterator& operator++() { ++m_iterator; return *this; } 299 300 // postfix ++ intentionally omitted 301 302 iterator& operator--() { --m_iterator; return *this; } 303 304 // postfix -- intentionally omitted 305 306 // Comparison. 307 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 308 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 309 310 operator const_iterator() const { return m_iterator; } 311 312private: 313 Node* node() { return m_iterator.node(); } 314 315 const_iterator m_iterator; 316}; 317 318template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator { 319private: 320 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType; 321 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator; 322 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator; 323 typedef ListHashSetNode<ValueArg, inlineCapacity> Node; 324 typedef ValueArg ValueType; 325 326 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>; 327 friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>; 328 329 ListHashSetConstIterator(const ListHashSetType* set, Node* position) 330 : m_set(set) 331 , m_position(position) 332 { 333 } 334 335public: 336 typedef ptrdiff_t difference_type; 337 typedef const ValueType value_type; 338 typedef const ValueType* pointer; 339 typedef const ValueType& reference; 340 typedef std::bidirectional_iterator_tag iterator_category; 341 342 ListHashSetConstIterator() 343 { 344 } 345 346 const ValueType* get() const 347 { 348 return &m_position->m_value; 349 } 350 351 const ValueType& operator*() const { return *get(); } 352 const ValueType* operator->() const { return get(); } 353 354 const_iterator& operator++() 355 { 356 ASSERT(m_position != 0); 357 m_position = m_position->m_next; 358 return *this; 359 } 360 361 // postfix ++ intentionally omitted 362 363 const_iterator& operator--() 364 { 365 ASSERT(m_position != m_set->m_head); 366 if (!m_position) 367 m_position = m_set->m_tail; 368 else 369 m_position = m_position->m_prev; 370 return *this; 371 } 372 373 // postfix -- intentionally omitted 374 375 // Comparison. 376 bool operator==(const const_iterator& other) const 377 { 378 return m_position == other.m_position; 379 } 380 bool operator!=(const const_iterator& other) const 381 { 382 return m_position != other.m_position; 383 } 384 385private: 386 Node* node() { return m_position; } 387 388 const ListHashSetType* m_set; 389 Node* m_position; 390}; 391 392template<typename HashFunctions> 393struct ListHashSetTranslator { 394 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 395 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); } 396 template<typename T, typename U, typename V> static void translate(T*& location, U&& key, const V& allocator) 397 { 398 location = new (allocator) T(std::forward<U>(key)); 399 } 400}; 401 402template<typename T, size_t inlineCapacity, typename U> 403inline ListHashSet<T, inlineCapacity, U>::ListHashSet() 404 : m_head(0) 405 , m_tail(0) 406 , m_allocator(std::make_unique<NodeAllocator>()) 407{ 408} 409 410template<typename T, size_t inlineCapacity, typename U> 411inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other) 412 : m_head(0) 413 , m_tail(0) 414 , m_allocator(std::make_unique<NodeAllocator>()) 415{ 416 for (auto it = other.begin(), end = other.end(); it != end; ++it) 417 add(*it); 418} 419 420template<typename T, size_t inlineCapacity, typename U> 421inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other) 422{ 423 ListHashSet tmp(other); 424 swap(tmp); 425 return *this; 426} 427 428template<typename T, size_t inlineCapacity, typename U> 429inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other) 430{ 431 m_impl.swap(other.m_impl); 432 std::swap(m_head, other.m_head); 433 std::swap(m_tail, other.m_tail); 434 m_allocator.swap(other.m_allocator); 435} 436 437template<typename T, size_t inlineCapacity, typename U> 438inline ListHashSet<T, inlineCapacity, U>::~ListHashSet() 439{ 440 deleteAllNodes(); 441} 442 443template<typename T, size_t inlineCapacity, typename U> 444inline int ListHashSet<T, inlineCapacity, U>::size() const 445{ 446 return m_impl.size(); 447} 448 449template<typename T, size_t inlineCapacity, typename U> 450inline int ListHashSet<T, inlineCapacity, U>::capacity() const 451{ 452 return m_impl.capacity(); 453} 454 455template<typename T, size_t inlineCapacity, typename U> 456inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const 457{ 458 return m_impl.isEmpty(); 459} 460 461template<typename T, size_t inlineCapacity, typename U> 462inline T& ListHashSet<T, inlineCapacity, U>::first() 463{ 464 ASSERT(!isEmpty()); 465 return m_head->m_value; 466} 467 468template<typename T, size_t inlineCapacity, typename U> 469inline void ListHashSet<T, inlineCapacity, U>::removeFirst() 470{ 471 takeFirst(); 472} 473 474template<typename T, size_t inlineCapacity, typename U> 475inline T ListHashSet<T, inlineCapacity, U>::takeFirst() 476{ 477 ASSERT(!isEmpty()); 478 auto it = m_impl.find(m_head); 479 480 T result = WTF::move((*it)->m_value); 481 m_impl.remove(it); 482 unlinkAndDelete(m_head); 483 484 return result; 485} 486 487template<typename T, size_t inlineCapacity, typename U> 488inline const T& ListHashSet<T, inlineCapacity, U>::first() const 489{ 490 ASSERT(!isEmpty()); 491 return m_head->m_value; 492} 493 494template<typename T, size_t inlineCapacity, typename U> 495inline T& ListHashSet<T, inlineCapacity, U>::last() 496{ 497 ASSERT(!isEmpty()); 498 return m_tail->m_value; 499} 500 501template<typename T, size_t inlineCapacity, typename U> 502inline const T& ListHashSet<T, inlineCapacity, U>::last() const 503{ 504 ASSERT(!isEmpty()); 505 return m_tail->m_value; 506} 507 508template<typename T, size_t inlineCapacity, typename U> 509inline void ListHashSet<T, inlineCapacity, U>::removeLast() 510{ 511 takeLast(); 512} 513 514template<typename T, size_t inlineCapacity, typename U> 515inline T ListHashSet<T, inlineCapacity, U>::takeLast() 516{ 517 ASSERT(!isEmpty()); 518 auto it = m_impl.find(m_tail); 519 520 T result = WTF::move((*it)->m_value); 521 m_impl.remove(it); 522 unlinkAndDelete(m_tail); 523 524 return result; 525} 526 527template<typename T, size_t inlineCapacity, typename U> 528inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) -> iterator 529{ 530 auto it = m_impl.template find<BaseTranslator>(value); 531 if (it == m_impl.end()) 532 return end(); 533 return makeIterator(*it); 534} 535 536template<typename T, size_t inlineCapacity, typename U> 537inline auto ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const -> const_iterator 538{ 539 auto it = m_impl.template find<BaseTranslator>(value); 540 if (it == m_impl.end()) 541 return end(); 542 return makeConstIterator(*it); 543} 544 545template<typename Translator> 546struct ListHashSetTranslatorAdapter { 547 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 548 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); } 549}; 550 551template<typename ValueType, size_t inlineCapacity, typename U> 552template<typename T, typename HashTranslator> 553inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) -> iterator 554{ 555 auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value); 556 if (it == m_impl.end()) 557 return end(); 558 return makeIterator(*it); 559} 560 561template<typename ValueType, size_t inlineCapacity, typename U> 562template<typename T, typename HashTranslator> 563inline auto ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const -> const_iterator 564{ 565 auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value); 566 if (it == m_impl.end()) 567 return end(); 568 return makeConstIterator(*it); 569} 570 571template<typename ValueType, size_t inlineCapacity, typename U> 572template<typename T, typename HashTranslator> 573inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const 574{ 575 return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value); 576} 577 578template<typename T, size_t inlineCapacity, typename U> 579inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const 580{ 581 return m_impl.template contains<BaseTranslator>(value); 582} 583 584template<typename T, size_t inlineCapacity, typename U> 585auto ListHashSet<T, inlineCapacity, U>::add(const ValueType& value) -> AddResult 586{ 587 auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 588 if (result.isNewEntry) 589 appendNode(*result.iterator); 590 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 591} 592 593template<typename T, size_t inlineCapacity, typename U> 594auto ListHashSet<T, inlineCapacity, U>::add(ValueType&& value) -> AddResult 595{ 596 auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get()); 597 if (result.isNewEntry) 598 appendNode(*result.iterator); 599 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 600} 601 602template<typename T, size_t inlineCapacity, typename U> 603auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType& value) -> AddResult 604{ 605 auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 606 Node* node = *result.iterator; 607 if (!result.isNewEntry) 608 unlink(node); 609 appendNode(node); 610 611 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 612} 613 614template<typename T, size_t inlineCapacity, typename U> 615auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(ValueType&& value) -> AddResult 616{ 617 auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get()); 618 Node* node = *result.iterator; 619 if (!result.isNewEntry) 620 unlink(node); 621 appendNode(node); 622 623 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 624} 625 626template<typename T, size_t inlineCapacity, typename U> 627auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult 628{ 629 auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get()); 630 Node* node = *result.iterator; 631 if (!result.isNewEntry) 632 unlink(node); 633 prependNode(node); 634 635 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 636} 637 638template<typename T, size_t inlineCapacity, typename U> 639auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult 640{ 641 auto result = m_impl.template add<BaseTranslator>(WTF::move(value), m_allocator.get()); 642 Node* node = *result.iterator; 643 if (!result.isNewEntry) 644 unlink(node); 645 prependNode(node); 646 647 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 648} 649 650template<typename T, size_t inlineCapacity, typename U> 651auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult 652{ 653 return insertBefore(find(beforeValue), newValue); 654} 655 656template<typename T, size_t inlineCapacity, typename U> 657auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult 658{ 659 return insertBefore(find(beforeValue), WTF::move(newValue)); 660} 661 662template<typename T, size_t inlineCapacity, typename U> 663auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult 664{ 665 auto result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get()); 666 if (result.isNewEntry) 667 insertNodeBefore(it.node(), *result.iterator); 668 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 669} 670 671template<typename T, size_t inlineCapacity, typename U> 672auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult 673{ 674 auto result = m_impl.template add<BaseTranslator>(WTF::move(newValue), m_allocator.get()); 675 if (result.isNewEntry) 676 insertNodeBefore(it.node(), *result.iterator); 677 return AddResult(makeIterator(*result.iterator), result.isNewEntry); 678} 679 680template<typename T, size_t inlineCapacity, typename U> 681inline bool ListHashSet<T, inlineCapacity, U>::remove(iterator it) 682{ 683 if (it == end()) 684 return false; 685 m_impl.remove(it.node()); 686 unlinkAndDelete(it.node()); 687 return true; 688} 689 690template<typename T, size_t inlineCapacity, typename U> 691inline bool ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value) 692{ 693 return remove(find(value)); 694} 695 696template<typename T, size_t inlineCapacity, typename U> 697inline void ListHashSet<T, inlineCapacity, U>::clear() 698{ 699 deleteAllNodes(); 700 m_impl.clear(); 701 m_head = 0; 702 m_tail = 0; 703} 704 705template<typename T, size_t inlineCapacity, typename U> 706void ListHashSet<T, inlineCapacity, U>::unlink(Node* node) 707{ 708 if (!node->m_prev) { 709 ASSERT(node == m_head); 710 m_head = node->m_next; 711 } else { 712 ASSERT(node != m_head); 713 node->m_prev->m_next = node->m_next; 714 } 715 716 if (!node->m_next) { 717 ASSERT(node == m_tail); 718 m_tail = node->m_prev; 719 } else { 720 ASSERT(node != m_tail); 721 node->m_next->m_prev = node->m_prev; 722 } 723} 724 725template<typename T, size_t inlineCapacity, typename U> 726void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node) 727{ 728 unlink(node); 729 node->destroy(m_allocator.get()); 730} 731 732template<typename T, size_t inlineCapacity, typename U> 733void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node) 734{ 735 node->m_prev = m_tail; 736 node->m_next = 0; 737 738 if (m_tail) { 739 ASSERT(m_head); 740 m_tail->m_next = node; 741 } else { 742 ASSERT(!m_head); 743 m_head = node; 744 } 745 746 m_tail = node; 747} 748 749template<typename T, size_t inlineCapacity, typename U> 750void ListHashSet<T, inlineCapacity, U>::prependNode(Node* node) 751{ 752 node->m_prev = 0; 753 node->m_next = m_head; 754 755 if (m_head) 756 m_head->m_prev = node; 757 else 758 m_tail = node; 759 760 m_head = node; 761} 762 763template<typename T, size_t inlineCapacity, typename U> 764void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode) 765{ 766 if (!beforeNode) 767 return appendNode(newNode); 768 769 newNode->m_next = beforeNode; 770 newNode->m_prev = beforeNode->m_prev; 771 if (beforeNode->m_prev) 772 beforeNode->m_prev->m_next = newNode; 773 beforeNode->m_prev = newNode; 774 775 if (!newNode->m_prev) 776 m_head = newNode; 777} 778 779template<typename T, size_t inlineCapacity, typename U> 780void ListHashSet<T, inlineCapacity, U>::deleteAllNodes() 781{ 782 if (!m_head) 783 return; 784 785 for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0) 786 node->destroy(m_allocator.get()); 787} 788 789template<typename T, size_t inlineCapacity, typename U> 790inline auto ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position) -> iterator 791{ 792 return iterator(this, position); 793} 794 795template<typename T, size_t inlineCapacity, typename U> 796inline auto ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const -> const_iterator 797{ 798 return const_iterator(this, position); 799} 800 801} // namespace WTF 802 803using WTF::ListHashSet; 804 805#endif /* WTF_ListHashSet_h */ 806