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