16f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch/* 26f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 36f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> 46f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * 56f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * This library is free software; you can redistribute it and/or 66f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * modify it under the terms of the GNU Library General Public 76f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * License as published by the Free Software Foundation; either 86f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * version 2 of the License, or (at your option) any later version. 96f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * 106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * This library is distributed in the hope that it will be useful, 116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * but WITHOUT ANY WARRANTY; without even the implied warranty of 126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * Library General Public License for more details. 146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * 156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * You should have received a copy of the GNU Library General Public License 166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * along with this library; see the file COPYING.LIB. If not, write to 176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * Boston, MA 02110-1301, USA. 196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch * 206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch */ 216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#ifndef WTF_LinkedHashSet_h 236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#define WTF_LinkedHashSet_h 246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#include "wtf/DefaultAllocator.h" 266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#include "wtf/HashSet.h" 276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#include "wtf/OwnPtr.h" 286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#include "wtf/PassOwnPtr.h" 296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochnamespace WTF { 316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// LinkedHashSet: Just like HashSet, this class provides a Set 336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// interface - a collection of unique objects with O(1) insertion, 346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// removal and test for containership. However, it also has an 356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// order - iterating it will always give back values in the order 366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// in which they are added. 376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// Unlike ListHashSet, but like most WTF collections, iteration is NOT safe 396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// against mutation of the LinkedHashSet. 406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet; 426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSet> class LinkedHashSetIterator; 446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSet> class LinkedHashSetConstIterator; 456f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSet> class LinkedHashSetReverseIterator; 466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSet> class LinkedHashSetConstReverseIterator; 476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename HashFunctions, typename Allocator> struct LinkedHashSetTranslator; 497242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename Allocator> struct LinkedHashSetExtractor; 507242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename ValueTraits, typename Allocator> struct LinkedHashSetTraits; 516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetNodeBase { 536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase() : m_prev(this), m_next(this) { } 556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void unlink() 576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!m_next) 596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return; 606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_prev); 616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_next->m_prev == this); 626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_prev->m_next == this); 636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_next->m_prev = m_prev; 646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_prev->m_next = m_next; 656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ~LinkedHashSetNodeBase() 686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch unlink(); 706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void insertBefore(LinkedHashSetNodeBase& other) 736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch other.m_next = this; 756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch other.m_prev = m_prev; 766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_prev->m_next = &other; 776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_prev = &other; 786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(other.m_next); 796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(other.m_prev); 806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_next); 816f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_prev); 826f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 836f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void insertAfter(LinkedHashSetNodeBase& other) 856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch other.m_prev = this; 876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch other.m_next = m_next; 886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_next->m_prev = &other; 896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_next = &other; 906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(other.m_next); 916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(other.m_prev); 926f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_next); 936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_prev); 946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next) 976f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : m_prev(prev) 986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , m_next(next) 996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 1006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT((prev && next) || (!prev && !next)); 1016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 1026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase* m_prev; 1046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase* m_next; 1056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprotected: 1076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // If we take a copy of a node we can't copy the next and prev pointers, 1086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // since they point to something that does not point at us. This is used 1096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // inside the shouldExpand() "if" in HashTable::add. 1106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase(const LinkedHashSetNodeBase& other) 1116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : m_prev(0) 1126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , m_next(0) { } 1136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 1156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Should not be used. 1166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other); 1176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 1186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1197242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename ValueArg, typename Allocator> 1206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetNode : public LinkedHashSetNodeBase { 1216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 1226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNode(const ValueArg& value, LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next) 1236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : LinkedHashSetNodeBase(prev, next) 1246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , m_value(value) 1256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 1266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 1276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ValueArg m_value; 1296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 1316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Not used. 1326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetNode(const LinkedHashSetNode&); 1336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 1346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate< 1366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename ValueArg, 1376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename HashFunctions = typename DefaultHash<ValueArg>::Hash, 1386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename TraitsArg = HashTraits<ValueArg>, 1396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename Allocator = DefaultAllocator> 1406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSet { 141f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu WTF_USE_ALLOCATOR(LinkedHashSet, Allocator); 1426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 1436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef ValueArg Value; 1446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef TraitsArg Traits; 1457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci typedef LinkedHashSetNode<Value, Allocator> Node; 1466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetNodeBase NodeBase; 1477242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci typedef LinkedHashSetTranslator<Value, HashFunctions, Allocator> NodeHashFunctions; 1487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci typedef LinkedHashSetTraits<Value, Traits, Allocator> NodeHashTraits; 1496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef HashTable<Node, Node, IdentityExtractor, 1516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch NodeHashFunctions, NodeHashTraits, NodeHashTraits, Allocator> ImplType; 1526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 1546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetIterator<LinkedHashSet> iterator; 1556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch friend class LinkedHashSetIterator<LinkedHashSet>; 1566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetConstIterator<LinkedHashSet> const_iterator; 1576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch friend class LinkedHashSetConstIterator<LinkedHashSet>; 1586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetReverseIterator<LinkedHashSet> reverse_iterator; 1606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch friend class LinkedHashSetReverseIterator<LinkedHashSet>; 1616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetConstReverseIterator<LinkedHashSet> const_reverse_iterator; 1626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch friend class LinkedHashSetConstReverseIterator<LinkedHashSet>; 1636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch struct AddResult { 1656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult(const typename ImplType::AddResult& hashTableAddResult) 1666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : storedValue(&hashTableAddResult.storedValue->m_value) 1676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , isNewEntry(hashTableAddResult.isNewEntry) 1686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 1696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 1706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Value* storedValue; 1726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool isNewEntry; 1736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch }; 1746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename HashTraits<Value>::PeekInType ValuePeekInType; 1766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSet(); 1786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSet(const LinkedHashSet&); 1796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSet& operator=(const LinkedHashSet&); 180f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles) 181f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles) // Needs finalization. The anchor needs to unlink itself from the chain. 1826f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ~LinkedHashSet(); 1836f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static void finalize(void* pointer) { reinterpret_cast<LinkedHashSet*>(pointer)->~LinkedHashSet(); } 1856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void swap(LinkedHashSet&); 1876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch unsigned size() const { return m_impl.size(); } 1896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch unsigned capacity() const { return m_impl.capacity(); } 1906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool isEmpty() const { return m_impl.isEmpty(); } 1916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1926f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator begin() { return makeIterator(firstNode()); } 1936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator end() { return makeIterator(anchor()); } 1946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator begin() const { return makeConstIterator(firstNode()); } 1956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator end() const { return makeConstIterator(anchor()); } 1966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 1976f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch reverse_iterator rbegin() { return makeReverseIterator(lastNode()); } 1986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch reverse_iterator rend() { return makeReverseIterator(anchor()); } 1996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_reverse_iterator rbegin() const { return makeConstReverseIterator(lastNode()); } 2006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_reverse_iterator rend() const { return makeConstReverseIterator(anchor()); } 2016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Value& first(); 2036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Value& first() const; 2046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void removeFirst(); 2056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Value& last(); 2076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Value& last() const; 2086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void removeLast(); 2096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator find(ValuePeekInType); 2116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator find(ValuePeekInType) const; 2126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool contains(ValuePeekInType) const; 2136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // An alternate version of find() that finds the object by hashing and comparing 2156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // with some other type, to avoid the cost of type conversion. 2166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // The HashTranslator interface is defined in HashSet. 2176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename HashTranslator, typename T> iterator find(const T&); 2186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename HashTranslator, typename T> const_iterator find(const T&) const; 2196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename HashTranslator, typename T> bool contains(const T&) const; 2206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // The return value of add is a pair of a pointer to the stored value, 2226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // and a bool that is true if an new entry was added. 2236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult add(ValuePeekInType); 2246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Same as add() except that the return value is an 2266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // iterator. Useful in cases where it's needed to have the 2276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // same return value as find() and where it's not possible to 2286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // use a pointer to the storedValue. 2296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator addReturnIterator(ValuePeekInType); 2306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Add the value to the end of the collection. If the value was already in 2326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // the list, it is moved to the end. 2336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult appendOrMoveToLast(ValuePeekInType); 2346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Add the value to the beginning of the collection. If the value was already in 2366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // the list, it is moved to the beginning. 2376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult prependOrMoveToFirst(ValuePeekInType); 2386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue); 2406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch AddResult insertBefore(iterator it, ValuePeekInType newValue) { return m_impl.template add<NodeHashFunctions>(newValue, it.node()); } 2416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void remove(ValuePeekInType); 2436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void remove(iterator); 2446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void clear() { m_impl.clear(); } 245f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu template<typename Collection> 246f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu void removeAll(const Collection& other) { WTF::removeAll(*this, other); } 2476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2486f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); } 2496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch int64_t modifications() const { return m_impl.modifications(); } 2516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void checkModifications(int64_t mods) const { m_impl.checkModifications(mods); } 2526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 2546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); } 2556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Node* anchor() const { return reinterpret_cast<const Node*>(&m_anchor); } 2566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* firstNode() { return reinterpret_cast<Node*>(m_anchor.m_next); } 2576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Node* firstNode() const { return reinterpret_cast<const Node*>(m_anchor.m_next); } 2586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* lastNode() { return reinterpret_cast<Node*>(m_anchor.m_prev); } 2596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Node* lastNode() const { return reinterpret_cast<const Node*>(m_anchor.m_prev); } 2606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator makeIterator(const Node* position) { return iterator(position, this); } 2626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator makeConstIterator(const Node* position) const { return const_iterator(position, this); } 2636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch reverse_iterator makeReverseIterator(const Node* position) { return reverse_iterator(position, this); } 2646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_reverse_iterator makeConstReverseIterator(const Node* position) const { return const_reverse_iterator(position, this); } 2656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ImplType m_impl; 2676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch NodeBase m_anchor; 2686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 2696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename HashFunctions, typename Allocator> 2716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochstruct LinkedHashSetTranslator { 2727242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci typedef LinkedHashSetNode<Value, Allocator> Node; 2736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetNodeBase NodeBase; 2746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename HashTraits<Value>::PeekInType ValuePeekInType; 2756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); } 2766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static unsigned hash(const ValuePeekInType& key) { return HashFunctions::hash(key); } 2776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static bool equal(const Node& a, const ValuePeekInType& b) { return HashFunctions::equal(a.m_value, b); } 2786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); } 2796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static void translate(Node& location, ValuePeekInType key, NodeBase* anchor) 2806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 2816f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch anchor->insertBefore(location); 2827242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci location.m_value = key; 2836f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 2846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Empty (or deleted) slots have the m_next pointer set to null, but we 2866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // don't do anything to the other fields, which may contain junk. 2876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Therefore you can't compare a newly constructed empty value with a 2886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // slot and get the right answer. 2896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const bool safeToCompareToEmptyOrDeleted = false; 2906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 2916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2927242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename Allocator> 2936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochstruct LinkedHashSetExtractor { 2947242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci static const Value& extract(const LinkedHashSetNode<Value, Allocator>& node) { return node.m_value; } 2956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 2966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 2977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Value, typename ValueTraitsArg, typename Allocator> 2987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccistruct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator> > { 2997242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci typedef LinkedHashSetNode<Value, Allocator> Node; 3006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef ValueTraitsArg ValueTraits; 3016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // The slot is empty when the m_next field is zero so it's safe to zero 3036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // the backing. 3046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const bool emptyValueIsZero = true; 3056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const bool hasIsEmptyValueFunction = true; 3075d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) static bool isEmptyValue(const Node& node) { return !node.m_next; } 3086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const int deletedValue = -1; 3106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3117242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci static void constructDeletedValue(Node& slot, bool) { slot.m_next = reinterpret_cast<Node*>(deletedValue); } 3126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); } 3136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // We always need to call destructors, that's how we get linked and 3156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // unlinked from the chain. 3166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const bool needsDestruction = true; 3176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Whether we need to trace and do weak processing depends on the traits of 3196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // the type inside the node. 3206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename U = void> 3216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch struct NeedsTracingLazily { 3226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch static const bool value = ValueTraits::template NeedsTracingLazily<>::value; 3236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch }; 3245d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles) static const WeakHandlingFlag weakHandlingFlag = ValueTraits::weakHandlingFlag; 3256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 3266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSetType> 3286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetIterator { 3296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 3306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Node Node; 3316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Traits Traits; 3326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Value& ReferenceType; 3346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Value* PointerType; 3356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator; 3376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* node() { return const_cast<Node*>(m_iterator.node()); } 3396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprotected: 3416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container) 3426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : m_iterator(position , m_container) 3436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 3446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 3456f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 3476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Default copy, assignment and destructor are OK. 3486f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 3506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ReferenceType operator*() const { return *get(); } 3516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch PointerType operator->() const { return get(); } 3526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetIterator& operator++() { ++m_iterator; return *this; } 3546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetIterator& operator--() { --m_iterator; return *this; } 3556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Postfix ++ and -- intentionally omitted. 3576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Comparison. 3596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; } 3606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; } 3616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch operator const_iterator() const { return m_iterator; } 3636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprotected: 3656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator m_iterator; 3666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 3676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 3686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSetType> 3706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetConstIterator { 3716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 3726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Node Node; 3736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Traits Traits; 3746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef const typename LinkedHashSetType::Value& ReferenceType; 3766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef const typename LinkedHashSetType::Value* PointerType; 3776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const Node* node() const { return static_cast<const Node*>(m_position); } 3796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprotected: 3816f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstIterator(const LinkedHashSetNodeBase* position, const LinkedHashSetType* container) 3826f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : m_position(position) 383197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 3846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , m_container(container) 3856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch , m_containerModifications(container->modifications()) 3866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#endif 3876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 3886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 3896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 3916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch PointerType get() const 3926f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 3936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch checkModifications(); 3946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return &static_cast<const Node*>(m_position)->m_value; 3956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 3966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ReferenceType operator*() const { return *get(); } 3976f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch PointerType operator->() const { return get(); } 3986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 3996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstIterator& operator++() 4006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 4016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_position); 4026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch checkModifications(); 4036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_position = m_position->m_next; 4046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return *this; 4056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 4066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstIterator& operator--() 4086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 4096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(m_position); 4106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch checkModifications(); 4116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_position = m_position->m_prev; 4126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return *this; 4136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 4146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Postfix ++ and -- intentionally omitted. 4166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Comparison. 4186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool operator==(const LinkedHashSetConstIterator& other) const 4196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 4206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return m_position == other.m_position; 4216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 4226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch bool operator!=(const LinkedHashSetConstIterator& other) const 4236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch { 4246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return m_position != other.m_position; 4256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 4266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprivate: 4286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const LinkedHashSetNodeBase* m_position; 429197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 4306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void checkModifications() const { m_container->checkModifications(m_containerModifications); } 4316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const LinkedHashSetType* m_container; 4326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch int64_t m_containerModifications; 4336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#else 4346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch void checkModifications() const { } 4356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#endif 4366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 4376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch friend class LinkedHashSetIterator<LinkedHashSetType>; 4386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 4396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSetType> 4416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> { 4426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetIterator<LinkedHashSetType> Superclass; 4436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator; 4446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Node Node; 4456f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochprotected: 4476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container) 4486f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : Superclass(position, container) { } 4496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 4516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; } 4526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; } 4536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Postfix ++ and -- intentionally omitted. 4556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); } 4576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 4596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 4606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename LinkedHashSetType> 4626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochclass LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> { 4636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass; 4646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSetType::Node Node; 4656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochpublic: 4676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container) 4686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : Superclass(position, container) { } 4696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; } 4716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; } 4726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // Postfix ++ and -- intentionally omitted. 4746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T, typename U, typename V, typename W> friend class LinkedHashSet; 4766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 4776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 4796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline LinkedHashSet<T, U, V, W>::LinkedHashSet() { } 4806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4816f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 4826f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other) 4836f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch : m_anchor() 4846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 4856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const_iterator end = other.end(); 4866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch for (const_iterator it = other.begin(); it != end; ++it) 4876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch add(*it); 4886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 4896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 4916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other) 4926f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 4936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSet tmp(other); 4946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch swap(tmp); 4956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return *this; 4966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 4976f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 4986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 4996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other) 5006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_impl.swap(other.m_impl); 502e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) swapAnchor(m_anchor, other.m_anchor); 5036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename Allocator> 5066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet() 5076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // The destructor of m_anchor will implicitly be called here, which will 5096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch // unlink the anchor from the collection. 5106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline T& LinkedHashSet<T, U, V, W>::first() 5146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return firstNode()->m_value; 5176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline const T& LinkedHashSet<T, U, V, W>::first() const 5216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return firstNode()->m_value; 5246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void LinkedHashSet<T, U, V, W>::removeFirst() 5286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_impl.remove(static_cast<Node*>(m_anchor.m_next)); 5316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline T& LinkedHashSet<T, U, V, W>::last() 5356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return lastNode()->m_value; 5386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline const T& LinkedHashSet<T, U, V, W>::last() const 5426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return lastNode()->m_value; 5456f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5486f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void LinkedHashSet<T, U, V, W>::removeLast() 5496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch ASSERT(!isEmpty()); 5516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_impl.remove(static_cast<Node*>(m_anchor.m_prev)); 5526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) 5566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 5586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!node) 5596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return end(); 5606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return makeIterator(node); 5616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 5646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(ValuePeekInType value) const 5656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, ValuePeekInType>(value); 5676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!node) 5686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return end(); 5696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return makeConstIterator(node); 5706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Translator> 5736f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochstruct LinkedHashSetTranslatorAdapter { 5746f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); } 5756f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a.m_value, b); } 5766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}; 5776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Value, typename U, typename V, typename W> 5796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename HashTranslator, typename T> 5806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value) 5816f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5826f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 5836f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 5846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!node) 5856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return end(); 5866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return makeIterator(node); 5876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 5896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Value, typename U, typename V, typename W> 5906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename HashTranslator, typename T> 5916f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const 5926f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 5936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetTranslatorAdapter<HashTranslator> TranslatedFunctions; 5946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch const LinkedHashSet::Node* node = m_impl.template lookup<TranslatedFunctions, const T&>(value); 5956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!node) 5966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return end(); 5976f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return makeConstIterator(node); 5986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 5996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Value, typename U, typename V, typename W> 6016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename HashTranslator, typename T> 6026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const 6036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value); 6056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6086f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline bool LinkedHashSet<T, U, V, W>::contains(ValuePeekInType value) const 6096f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return m_impl.template contains<NodeHashFunctions>(value); 6116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6126f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename Value, typename HashFunctions, typename Traits, typename Allocator> 6146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtypename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(ValuePeekInType value) 6156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return m_impl.template add<NodeHashFunctions>(value, &m_anchor); 6176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtypename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(ValuePeekInType value) 6216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 6236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return makeIterator(result.storedValue); 6246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtypename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(ValuePeekInType value) 6286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, &m_anchor); 6306f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* node = result.storedValue; 6316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!result.isNewEntry) { 6326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch node->unlink(); 6336f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_anchor.insertBefore(*node); 6346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 6356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return result; 6366f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtypename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(ValuePeekInType value) 6406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value, m_anchor.m_next); 6426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch Node* node = result.storedValue; 6436f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (!result.isNewEntry) { 6446f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch node->unlink(); 6456f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_anchor.insertAfter(*node); 6466f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 6476f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return result; 6486f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtypename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(ValuePeekInType beforeValue, ValuePeekInType newValue) 6526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return insertBefore(find(beforeValue), newValue); 6546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void LinkedHashSet<T, U, V, W>::remove(iterator it) 6586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6596f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (it == end()) 6606f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch return; 6616f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch m_impl.remove(it.node()); 6626f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6636f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 6646f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename T, typename U, typename V, typename W> 6656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void LinkedHashSet<T, U, V, W>::remove(ValuePeekInType value) 6666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 6676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch remove(find(value)); 6686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 6696f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 670e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)inline void swapAnchor(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) 671e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles){ 672e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(a.m_prev && a.m_next && b.m_prev && b.m_next); 673e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) swap(a.m_prev, b.m_prev); 674e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) swap(a.m_next, b.m_next); 675e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) if (b.m_next == &a) { 676e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(b.m_prev == &a); 677e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) b.m_next = &b; 678e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) b.m_prev = &b; 679e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) } else { 680e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) b.m_next->m_prev = &b; 681e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) b.m_prev->m_next = &b; 682e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) } 683e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) if (a.m_next == &b) { 684e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(a.m_prev == &b); 685e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) a.m_next = &a; 686e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) a.m_prev = &a; 687e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) } else { 688e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) a.m_next->m_prev = &a; 689e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) a.m_prev->m_next = &a; 690e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) } 691e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)} 692e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) 6936f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochinline void swap(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b) 6946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 695e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles) ASSERT(a.m_next != &a && b.m_next != &b); 6966f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch swap(a.m_prev, b.m_prev); 697323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) swap(a.m_next, b.m_next); 6986f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (b.m_next) { 6996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch b.m_next->m_prev = &b; 7006f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch b.m_prev->m_next = &b; 7016f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 7026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch if (a.m_next) { 7036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch a.m_next->m_prev = &a; 7046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch a.m_prev->m_next = &a; 7056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 7066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 7076f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 7087242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename T, typename Allocator> 7097242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucciinline void swap(LinkedHashSetNode<T, Allocator>& a, LinkedHashSetNode<T, Allocator>& b) 7106f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 7116f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef LinkedHashSetNodeBase Base; 7127242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci Allocator::enterNoAllocationScope(); 7136f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch swap(static_cast<Base&>(a), static_cast<Base&>(b)); 7146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch swap(a.m_value, b.m_value); 7157242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci Allocator::leaveNoAllocationScope(); 7166f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 7176f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 7186f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// Warning: After and while calling this you have a collection with deleted 7196f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// pointers. Consider using a smart pointer like OwnPtr and calling clear() 7206f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch// instead. 7216f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochtemplate<typename ValueType, typename T, typename U> 7226f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochvoid deleteAllValues(const LinkedHashSet<ValueType, T, U>& set) 7236f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{ 7246f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch typedef typename LinkedHashSet<ValueType, T, U>::const_iterator iterator; 7256f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch iterator end = set.end(); 7266f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch for (iterator it = set.begin(); it != end; ++it) 7276f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch delete *it; 7286f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 7296f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 730197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(OILPAN) 731197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename T, typename U, typename V> 732197021e6b966cfb06891637935ef33fff06433d1Ben Murdochstruct NeedsTracing<LinkedHashSet<T, U, V> > { 733197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static const bool value = false; 734197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}; 735197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif 736197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 7376f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch} 7386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 7396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdochusing WTF::LinkedHashSet; 7406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch 7416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch#endif /* WTF_LinkedHashSet_h */ 742