1/*
2 * Copyright (C) 2005-2019 Apple Inc. All rights reserved.
3 * Copyright (C) 2011, Benjamin Poulain <[email protected]>
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 final {
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 constexpr bool safeToCompareToEmptyOrDeleted = false;
185};
186
187template<typename ValueArg, typename HashArg> class ListHashSetIterator {
188 WTF_MAKE_FAST_ALLOCATED;
189private:
190 typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
191 typedef ListHashSetIterator<ValueArg, HashArg> iterator;
192 typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
193 typedef ListHashSetNode<ValueArg> Node;
194 typedef ValueArg ValueType;
195
196 friend class ListHashSet<ValueArg, HashArg>;
197
198 ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }
199
200public:
201 typedef ptrdiff_t difference_type;
202 typedef ValueType value_type;
203 typedef ValueType* pointer;
204 typedef ValueType& reference;
205 typedef std::bidirectional_iterator_tag iterator_category;
206
207 ListHashSetIterator() { }
208
209 // default copy, assignment and destructor are OK
210
211 ValueType* get() const { return const_cast<ValueType*>(m_iterator.get()); }
212 ValueType& operator*() const { return *get(); }
213 ValueType* operator->() const { return get(); }
214
215 iterator& operator++() { ++m_iterator; return *this; }
216
217 // postfix ++ intentionally omitted
218
219 iterator& operator--() { --m_iterator; return *this; }
220
221 // postfix -- intentionally omitted
222
223 // Comparison.
224 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
225 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
226
227 operator const_iterator() const { return m_iterator; }
228
229private:
230 Node* node() { return m_iterator.node(); }
231
232 const_iterator m_iterator;
233};
234
235template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {
236 WTF_MAKE_FAST_ALLOCATED;
237private:
238 typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
239 typedef ListHashSetIterator<ValueArg, HashArg> iterator;
240 typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
241 typedef ListHashSetNode<ValueArg> Node;
242 typedef ValueArg ValueType;
243
244 friend class ListHashSet<ValueArg, HashArg>;
245 friend class ListHashSetIterator<ValueArg, HashArg>;
246
247 ListHashSetConstIterator(const ListHashSetType* set, Node* position)
248 : m_set(set)
249 , m_position(position)
250 {
251 }
252
253public:
254 typedef ptrdiff_t difference_type;
255 typedef const ValueType value_type;
256 typedef const ValueType* pointer;
257 typedef const ValueType& reference;
258 typedef std::bidirectional_iterator_tag iterator_category;
259
260 ListHashSetConstIterator()
261 {
262 }
263
264 const ValueType* get() const
265 {
266 return std::addressof(m_position->m_value);
267 }
268
269 const ValueType& operator*() const { return *get(); }
270 const ValueType* operator->() const { return get(); }
271
272 const_iterator& operator++()
273 {
274 ASSERT(m_position);
275 m_position = m_position->m_next;
276 return *this;
277 }
278
279 // postfix ++ intentionally omitted
280
281 const_iterator& operator--()
282 {
283 ASSERT(m_position != m_set->m_head);
284 if (!m_position)
285 m_position = m_set->m_tail;
286 else
287 m_position = m_position->m_prev;
288 return *this;
289 }
290
291 // postfix -- intentionally omitted
292
293 // Comparison.
294 bool operator==(const const_iterator& other) const
295 {
296 return m_position == other.m_position;
297 }
298 bool operator!=(const const_iterator& other) const
299 {
300 return m_position != other.m_position;
301 }
302
303private:
304 Node* node() { return m_position; }
305
306 const ListHashSetType* m_set;
307 Node* m_position;
308};
309
310template<typename HashFunctions>
311struct ListHashSetTranslator {
312 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
313 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a->m_value, b); }
314 template<typename T, typename U, typename V> static void translate(T*& location, U&& key, V&&)
315 {
316 location = new T(std::forward<U>(key));
317 }
318};
319
320
321template<typename T, typename U>
322inline ListHashSet<T, U>::ListHashSet(std::initializer_list<T> initializerList)
323{
324 for (const auto& value : initializerList)
325 add(value);
326}
327
328template<typename T, typename U>
329inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
330{
331 for (auto it = other.begin(), end = other.end(); it != end; ++it)
332 add(*it);
333}
334
335template<typename T, typename U>
336inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
337{
338 ListHashSet tmp(other);
339 swap(tmp);
340 return *this;
341}
342
343template<typename T, typename U>
344inline ListHashSet<T, U>::ListHashSet(ListHashSet&& other)
345 : m_impl(WTFMove(other.m_impl))
346 , m_head(std::exchange(other.m_head, nullptr))
347 , m_tail(std::exchange(other.m_tail, nullptr))
348{
349}
350
351template<typename T, typename U>
352inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(ListHashSet&& other)
353{
354 m_impl = WTFMove(other.m_impl);
355 m_head = std::exchange(other.m_head, nullptr);
356 m_tail = std::exchange(other.m_tail, nullptr);
357 return *this;
358}
359
360template<typename T, typename U>
361inline void ListHashSet<T, U>::swap(ListHashSet& other)
362{
363 m_impl.swap(other.m_impl);
364 std::swap(m_head, other.m_head);
365 std::swap(m_tail, other.m_tail);
366}
367
368template<typename T, typename U>
369inline ListHashSet<T, U>::~ListHashSet()
370{
371 deleteAllNodes();
372}
373
374template<typename T, typename U>
375inline unsigned ListHashSet<T, U>::size() const
376{
377 return m_impl.size();
378}
379
380template<typename T, typename U>
381inline unsigned ListHashSet<T, U>::capacity() const
382{
383 return m_impl.capacity();
384}
385
386template<typename T, typename U>
387inline bool ListHashSet<T, U>::isEmpty() const
388{
389 return m_impl.isEmpty();
390}
391
392template<typename T, typename U>
393inline T& ListHashSet<T, U>::first()
394{
395 ASSERT(!isEmpty());
396 return m_head->m_value;
397}
398
399template<typename T, typename U>
400inline void ListHashSet<T, U>::removeFirst()
401{
402 takeFirst();
403}
404
405template<typename T, typename U>
406inline T ListHashSet<T, U>::takeFirst()
407{
408 ASSERT(!isEmpty());
409 auto it = m_impl.find(m_head);
410
411 T result = WTFMove((*it)->m_value);
412 m_impl.remove(it);
413 unlinkAndDelete(m_head);
414
415 return result;
416}
417
418template<typename T, typename U>
419inline const T& ListHashSet<T, U>::first() const
420{
421 ASSERT(!isEmpty());
422 return m_head->m_value;
423}
424
425template<typename T, typename U>
426inline T& ListHashSet<T, U>::last()
427{
428 ASSERT(!isEmpty());
429 return m_tail->m_value;
430}
431
432template<typename T, typename U>
433inline const T& ListHashSet<T, U>::last() const
434{
435 ASSERT(!isEmpty());
436 return m_tail->m_value;
437}
438
439template<typename T, typename U>
440inline void ListHashSet<T, U>::removeLast()
441{
442 takeLast();
443}
444
445template<typename T, typename U>
446inline T ListHashSet<T, U>::takeLast()
447{
448 ASSERT(!isEmpty());
449 auto it = m_impl.find(m_tail);
450
451 T result = WTFMove((*it)->m_value);
452 m_impl.remove(it);
453 unlinkAndDelete(m_tail);
454
455 return result;
456}
457
458template<typename T, typename U>
459inline auto ListHashSet<T, U>::find(const ValueType& value) -> iterator
460{
461 auto it = m_impl.template find<BaseTranslator>(value);
462 if (it == m_impl.end())
463 return end();
464 return makeIterator(*it);
465}
466
467template<typename T, typename U>
468inline auto ListHashSet<T, U>::find(const ValueType& value) const -> const_iterator
469{
470 auto it = m_impl.template find<BaseTranslator>(value);
471 if (it == m_impl.end())
472 return end();
473 return makeConstIterator(*it);
474}
475
476template<typename Translator>
477struct ListHashSetTranslatorAdapter {
478 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
479 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
480};
481
482template<typename ValueType, typename U>
483template<typename HashTranslator, typename T>
484inline auto ListHashSet<ValueType, U>::find(const T& value) -> iterator
485{
486 auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
487 if (it == m_impl.end())
488 return end();
489 return makeIterator(*it);
490}
491
492template<typename ValueType, typename U>
493template<typename HashTranslator, typename T>
494inline auto ListHashSet<ValueType, U>::find(const T& value) const -> const_iterator
495{
496 auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
497 if (it == m_impl.end())
498 return end();
499 return makeConstIterator(*it);
500}
501
502template<typename ValueType, typename U>
503template<typename HashTranslator, typename T>
504inline bool ListHashSet<ValueType, U>::contains(const T& value) const
505{
506 return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
507}
508
509template<typename T, typename U>
510inline bool ListHashSet<T, U>::contains(const ValueType& value) const
511{
512 return m_impl.template contains<BaseTranslator>(value);
513}
514
515template<typename T, typename U>
516auto ListHashSet<T, U>::add(const ValueType& value) -> AddResult
517{
518 auto result = m_impl.template add<BaseTranslator>(value, nullptr);
519 if (result.isNewEntry)
520 appendNode(*result.iterator);
521 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
522}
523
524template<typename T, typename U>
525auto ListHashSet<T, U>::add(ValueType&& value) -> AddResult
526{
527 auto result = m_impl.template add<BaseTranslator>(WTFMove(value), nullptr);
528 if (result.isNewEntry)
529 appendNode(*result.iterator);
530 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
531}
532
533template<typename T, typename U>
534auto ListHashSet<T, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
535{
536 auto result = m_impl.template add<BaseTranslator>(value, nullptr);
537 Node* node = *result.iterator;
538 if (!result.isNewEntry)
539 unlink(node);
540 appendNode(node);
541
542 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
543}
544
545template<typename T, typename U>
546auto ListHashSet<T, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
547{
548 auto result = m_impl.template add<BaseTranslator>(WTFMove(value), nullptr);
549 Node* node = *result.iterator;
550 if (!result.isNewEntry)
551 unlink(node);
552 appendNode(node);
553
554 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
555}
556
557template<typename T, typename U>
558auto ListHashSet<T, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
559{
560 auto result = m_impl.template add<BaseTranslator>(value, nullptr);
561 Node* node = *result.iterator;
562 if (!result.isNewEntry)
563 unlink(node);
564 prependNode(node);
565
566 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
567}
568
569template<typename T, typename U>
570auto ListHashSet<T, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
571{
572 auto result = m_impl.template add<BaseTranslator>(WTFMove(value), nullptr);
573 Node* node = *result.iterator;
574 if (!result.isNewEntry)
575 unlink(node);
576 prependNode(node);
577
578 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
579}
580
581template<typename T, typename U>
582auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
583{
584 return insertBefore(find(beforeValue), newValue);
585}
586
587template<typename T, typename U>
588auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
589{
590 return insertBefore(find(beforeValue), WTFMove(newValue));
591}
592
593template<typename T, typename U>
594auto ListHashSet<T, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
595{
596 auto result = m_impl.template add<BaseTranslator>(newValue, nullptr);
597 if (result.isNewEntry)
598 insertNodeBefore(it.node(), *result.iterator);
599 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
600}
601
602template<typename T, typename U>
603auto ListHashSet<T, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
604{
605 auto result = m_impl.template add<BaseTranslator>(WTFMove(newValue), nullptr);
606 if (result.isNewEntry)
607 insertNodeBefore(it.node(), *result.iterator);
608 return AddResult(makeIterator(*result.iterator), result.isNewEntry);
609}
610
611template<typename T, typename U>
612inline bool ListHashSet<T, U>::remove(iterator it)
613{
614 if (it == end())
615 return false;
616 m_impl.remove(it.node());
617 unlinkAndDelete(it.node());
618 return true;
619}
620
621template<typename T, typename U>
622inline bool ListHashSet<T, U>::remove(const ValueType& value)
623{
624 return remove(find(value));
625}
626
627template<typename T, typename U>
628inline void ListHashSet<T, U>::clear()
629{
630 deleteAllNodes();
631 m_impl.clear();
632 m_head = nullptr;
633 m_tail = nullptr;
634}
635
636template<typename T, typename U>
637template<typename V>
638inline auto ListHashSet<T, U>::find(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type
639{
640 auto it = m_impl.template find<BaseTranslator>(value);
641 if (it == m_impl.end())
642 return end();
643 return makeIterator(*it);
644}
645
646template<typename T, typename U>
647template<typename V>
648inline auto ListHashSet<T, U>::find(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, const_iterator>::type
649{
650 auto it = m_impl.template find<BaseTranslator>(value);
651 if (it == m_impl.end())
652 return end();
653 return makeConstIterator(*it);
654}
655
656template<typename T, typename U>
657template<typename V>
658inline auto ListHashSet<T, U>::contains(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
659{
660 return m_impl.template contains<BaseTranslator>(value);
661}
662
663template<typename T, typename U>
664template<typename V>
665inline auto ListHashSet<T, U>::insertBefore(typename GetPtrHelper<V>::PtrType beforeValue, const ValueType& newValue) -> typename std::enable_if<IsSmartPtr<V>::value, AddResult>::type
666{
667 return insertBefore(find(beforeValue), newValue);
668}
669
670template<typename T, typename U>
671template<typename V>
672inline auto ListHashSet<T, U>::insertBefore(typename GetPtrHelper<V>::PtrType beforeValue, ValueType&& newValue) -> typename std::enable_if<IsSmartPtr<V>::value, AddResult>::type
673{
674 return insertBefore(find(beforeValue), WTFMove(newValue));
675}
676
677template<typename T, typename U>
678template<typename V>
679inline auto ListHashSet<T, U>::remove(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
680{
681 return remove(find(value));
682}
683
684template<typename T, typename U>
685void ListHashSet<T, U>::unlink(Node* node)
686{
687 if (!node->m_prev) {
688 ASSERT(node == m_head);
689 m_head = node->m_next;
690 } else {
691 ASSERT(node != m_head);
692 node->m_prev->m_next = node->m_next;
693 }
694
695 if (!node->m_next) {
696 ASSERT(node == m_tail);
697 m_tail = node->m_prev;
698 } else {
699 ASSERT(node != m_tail);
700 node->m_next->m_prev = node->m_prev;
701 }
702}
703
704template<typename T, typename U>
705void ListHashSet<T, U>::unlinkAndDelete(Node* node)
706{
707 unlink(node);
708 delete node;
709}
710
711template<typename T, typename U>
712void ListHashSet<T, U>::appendNode(Node* node)
713{
714 node->m_prev = m_tail;
715 node->m_next = nullptr;
716
717 if (m_tail) {
718 ASSERT(m_head);
719 m_tail->m_next = node;
720 } else {
721 ASSERT(!m_head);
722 m_head = node;
723 }
724
725 m_tail = node;
726}
727
728template<typename T, typename U>
729void ListHashSet<T, U>::prependNode(Node* node)
730{
731 node->m_prev = nullptr;
732 node->m_next = m_head;
733
734 if (m_head)
735 m_head->m_prev = node;
736 else
737 m_tail = node;
738
739 m_head = node;
740}
741
742template<typename T, typename U>
743void ListHashSet<T, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
744{
745 if (!beforeNode)
746 return appendNode(newNode);
747
748 newNode->m_next = beforeNode;
749 newNode->m_prev = beforeNode->m_prev;
750 if (beforeNode->m_prev)
751 beforeNode->m_prev->m_next = newNode;
752 beforeNode->m_prev = newNode;
753
754 if (!newNode->m_prev)
755 m_head = newNode;
756}
757
758template<typename T, typename U>
759void ListHashSet<T, U>::deleteAllNodes()
760{
761 if (!m_head)
762 return;
763
764 for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : nullptr)
765 delete node;
766}
767
768template<typename T, typename U>
769inline auto ListHashSet<T, U>::makeIterator(Node* position) -> iterator
770{
771 return iterator(this, position);
772}
773
774template<typename T, typename U>
775inline auto ListHashSet<T, U>::makeConstIterator(Node* position) const -> const_iterator
776{
777 return const_iterator(this, position);
778}
779
780} // namespace WTF
781
782using WTF::ListHashSet;
783