Remove some stray uses of OwnPtr and PassOwnPtr in WTF (outside of the template defin...
[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 #ifndef WTF_ListHashSet_h
23 #define WTF_ListHashSet_h
24
25 #include <wtf/HashSet.h>
26
27 namespace WTF {
28
29 // ListHashSet: Just like HashSet, this class provides a Set
30 // interface - a collection of unique objects with O(1) insertion,
31 // removal and test for containership. However, it also has an
32 // order - iterating it will always give back values in the order
33 // in which they are added.
34
35 // Unlike iteration of most WTF Hash data structures, iteration is
36 // guaranteed safe against mutation of the ListHashSet, except for
37 // removal of the item currently pointed to by a given iterator.
38
39 template<typename Value, typename HashFunctions> class ListHashSet;
40
41 template<typename ValueArg, typename HashArg> class ListHashSetIterator;
42 template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;
43
44 template<typename ValueArg> struct ListHashSetNode;
45
46 template<typename HashArg> struct ListHashSetNodeHashFunctions;
47 template<typename HashArg> struct ListHashSetTranslator;
48
49 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
50     WTF_MAKE_FAST_ALLOCATED;
51 private:
52     typedef ListHashSetNode<ValueArg> Node;
53
54     typedef HashTraits<Node*> NodeTraits;
55     typedef ListHashSetNodeHashFunctions<HashArg> NodeHash;
56     typedef ListHashSetTranslator<HashArg> BaseTranslator;
57
58     typedef HashArg HashFunctions;
59
60 public:
61     typedef ValueArg ValueType;
62
63     typedef ListHashSetIterator<ValueType, HashArg> iterator;
64     typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;
65     friend class ListHashSetConstIterator<ValueType, HashArg>;
66
67     typedef std::reverse_iterator<iterator> reverse_iterator;
68     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
69
70     typedef HashTableAddResult<iterator> AddResult;
71
72     ListHashSet();
73     ListHashSet(const ListHashSet&);
74     ListHashSet& operator=(const ListHashSet&);
75     ~ListHashSet();
76
77     void swap(ListHashSet&);
78
79     unsigned size() const;
80     unsigned capacity() const;
81     bool isEmpty() const;
82
83     iterator begin() { return makeIterator(m_head); }
84     iterator end() { return makeIterator(nullptr); }
85     const_iterator begin() const { return makeConstIterator(m_head); }
86     const_iterator end() const { return makeConstIterator(nullptr); }
87
88     reverse_iterator rbegin() { return reverse_iterator(end()); }
89     reverse_iterator rend() { return reverse_iterator(begin()); }
90     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
91     const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
92
93     ValueType& first();
94     const ValueType& first() const;
95     void removeFirst();
96     ValueType takeFirst();
97
98     ValueType& last();
99     const ValueType& last() const;
100     void removeLast();
101     ValueType takeLast();
102
103     iterator find(const ValueType&);
104     const_iterator find(const ValueType&) const;
105     bool contains(const ValueType&) const;
106
107     // An alternate version of find() that finds the object by hashing and comparing
108     // with some other type, to avoid the cost of type conversion.
109     // The HashTranslator interface is defined in HashSet.
110     // FIXME: We should reverse the order of the template arguments so that callers
111     // can just pass the translator let the compiler deduce T.
112     template<typename T, typename HashTranslator> iterator find(const T&);
113     template<typename T, typename HashTranslator> const_iterator find(const T&) const;
114     template<typename T, typename HashTranslator> bool contains(const T&) const;
115
116     // The return value of add is a pair of an iterator to the new value's location, 
117     // and a bool that is true if an new entry was added.
118     AddResult add(const ValueType&);
119     AddResult add(ValueType&&);
120
121     // Add the value to the end of the collection. If the value was already in
122     // the list, it is moved to the end.
123     AddResult appendOrMoveToLast(const ValueType&);
124     AddResult appendOrMoveToLast(ValueType&&);
125
126     // Add the value to the beginning of the collection. If the value was already in
127     // the list, it is moved to the beginning.
128     AddResult prependOrMoveToFirst(const ValueType&);
129     AddResult prependOrMoveToFirst(ValueType&&);
130
131     AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue);
132     AddResult insertBefore(const ValueType& beforeValue, ValueType&& newValue);
133     AddResult insertBefore(iterator, const ValueType&);
134     AddResult insertBefore(iterator, ValueType&&);
135
136     bool remove(const ValueType&);
137     bool remove(iterator);
138     void clear();
139
140 private:
141     void unlink(Node*);
142     void unlinkAndDelete(Node*);
143     void appendNode(Node*);
144     void prependNode(Node*);
145     void insertNodeBefore(Node* beforeNode, Node* newNode);
146     void deleteAllNodes();
147     
148     iterator makeIterator(Node*);
149     const_iterator makeConstIterator(Node*) const;
150
151     HashTable<Node*, Node*, IdentityExtractor, NodeHash, NodeTraits, NodeTraits> m_impl;
152     Node* m_head;
153     Node* m_tail;
154 };
155
156 template<typename ValueArg> struct ListHashSetNode {
157     WTF_MAKE_FAST_ALLOCATED;
158 public:
159     template<typename T>
160     ListHashSetNode(T&& value)
161         : m_value(std::forward<T>(value))
162         , m_prev(0)
163         , m_next(0)
164     {
165     }
166
167     ValueArg m_value;
168     ListHashSetNode* m_prev;
169     ListHashSetNode* m_next;
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 != 0);
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 template<typename T, typename U>
310 inline ListHashSet<T, U>::ListHashSet()
311     : m_head(0)
312     , m_tail(0)
313 {
314 }
315
316 template<typename T, typename U>
317 inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
318     : m_head(0)
319     , m_tail(0)
320 {
321     for (auto it = other.begin(), end = other.end(); it != end; ++it)
322         add(*it);
323 }
324
325 template<typename T, typename U>
326 inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
327 {
328     ListHashSet tmp(other);
329     swap(tmp);
330     return *this;
331 }
332
333 template<typename T, typename U>
334 inline void ListHashSet<T, U>::swap(ListHashSet& other)
335 {
336     m_impl.swap(other.m_impl);
337     std::swap(m_head, other.m_head);
338     std::swap(m_tail, other.m_tail);
339 }
340
341 template<typename T, typename U>
342 inline ListHashSet<T, U>::~ListHashSet()
343 {
344     deleteAllNodes();
345 }
346
347 template<typename T, typename U>
348 inline unsigned ListHashSet<T, U>::size() const
349 {
350     return m_impl.size(); 
351 }
352
353 template<typename T, typename U>
354 inline unsigned ListHashSet<T, U>::capacity() const
355 {
356     return m_impl.capacity(); 
357 }
358
359 template<typename T, typename U>
360 inline bool ListHashSet<T, U>::isEmpty() const
361 {
362     return m_impl.isEmpty(); 
363 }
364
365 template<typename T, typename U>
366 inline T& ListHashSet<T, U>::first()
367 {
368     ASSERT(!isEmpty());
369     return m_head->m_value;
370 }
371
372 template<typename T, typename U>
373 inline void ListHashSet<T, U>::removeFirst()
374 {
375     takeFirst();
376 }
377
378 template<typename T, typename U>
379 inline T ListHashSet<T, U>::takeFirst()
380 {
381     ASSERT(!isEmpty());
382     auto it = m_impl.find(m_head);
383
384     T result = WTF::move((*it)->m_value);
385     m_impl.remove(it);
386     unlinkAndDelete(m_head);
387
388     return result;
389 }
390
391 template<typename T, typename U>
392 inline const T& ListHashSet<T, U>::first() const
393 {
394     ASSERT(!isEmpty());
395     return m_head->m_value;
396 }
397
398 template<typename T, typename U>
399 inline T& ListHashSet<T, U>::last()
400 {
401     ASSERT(!isEmpty());
402     return m_tail->m_value;
403 }
404
405 template<typename T, typename U>
406 inline const T& ListHashSet<T, U>::last() const
407 {
408     ASSERT(!isEmpty());
409     return m_tail->m_value;
410 }
411
412 template<typename T, typename U>
413 inline void ListHashSet<T, U>::removeLast()
414 {
415     takeLast();
416 }
417
418 template<typename T, typename U>
419 inline T ListHashSet<T, U>::takeLast()
420 {
421     ASSERT(!isEmpty());
422     auto it = m_impl.find(m_tail);
423
424     T result = WTF::move((*it)->m_value);
425     m_impl.remove(it);
426     unlinkAndDelete(m_tail);
427
428     return result;
429 }
430
431 template<typename T, typename U>
432 inline auto ListHashSet<T, U>::find(const ValueType& value) -> iterator
433 {
434     auto it = m_impl.template find<BaseTranslator>(value);
435     if (it == m_impl.end())
436         return end();
437     return makeIterator(*it); 
438 }
439
440 template<typename T, typename U>
441 inline auto ListHashSet<T, U>::find(const ValueType& value) const -> const_iterator
442 {
443     auto it = m_impl.template find<BaseTranslator>(value);
444     if (it == m_impl.end())
445         return end();
446     return makeConstIterator(*it);
447 }
448
449 template<typename Translator>
450 struct ListHashSetTranslatorAdapter {
451     template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
452     template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
453 };
454
455 template<typename ValueType, typename U>
456 template<typename T, typename HashTranslator>
457 inline auto ListHashSet<ValueType, U>::find(const T& value) -> iterator
458 {
459     auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
460     if (it == m_impl.end())
461         return end();
462     return makeIterator(*it);
463 }
464
465 template<typename ValueType, typename U>
466 template<typename T, typename HashTranslator>
467 inline auto ListHashSet<ValueType, U>::find(const T& value) const -> const_iterator
468 {
469     auto it = m_impl.template find<ListHashSetTranslatorAdapter<HashTranslator>>(value);
470     if (it == m_impl.end())
471         return end();
472     return makeConstIterator(*it);
473 }
474
475 template<typename ValueType, typename U>
476 template<typename T, typename HashTranslator>
477 inline bool ListHashSet<ValueType, U>::contains(const T& value) const
478 {
479     return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
480 }
481
482 template<typename T, typename U>
483 inline bool ListHashSet<T, U>::contains(const ValueType& value) const
484 {
485     return m_impl.template contains<BaseTranslator>(value);
486 }
487
488 template<typename T, typename U>
489 auto ListHashSet<T, U>::add(const ValueType& value) -> AddResult
490 {
491     auto result = m_impl.template add<BaseTranslator>(value, nullptr);
492     if (result.isNewEntry)
493         appendNode(*result.iterator);
494     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
495 }
496
497 template<typename T, typename U>
498 auto ListHashSet<T, U>::add(ValueType&& value) -> AddResult
499 {
500     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
501     if (result.isNewEntry)
502         appendNode(*result.iterator);
503     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
504 }
505
506 template<typename T, typename U>
507 auto ListHashSet<T, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
508 {
509     auto result = m_impl.template add<BaseTranslator>(value, nullptr);
510     Node* node = *result.iterator;
511     if (!result.isNewEntry)
512         unlink(node);
513     appendNode(node);
514
515     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
516 }
517
518 template<typename T, typename U>
519 auto ListHashSet<T, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
520 {
521     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
522     Node* node = *result.iterator;
523     if (!result.isNewEntry)
524         unlink(node);
525     appendNode(node);
526
527     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
528 }
529
530 template<typename T, typename U>
531 auto ListHashSet<T, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
532 {
533     auto result = m_impl.template add<BaseTranslator>(value, nullptr);
534     Node* node = *result.iterator;
535     if (!result.isNewEntry)
536         unlink(node);
537     prependNode(node);
538
539     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
540 }
541
542 template<typename T, typename U>
543 auto ListHashSet<T, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
544 {
545     auto result = m_impl.template add<BaseTranslator>(WTF::move(value), nullptr);
546     Node* node = *result.iterator;
547     if (!result.isNewEntry)
548         unlink(node);
549     prependNode(node);
550
551     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
552 }
553
554 template<typename T, typename U>
555 auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
556 {
557     return insertBefore(find(beforeValue), newValue);
558 }
559
560 template<typename T, typename U>
561 auto ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
562 {
563     return insertBefore(find(beforeValue), WTF::move(newValue));
564 }
565
566 template<typename T, typename U>
567 auto ListHashSet<T, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
568 {
569     auto result = m_impl.template add<BaseTranslator>(newValue, nullptr);
570     if (result.isNewEntry)
571         insertNodeBefore(it.node(), *result.iterator);
572     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
573 }
574
575 template<typename T, typename U>
576 auto ListHashSet<T, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
577 {
578     auto result = m_impl.template add<BaseTranslator>(WTF::move(newValue), nullptr);
579     if (result.isNewEntry)
580         insertNodeBefore(it.node(), *result.iterator);
581     return AddResult(makeIterator(*result.iterator), result.isNewEntry);
582 }
583
584 template<typename T, typename U>
585 inline bool ListHashSet<T, U>::remove(iterator it)
586 {
587     if (it == end())
588         return false;
589     m_impl.remove(it.node());
590     unlinkAndDelete(it.node());
591     return true;
592 }
593
594 template<typename T, typename U>
595 inline bool ListHashSet<T, U>::remove(const ValueType& value)
596 {
597     return remove(find(value));
598 }
599
600 template<typename T, typename U>
601 inline void ListHashSet<T, U>::clear()
602 {
603     deleteAllNodes();
604     m_impl.clear(); 
605     m_head = 0;
606     m_tail = 0;
607 }
608
609 template<typename T, typename U>
610 void ListHashSet<T, U>::unlink(Node* node)
611 {
612     if (!node->m_prev) {
613         ASSERT(node == m_head);
614         m_head = node->m_next;
615     } else {
616         ASSERT(node != m_head);
617         node->m_prev->m_next = node->m_next;
618     }
619
620     if (!node->m_next) {
621         ASSERT(node == m_tail);
622         m_tail = node->m_prev;
623     } else {
624         ASSERT(node != m_tail);
625         node->m_next->m_prev = node->m_prev;
626     }
627 }
628
629 template<typename T, typename U>
630 void ListHashSet<T, U>::unlinkAndDelete(Node* node)
631 {
632     unlink(node);
633     delete node;
634 }
635
636 template<typename T, typename U>
637 void ListHashSet<T, U>::appendNode(Node* node)
638 {
639     node->m_prev = m_tail;
640     node->m_next = 0;
641
642     if (m_tail) {
643         ASSERT(m_head);
644         m_tail->m_next = node;
645     } else {
646         ASSERT(!m_head);
647         m_head = node;
648     }
649
650     m_tail = node;
651 }
652
653 template<typename T, typename U>
654 void ListHashSet<T, U>::prependNode(Node* node)
655 {
656     node->m_prev = 0;
657     node->m_next = m_head;
658
659     if (m_head)
660         m_head->m_prev = node;
661     else
662         m_tail = node;
663
664     m_head = node;
665 }
666
667 template<typename T, typename U>
668 void ListHashSet<T, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
669 {
670     if (!beforeNode)
671         return appendNode(newNode);
672     
673     newNode->m_next = beforeNode;
674     newNode->m_prev = beforeNode->m_prev;
675     if (beforeNode->m_prev)
676         beforeNode->m_prev->m_next = newNode;
677     beforeNode->m_prev = newNode;
678
679     if (!newNode->m_prev)
680         m_head = newNode;
681 }
682
683 template<typename T, typename U>
684 void ListHashSet<T, U>::deleteAllNodes()
685 {
686     if (!m_head)
687         return;
688
689     for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
690         delete node;
691 }
692
693 template<typename T, typename U>
694 inline auto ListHashSet<T, U>::makeIterator(Node* position) -> iterator
695 {
696     return iterator(this, position);
697 }
698
699 template<typename T, typename U>
700 inline auto ListHashSet<T, U>::makeConstIterator(Node* position) const -> const_iterator
701
702     return const_iterator(this, position);
703 }
704
705 } // namespace WTF
706
707 using WTF::ListHashSet;
708
709 #endif /* WTF_ListHashSet_h */