Create HeapLinkedHashSet and LinkedHashSet, ordered heap-friendly hash sets.

Source/wtf/LinkedHashSet.h

+/*
+ * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.

[Mads Ager (chromium), 2014/04/03 09:24:35]

Ehm, no.

You should use the short copyright notice here for new files.

+ * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef WTF_LinkedHashSet_h
+#define WTF_LinkedHashSet_h
+
+#include "wtf/DefaultAllocator.h"
+#include "wtf/HashSet.h"
+#include "wtf/OwnPtr.h"
+#include "wtf/PassOwnPtr.h"
+
+namespace WTF {
+
+// LinkedHashSet: Just like HashSet, this class provides a Set
+// interface - a collection of unique objects with O(1) insertion,
+// removal and test for containership. However, it also has an
+// order - iterating it will always give back values in the order
+// in which they are added.
+
+// Unlike ListHashSet, but like most WTF collections, iteration is NOT safe
+// against mutation of the LinkedHashSet.
+
+template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator> class LinkedHashSet;
+
+template<typename LinkedHashSet> class LinkedHashSetIterator;
+template<typename LinkedHashSet> class LinkedHashSetConstIterator;
+template<typename LinkedHashSet> class LinkedHashSetReverseIterator;
+template<typename LinkedHashSet> class LinkedHashSetConstReverseIterator;
+
+template<typename Value, typename HashFunctions> struct LinkedHashSetTranslator;
+template<typename Value> struct LinkedHashSetExtractor;
+template<typename Value, typename ValueTraits> struct LinkedHashSetTraits;
+
+struct LinkedHashSetNodeBase {

[Mikhail, 2014/04/03 09:32:18]

this actually better to be class (since it's not a real C-style struct)

[Mads Ager (chromium), 2014/04/03 09:44:58]

Why not class?

[Erik Corry, 2014/04/10 10:47:37]

Done.

[Erik Corry, 2014/04/10 10:47:37]

Done.

+    ~LinkedHashSetNodeBase()

[Mikhail, 2014/04/03 09:32:18]

Can nodes be deleted via base interface? should the destructor be virtual? (if
should not, I think it's worth making it protected)

[Erik Corry, 2014/04/10 10:47:37]

There's no virtualness here and we don't want to bloat the object.

There's a base node in the LinkedHashSet, the anchor, so we can't make the
destructor protected.

I moved the destructor to be after the constructor, which is more conventional.

+    {
+        if (!m_next)
+            return;
+        ASSERT(m_prev);
+        ASSERT(m_next->m_prev == this);
+        ASSERT(m_prev->m_next == this);
+        m_next->m_prev = m_prev;
+        m_prev->m_next = m_next;
+    }
+
+    LinkedHashSetNodeBase() : m_prev(this), m_next(this) { }
+
+    void insertBefore(LinkedHashSetNodeBase& other)
+    {
+        ASSERT(!other.m_next);
+        ASSERT(!other.m_prev);
+        other.m_next = this;
+        other.m_prev = m_prev;
+        m_prev->m_next = &other;
+        m_prev = &other;
+        ASSERT(other.m_next);
+        ASSERT(other.m_prev);
+        ASSERT(m_next);
+        ASSERT(m_prev);
+    }
+
+    LinkedHashSetNodeBase(LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
+        : m_prev(prev)
+        , m_next(next)
+    {
+        ASSERT((prev && next) || (!prev && !next));
+    }
+
+    LinkedHashSetNodeBase* m_prev;
+    LinkedHashSetNodeBase* m_next;
+
+protected:
+    // If we take a copy of a node we can't copy the next and prev pointers,
+    // since they point to something that does not point at us. This is used
+    // inside the shouldExpand() "if" in HashTable::add.
+    LinkedHashSetNodeBase(const LinkedHashSetNodeBase& other)

[Mikhail, 2014/04/03 09:32:18]

Do we have cases when nodes are copied? 

[Erik Corry, 2014/04/10 10:47:37]

Yes, as explained in the comment.

+        : m_prev(0)
+        , m_next(0) { }
+
+private:
+    // Should not be used.
+    LinkedHashSetNodeBase& operator=(const LinkedHashSetNodeBase& other);
+};
+
+template<typename ValueArg>
+struct LinkedHashSetNode : public LinkedHashSetNodeBase {

[Mads Ager (chromium), 2014/04/03 09:44:58]

class?

[Erik Corry, 2014/04/10 10:47:37]

Done.

+    LinkedHashSetNode(const ValueArg& value, LinkedHashSetNodeBase* prev, LinkedHashSetNodeBase* next)
+        : LinkedHashSetNodeBase(prev, next)
+        , m_value(value)
+    {
+    }

[Mikhail, 2014/04/03 09:32:18]

If you want 'LinkedHashSetNodeBase' copy constructor to actually work you should
probably define a copy constructor here as well (and it should invoke parent's
copy constructor explicitly)

[Erik Corry, 2014/04/10 10:47:37]

I made the copy constructor for this class undefined and private instead, since
it's not used.

+
+    ValueArg m_value;
+};
+
+template<
+    typename ValueArg,
+    typename HashFunctions = typename DefaultHash<ValueArg>::Hash,
+    typename TraitsArg = HashTraits<ValueArg>,
+    typename Allocator = DefaultAllocator>
+    class LinkedHashSet {

[Mads Ager (chromium), 2014/04/03 09:44:58]

Indentation

[Erik Corry, 2014/04/10 10:47:37]

Done.

+private:
+    typedef ValueArg Value;
+    typedef TraitsArg Traits;
+    typedef LinkedHashSetNode<Value> Node;
+    typedef LinkedHashSetNodeBase NodeBase;
+    typedef LinkedHashSetTranslator<Value, HashFunctions> NodeHashFunctions;
+    typedef LinkedHashSetTraits<Value, Traits> NodeHashTraits;
+
+    typedef HashTable<Node, Node, IdentityExtractor,

[Mikhail, 2014/04/03 09:32:18]

Why not "HashTable<Node*, Node*" ?

[Erik Corry, 2014/04/10 10:47:37]

Then we would have to allocate lots of small Node objects.  This way they are
inlined in the backing store.

For the Heap version of LinkedHashSet there is the extra consideration that this
enables the weak processing to work: There is one backing store and the iterator
points into it, causing the weak processing to be disabled while the iterator
exists on the stack.

+        NodeHashFunctions, NodeHashTraits, NodeHashTraits, Allocator> ImplType;
+
+public:
+    typedef LinkedHashSetIterator<LinkedHashSet> iterator;
+    friend class LinkedHashSetIterator<LinkedHashSet>;
+    typedef LinkedHashSetConstIterator<LinkedHashSet> const_iterator;
+    friend class LinkedHashSetConstIterator<LinkedHashSet>;
+
+    typedef LinkedHashSetReverseIterator<LinkedHashSet> reverse_iterator;
+    friend class LinkedHashSetReverseIterator<LinkedHashSet>;
+    typedef LinkedHashSetConstReverseIterator<LinkedHashSet> const_reverse_iterator;
+    friend class LinkedHashSetConstReverseIterator<LinkedHashSet>;
+
+    struct AddResult {
+        AddResult(const typename ImplType::AddResult& hashTableAddResult)
+            : storedValue(&hashTableAddResult.storedValue->m_value)
+            , isNewEntry(hashTableAddResult.isNewEntry) { }

[Mads Ager (chromium), 2014/04/03 09:44:58]

When you are using multiple lines you should have the '{}' on separate lines:

...
{
}

[Erik Corry, 2014/04/10 10:47:37]

Done.

+
+        Value* storedValue;
+        bool isNewEntry;
+    };
+
+    void* operator new(size_t size)
+    {
+        return Allocator::template malloc<void*, LinkedHashSet>(size);
+    }
+    void operator delete(void* p) { Allocator::free(p); }
+    void* operator new[](size_t size) { return Allocator::template newArray<LinkedHashSet>(size); }
+    void operator delete[](void* p) { Allocator::deleteArray(p); }
+    void* operator new(size_t, NotNullTag, void* location)
+    {
+        COMPILE_ASSERT(!Allocator::isGarbageCollected, Garbage_collector_must_be_disabled);
+        ASSERT(location);
+        return location;
+    }
+
+    LinkedHashSet();
+    LinkedHashSet(const LinkedHashSet&);
+    LinkedHashSet& operator=(const LinkedHashSet&);
+    ~LinkedHashSet();
+
+    static void finalize(void* pointer) { reinterpret_cast<LinkedHashSet*>(pointer)->~LinkedHashSet(); }
+
+    void swap(LinkedHashSet&);
+
+    unsigned size() const { return m_impl.size(); }
+    unsigned capacity() const { return m_impl.capacity(); }
+    bool isEmpty() const { return m_impl.isEmpty(); }
+
+    iterator begin() { return makeIterator(firstNode()); }
+    iterator end() { return makeIterator(anchor()); }
+    const_iterator begin() const { return makeConstIterator(firstNode()); }
+    const_iterator end() const { return makeConstIterator(anchor()); }
+
+    reverse_iterator rbegin() { return makeReverseIterator(lastNode()); }
+    reverse_iterator rend() { return makeReverseIterator(anchor()); }
+    const_reverse_iterator rbegin() const { return makeConstReverseIterator(lastNode()); }
+    const_reverse_iterator rend() const { return makeConstReverseIterator(anchor()); }
+
+    Value& first();
+    const Value& first() const;
+    void removeFirst();
+
+    Value& last();
+    const Value& last() const;
+    void removeLast();
+
+    iterator find(const Value&);

[Mikhail, 2014/04/03 09:32:18]

maybe 'ValuePeekInType' is worth using here?

[Erik Corry, 2014/04/10 10:47:37]

Good idea.  Done.

To do this I had to change the type of the templated lookup function in
HashTable.h.  I checked all the places it was called to make sure that it was
still passing references, and not dereffing, causing ref pointer churn.

+    const_iterator find(const Value&) const;
+    bool contains(const Value&) const;
+
+    // An alternate version of find() that finds the object by hashing and comparing
+    // with some other type, to avoid the cost of type conversion.
+    // The HashTranslator interface is defined in HashSet.
+    template<typename HashTranslator, typename T> iterator find(const T&);
+    template<typename HashTranslator, typename T> const_iterator find(const T&) const;
+    template<typename HashTranslator, typename T> bool contains(const T&) const;
+
+    // The return value of add is a pair of a pointer to the stored value,
+    // and a bool that is true if an new entry was added.
+    AddResult add(const Value&);
+
+    // Same as add() except that the return value is an
+    // iterator. Useful in cases where it's needed to have the
+    // same return value as find() and where it's not possible to
+    // use a pointer to the storedValue.
+    iterator addReturnIterator(const Value&);
+
+    // Add the value to the end of the collection. If the value was already in
+    // the list, it is moved to the end.
+    AddResult appendOrMoveToLast(const Value&);
+
+    // Add the value to the beginning of the collection. If the value was already in
+    // the list, it is moved to the beginning.
+    AddResult prependOrMoveToFirst(const Value&);
+
+    AddResult insertBefore(const Value& beforeValue, const Value& newValue);
+    AddResult insertBefore(iterator, const Value&);
+
+    void remove(const Value&);
+    void remove(iterator);
+    void clear() { m_impl.clear(); }
+
+    void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); }
+
+    int64_t modifications() const { return m_impl.modifications(); }
+    void checkModifications(int64_t mods) const { m_impl.checkModifications(mods); }
+
+private:
+    void unlink(Node*);
+    void insertNodeBefore(Node* beforeNode, Node* newNode);
+
+    Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); }
+    const Node* anchor() const { return reinterpret_cast<const Node*>(&m_anchor); }
+    Node* firstNode() { return reinterpret_cast<Node*>(m_anchor.m_next); }
+    const Node* firstNode() const { return reinterpret_cast<const Node*>(m_anchor.m_next); }
+    Node* lastNode() { return reinterpret_cast<Node*>(m_anchor.m_prev); }
+    const Node* lastNode() const { return reinterpret_cast<const Node*>(m_anchor.m_prev); }
+
+    iterator makeIterator(const Node* position) { return iterator(position, this); }
+    const_iterator makeConstIterator(const Node* position) const { return const_iterator(position, this); }
+    reverse_iterator makeReverseIterator(const Node* position) { return reverse_iterator(position, this); }
+    const_reverse_iterator makeConstReverseIterator(const Node* position) const { return const_reverse_iterator(position, this); }
+
+    ImplType m_impl;
+    NodeBase m_anchor;

[Mikhail, 2014/04/03 09:32:18]

Could you pls explain why not working with pointers (NodeBase* m_anchor;) like
ListHashSet does?

[Erik Corry, 2014/04/10 10:47:37]

Locality of reference, pressure on the allocator, ease of getting the weak
processing support working.

+#ifndef NDEBUG
+    uint64_t m_modifications;
+#endif
+};
+
+template<typename Value, typename HashFunctions>
+struct LinkedHashSetTranslator {
+    typedef LinkedHashSetNode<Value> Node;
+    typedef LinkedHashSetNodeBase NodeBase;
+    static unsigned hash(const Node& node) { return HashFunctions::hash(node.m_value); }
+    static unsigned hash(const Value& key) { return HashFunctions::hash(key); }
+    static bool equal(const Value& a, const Value& b) { return HashFunctions::equal(a, b); }
+    static bool equal(const Node& a, const Value& b) { return HashFunctions::equal(a.m_value, b); }
+    static bool equal(const Value& a, const Node& b) { return HashFunctions::equal(a, b.m_value); }
+    static bool equal(const Node& a, const Node& b) { return HashFunctions::equal(a.m_value, b.m_value); }
+    static void translate(Node& location, const Value& key, NodeBase* anchor)
+    {
+        location.m_value = key;
+        anchor->insertBefore(location);
+    }
+
+    // Empty (or deleted) slots have the m_next pointer set to null, but we
+    // don't do anything to the other fields, which may contain junk.
+    // Therefore you can't compare a newly constructed empty value with a
+    // slot and get the right answer.
+    static const bool safeToCompareToEmptyOrDeleted = false;
+};
+
+template<typename Value>
+struct LinkedHashSetExtractor {
+    static const Value& extract(const LinkedHashSetNode<Value>& node) { return node.m_value; }
+};
+
+template<typename Value, typename ValueTraitsArg>
+struct LinkedHashSetTraits : public SimpleClassHashTraits<LinkedHashSetNode<Value> > {
+    typedef LinkedHashSetNode<Value> Node;
+    typedef ValueTraitsArg ValueTraits;
+
+    // The slot is empty when the m_next field is zero so it's safe to zero
+    // the backing.
+    static const bool emptyValueIsZero = true;
+
+    static const bool hasIsEmptyValueFunction = true;
+    static bool isEmptyValue(const Node& value) { return !value.m_next; }
+
+    static const int deletedValue = -1;
+
+    static void constructDeletedValue(Node& slot) { slot.m_next = reinterpret_cast<Node*>(deletedValue); }
+    static bool isDeletedValue(const Node& slot) { return slot.m_next == reinterpret_cast<Node*>(deletedValue); }
+
+    // We always need to call destructors, that's how we get linked and
+    // unlinked from the chain.
+    static const bool needsDestruction = true;
+
+    // Whether we need to trace and do weak processing depends on the traits of
+    // the type inside the node.
+    template<typename U = void>
+    struct NeedsTracingLazily {
+        static const bool value = ValueTraits::template NeedsTracingLazily<>::value;
+    };
+    static const bool isWeak = ValueTraits::isWeak;
+};
+
+template<typename LinkedHashSetType>
+class LinkedHashSetIterator {
+private:
+    typedef typename LinkedHashSetType::Node Node;
+    typedef typename LinkedHashSetType::Traits Traits;
+
+    typedef typename LinkedHashSetType::Value& ReferenceType;
+    typedef typename LinkedHashSetType::Value* PointerType;
+
+    typedef LinkedHashSetConstIterator<LinkedHashSetType> const_iterator;
+
+    Node* node() const { return const_cast<Node*>(m_iterator.node()); }
+
+protected:
+    LinkedHashSetIterator(const Node* position, LinkedHashSetType* m_container)
+        : m_iterator(position , m_container)
+    {
+    }
+
+public:
+    // default copy, assignment and destructor are OK

[Mads Ager (chromium), 2014/04/03 09:44:58]

Begin comment with capital letter and end with period?

[Erik Corry, 2014/04/10 10:47:37]

Done.

+
+    PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
+    ReferenceType operator*() const { return *get(); }
+    PointerType operator->() const { return get(); }
+
+    LinkedHashSetIterator& operator++() { ++m_iterator; return *this; }
+    LinkedHashSetIterator& operator--() { --m_iterator; return *this; }
+
+    // Postfix ++ and -- intentionally omitted.
+
+    // Comparison.
+    bool operator==(const LinkedHashSetIterator& other) const { return m_iterator == other.m_iterator; }
+    bool operator!=(const LinkedHashSetIterator& other) const { return m_iterator != other.m_iterator; }
+
+    operator const_iterator() const { return m_iterator; }
+
+protected:
+    const_iterator m_iterator;
+    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
+};
+
+template<typename LinkedHashSetType>
+class LinkedHashSetConstIterator {
+private:
+    typedef typename LinkedHashSetType::Node Node;
+    typedef typename LinkedHashSetType::Traits Traits;
+
+    typedef const typename LinkedHashSetType::Value& ReferenceType;
+    typedef const typename LinkedHashSetType::Value* PointerType;
+
+    const Node* node() const { return static_cast<const Node*>(m_position); }
+
+protected:
+    LinkedHashSetConstIterator(
+        const LinkedHashSetNodeBase* position,

[Mads Ager (chromium), 2014/04/03 09:44:58]

Very strange indentation. Just put this on one line?

[Erik Corry, 2014/04/10 10:47:37]

Done (I had some ifdefs here, but I got rid of them and forgot to normalize the
line breaks)

+        const LinkedHashSetType* container
+        )
+        : m_position(position)
+#ifndef NDEBUG

[Mikhail, 2014/04/03 09:32:18]

#ifdef ASSERT_ENABLED ? (same in other similar places)

[Erik Corry, 2014/04/10 10:47:37]

Done.

+        , m_container(container)
+        , m_containerModifications(container->modifications())
+#endif
+    {
+    }
+
+public:
+    PointerType get() const
+    {
+        checkModifications();
+        return &static_cast<const Node*>(m_position)->m_value;
+    }
+    ReferenceType operator*() const { return *get(); }
+    PointerType operator->() const { return get(); }
+
+    LinkedHashSetConstIterator& operator++()
+    {
+        ASSERT(m_position);
+        checkModifications();
+        m_position = m_position->m_next;
+        return *this;
+    }
+
+    LinkedHashSetConstIterator& operator--()
+    {
+        ASSERT(m_position);
+        checkModifications();
+        m_position = m_position->m_prev;
+        return *this;
+    }
+
+    // Postfix ++ and -- intentionally omitted.
+
+    // Comparison.
+    bool operator==(const LinkedHashSetConstIterator& other) const
+    {
+        return m_position == other.m_position;
+    }
+    bool operator!=(const LinkedHashSetConstIterator& other) const
+    {
+        return m_position != other.m_position;
+    }
+
+private:
+    const LinkedHashSetNodeBase* m_position;
+#ifdef NDEBUG

[Mads Ager (chromium), 2014/04/03 09:44:58]

These were guarded by ASSERT_ENABLED or something like that in hash table. Do
the same here?

[Erik Corry, 2014/04/10 10:47:37]

Done.

+    void checkModifications() const { }
+#else
+    void checkModifications() const { m_container->checkModifications(m_containerModifications); }
+    const LinkedHashSetType* m_container;

[Mikhail, 2014/04/03 09:32:18]

I guess m_container can be const pointer: const LinkedHashSetType* const
m_container;

[Erik Corry, 2014/04/10 10:47:37]

It turns out if you do this then you can't overwrite an iterator with the
assignment operator.  You can do that with the ListHashSet iterators, so I want
to be able to do that with these.  I also removed the const in
m_containerModifications.

+    const int64_t m_containerModifications;
+#endif
+    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
+    friend class LinkedHashSetIterator<LinkedHashSetType>;
+};
+
+template<typename LinkedHashSetType>
+class LinkedHashSetReverseIterator : public LinkedHashSetIterator<LinkedHashSetType> {
+    typedef LinkedHashSetIterator<LinkedHashSetType> Superclass;
+    typedef LinkedHashSetConstReverseIterator<LinkedHashSetType> const_reverse_iterator;
+    typedef typename LinkedHashSetType::Node Node;
+
+protected:
+    LinkedHashSetReverseIterator(const Node* position, LinkedHashSetType* container)
+        : Superclass(position, container) { }
+
+public:
+    LinkedHashSetReverseIterator& operator++() { Superclass::operator--(); return *this; }
+    LinkedHashSetReverseIterator& operator--() { Superclass::operator++(); return *this; }
+
+    // Postfix ++ and -- intentionally omitted.
+
+    operator const_reverse_iterator() const { return *reinterpret_cast<const_reverse_iterator*>(this); }
+
+    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
+};
+
+template<typename LinkedHashSetType>
+class LinkedHashSetConstReverseIterator : public LinkedHashSetConstIterator<LinkedHashSetType> {
+    typedef LinkedHashSetConstIterator<LinkedHashSetType> Superclass;
+    typedef typename LinkedHashSetType::Node Node;
+
+public:
+    LinkedHashSetConstReverseIterator(const Node* position, const LinkedHashSetType* container)
+        : Superclass(position, container) { }
+
+    LinkedHashSetConstReverseIterator& operator++() { Superclass::operator--(); return *this; }
+    LinkedHashSetConstReverseIterator& operator--() { Superclass::operator++(); return *this; }
+
+    // Postfix ++ and -- intentionally omitted.
+
+    template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
+};
+
+template<typename T, typename U, typename V, typename W>
+inline LinkedHashSet<T, U, V, W>::LinkedHashSet() : m_anchor() { }

[Mikhail, 2014/04/03 09:32:18]

well if m_anchor is a class instance, the default ctor will be invoked
implicitly (no need for explicit call)

[Erik Corry, 2014/04/10 10:47:37]

Done.

+
+template<typename T, typename U, typename V, typename W>
+inline LinkedHashSet<T, U, V, W>::LinkedHashSet(const LinkedHashSet& other)
+    : m_anchor()
+{
+    const_iterator end = other.end();
+    for (const_iterator it = other.begin(); it != end; ++it)
+        add(*it);
+}
+
+template<typename T, typename U, typename V, typename W>
+inline LinkedHashSet<T, U, V, W>& LinkedHashSet<T, U, V, W>::operator=(const LinkedHashSet& other)
+{
+    LinkedHashSet tmp(other);
+    swap(tmp);
+    return *this;
+}
+
+template<typename T, typename U, typename V, typename W>
+inline void LinkedHashSet<T, U, V, W>::swap(LinkedHashSet& other)
+{
+    m_impl.swap(other.m_impl);
+    using namespace std;

[Mikhail, 2014/04/03 09:32:18]

"using std::swap;" is better to use IMHO, so that nothing else from "std" is
picked.

[Mads Ager (chromium), 2014/04/03 09:44:58]

We decided to not do this style of swap, right. Just use std::swap.

[Erik Corry, 2014/04/10 10:47:37]

I removed the using std instead, because in this case we don't want to use
std::swap.

[Erik Corry, 2014/04/10 10:47:37]

Fixed.

+    swap(m_anchor, other.m_anchor);
+}
+
+template<typename T, typename U, typename V, typename Allocator>
+inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet()
+{
+    // The destructor of m_anchor will implicitly be called here, which will
+    // unlink the anchor from the collection.
+}
+
+template<typename T, typename U, typename V, typename W>
+inline T& LinkedHashSet<T, U, V, W>::first()
+{
+    ASSERT(!isEmpty());
+    return firstNode()->m_value;
+}
+
+template<typename T, typename U, typename V, typename W>
+inline const T& LinkedHashSet<T, U, V, W>::first() const
+{
+    ASSERT(!isEmpty());
+    return firstNode()->m_value;
+}
+
+template<typename T, typename U, typename V, typename W>
+inline void LinkedHashSet<T, U, V, W>::removeFirst()
+{
+    ASSERT(!isEmpty());
+    m_impl.remove(*m_anchor.m_next);
+}
+
+template<typename T, typename U, typename V, typename W>
+inline T& LinkedHashSet<T, U, V, W>::last()
+{
+    ASSERT(!isEmpty());
+    return lastNode()->m_value;
+}
+
+template<typename T, typename U, typename V, typename W>
+inline const T& LinkedHashSet<T, U, V, W>::last() const
+{
+    ASSERT(!isEmpty());
+    return lastNode()->m_value;
+}
+
+template<typename T, typename U, typename V, typename W>
+inline void LinkedHashSet<T, U, V, W>::removeLast()
+{
+    ASSERT(!isEmpty());
+    m_impl.remove(m_anchor.m_prev);

[Mikhail, 2014/04/03 09:32:18]

shoudl it be m_impl.remove(*m_anchor.m_prev); ?

[Mads Ager (chromium), 2014/04/03 09:44:58]

Do you have tests for all of these methods? This looks like it is using a
pointer instead of a value object in remove?

[Erik Corry, 2014/04/10 10:47:37]

Actually it should be m_impl.remove(static_cast<Node*>(m_anchor.m_prev))

Also fixed in removeFirst()

[Erik Corry, 2014/04/10 10:47:37]

No, I didn't test this and it didn't work (of course).

It should actually use a pointer, so we don't have to do a hash lookup in
removeFirst and removeLast, because we have a direct pointer to the first and
last elements.

+}
+
+template<typename T, typename U, typename V, typename W>
+inline typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::find(const T& value)
+{
+    LinkedHashSet::Node* node = m_impl.template lookup<LinkedHashSet::NodeHashFunctions, T>(value);
+    if (!node)
+        return end();
+    return makeIterator(node);
+}
+
+template<typename T, typename U, typename V, typename W>
+inline typename LinkedHashSet<T, U, V, W>::const_iterator LinkedHashSet<T, U, V, W>::find(const T& value) const
+{
+    const_iterator it = begin();

[Mikhail, 2014/04/03 09:32:18]

I did not get why this method is so different from the previous one, could you
pls explain?

[Erik Corry, 2014/04/10 10:47:37]

This was accidentally left in.  My first thought was that the LinkedHashSet
should return the first entry that was equal because it is ordered, but the
whole point of a set is that there are no dupes, so it makes no difference what
order you search.  Replaced with an implementation that looks like the non-const
find()

+    const_iterator endIterator = end();
+    while (it != endIterator && !HashTraits<T>::equal(it->m_value, value))
+        ++it;
+    return it;
+}
+
+template<typename Value, typename U, typename V, typename W>
+template<typename HashTranslator, typename T>
+inline typename LinkedHashSet<Value, U, V, W>::iterator LinkedHashSet<Value, U, V, W>::find(const T& value)
+{
+    iterator it = begin();
+    iterator endIterator = end();
+    while (it != endIterator && !HashTranslator::template equal<Value, T>(it->m_value, value))
+        ++it;
+    return it;
+}
+
+template<typename Value, typename U, typename V, typename W>
+template<typename HashTranslator, typename T>
+inline typename LinkedHashSet<Value, U, V, W>::const_iterator LinkedHashSet<Value, U, V, W>::find(const T& value) const
+{
+    const_iterator it = begin();
+    const_iterator endIterator = end();
+    while (it != endIterator && !HashTranslator::template equal<Value, T>(it->m_value, value))
+        ++it;
+    return it;
+}
+
+template<typename Translator>
+struct LinkedHashSetTranslatorAdapter {
+    template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
+    template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a->m_value, b); }
+};
+
+template<typename Value, typename U, typename V, typename W>
+template<typename HashTranslator, typename T>
+inline bool LinkedHashSet<Value, U, V, W>::contains(const T& value) const
+{
+    return m_impl.template contains<LinkedHashSetTranslatorAdapter<HashTranslator> >(value);
+}
+
+template<typename T, typename U, typename V, typename W>
+inline bool LinkedHashSet<T, U, V, W>::contains(const T& value) const
+{
+    return m_impl.template contains<NodeHashFunctions>(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
+typename LinkedHashSet<Value, HashFunctions, Traits, Allocator>::AddResult LinkedHashSet<Value, HashFunctions, Traits, Allocator>::add(const Value &value)
+{
+    return m_impl.template add<LinkedHashSetTranslator<Value, HashFunctions> >(value, &m_anchor);
+}
+
+template<typename T, typename U, typename V, typename W>
+typename LinkedHashSet<T, U, V, W>::iterator LinkedHashSet<T, U, V, W>::addReturnIterator(const T &value)
+{
+    return m_impl.template addReturnIterator<NodeHashFunctions>(value);
+}
+
+template<typename T, typename U, typename V, typename W>
+typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::appendOrMoveToLast(const T &value)
+{
+    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value);
+    Node* node = *result.storedValue;
+    if (!result.isNewEntry)
+        unlink(node);
+    appendNode(node);
+    return AddResult(*result.storedValue, result.isNewEntry);
+}
+
+template<typename T, typename U, typename V, typename W>
+typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::prependOrMoveToFirst(const T &value)
+{
+    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(value);
+    Node* node = *result.storedValue;
+    if (!result.isNewEntry)
+        unlink(node);
+    prependNode(node);
+    return AddResult(*result.storedValue, result.isNewEntry);
+}
+
+template<typename T, typename U, typename V, typename W>
+typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(iterator it, const T& newValue)
+{
+    typename ImplType::AddResult result = m_impl.template add<NodeHashFunctions>(newValue);
+    if (result.isNewEntry)
+        insertNodeBefore(it.node(), *result.storedValue);
+    return AddResult(*result.storedValue, result.isNewEntry);
+}
+
+template<typename T, typename U, typename V, typename W>
+typename LinkedHashSet<T, U, V, W>::AddResult LinkedHashSet<T, U, V, W>::insertBefore(const T& beforeValue, const T& newValue)
+{
+    return insertBefore(find(beforeValue), newValue);
+}
+
+template<typename T, typename U, typename V, typename W>
+inline void LinkedHashSet<T, U, V, W>::remove(iterator it)
+{
+    if (it == end())
+        return;
+    m_impl.remove(it.node());
+}
+
+template<typename T, typename U, typename V, typename W>
+inline void LinkedHashSet<T, U, V, W>::remove(const T& value)
+{
+    remove(find(value));
+}
+
+template<typename T>
+struct IsWeak<LinkedHashSetNode<T> > {
+    static const bool value = IsWeak<T>::value;
+};
+
+inline void swap(LinkedHashSetNodeBase& a, LinkedHashSetNodeBase& b)
+{
+    typedef LinkedHashSetNodeBase Base;
+    Base* aNext = a.m_next;
+    Base* aPrev = a.m_prev;
+    Base* bNext = b.m_next;
+    Base* bPrev = b.m_prev;
+    b.m_next = aNext;

[Mikhail, 2014/04/03 09:32:18]

swap(a.m_next, b.m_next) ?

[Mads Ager (chromium), 2014/04/03 09:44:58]

Can you just use std::swap(a.m_next, b.m_next) for these?

[Erik Corry, 2014/04/10 10:47:37]

swap gets us part of the way, so I refactored to use swap.

+    b.m_prev = aPrev;
+    a.m_next = bNext;
+    a.m_prev = bPrev;
+    if (aNext) {
+        aNext->m_prev = &b;
+        aPrev->m_next = &b;
+    }
+    if (bNext) {
+        bNext->m_prev = &a;
+        bPrev->m_next = &a;
+    }
+}
+
+template<typename T>
+inline void swap(LinkedHashSetNode<T>& a, LinkedHashSetNode<T>& b)
+{
+    typedef LinkedHashSetNodeBase Base;
+
+    using namespace std;
+
+    swap(static_cast<Base&>(a), static_cast<Base&>(b));
+    swap(a.m_value, b.m_value);
+}
+
+}
+
+using WTF::LinkedHashSet;
+
+#endif /* WTF_LinkedHashSet_h */