listhashset.h

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

/*
 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
 *
 * 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_ListHashSet_h
#define WTF_ListHashSet_h

#include "Assertions.h"
#include "HashSet.h"
#include "OwnPtr.h"

namespace WTF {

    // ListHashSet: 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.

    // In theory it would be possible to add prepend, insertAfter
    // and an append that moves the element to the end even if already present,
    // but unclear yet if these are needed.

    template<typename Value, typename HashFunctions> class ListHashSet;

    template<typename T> struct IdentityExtractor;

    template<typename Value, typename HashFunctions>
    void deleteAllValues(const ListHashSet<Value, HashFunctions>&);

    template<typename ValueArg, typename HashArg> class ListHashSetIterator;
    template<typename ValueArg, typename HashArg> class ListHashSetConstIterator;

    template<typename ValueArg> struct ListHashSetNode;
    template<typename ValueArg> struct ListHashSetNodeAllocator;
    template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions;

    template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash> class ListHashSet {
    private:
        typedef ListHashSetNode<ValueArg> Node;
        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

        typedef HashTraits<Node*> NodeTraits;
        typedef ListHashSetNodeHashFunctions<ValueArg, HashArg> NodeHash;

        typedef HashTable<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplType;
        typedef HashTableIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeIterator;
        typedef HashTableConstIterator<Node*, Node*, IdentityExtractor<Node*>, NodeHash, NodeTraits, NodeTraits> ImplTypeConstIterator;

        typedef HashArg HashFunctions;

    public:
        typedef ValueArg ValueType;
        typedef ListHashSetIterator<ValueType, HashArg> iterator;
        typedef ListHashSetConstIterator<ValueType, HashArg> const_iterator;

        friend class ListHashSetConstIterator<ValueType, HashArg>;

        ListHashSet();
        ListHashSet(const ListHashSet&);
        ListHashSet& operator=(const ListHashSet&);
        ~ListHashSet();

        void swap(ListHashSet&);

        int size() const;
        int capacity() const;
        bool isEmpty() const;

        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        iterator find(const ValueType&);
        const_iterator find(const ValueType&) const;
        bool contains(const ValueType&) const;

        // the return value is a pair of an iterator to the new value's location, 
        // and a bool that is true if an new entry was added
        pair<iterator, bool> add(const ValueType&);

        pair<iterator, bool> insertBefore(const ValueType& beforeValue, const ValueType& newValue);
        pair<iterator, bool> insertBefore(iterator it, const ValueType&);

        void remove(const ValueType&);
        void remove(iterator);
        void clear();

    private:
        void unlinkAndDelete(Node*);
        void appendNode(Node*);
        void insertNodeBefore(Node* beforeNode, Node* newNode);
        void deleteAllNodes();
        iterator makeIterator(Node*);
        const_iterator makeConstIterator(Node*) const;

        friend void deleteAllValues<>(const ListHashSet&);

        ImplType m_impl;
        Node* m_head;
        Node* m_tail;
        OwnPtr<NodeAllocator> m_allocator;
    };

    template<typename ValueArg> struct ListHashSetNodeAllocator {
        typedef ListHashSetNode<ValueArg> Node;
        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

        ListHashSetNodeAllocator() 
            : m_freeList(pool())
            , m_isDoneWithInitialFreeList(false)
        { 
            memset(m_pool.pool, 0, sizeof(m_pool.pool));
        }

        Node* allocate()
        { 
            Node* result = m_freeList;

            if (!result)
                return static_cast<Node*>(fastMalloc(sizeof(Node)));

            ASSERT(!result->m_isAllocated);

            Node* next = result->m_next;
            ASSERT(!next || !next->m_isAllocated);
            if (!next && !m_isDoneWithInitialFreeList) {
                next = result + 1;
                if (next == pastPool()) {
                    m_isDoneWithInitialFreeList = true;
                    next = 0;
                } else {
                    ASSERT(inPool(next));
                    ASSERT(!next->m_isAllocated);
                }
            }
            m_freeList = next;

            return result;
        }

        void deallocate(Node* node) 
        {
            if (inPool(node)) {
#ifndef NDEBUG
                node->m_isAllocated = false;
#endif
                node->m_next = m_freeList;
                m_freeList = node;
                return;
            }

            fastFree(node);
        }

    private:
        Node* pool() { return reinterpret_cast<Node*>(m_pool.pool); }
        Node* pastPool() { return pool() + m_poolSize; }

        bool inPool(Node* node)
        {
            return node >= pool() && node < pastPool();
        }

        Node* m_freeList;
        bool m_isDoneWithInitialFreeList;
        static const size_t m_poolSize = 256;
        union {
            char pool[sizeof(Node) * m_poolSize];
            double forAlignment;
        } m_pool;
    };

    template<typename ValueArg> struct ListHashSetNode {
        typedef ListHashSetNodeAllocator<ValueArg> NodeAllocator;

        ListHashSetNode(ValueArg value)
            : m_value(value)
            , m_prev(0)
            , m_next(0)
#ifndef NDEBUG
            , m_isAllocated(true)
#endif
        {
        }

        void* operator new(size_t, NodeAllocator* allocator)
        {
            return allocator->allocate();
        }
        void destroy(NodeAllocator* allocator)
        {
            this->~ListHashSetNode();
            allocator->deallocate(this);
        }

        ValueArg m_value;
        ListHashSetNode* m_prev;
        ListHashSetNode* m_next;

#ifndef NDEBUG
        bool m_isAllocated;
#endif
    };

    template<typename ValueArg, typename HashArg> struct ListHashSetNodeHashFunctions {
        typedef ListHashSetNode<ValueArg> Node;
        
        static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
        static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
        static const bool safeToCompareToEmptyOrDeleted = false;
    };

    template<typename ValueArg, typename HashArg> class ListHashSetIterator {
    private:
        typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
        typedef ListHashSetIterator<ValueArg, HashArg> iterator;
        typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
        typedef ListHashSetNode<ValueArg> Node;
        typedef ValueArg ValueType;
        typedef ValueType& ReferenceType;
        typedef ValueType* PointerType;

        friend class ListHashSet<ValueArg, HashArg>;

        ListHashSetIterator(const ListHashSetType* set, Node* position) : m_iterator(set, position) { }

    public:
        ListHashSetIterator() { }

        // default copy, assignment and destructor are OK

        PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
        ReferenceType operator*() const { return *get(); }
        PointerType operator->() const { return get(); }

        iterator& operator++() { ++m_iterator; return *this; }

        // postfix ++ intentionally omitted

        iterator& operator--() { --m_iterator; return *this; }

        // postfix -- intentionally omitted

        // Comparison.
        bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
        bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }

        operator const_iterator() const { return m_iterator; }

    private:
        Node* node() { return m_iterator.node(); }

        const_iterator m_iterator;
    };

    template<typename ValueArg, typename HashArg> class ListHashSetConstIterator {
    private:
        typedef ListHashSet<ValueArg, HashArg> ListHashSetType;
        typedef ListHashSetIterator<ValueArg, HashArg> iterator;
        typedef ListHashSetConstIterator<ValueArg, HashArg> const_iterator;
        typedef ListHashSetNode<ValueArg> Node;
        typedef ValueArg ValueType;
        typedef const ValueType& ReferenceType;
        typedef const ValueType* PointerType;

        friend class ListHashSet<ValueArg, HashArg>;
        friend class ListHashSetIterator<ValueArg, HashArg>;

        ListHashSetConstIterator(const ListHashSetType* set, Node* position)
            : m_set(set)
            , m_position(position)
        {
        }

    public:
        ListHashSetConstIterator()
        {
        }

        PointerType get() const
        {
            return &m_position->m_value;
        }
        ReferenceType operator*() const { return *get(); }
        PointerType operator->() const { return get(); }

        const_iterator& operator++()
        {
            ASSERT(m_position != 0);
            m_position = m_position->m_next;
            return *this;