2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
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.
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.
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.
22 #ifndef WTF_ListHashSet_h
23 #define WTF_ListHashSet_h
25 #include "Assertions.h"
28 #include "PassOwnPtr.h"
29 #include "StdLibExtras.h"
33 // ListHashSet: Just like HashSet, this class provides a Set
34 // interface - a collection of unique objects with O(1) insertion,
35 // removal and test for containership. However, it also has an
36 // order - iterating it will always give back values in the order
37 // in which they are added.
39 // In theory it would be possible to add prepend, insertAfter
40 // and an append that moves the element to the end even if already present,
41 // but unclear yet if these are needed.
43 template<typename Value, size_t inlineCapacity, typename HashFunctions> class ListHashSet;
45 template<typename T> struct IdentityExtractor;
47 template<typename Value, size_t inlineCapacity, typename HashFunctions>
48 void deleteAllValues(const ListHashSet<Value, inlineCapacity, HashFunctions>&);
50 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator;
51 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator;
53 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode;
54 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator;
55 template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions;
57 template<typename ValueArg, size_t inlineCapacity = 256, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
58 WTF_MAKE_FAST_ALLOCATED;
60 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
61 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
63 typedef HashTraits<Node*> NodeTraits;
64 typedef ListHashSetNodeHashFunctions<ValueArg, inlineCapacity, HashArg> NodeHash;
66 typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
67 typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
68 typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;
70 typedef HashArg HashFunctions;
73 typedef ValueArg ValueType;
74 typedef ListHashSetIterator<ValueType, inlineCapacity, HashArg> iterator;
75 typedef ListHashSetConstIterator<ValueType, inlineCapacity, HashArg> const_iterator;
77 friend class ListHashSetConstIterator<ValueType, inlineCapacity, HashArg>;
80 ListHashSet(const ListHashSet&);
81 ListHashSet& operator=(const ListHashSet&);
84 void swap(ListHashSet&);
92 const_iterator begin() const;
93 const_iterator end() const;
96 const ValueType& first() const;
99 const ValueType& last() const;
102 iterator find(const ValueType&);
103 const_iterator find(const ValueType&) const;
104 bool contains(const ValueType&) const;
106 // An alternate version of find() that finds the object by hashing and comparing
107 // with some other type, to avoid the cost of type conversion.
108 // The HashTranslator interface is defined in HashSet.
109 template<typename T, typename HashTranslator> iterator find(const T&);
110 template<typename T, typename HashTranslator> const_iterator find(const T&) const;
111 template<typename T, typename HashTranslator> bool contains(const T&) const;
113 // the return value is a pair of an iterator to the new value's location,
114 // and a bool that is true if an new entry was added
115 pair<iterator, bool> add(const ValueType&);
117 pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue);
118 pair<iterator, bool> insertBefore(iterator it, const ValueType&);
120 void remove(const ValueType&);
121 void remove(iterator);
125 void unlinkAndDelete(Node*);
126 void appendNode(Node*);
127 void insertNodeBefore(Node* beforeNode, Node* newNode);
128 void deleteAllNodes();
129 iterator makeIterator(Node*);
130 const_iterator makeConstIterator(Node*) const;
132 friend void deleteAllValues<>(const ListHashSet&);
137 OwnPtr<NodeAllocator> m_allocator;
140 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNodeAllocator {
141 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
142 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
144 ListHashSetNodeAllocator()
146 , m_isDoneWithInitialFreeList(false)
148 memset(m_pool.pool, 0, sizeof(m_pool.pool));
153 Node* result = m_freeList;
156 return static_cast<Node*>(fastMalloc(sizeof(Node)));
158 ASSERT(!result->m_isAllocated);
160 Node* next = result->m_next;
161 ASSERT(!next || !next->m_isAllocated);
162 if (!next && !m_isDoneWithInitialFreeList) {
164 if (next == pastPool()) {
165 m_isDoneWithInitialFreeList = true;
168 ASSERT(inPool(next));
169 ASSERT(!next->m_isAllocated);
177 void deallocate(Node* node)
181 node->m_isAllocated = false;
183 node->m_next = m_freeList;
192 Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.pool); }
193 Node* pastPool() { return pool() + m_poolSize; }
195 bool inPool(Node* node)
197 return node >= pool() && node < pastPool();
201 bool m_isDoneWithInitialFreeList;
202 static const size_t m_poolSize = inlineCapacity;
204 char pool[sizeof(Node) * m_poolSize];
209 template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
210 typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
212 ListHashSetNode(ValueArg value)
217 , m_isAllocated(true)
222 void* operator new(size_t, NodeAllocator* allocator)
224 return allocator->allocate();
226 void destroy(NodeAllocator* allocator)
228 this->~ListHashSetNode();
229 allocator->deallocate(this);
233 ListHashSetNode* m_prev;
234 ListHashSetNode* m_next;
241 template<typename ValueArg, size_t inlineCapacity, typename HashArg> struct ListHashSetNodeHashFunctions {
242 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
244 static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
245 static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
246 static const bool safeToCompareToEmptyOrDeleted = false;
249 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetIterator {
251 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
252 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
253 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
254 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
255 typedef ValueArg ValueType;
256 typedef ValueType& ReferenceType;
257 typedef ValueType* PointerType;
259 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
261 ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
264 ListHashSetIterator() { }
266 // default copy, assignment and destructor are OK
268 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
269 ReferenceType operator*() const { return *get(); }
270 PointerType operator->() const { return get(); }
272 iterator& operator++() { ++m_iterator; return *this; }
274 // postfix ++ intentionally omitted
276 iterator& operator--() { --m_iterator; return *this; }
278 // postfix -- intentionally omitted
281 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
282 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
284 operator const_iterator() const { return m_iterator; }
287 Node* node() { return m_iterator.node(); }
289 const_iterator m_iterator;
292 template<typename ValueArg, size_t inlineCapacity, typename HashArg> class ListHashSetConstIterator {
294 typedef ListHashSet<ValueArg, inlineCapacity, HashArg> ListHashSetType;
295 typedef ListHashSetIterator<ValueArg, inlineCapacity, HashArg> iterator;
296 typedef ListHashSetConstIterator<ValueArg, inlineCapacity, HashArg> const_iterator;
297 typedef ListHashSetNode<ValueArg, inlineCapacity> Node;
298 typedef ValueArg ValueType;
299 typedef const ValueType& ReferenceType;
300 typedef const ValueType* PointerType;
302 friend class ListHashSet<ValueArg, inlineCapacity, HashArg>;
303 friend class ListHashSetIterator<ValueArg, inlineCapacity, HashArg>;
305 ListHashSetConstIterator(const ListHashSetType* set, Node* position)
307 , m_position(position)
312 ListHashSetConstIterator()
316 PointerType get() const
318 return &m_position->m_value;
320 ReferenceType operator*() const { return *get(); }
321 PointerType operator->() const { return get(); }
323 const_iterator& operator++()
325 ASSERT(m_position != 0);
326 m_position = m_position->m_next;
330 // postfix ++ intentionally omitted
332 const_iterator& operator--()
334 ASSERT(m_position != m_set->m_head);
336 m_position = m_set->m_tail;
338 m_position = m_position->m_prev;
342 // postfix -- intentionally omitted
345 bool operator==(const const_iterator& other) const
347 return m_position == other.m_position;
349 bool operator!=(const const_iterator& other) const
351 return m_position != other.m_position;
355 Node* node() { return m_position; }
357 const ListHashSetType* m_set;
362 template<typename ValueType, size_t inlineCapacity, typename HashFunctions>
363 struct ListHashSetTranslator {
365 typedef ListHashSetNode<ValueType, inlineCapacity> Node;
366 typedef ListHashSetNodeAllocator<ValueType, inlineCapacity> NodeAllocator;
368 static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
369 static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
370 static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
372 location = new (allocator) Node(key);
376 template<typename T, size_t inlineCapacity, typename U>
377 inline ListHashSet<T, inlineCapacity, U>::ListHashSet()
380 , m_allocator(adoptPtr(new NodeAllocator))
384 template<typename T, size_t inlineCapacity, typename U>
385 inline ListHashSet<T, inlineCapacity, U>::ListHashSet(const ListHashSet& other)
388 , m_allocator(adoptPtr(new NodeAllocator))
390 const_iterator end = other.end();
391 for (const_iterator it = other.begin(); it != end; ++it)
395 template<typename T, size_t inlineCapacity, typename U>
396 inline ListHashSet<T, inlineCapacity, U>& ListHashSet<T, inlineCapacity, U>::operator=(const ListHashSet& other)
398 ListHashSet tmp(other);
403 template<typename T, size_t inlineCapacity, typename U>
404 inline void ListHashSet<T, inlineCapacity, U>::swap(ListHashSet& other)
406 m_impl.swap(other.m_impl);
407 std::swap(m_head, other.m_head);
408 std::swap(m_tail, other.m_tail);
409 m_allocator.swap(other.m_allocator);
412 template<typename T, size_t inlineCapacity, typename U>
413 inline ListHashSet<T, inlineCapacity, U>::~ListHashSet()
418 template<typename T, size_t inlineCapacity, typename U>
419 inline int ListHashSet<T, inlineCapacity, U>::size() const
421 return m_impl.size();
424 template<typename T, size_t inlineCapacity, typename U>
425 inline int ListHashSet<T, inlineCapacity, U>::capacity() const
427 return m_impl.capacity();
430 template<typename T, size_t inlineCapacity, typename U>
431 inline bool ListHashSet<T, inlineCapacity, U>::isEmpty() const
433 return m_impl.isEmpty();
436 template<typename T, size_t inlineCapacity, typename U>
437 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::begin()
439 return makeIterator(m_head);
442 template<typename T, size_t inlineCapacity, typename U>
443 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::end()
445 return makeIterator(0);
448 template<typename T, size_t inlineCapacity, typename U>
449 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::begin() const
451 return makeConstIterator(m_head);
454 template<typename T, size_t inlineCapacity, typename U>
455 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::end() const
457 return makeConstIterator(0);
460 template<typename T, size_t inlineCapacity, typename U>
461 inline T& ListHashSet<T, inlineCapacity, U>::first()
464 return m_head->m_value;
467 template<typename T, size_t inlineCapacity, typename U>
468 inline const T& ListHashSet<T, inlineCapacity, U>::first() const
471 return m_head->m_value;
474 template<typename T, size_t inlineCapacity, typename U>
475 inline T& ListHashSet<T, inlineCapacity, U>::last()
478 return m_tail->m_value;
481 template<typename T, size_t inlineCapacity, typename U>
482 inline const T& ListHashSet<T, inlineCapacity, U>::last() const
485 return m_tail->m_value;
488 template<typename T, size_t inlineCapacity, typename U>
489 inline void ListHashSet<T, inlineCapacity, U>::removeLast()
492 m_impl.remove(m_tail);
493 unlinkAndDelete(m_tail);
496 template<typename T, size_t inlineCapacity, typename U>
497 inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value)
499 typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
500 ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value);
501 if (it == m_impl.end())
503 return makeIterator(*it);
506 template<typename T, size_t inlineCapacity, typename U>
507 inline typename ListHashSet<T, inlineCapacity, U>::const_iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value) const
509 typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
510 ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value);
511 if (it == m_impl.end())
513 return makeConstIterator(*it);
516 template<typename ValueType, size_t inlineCapacity, typename T, typename Translator>
517 struct ListHashSetTranslatorAdapter {
519 typedef ListHashSetNode<ValueType, inlineCapacity> Node;
521 static unsigned hash(const T& key) { return Translator::hash(key); }
522 static bool equal(Node* const& a, const T& b) { return Translator::equal(a->m_value, b); }
525 template<typename ValueType, size_t inlineCapacity, typename U>
526 template<typename T, typename HashTranslator>
527 inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value)
529 typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
530 ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
531 if (it == m_impl.end())
533 return makeIterator(*it);
536 template<typename ValueType, size_t inlineCapacity, typename U>
537 template<typename T, typename HashTranslator>
538 inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const
540 typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
541 ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
542 if (it == m_impl.end())
544 return makeConstIterator(*it);
547 template<typename ValueType, size_t inlineCapacity, typename U>
548 template<typename T, typename HashTranslator>
549 inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
551 typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
552 return m_impl.template contains<T, Adapter>(value);
555 template<typename T, size_t inlineCapacity, typename U>
556 inline bool ListHashSet<T, inlineCapacity, U>::contains(const ValueType& value) const
558 typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
559 return m_impl.template contains<ValueType, Translator>(value);
562 template<typename T, size_t inlineCapacity, typename U>
563 pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::add(const ValueType &value)
565 typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
566 pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());
568 appendNode(*result.first);
569 return std::make_pair(makeIterator(*result.first), result.second);
572 template<typename T, size_t inlineCapacity, typename U>
573 pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue)
575 typedef ListHashSetTranslator<ValueType, inlineCapacity, HashFunctions> Translator;
576 pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get());
578 insertNodeBefore(it.node(), *result.first);
579 return std::make_pair(makeIterator(*result.first), result.second);
583 template<typename T, size_t inlineCapacity, typename U>
584 pair<typename ListHashSet<T, inlineCapacity, U>::iterator, bool> ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
586 return insertBefore(find(beforeValue), newValue);
589 template<typename T, size_t inlineCapacity, typename U>
590 inline void ListHashSet<T, inlineCapacity, U>::remove(iterator it)
594 m_impl.remove(it.node());
595 unlinkAndDelete(it.node());
598 template<typename T, size_t inlineCapacity, typename U>
599 inline void ListHashSet<T, inlineCapacity, U>::remove(const ValueType& value)
604 template<typename T, size_t inlineCapacity, typename U>
605 inline void ListHashSet<T, inlineCapacity, U>::clear()
613 template<typename T, size_t inlineCapacity, typename U>
614 void ListHashSet<T, inlineCapacity, U>::unlinkAndDelete(Node* node)
617 ASSERT(node == m_head);
618 m_head = node->m_next;
620 ASSERT(node != m_head);
621 node->m_prev->m_next = node->m_next;
625 ASSERT(node == m_tail);
626 m_tail = node->m_prev;
628 ASSERT(node != m_tail);
629 node->m_next->m_prev = node->m_prev;
632 node->destroy(m_allocator.get());
635 template<typename T, size_t inlineCapacity, typename U>
636 void ListHashSet<T, inlineCapacity, U>::appendNode(Node* node)
638 node->m_prev = m_tail;
643 m_tail->m_next = node;
652 template<typename T, size_t inlineCapacity, typename U>
653 void ListHashSet<T, inlineCapacity, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
656 return appendNode(newNode);
658 newNode->m_next = beforeNode;
659 newNode->m_prev = beforeNode->m_prev;
660 if (beforeNode->m_prev)
661 beforeNode->m_prev->m_next = newNode;
662 beforeNode->m_prev = newNode;
664 if (!newNode->m_prev)
668 template<typename T, size_t inlineCapacity, typename U>
669 void ListHashSet<T, inlineCapacity, U>::deleteAllNodes()
674 for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
675 node->destroy(m_allocator.get());
678 template<typename T, size_t inlineCapacity, typename U>
679 inline ListHashSetIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeIterator(Node* position)
681 return ListHashSetIterator<T, inlineCapacity, U>(this, position);
684 template<typename T, size_t inlineCapacity, typename U>
685 inline ListHashSetConstIterator<T, inlineCapacity, U> ListHashSet<T, inlineCapacity, U>::makeConstIterator(Node* position) const
687 return ListHashSetConstIterator<T, inlineCapacity, U>(this, position);
690 template<bool, typename ValueType, typename HashTableType>
691 void deleteAllValues(HashTableType& collection)
693 typedef typename HashTableType::const_iterator iterator;
694 iterator end = collection.end();
695 for (iterator it = collection.begin(); it != end; ++it)
696 delete (*it)->m_value;
699 template<typename T, size_t inlineCapacity, typename U>
700 inline void deleteAllValues(const ListHashSet<T, inlineCapacity, U>& collection)
702 deleteAllValues<true, typename ListHashSet<T, inlineCapacity, U>::ValueType>(collection.m_impl);
707 using WTF::ListHashSet;
709 #endif /* WTF_ListHashSet_h */