2009-02-18 David Levin <levin@chromium.org>
authorlevin@chromium.org <levin@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 18 Feb 2009 23:26:35 +0000 (23:26 +0000)
committerlevin@chromium.org <levin@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 18 Feb 2009 23:26:35 +0000 (23:26 +0000)
        Reviewed by Alexey Proskuryakov.

        Bug 23974: Deque::Remove would be a useful method.
        <https://bugs.webkit.org/show_bug.cgi?id=23974>

        Add Deque::remove and DequeIteratorBase<T>::operator=.

        Why was operator= added? Every concrete iterator (DequeIterator..DequeConstReverseIterator)
        was calling DequeIteratorBase::assign(), which called Base::operator=(). Base::operator=()
        was not implemented. This went unnoticed because the iterator copy code has been unused.

        * wtf/Deque.h:
        (WTF::Deque<T>::remove):
        (WTF::DequeIteratorBase<T>::removeFromIteratorsList):
        (WTF::DequeIteratorBase<T>::operator=):
        (WTF::DequeIteratorBase<T>::~DequeIteratorBase):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@41068 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/wtf/Deque.h

index dac3c2d3083e9b34ea8267f67e4d937373b876aa..7b14d2823edbfa7fa680aff4d505d80a196f97b5 100644 (file)
@@ -1,3 +1,22 @@
+2009-02-18  David Levin  <levin@chromium.org>
+
+        Reviewed by Alexey Proskuryakov.
+
+        Bug 23974: Deque::Remove would be a useful method.
+        <https://bugs.webkit.org/show_bug.cgi?id=23974>
+
+        Add Deque::remove and DequeIteratorBase<T>::operator=.
+
+        Why was operator= added? Every concrete iterator (DequeIterator..DequeConstReverseIterator)
+        was calling DequeIteratorBase::assign(), which called Base::operator=(). Base::operator=()
+        was not implemented. This went unnoticed because the iterator copy code has been unused.
+
+        * wtf/Deque.h:
+        (WTF::Deque<T>::remove):
+        (WTF::DequeIteratorBase<T>::removeFromIteratorsList):
+        (WTF::DequeIteratorBase<T>::operator=):
+        (WTF::DequeIteratorBase<T>::~DequeIteratorBase):
+
 2009-02-18  Gustavo Noronha Silva  <gns@gnome.org>
 
         Reviewed by Holger Freyther.
index 70c546b81666f522443cfae2122c58508035294b..22b29c9097f5d29f1c335d42bcddeaa204714171 100644 (file)
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
+ * Copyright (C) 2009 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -75,6 +76,8 @@ namespace WTF {
         template<typename U> void append(const U&);
         template<typename U> void prepend(const U&);
         void removeFirst();
+        void remove(iterator&);
+        void remove(const_iterator&);
 
         void clear();
 
@@ -85,6 +88,7 @@ namespace WTF {
         typedef VectorTypeOperations<T> TypeOperations;
         typedef DequeIteratorBase<T> IteratorBase;
 
+        void remove(size_t position);
         void invalidateIterators();
         void destroyAll();
         void checkValidity() const;
@@ -124,6 +128,7 @@ namespace WTF {
 
     private:
         void addToIteratorsList();
+        void removeFromIteratorsList();
         void checkValidity() const;
         void checkValidity(const Base&) const;
 
@@ -447,10 +452,48 @@ namespace WTF {
         checkValidity();
     }
 
+    template<typename T>
+    inline void Deque<T>::remove(iterator& it)
+    {
+        it.checkValidity();
+        remove(it.m_index);
+    }
+
+    template<typename T>
+    inline void Deque<T>::remove(const_iterator& it)
+    {
+        it.checkValidity();
+        remove(it.m_index);
+    }
+
+    template<typename T>
+    inline void Deque<T>::remove(size_t position)
+    {
+        if (position == m_end)
+            return;
+
+        checkValidity();
+        invalidateIterators();
+
+        T* buffer = m_buffer.buffer();
+        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);
+
+        // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
+        if (position >= m_start) {
+            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
+            m_start = (m_start + 1) % m_buffer.capacity();
+        } else {
+            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
+            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
+        }
+        checkValidity();
+    }
+
 #ifdef NDEBUG
     template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
     template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
     template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
+    template<typename T> inline void DequeIteratorBase<T>::removeFromIteratorsList() { }
 #else
     template<typename T>
     void DequeIteratorBase<T>::checkValidity() const
@@ -480,6 +523,30 @@ namespace WTF {
         }
         m_previous = 0;
     }
+
+    template<typename T>
+    void DequeIteratorBase<T>::removeFromIteratorsList()
+    {
+        if (!m_deque) {
+            ASSERT(!m_next);
+            ASSERT(!m_previous);
+        } else {
+            if (m_next) {
+                ASSERT(m_next->m_previous == this);
+                m_next->m_previous = m_previous;
+            }
+            if (m_previous) {
+                ASSERT(m_deque->m_iterators != this);
+                ASSERT(m_previous->m_next == this);
+                m_previous->m_next = m_next;
+            } else {
+                ASSERT(m_deque->m_iterators == this);
+                m_deque->m_iterators = m_next;
+            }
+        }
+        m_next = 0;
+        m_previous = 0;
+    }
 #endif
 
     template<typename T>
@@ -506,31 +573,26 @@ namespace WTF {
         checkValidity();
     }
 
+    template<typename T>
+    inline DequeIteratorBase<T>& DequeIteratorBase<T>::operator=(const Base& other)
+    {
+        checkValidity();
+        other.checkValidity();
+        removeFromIteratorsList();
+
+        m_deque = other.m_deque;
+        m_index = other.m_index;
+        addToIteratorsList();
+        checkValidity();
+        return *this;
+    }
+
     template<typename T>
     inline DequeIteratorBase<T>::~DequeIteratorBase()
     {
 #ifndef NDEBUG
-        // Delete iterator from doubly-linked list of iterators.
-        if (!m_deque) {
-            ASSERT(!m_next);
-            ASSERT(!m_previous);
-        } else {
-            if (m_next) {
-                ASSERT(m_next->m_previous == this);
-                m_next->m_previous = m_previous;
-            }
-            if (m_previous) {
-                ASSERT(m_deque->m_iterators != this);
-                ASSERT(m_previous->m_next == this);
-                m_previous->m_next = m_next;
-            } else {
-                ASSERT(m_deque->m_iterators == this);
-                m_deque->m_iterators = m_next;
-            }
-        }
+        removeFromIteratorsList();
         m_deque = 0;
-        m_next = 0;
-        m_previous = 0;
 #endif
     }