QPID-3888: ensure the SQEL iterator uses the getNextValidEntry() method to advance, simplifying its implementation and aiding queue cleanup by releasing deleted entries from the data structure. In doing so ensure that it ignores a deleted node at the end of the list, returning that it is atTail and cannot advance. Add unit test highlighting the issue and confirming its resolution.

git-svn-id: https://svn.apache.org/repos/asf/qpid/trunk@1297794 13f79535-47bb-0310-9956-ffa450edef68

4 files changed, 69 insertions, 22 deletions

diff --git a/qpid/java/broker/src/main/java/org/apache/qpid/server/queue/SimpleQueueEntryList.java b/qpid/java/broker/src/main/java/org/apache/qpid/server/queue/SimpleQueueEntryList.java
index e57390163c..c82d1b984a 100644
--- a/qpid/java/broker/src/main/java/org/apache/qpid/server/queue/SimpleQueueEntryList.java
+++ b/qpid/java/broker/src/main/java/org/apache/qpid/server/queue/SimpleQueueEntryList.java
@@ -116,7 +116,6 @@ public class SimpleQueueEntryList implements QueueEntryList<SimpleQueueEntryImpl
 
     public static class QueueEntryIteratorImpl implements QueueEntryIterator<SimpleQueueEntryImpl>
     {
-
         private SimpleQueueEntryImpl _lastNode;
 
         QueueEntryIteratorImpl(SimpleQueueEntryImpl startNode)
@@ -124,10 +123,9 @@ public class SimpleQueueEntryList implements QueueEntryList<SimpleQueueEntryImpl
             _lastNode = startNode;
         }
 
-
         public boolean atTail()
         {
-            return _lastNode.getNextNode() == null;
+            return _lastNode.getNextValidEntry() == null;
         }
 
         public SimpleQueueEntryImpl getNode()
@@ -137,28 +135,17 @@ public class SimpleQueueEntryList implements QueueEntryList<SimpleQueueEntryImpl
 
         public boolean advance()
         {
+            SimpleQueueEntryImpl nextValidNode = _lastNode.getNextValidEntry();
 
-            if(!atTail())
+            if(nextValidNode != null)
             {
-                SimpleQueueEntryImpl nextNode = _lastNode.getNextNode();
-                while(nextNode.isDispensed() && nextNode.getNextNode() != null)
-                {
-                    nextNode = nextNode.getNextNode();
-                }
-                _lastNode = nextNode;
-                return true;
-
-            }
-            else
-            {
-                return false;
+                _lastNode = nextValidNode;
             }
 
+            return nextValidNode != null;
         }
-
     }
 
-
     public QueueEntryIteratorImpl iterator()
     {
         return new QueueEntryIteratorImpl(_head);
diff --git a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/QueueEntryListTestBase.java b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/QueueEntryListTestBase.java
index 7f81aaed51..4b40c3b552 100644
--- a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/QueueEntryListTestBase.java
+++ b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/QueueEntryListTestBase.java
@@ -31,6 +31,7 @@ public abstract class QueueEntryListTestBase extends TestCase
 {
     protected static final AMQQueue _testQueue = new MockAMQQueue("test");
     public abstract QueueEntryList<QueueEntry> getTestList();
+    public abstract QueueEntryList<QueueEntry> getTestList(boolean newList);
     public abstract long getExpectedFirstMsgId();
     public abstract int getExpectedListLength();
     public abstract ServerMessage getTestMessageToAdd() throws AMQException;
@@ -188,4 +189,36 @@ public abstract class QueueEntryListTestBase extends TestCase
                         .getMessage().getMessageNumber(), third.getMessage().getMessageNumber());
     }
 
+    /**
+     * Tests that after the last node of the list is marked deleted but has not yet been removed,
+     * the iterator still ignores it and returns that it is 'atTail()' and can't 'advance()'
+     *
+     * @see QueueEntryListTestBase#getTestList()
+     * @see QueueEntryListTestBase#getExpectedListLength()
+     */
+    public void testIteratorIgnoresDeletedFinalNode() throws Exception
+    {
+        QueueEntryList<QueueEntry> list = getTestList(true);
+        int i = 0;
+
+        QueueEntry queueEntry1 = list.add(new MockAMQMessage(i++));
+        QueueEntry queueEntry2 = list.add(new MockAMQMessage(i++));
+
+        assertSame(queueEntry2, list.next(queueEntry1));
+        assertNull(list.next(queueEntry2));
+
+        //'delete' the 2nd QueueEntry
+        assertTrue("Deleting node should have succeeded", queueEntry2.delete());
+
+        QueueEntryIterator<QueueEntry> iter = list.iterator();
+
+        //verify the iterator isn't 'atTail', can advance, and returns the 1st QueueEntry
+        assertFalse("Iterator should not have been 'atTail'", iter.atTail());
+        assertTrue("Iterator should have been able to advance", iter.advance());
+        assertSame("Iterator returned unexpected QueueEntry", queueEntry1, iter.getNode());
+
+        //verify the iterator is atTail() and can't advance
+        assertTrue("Iterator should have been 'atTail'", iter.atTail());
+        assertFalse("Iterator should not have been able to advance", iter.advance());
+    }
 }
diff --git a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SimpleQueueEntryListTest.java b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SimpleQueueEntryListTest.java
index 55c6143124..caf1eea09f 100644
--- a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SimpleQueueEntryListTest.java
+++ b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SimpleQueueEntryListTest.java
@@ -23,6 +23,7 @@ package org.apache.qpid.server.queue;
 import org.apache.qpid.AMQException;
 import org.apache.qpid.server.message.AMQMessage;
 import org.apache.qpid.server.message.ServerMessage;
+import org.apache.qpid.server.queue.SimpleQueueEntryList.QueueEntryIteratorImpl;
 
 import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
@@ -59,11 +60,24 @@ public class SimpleQueueEntryListTest extends QueueEntryListTestBase
             System.clearProperty(SCAVENGE_PROP);
         }
     }
-    
+
     @Override
     public QueueEntryList getTestList()
     {
-        return _sqel;
+        return getTestList(false);
+    }
+
+    @Override
+    public QueueEntryList getTestList(boolean newList)
+    {
+        if(newList)
+        {
+            return new SimpleQueueEntryList(_testQueue);
+        }
+        else
+        {
+            return _sqel;
+        }
     }
 
     @Override
@@ -216,5 +230,4 @@ public class SimpleQueueEntryListTest extends QueueEntryListTestBase
         next = next.getNextValidEntry();
         assertNull("The next entry after the last should be null", next);
     }
-
 }
diff --git a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SortedQueueEntryListTest.java b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SortedQueueEntryListTest.java
index 794888f780..38b12f8250 100644
--- a/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SortedQueueEntryListTest.java
+++ b/qpid/java/broker/src/test/java/org/apache/qpid/server/queue/SortedQueueEntryListTest.java
@@ -77,9 +77,23 @@ public class SortedQueueEntryListTest extends QueueEntryListTestBase
 
     }
 
+    @Override
     public QueueEntryList getTestList()
     {
-        return _sqel;
+        return getTestList(false);
+    }
+
+    @Override
+    public QueueEntryList getTestList(boolean newList)
+    {
+        if(newList)
+        {
+            return new SelfValidatingSortedQueueEntryList(_testQueue, "KEY");
+        }
+        else
+        {
+            return _sqel;
+        }
     }
 
     public int getExpectedListLength()