Repository: activemq Updated Branches: refs/heads/master 2f5e5efec -> 8f88dcda0
AMQ-7055 - Optimization on SequenceSet to prevent iterating through the whole set when a value bigger than the last value is added Signed-off-by: gtully <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/activemq/repo Commit: http://git-wip-us.apache.org/repos/asf/activemq/commit/8f88dcda Tree: http://git-wip-us.apache.org/repos/asf/activemq/tree/8f88dcda Diff: http://git-wip-us.apache.org/repos/asf/activemq/diff/8f88dcda Branch: refs/heads/master Commit: 8f88dcda09760df3aba3306f49a3311fb22a654f Parents: 2f5e5ef Author: Alan Protasio <[email protected]> Authored: Wed Sep 19 12:20:59 2018 -0700 Committer: gtully <[email protected]> Committed: Thu Sep 20 10:38:44 2018 +0100 ---------------------------------------------------------------------- .../store/kahadb/disk/util/Sequence.java | 4 +++ .../store/kahadb/disk/util/SequenceSet.java | 7 +++++ .../store/kahadb/disk/util/SequenceSetTest.java | 31 ++++++++++++++++++++ 3 files changed, 42 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/activemq/blob/8f88dcda/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java index f52931b..25e594b 100644 --- a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java +++ b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java @@ -38,6 +38,10 @@ public class Sequence extends LinkedNode<Sequence> { return last + 1 == value; } + public boolean isBiggerButNotAdjacentToLast(long value) { + return last + 1 < value; + } + public boolean isAdjacentToFirst(long value) { return first - 1 == value; } http://git-wip-us.apache.org/repos/asf/activemq/blob/8f88dcda/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java index 2946a22..fac831b 100644 --- a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java +++ b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java @@ -114,6 +114,13 @@ public class SequenceSet extends LinkedNodeList<Sequence> implements Iterable<Lo return true; } + // check if the value is greater than the bigger sequence value and if it's not adjacent to it + // in this case, we are sure that the value should be add to the tail of the sequence. + if (sequence.isBiggerButNotAdjacentToLast(value)) { + addLast(new Sequence(value)); + return true; + } + sequence = getHead(); while (sequence != null) { http://git-wip-us.apache.org/repos/asf/activemq/blob/8f88dcda/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java b/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java index 272077a..a25b4e7 100644 --- a/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java +++ b/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java @@ -86,6 +86,37 @@ public class SequenceSetTest { } @Test + public void testAddValuesToTail() { + SequenceSet set = new SequenceSet(); + set.add(new Sequence(0, 10)); + set.add(new Sequence(21, 42)); + set.add(new Sequence(142, 512)); + + set.add(513); + + for (int i = 600; i < 650; i++) { + set.add(i); + } + + for (int i = 0; i < 10; i++) { + set.add(i * 100); + } + + assertTrue(set.contains(0)); + assertTrue(set.contains(25)); + + assertTrue(set.contains(513)); + assertTrue(!set.contains(514)); + assertFalse(set.contains(599)); + assertTrue(set.contains(625)); + assertFalse(set.contains(651)); + + for (int i = 0; i < 10; i++) { + assertTrue(set.contains(i * 100)); + } + } + + @Test public void testRemove() { SequenceSet set = new SequenceSet(); set.add(new Sequence(0, 100));
