[kafka] branch trunk updated: MINOR: fix a bug in removing elements from an ImplicitLinkedHashColle… (#9428)

[cm...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

cmccabe pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/kafka.git


The following commit(s) were added to refs/heads/trunk by this push:
     new 7f9beea  MINOR: fix a bug in removing elements from an ImplicitLinkedHashColle… (#9428)
7f9beea is described below

commit 7f9beeaaafdb1bc74a5f0c1386f7e01f5f831d6b
Author: Colin Patrick McCabe <cm...@confluent.io>
AuthorDate: Wed Oct 14 14:53:30 2020 -0700

    MINOR: fix a bug in removing elements from an ImplicitLinkedHashColle… (#9428)
    
    Fix a bug that was introduced by change 86013dc that resulted in incorrect behavior when
    deleting through an iterator.
    
    The bug is that the hash table relies on a denseness invariant... if you remove something,
    you might have to move some other things. Calling removeElementAtSlot will do this.
    Calling removeFromList is not enough.
    
    Reviewers: Jason Gustafson <ja...@confluent.io>
---
 .../common/utils/ImplicitLinkedHashCollection.java |  3 +--
 .../utils/ImplicitLinkedHashCollectionTest.java    | 24 +++++++++++++++++++++-
 2 files changed, 24 insertions(+), 3 deletions(-)

diff --git a/clients/src/main/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollection.java b/clients/src/main/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollection.java
index decabe8..3e1bccc 100644
--- a/clients/src/main/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollection.java
+++ b/clients/src/main/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollection.java
@@ -208,8 +208,7 @@ public class ImplicitLinkedHashCollection<E extends ImplicitLinkedHashCollection
                 throw new IllegalStateException();
             }
             Element nextElement = indexToElement(head, elements, lastReturned.next());
-            removeFromList(head, elements, nextElement.prev());
-            size--;
+            ImplicitLinkedHashCollection.this.removeElementAtSlot(nextElement.prev());
             if (lastReturned == cur) {
                 // If the element we are removing was cur, set cur to cur->next.
                 cur = nextElement;
diff --git a/clients/src/test/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollectionTest.java b/clients/src/test/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollectionTest.java
index 01be3a6..152d5be 100644
--- a/clients/src/test/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollectionTest.java
+++ b/clients/src/test/java/org/apache/kafka/common/utils/ImplicitLinkedHashCollectionTest.java
@@ -103,7 +103,8 @@ public class ImplicitLinkedHashCollectionTest {
 
         @Override
         public int hashCode() {
-            return key;
+            long hashCode = 2654435761L * key;
+            return (int) (hashCode >> 32);
         }
     }
 
@@ -596,4 +597,25 @@ public class ImplicitLinkedHashCollectionTest {
         Assert.assertThrows(RuntimeException.class, () ->
             coll.moveToEnd(new TestElement(4, 4)));
     }
+
+    @Test
+    public void testRemovals() {
+        ImplicitLinkedHashCollection<TestElement> coll = new ImplicitLinkedHashCollection<>();
+        List<TestElement> elements  = new ArrayList<>();
+        for (int i = 0; i < 100; i++) {
+            TestElement element  = new TestElement(i, i);
+            elements.add(element);
+            coll.add(element);
+        }
+        assertEquals(100, coll.size());
+        Iterator<TestElement> iter = coll.iterator();
+        for (int i = 0; i < 50; i++) {
+            iter.next();
+            iter.remove();
+        }
+        assertEquals(50, coll.size());
+        for (int i = 50; i < 100; i++) {
+            assertEquals(new TestElement(i, i), coll.find(elements.get(i)));
+        }
+    }
 }