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