This is an automated email from the ASF dual-hosted git repository. asf-gitbox-commits pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-jcs.git
commit f54bb2b058427c03dee43576ad2df6748aa3f56d Author: Thomas Vandahl <[email protected]> AuthorDate: Wed Sep 30 12:44:47 2026 +0200 Fix eviction in multi-shard scenario --- .../jcs4/utils/struct/DoubleLinkedList.java | 85 +++++++++++++--------- .../jcs4/utils/struct/DoubleLinkedListNode.java | 20 ++++- .../utils/struct/DoubleLinkedListDumpUnitTest.java | 6 +- .../utils/struct/DoubleLinkedListUnitTest.java | 35 +++++++++ 4 files changed, 106 insertions(+), 40 deletions(-) diff --git a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java index 87e2c264..7631a3d4 100644 --- a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java +++ b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedList.java @@ -40,7 +40,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> private static final Log log = Log.getLog( DoubleLinkedList.class ); /** Record size to avoid having to iterate */ - private int size; + private AtomicInteger size; /** Number of shards */ private final int shards; @@ -62,7 +62,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> private AtomicCyclicCounter(int max) { this.max = max; - counter = new AtomicInteger(); + counter = new AtomicInteger(-1); } private int incrementAndGet() @@ -81,6 +81,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> */ public DoubleLinkedList(int shards) { + this.size = new AtomicInteger(); this.shards = shards; this.lock = new Lock[shards]; this.first = new DoubleLinkedListNode[shards]; @@ -89,10 +90,8 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> for (int i = 0; i < shards; i++) { - first[i] = new DoubleLinkedListNode(); - first[i].setShard(i); - last[i] = new DoubleLinkedListNode(); - last[i].setShard(i); + first[i] = new DoubleLinkedListNode(i); + last[i] = new DoubleLinkedListNode(i); first[i].next = this.last[i]; last[i].prev = this.first[i]; lock[i] = new ReentrantLock(); @@ -136,7 +135,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> me.next = first[shard].next; first[shard].next.prev = me; first[shard].next = me; - size++; + size.incrementAndGet(); } finally { @@ -159,7 +158,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> me.prev = last[shard].prev; last[shard].prev.next = me; last[shard].prev = me; - size++; + size.incrementAndGet(); } finally { @@ -188,21 +187,29 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> * * @return the first node, null if the list is empty. */ - @SuppressWarnings({"unchecked"}) // Don't know how to resolve this with generics public T getFirst() { log.debug("returning first node"); - int shard = this.spoolShard.incrementAndGet(); - lock[shard].lock(); - try - { - DoubleLinkedListNode f = first[shard].next; - return (T) (f == last[shard] ? null : f); - } - finally + for (int i = 0; i < shards; i++) { - lock[shard].unlock(); + int shard = this.spoolShard.incrementAndGet(); + lock[shard].lock(); + try + { + @SuppressWarnings({"unchecked"}) // Don't know how to resolve this with generics + T f = (T) first[shard].next; + if (f != last[shard]) + { + return f; + } + } + finally + { + lock[shard].unlock(); + } } + + return null; } /** @@ -210,21 +217,29 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> * * @return The last node, null if the list is empty. */ - @SuppressWarnings({"unchecked"}) // Don't know how to resolve this with generics public T getLast() { log.debug("returning last node"); - int shard = this.spoolShard.incrementAndGet(); - lock[shard].lock(); - try - { - DoubleLinkedListNode l = last[shard].prev; - return (T) (l == first[shard] ? null : l); - } - finally + for (int i = 0; i < shards; i++) { - lock[shard].unlock(); + int shard = this.spoolShard.incrementAndGet(); + lock[shard].lock(); + try + { + @SuppressWarnings({"unchecked"}) // Don't know how to resolve this with generics + T l = (T) last[shard].prev; + if (l != first[shard]) + { + return l; + } + } + finally + { + lock[shard].unlock(); + } } + + return null; } /** @@ -242,13 +257,13 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> { ln.prev.next = ln.next; ln.next.prev = ln.prev; - size--; + size.decrementAndGet(); } ln.prev = first[shard]; ln.next = first[shard].next; first[shard].next.prev = ln; first[shard].next = ln; - size++; + size.incrementAndGet(); } finally { @@ -271,13 +286,13 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> { ln.prev.next = ln.next; ln.next.prev = ln.prev; - size--; + size.decrementAndGet(); } ln.next = last[shard]; ln.prev = last[shard].prev; last[shard].prev.next = ln; last[shard].prev = ln; - size++; + size.incrementAndGet(); } finally { @@ -303,7 +318,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> me.prev.next = me.next; me.next.prev = me.prev; me.prev = me.next = null; - size--; + size.decrementAndGet(); } } finally @@ -331,6 +346,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> me = me.next; toRemove.prev = null; toRemove.next = null; + size.decrementAndGet(); } first[i].next = last[i]; last[i].prev = first[i]; @@ -340,7 +356,6 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> lock[i].unlock(); } } - size = 0; } /** @@ -367,7 +382,7 @@ public class DoubleLinkedList<T extends DoubleLinkedListNode> */ public int size() { - return size; + return size.get(); } /** diff --git a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListNode.java b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListNode.java index f1f0d1b9..737b03f1 100644 --- a/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListNode.java +++ b/commons-jcs4-core/src/main/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListNode.java @@ -36,11 +36,29 @@ public class DoubleLinkedListNode private static final long serialVersionUID = -1114934407695836097L; /** Number of the shard I belong to */ - private volatile int shard = 0; + private volatile int shard; /** Double Linked list references */ protected volatile DoubleLinkedListNode prev, next; + /** + * Constructs default object + */ + public DoubleLinkedListNode() + { + this(0); + } + + /** + * Constructs node for a given shard + * + * @param shard the number of the shard + */ + public DoubleLinkedListNode(int shard) + { + this.shard = shard; + } + /** * Returns the shard of this node * diff --git a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListDumpUnitTest.java b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListDumpUnitTest.java index ee2e310e..fcad91b9 100644 --- a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListDumpUnitTest.java +++ b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListDumpUnitTest.java @@ -39,10 +39,8 @@ class DoubleLinkedListDumpUnitTest final DoubleLinkedList<DoubleLinkedListNode> list = new DoubleLinkedList<>(2); - final DoubleLinkedListNode node1 = new DoubleLinkedListNode(); - node1.setShard(0); - final DoubleLinkedListNode node2 = new DoubleLinkedListNode(); - node2.setShard(1); + final DoubleLinkedListNode node1 = new DoubleLinkedListNode(0); + final DoubleLinkedListNode node2 = new DoubleLinkedListNode(1); list.addLast( node1 ); list.addLast( node2 ); diff --git a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java index 69ad5927..648b5fd6 100644 --- a/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java +++ b/commons-jcs4-core/src/test/java/org/apache/commons/jcs4/utils/struct/DoubleLinkedListUnitTest.java @@ -149,6 +149,41 @@ class DoubleLinkedListUnitTest assertEquals( node2, list.getFirst(), "Wrong first" ); } + /** Verify shard cleanup */ + @Test + void testMakeLast_getLast_with_shards() + { + // SETUP + final DoubleLinkedList<DoubleLinkedListNode> list = new DoubleLinkedList<>(3); + + final DoubleLinkedListNode node00 = new DoubleLinkedListNode(0); + final DoubleLinkedListNode node02 = new DoubleLinkedListNode(2); + final DoubleLinkedListNode node10 = new DoubleLinkedListNode(0); + final DoubleLinkedListNode node12 = new DoubleLinkedListNode(2); + + list.addFirst(node00); + list.addFirst(node02); + list.addFirst(node10); + list.addFirst(node12); + + // DO WORK + list.makeLast(node10); + + // Expected content + // shard 0: node00 node10 + // shard 1: + // shard 2: node12 node02 + + // VERIFY + assertEquals(4, list.size(), "Wrong size"); + assertEquals(node10, list.getLast(), "Wrong last"); + assertEquals(node02, list.getLast(), "Wrong last"); + assertEquals(node10, list.getLast(), "Wrong last"); + assertEquals(node12, list.getFirst(), "Wrong first"); + assertEquals(node00, list.getFirst(), "Wrong first"); + assertEquals(node12, list.getFirst(), "Wrong first"); + } + /** Verify that remove and removeAll work. */ @Test void testRemove()
