svn commit: r473135 - /incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h

[gs...@apache.org]

Author: gshimansky
Date: Thu Nov  9 15:20:44 2006
New Revision: 473135

URL: http://svn.apache.org/viewvc?view=rev&rev=473135
Log:
Applied HARMONY-2133 [drlvm][jvmti] ulist.h iteration over empty chunks is broken

Tests passed on windows xp and ubuntu


Modified:
    incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h

Modified: incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h?view=diff&rev=473135&r1=473134&r2=473135
==============================================================================
--- incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h (original)
+++ incubator/harmony/enhanced/drlvm/trunk/vm/vmcore/src/jvmti/ulist.h Thu Nov  9 15:20:44 2006
@@ -58,9 +58,14 @@
             index++;
             assert(index >= 0);
             if ((size_t)index >= current->used) {
-                current = current->next;
                 index = 0;
+                do {
+                    current = current->next;
+                    // skip emptied chunk during iteration,
+                    // as they have no elements to iterate
+                } while (current && current->used == 0);
             }
+            assert(0 <= index); assert(current == NULL || ((size_t)index < current->used));
             return *this;
         }
 
@@ -71,6 +76,7 @@
         }
 
         T & operator*() {
+            assert(0 <= index); assert((size_t)index < current->used);
             return current->chunk[index];
         }
 
@@ -152,8 +158,10 @@
     }
 
     void erase(iterator i) {
-        assert(0 <= i.index && (size_t)i.index < i.current->used);
-        i.current->used--;
+        assert(0 <= i.index); assert((size_t)i.index < i.current->used);
+        i.current->used--; assert(i.current->used >= 0);
+
+        // compact array if the erased element was not the last
         if ((size_t)i.index < i.current->used) {
             i.current->chunk[i.index] = i.current->chunk[i.current->used];
             // moving element notification
@@ -177,7 +185,13 @@
 
     // iteration is not compatible with adding elements !!!
     iterator begin() {
-        return iterator(this, 0);
+        ulist<T> *current = this;
+        while (current && current->used == 0) {
+            current = current->next;
+            // skip empty chunk during iteration,
+            // as they have no elements to iterate
+        }
+        return iterator(current, 0);
     }
 
     iterator end() {
@@ -263,6 +277,53 @@
     assert(c == N/2);
 }
 
+TEST(erase_random) {
+    ulist<int> list(3);
+    int N = 77;
+    int j;
+    for (j = 0; j < N; j++) {
+        list.push_back(j);
+    }
+    ulist<int>::iterator i;
+    int removed = 0;
+    for (i = list.begin(), j = 0; i != list.end(); i++, j++) {
+        if (j % 3 == 0) {
+            list.erase(i--);
+            removed++;
+        }
+    }
+    assert(j == N);
+    N -= removed;
+    removed = 0;
+    for (i = list.begin(), j = 0; i != list.end(); i++, j++) {
+        if (j % 3 == 0) {
+            list.erase(i--);
+            removed++;
+        }
+    }
+    assert(j == N);
+    N -= removed;
+    removed = 0;
+    for (i = list.begin(), j = 0; i != list.end(); i++, j++) {
+        if (j < N/3 || j > N-N/3) {
+            list.erase(i--);
+            removed++;
+        }
+    }
+    assert(j == N);
+    N -= removed;
+    removed = 0;
+    for (i = list.begin(), j = 0; i != list.end(); i++, j++) {
+        list.erase(i--);
+        removed++;
+    }
+    assert(j == N);
+    assert(removed == N);
+    for (i = list.begin(); i != list.end(); i++) {
+        assert(!"should not have any elements");
+    }
+}
+
 TEST(erase_all) {
     ulist<int> list(10);
     int N = 33;
@@ -348,6 +409,25 @@
 
     delete[] elements;
     elements = NULL;
+}
+
+TEST(iterate_empty) {
+    ulist<int> list(10);
+    assert(!(list.begin() != list.end()));
+}
+
+TEST(iterate_emptied) {
+    ulist<int> list(10);
+    int N = 33;
+    int j;
+    for (j = 0; j < N; j++) {
+        list.push_back(j);
+    }
+    ulist<int>::iterator i;
+    for (i = list.begin(); i != list.end(); i++) {
+        list.erase(i--);
+    }
+    assert(!(list.begin() != list.end()));
 }
 
 #endif // UNIT_TEST