Bug 713381 - Add nsDeque::RemoveObjectAt(index). r=bsmedberg
authorChris Pearce <chris@pearce.org.nz>
Thu, 19 Jan 2012 09:15:56 +1300
changeset 86039 d5ebbc25b4b8e8f3e9e9fc3cbd7ce7d251de43ba
parent 86038 38271572005b735b177b4b7039962486f07435f0
child 86040 6435f51dd10d6ace3a410d560ed8d92b27ed4ede
push id805
push userakeybl@mozilla.com
push dateWed, 01 Feb 2012 18:17:35 +0000
treeherdermozilla-aurora@6fb3bf232436 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbsmedberg
bugs713381
milestone12.0a1
Bug 713381 - Add nsDeque::RemoveObjectAt(index). r=bsmedberg
xpcom/glue/nsDeque.cpp
xpcom/glue/nsDeque.h
xpcom/tests/Makefile.in
xpcom/tests/TestDeque.cpp
--- a/xpcom/glue/nsDeque.cpp
+++ b/xpcom/glue/nsDeque.cpp
@@ -345,16 +345,32 @@ void* nsDeque::PeekFront() {
 void* nsDeque::ObjectAt(PRInt32 aIndex) const {
   void* result=0;
   if ((aIndex>=0) && (aIndex<mSize)) {
     result=mData[modulus(mOrigin + aIndex, mCapacity)];
   }
   return result;
 }
 
+void* nsDeque::RemoveObjectAt(PRInt32 aIndex) {
+  if ((aIndex<0) || (aIndex>=mSize)) {
+    return 0;
+  }
+  void* result=mData[modulus(mOrigin + aIndex, mCapacity)];
+
+  // "Shuffle down" all elements in the array by 1, overwritting the element
+  // being removed.
+  for (PRInt32 i=aIndex; i<mSize; i++) {
+    mData[modulus(mOrigin + i, mCapacity)] = mData[modulus(mOrigin + i + 1, mCapacity)];
+  }
+  mSize--;
+
+  return result;
+}
+
 /**
  * Create and return an iterator pointing to
  * the beginning of the queue. Note that this
  * takes the circular buffer semantics into account.
  *
  * @return  new deque iterator, init'ed to 1st item
  */
 nsDequeIterator nsDeque::Begin() const{
--- a/xpcom/glue/nsDeque.h
+++ b/xpcom/glue/nsDeque.h
@@ -148,16 +148,24 @@ class NS_COM_GLUE nsDeque {
    * Retrieve the i'th member from the deque without removing it.
    *
    * @param   index of desired item
    * @return  i'th element in list
    */
   void* ObjectAt(int aIndex) const;
 
   /**
+   * Removes and returns the i'th member from the deque.
+   *
+   * @param   index of desired item
+   * @return  the element which was removed
+   */
+  void* RemoveObjectAt(int aIndex);
+
+  /**
    * Remove all items from container without destroying them.
    *
    * @return  *this
    */
   nsDeque& Empty();
 
   /**
    * Remove and delete all items from container.
--- a/xpcom/tests/Makefile.in
+++ b/xpcom/tests/Makefile.in
@@ -84,16 +84,17 @@ SIMPLE_PROGRAMS	:= $(CPPSRCS:.cpp=$(BIN_
 
 CPP_UNIT_TESTS = \
                  ShowAlignments.cpp \
                  ShowSSEConfig.cpp \
                  TestAutoPtr.cpp \
                  TestCOMArray.cpp \
                  TestCOMPtr.cpp \
                  TestCOMPtrEq.cpp \
+                 TestDeque.cpp \
                  TestFile.cpp \
                  TestHashtables.cpp \
                  TestID.cpp \
                  TestObserverArray.cpp \
                  TestObserverService.cpp \
                  TestPipe.cpp \
                  TestRefPtr.cpp \
                  TestTextFormatter.cpp \
@@ -104,17 +105,16 @@ CPP_UNIT_TESTS = \
 ifdef MOZ_MEMORY
 CPP_UNIT_TESTS += TestJemalloc.cpp
 endif
 
 # XXX Make this tests work in libxul builds.
 #CPP_UNIT_TESTS += \
 #                  TestArray.cpp \
 #                  TestCRT.cpp \
-#                  TestDeque.cpp \
 #                  TestEncoding.cpp \
 #                  TestExpirationTracker.cpp \
 #                  TestPipes.cpp \
 #                  TestPriorityQueue.cpp \
 #                  TestStorageStream.cpp \
 #                  TestStrings.cpp \
 #                  TestSynchronization.cpp \
 #                  TestTArray.cpp \
--- a/xpcom/tests/TestDeque.cpp
+++ b/xpcom/tests/TestDeque.cpp
@@ -30,126 +30,244 @@
  * use your version of this file under the terms of the MPL, indicate your
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
+#include "TestHarness.h"
 #include "nsDeque.h"
 #include "nsCRT.h"
 #include <stdio.h>
 
 /**************************************************************
   Now define the token deallocator class...
  **************************************************************/
 class _TestDeque {
 public:
-  _TestDeque() {
-    SelfTest();
-  }
-  int SelfTest();
-  nsresult OriginalTest();
-  nsresult OriginalFlaw();
-  nsresult AssignFlaw();
+  int Test();
+private:
+  int OriginalTest();
+  int OriginalFlaw();
+  int AssignFlaw();
+  int TestRemove();
 };
 static _TestDeque sTestDeque;
 
 class _Dealloc: public nsDequeFunctor {
   virtual void* operator()(void* aObject) {
     return 0;
   }
 };
 
+#define TEST(aCondition, aMsg) \
+  if (!(aCondition)) { fail("TestDeque: "#aMsg); return 1; }
+
+
 /**
  * conduct automated self test for this class
  *
  * @param
  * @return
  */
-int _TestDeque::SelfTest() {
+int _TestDeque::Test() {
   /* the old deque should have failed a bunch of these tests */
   int results=0;
   results+=OriginalTest();
   results+=OriginalFlaw();
   results+=AssignFlaw();
+  results+=TestRemove();
   return results;
 }
 
-nsresult _TestDeque::OriginalTest() {
-  int ints[200];
-  int count=sizeof(ints)/sizeof(int);
+int _TestDeque::OriginalTest() {
+  const int size = 200;
+  int ints[size];
   int i=0;
-  int* temp;
+  int temp;
   nsDeque theDeque(new _Dealloc); //construct a simple one...
  
-  for (i=0;i<count;i++) { //initialize'em
-    ints[i]=10*(1+i);
+  // ints = [0...199]
+  for (i=0;i<size;i++) { //initialize'em
+    ints[i]=i;
   }
+  // queue = [0...69]
   for (i=0;i<70;i++) {
     theDeque.Push(&ints[i]);
+    temp=*(int*)theDeque.Peek();
+    TEST(temp == i, "Verify end after push #1");
+    TEST(theDeque.GetSize() == i + 1, "Verify size after push #1");
   }
-  for (i=0;i<56;i++) {
-    temp=(int*)theDeque.Pop();
+  TEST(theDeque.GetSize() == 70, "Verify overall size after pushes #1");
+  // queue = [0...14]
+  for (i=1;i<=55;i++) {
+    temp=*(int*)theDeque.Pop();
+    TEST(temp == 70-i, "Verify end after pop # 1");
+    TEST(theDeque.GetSize() == 70 - i, "Verify size after pop # 1");
   }
+  TEST(theDeque.GetSize() == 15, "Verify overall size after pops");
+
+  // queue = [0...14,0...54]
   for (i=0;i<55;i++) {
     theDeque.Push(&ints[i]);
+    temp=*(int*)theDeque.Peek();
+    TEST(temp == i, "Verify end after push #2");
+    TEST(theDeque.GetSize() == i + 15 + 1, "Verify size after push # 2");
   }
-  for (i=0;i<35;i++) {
-    temp=(int*)theDeque.Pop();
+  TEST(theDeque.GetSize() == 70, "Verify size after end of all pushes #2");
+
+  // queue = [0...14,0...19]
+  for (i=1;i<=35;i++) {
+    temp=*(int*)theDeque.Pop();
+    TEST(temp == 55-i, "Verify end after pop # 2");
+    TEST(theDeque.GetSize() == 70 - i, "Verify size after pop #2");
   }
+  TEST(theDeque.GetSize() == 35, "Verify overall size after end of all pops #2");
+
+  // queue = [0...14,0...19,0...34]
   for (i=0;i<35;i++) {
     theDeque.Push(&ints[i]);
+    temp = *(int*)theDeque.Peek();
+    TEST(temp == i, "Verify end after push # 3");
+    TEST(theDeque.GetSize() == 35 + 1 + i, "Verify size after push #3");
   }
-  for (i=0;i<38;i++) {
-    temp=(int*)theDeque.Pop();
+
+  // queue = [0...14,0...19]
+  for (i=0;i<35;i++) {
+    temp=*(int*)theDeque.Pop();
+    TEST(temp == 34 - i, "Verify end after pop # 3");
   }
-  return NS_OK;
+
+  // queue = [0...14]
+  for (i=0;i<20;i++) {
+    temp=*(int*)theDeque.Pop();
+    TEST(temp == 19 - i, "Verify end after pop # 4");
+  }
+
+  // queue = []
+  for (i=0;i<15;i++) {
+    temp=*(int*)theDeque.Pop();
+    TEST(temp == 14 - i, "Verify end after pop # 5");
+  }
+
+  TEST(theDeque.GetSize() == 0, "Deque should finish empty.");
+
+  return 0;
 }
 
-nsresult _TestDeque::OriginalFlaw() {
+int _TestDeque::OriginalFlaw() {
   int ints[200];
   int i=0;
-  int* temp;
-  nsDeque secondDeque(new _Dealloc);
+  int temp;
+  nsDeque d(new _Dealloc);
   /**
    * Test 1. Origin near end, semi full, call Peek().
    * you start, mCapacity is 8
    */
   printf("fill array\n");
-  for (i=32; i; --i)
-    ints[i]=i*3+10;
-  printf("push 6 times\n");
-  for (i=0; i<6; i++)
-    secondDeque.Push(&ints[i]);
-  printf("popfront 4 times:\n");
-  for (i=4; i; --i) {
-    temp=(int*)secondDeque.PopFront();
-    printf("%d\t",*temp);
+  for (i=0; i<30; i++)
+    ints[i]=i;
+
+  for (i=0; i<6; i++) {
+    d.Push(&ints[i]);
+    temp = *(int*)d.Peek();
+    TEST(temp == i, "OriginalFlaw push #1");
+  }
+  TEST(d.GetSize() == 6, "OriginalFlaw size check #1");
+
+  for (i=0; i<4; i++) {
+    temp=*(int*)d.PopFront();
+    TEST(temp == i, "PopFront test");
+  }
+  // d = [4,5]
+  TEST(d.GetSize() == 2, "OriginalFlaw size check #2");
+
+  for (i=0; i<4; i++) {
+    d.Push(&ints[6 + i]);
   }
-  printf("push 4 times\n");
-  for (int j=4; j; --j)
-    secondDeque.Push(&ints[++i]);
-  printf("origin should now be about 4\n");
-  printf("and size should be 6\n");
-  printf("origin+size>capacity\n");
+  // d = [4...9]
+
+  for (i=4; i<=9; i++) {
+    temp=*(int*)d.PopFront();
+    TEST(temp == i, "OriginalFlaw empty check");
+  }
+
+  return 0;
+}
 
-   /*<akk> Oh, I see ... it's a circular buffer */
-  printf("but the old code wasn't behaving accordingly.\n");
+int _TestDeque::AssignFlaw() {
+  nsDeque src(new _Dealloc),dest(new _Dealloc);
+  return 0;
+}
 
-   /*right*/
-  printf("we shouldn't crash or anything interesting, ");
-
-  temp=(int*)secondDeque.Peek();
-  printf("peek: %d\n",*temp);
-  return NS_OK;
+static bool VerifyContents(const nsDeque& aDeque, const int* aContents, int aLength) {
+  for (int i=0; i<aLength; ++i) {
+    if (*(int*)aDeque.ObjectAt(i) != aContents[i]) {
+      return false;
+    }
+  }
+  return true;
 }
 
-nsresult _TestDeque::AssignFlaw() {
-  nsDeque src(new _Dealloc),dest(new _Dealloc);
-  return NS_OK;
+int _TestDeque::TestRemove() {
+  nsDeque d;
+  const int count = 10;
+  int ints[count];
+  for (int i=0; i<count; i++) {
+    ints[i] = i;
+  }
+
+  for (int i=0; i<6; i++) {
+    d.Push(&ints[i]);
+  }
+  // d = [0...5]
+  d.PopFront();
+  d.PopFront();
+
+  // d = [2,5]
+  for (int i=2; i<=5; i++) {
+    int t = *(int*)d.ObjectAt(i-2);
+    TEST(t == i, "Verify ObjectAt()");
+  }
+
+  d.RemoveObjectAt(1);
+  // d == [2,4,5]
+  static const int t1[] = {2,4,5};
+  TEST(VerifyContents(d, t1, 3), "verify contents t1");
+
+  d.PushFront(&ints[1]);
+  d.PushFront(&ints[0]);
+  d.PushFront(&ints[7]);
+  d.PushFront(&ints[6]);
+  //  d == [6,7,0,1,2,4,5] // (0==mOrigin)
+  static const int t2[] = {6,7,0,1,2,4,5};
+  TEST(VerifyContents(d, t2, 7), "verify contents t2");
+
+  d.RemoveObjectAt(1);
+  //  d == [6,0,1,2,4,5] // (1==mOrigin)
+  static const int t3[] = {6,0,1,2,4,5};
+  TEST(VerifyContents(d, t3, 6), "verify contents t3");
+
+  d.RemoveObjectAt(5);
+  //  d == [6,0,1,2,4] // (1==mOrigin)
+  static const int t4[] = {6,0,1,2,4};
+  TEST(VerifyContents(d, t4, 5), "verify contents t4");
+
+  d.RemoveObjectAt(0);
+  //  d == [0,1,2,4] // (2==mOrigin)
+  static const int t5[] = {0,1,2,4};
+  TEST(VerifyContents(d, t5, 4), "verify contents t5");
+
+
+  return 0;
 }
 
 int main (void) {
+  ScopedXPCOM xpcom("TestTimers");
+  NS_ENSURE_FALSE(xpcom.failed(), 1);
+
   _TestDeque test;
+  int result = test.Test();
+  TEST(result == 0, "All tests pass");
   return 0;
 }