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 : public FastAllocBase { 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 */ 617
