Changeset 35144 in webkit for trunk/JavaScriptCore/wtf

Timestamp:

Jul 11, 2008, 7:24:25 PM (17 years ago)

Author:

[email protected]

Message:

2008-07-11 David Hyatt <​[email protected]>

Add an insertBefore method to ListHashSet to allow for insertions in the middle of the list (rather than just
at the end).

Reviewed by Anders

• wtf/ListHashSet.h: (WTF::::insertBefore): (WTF::::insertNodeBefore):

File:

• trunk/JavaScriptCore/wtf/ListHashSet.h (modified) (5 diffs)

trunk/JavaScriptCore/wtf/ListHashSet.h

@@ -35 +35 @@
     // in which they are added.
 
-    // In theory it would be possible to add prepend, insertAfter, insertBefore,
+    // 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.
@@ -92 +92 @@
         bool contains(const ValueType&) const;
 
-        // the return value is a pair of an interator to the new value's location, 
+        // 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&);
@@ -103 +106 @@
         void unlinkAndDelete(Node*);
         void appendNode(Node*);
+        void insertNodeBefore(Node* beforeNode, Node* newNode);
         void deleteAllNodes();
         iterator makeIterator(Node*);
@@ -470 +474 @@
 
     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)
+    {
+        insertBefore(find(beforeValue), newValue); 
+    }
+
+    template<typename T, typename U>
     inline void ListHashSet<T, U>::remove(iterator it)
     {
@@ -533 +554 @@
 
     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()
     {