listhashset.h

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

        }

        // postfix ++ intentionally omitted

        const_iterator& operator--()
        {
            ASSERT(m_position != m_set->m_head);
            if (!m_position)
                m_position = m_set->m_tail;
            else
                m_position = m_position->m_prev;
            return *this;
        }

        // postfix -- intentionally omitted

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

    private:
        Node* node() { return m_position; }

        const ListHashSetType* m_set;
        Node* m_position;
    };


    template<typename ValueType, typename HashFunctions>
    struct ListHashSetTranslator {
    private:
        typedef ListHashSetNode<ValueType> Node;
        typedef ListHashSetNodeAllocator<ValueType> NodeAllocator;
    public:
        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
        static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
        static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
        {
            location = new (allocator) Node(key);
        }
    };

    template<typename T, typename U>
    inline ListHashSet<T, U>::ListHashSet()
        : m_head(0)
        , m_tail(0)
        , m_allocator(new NodeAllocator)
    {
    }

    template<typename T, typename U>
    inline ListHashSet<T, U>::ListHashSet(const ListHashSet& other)
        : m_head(0)
        , m_tail(0)
        , m_allocator(new NodeAllocator)
    {
        const_iterator end = other.end();
        for (const_iterator it = other.begin(); it != end; ++it)
            add(*it);
    }

    template<typename T, typename U>
    inline ListHashSet<T, U>& ListHashSet<T, U>::operator=(const ListHashSet& other)
    {
        ListHashSet tmp(other);
        swap(tmp);
        return *this;
    }

    template<typename T, typename U>
    inline void ListHashSet<T, U>::swap(ListHashSet& other)
    {
        m_impl.swap(other.m_impl);
        std::swap(m_head, other.m_head);
        std::swap(m_tail, other.m_tail);
        m_allocator.swap(other.m_allocator);
    }

    template<typename T, typename U>
    inline ListHashSet<T, U>::~ListHashSet()
    {
        deleteAllNodes();
    }

    template<typename T, typename U>
    inline int ListHashSet<T, U>::size() const
    {
        return m_impl.size(); 
    }

    template<typename T, typename U>
    inline int ListHashSet<T, U>::capacity() const
    {
        return m_impl.capacity(); 
    }

    template<typename T, typename U>
    inline bool ListHashSet<T, U>::isEmpty() const
    {
        return m_impl.isEmpty(); 
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::begin()
    {
        return makeIterator(m_head); 
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::end()
    {
        return makeIterator(0);
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::begin() const
    {
        return makeConstIterator(m_head); 
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::end() const
    {
        return makeConstIterator(0); 
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::iterator ListHashSet<T, U>::find(const ValueType& value)
    {
        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
        ImplTypeIterator it = m_impl.template find<ValueType, Translator>(value);
        if (it == m_impl.end())
            return end();
        return makeIterator(*it); 
    }

    template<typename T, typename U>
    inline typename ListHashSet<T, U>::const_iterator ListHashSet<T, U>::find(const ValueType& value) const
    {
        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
        ImplTypeConstIterator it = m_impl.template find<ValueType, Translator>(value);
        if (it == m_impl.end())
            return end();
        return makeConstIterator(*it);
    }

    template<typename T, typename U>
    inline bool ListHashSet<T, U>::contains(const ValueType& value) const
    {
        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
        return m_impl.template contains<ValueType, Translator>(value);
    }

    template<typename T, typename U>
    pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::add(const ValueType &value)
    {
        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
        pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(value, m_allocator.get());
        if (result.second)
            appendNode(*result.first);
        return std::make_pair(makeIterator(*result.first), result.second);
    }

    template<typename T, typename U>
    pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::insertBefore(iterator it, const ValueType& newValue)
    {
        typedef ListHashSetTranslator<ValueType, HashFunctions> Translator;
        pair<typename ImplType::iterator, bool> result = m_impl.template add<ValueType, NodeAllocator*, Translator>(newValue, m_allocator.get());
        if (result.second)
            insertNodeBefore(it.node(), *result.first);
        return std::make_pair(makeIterator(*result.first), result.second);

    }

    template<typename T, typename U>
    pair<typename ListHashSet<T, U>::iterator, bool> ListHashSet<T, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue)
    {
        return insertBefore(find(beforeValue), newValue); 
    }

    template<typename T, typename U>
    inline void ListHashSet<T, U>::remove(iterator it)
    {
        if (it == end())
            return;
        m_impl.remove(it.node());
        unlinkAndDelete(it.node());
    }

    template<typename T, typename U>
    inline void ListHashSet<T, U>::remove(const ValueType& value)
    {
        remove(find(value));
    }

    template<typename T, typename U>
    inline void ListHashSet<T, U>::clear()
    {
        deleteAllNodes();
        m_impl.clear(); 
        m_head = 0;
        m_tail = 0;
    }

    template<typename T, typename U>
    void ListHashSet<T, U>::unlinkAndDelete(Node* node)
    {
        if (!node->m_prev) {
            ASSERT(node == m_head);
            m_head = node->m_next;
        } else {
            ASSERT(node != m_head);
            node->m_prev->m_next = node->m_next;
        }

        if (!node->m_next) {
            ASSERT(node == m_tail);
            m_tail = node->m_prev;
        } else {
            ASSERT(node != m_tail);
            node->m_next->m_prev = node->m_prev;
        }

        node->destroy(m_allocator.get());
    }

    template<typename T, typename U>
    void ListHashSet<T, U>::appendNode(Node* node)
    {
        node->m_prev = m_tail;
        node->m_next = 0;

        if (m_tail) {
            ASSERT(m_head);
            m_tail->m_next = node;
        } else {
            ASSERT(!m_head);
            m_head = node;
        }

        m_tail = node;
    }

    template<typename T, typename U>
    void ListHashSet<T, U>::insertNodeBefore(Node* beforeNode, Node* newNode)
    {
        if (!beforeNode)
            return appendNode(newNode);
        
        newNode->m_next = beforeNode;
        newNode->m_prev = beforeNode->m_prev;
        if (beforeNode->m_prev)
            beforeNode->m_prev->m_next = newNode;
        beforeNode->m_prev = newNode;

        if (!newNode->m_prev)
            m_head = newNode;
    }

    template<typename T, typename U>
    void ListHashSet<T, U>::deleteAllNodes()
    {
        if (!m_head)
            return;

        for (Node* node = m_head, *next = m_head->m_next; node; node = next, next = node ? node->m_next : 0)
            node->destroy(m_allocator.get());
    }

    template<typename T, typename U>
    inline ListHashSetIterator<T, U> ListHashSet<T, U>::makeIterator(Node* position) 
    {
        return ListHashSetIterator<T, U>(this, position); 
    }

    template<typename T, typename U>
    inline ListHashSetConstIterator<T, U> ListHashSet<T, U>::makeConstIterator(Node* position) const
    { 
        return ListHashSetConstIterator<T, U>(this, position); 
    }

    template<bool, typename ValueType, typename HashTableType>
    void deleteAllValues(HashTableType& collection)
    {
        typedef typename HashTableType::const_iterator iterator;
        iterator end = collection.end();
        for (iterator it = collection.begin(); it != end; ++it)
            delete (*it)->m_value;
    }

    template<typename T, typename U>
    inline void deleteAllValues(const ListHashSet<T, U>& collection)
    {
        deleteAllValues<true, typename ListHashSet<T, U>::ValueType>(collection.m_impl);
    }

} // namespace WTF

using WTF::ListHashSet;

#endif /* WTF_ListHashSet_h */