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