Author: chirino
Date: Wed Aug 20 11:18:18 2008
New Revision: 687406
URL: http://svn.apache.org/viewvc?rev=687406&view=rev
Log:
adding the SequenceSet impl which allows you to efficiently track sequences of
numbers.
Added:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNodeList.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/Sequence.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/SequenceSet.java
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNode.java
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java?rev=687406&r1=687405&r2=687406&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java
(original)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java
Wed Aug 20 11:18:18 2008
@@ -38,6 +38,10 @@
RedoStoreIndexItem item = (RedoStoreIndexItem)object;
item.writeExternal(out);
}
+
+ public Class getType() {
+ return RedoStoreIndexItem.class;
+ }
};
private static final long serialVersionUID = -4865508871719676655L;
Modified:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNode.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNode.java?rev=687406&r1=687405&r2=687406&view=diff
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNode.java
(original)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNode.java
Wed Aug 20 11:18:18 2008
@@ -22,137 +22,299 @@
*
* @author chirino
*/
-public class LinkedNode {
+public class LinkedNode<T extends LinkedNode<T>> {
- protected LinkedNode next = this;
- protected LinkedNode prev = this;
- protected boolean tail = true;
+ protected LinkedNodeList<T> list;
+ protected T next;
+ protected T prev;
- public LinkedNode getHeadNode() {
- if (isHeadNode()) {
- return this;
- }
- if (isTailNode()) {
- return next;
- }
- LinkedNode rc = prev;
- while (!rc.isHeadNode()) {
- rc = rc.prev;
- }
- return rc;
+ public LinkedNode() {
}
- public LinkedNode getTailNode() {
- if (isTailNode()) {
- return this;
- }
- if (isHeadNode()) {
- return prev;
- }
- LinkedNode rc = next;
- while (!rc.isTailNode()) {
- rc = rc.next;
- }
- return rc;
+ @SuppressWarnings("unchecked")
+ private T getThis() {
+ return (T) this;
}
- public LinkedNode getNext() {
- return tail ? null : next;
+ public T getHeadNode() {
+ return list.head;
}
- public LinkedNode getPrevious() {
- return prev.tail ? null : prev;
+ public T getTailNode() {
+ return list.head.prev;
+ }
+
+ public T getNext() {
+ return isTailNode() ? null : next;
+ }
+
+ public T getPrevious() {
+ return isHeadNode() ? null : prev;
+ }
+
+ public T getNextCircular() {
+ return next;
+ }
+
+ public T getPreviousCircular() {
+ return prev;
}
public boolean isHeadNode() {
- return prev.isTailNode();
+ return list.head == this;
}
public boolean isTailNode() {
- return tail;
+ return list.head.prev == this;
+ }
+
+ /**
+ * @param node
+ * the node to link after this node.
+ * @return this
+ */
+ public void linkAfter(T node) {
+ if (node == this) {
+ throw new IllegalArgumentException("You cannot link to yourself");
+ }
+ if (node.list != null) {
+ throw new IllegalArgumentException("You only insert nodes that are
not in a list");
+ }
+ if (list == null) {
+ throw new IllegalArgumentException("This node is not yet in a
list");
+ }
+
+ node.list = list;
+
+ // given we linked this<->next and are inserting node in between
+ node.prev = getThis(); // link this<-node
+ node.next = next; // link node->next
+ next.prev = node; // link node<-next
+ next = node; // this->node
+ list.size++;
}
/**
- * @param rightHead the node to link after this node.
+ * @param rightList
+ * the node to link after this node.
* @return this
*/
- public LinkedNode linkAfter(LinkedNode rightHead) {
+ public void linkAfter(LinkedNodeList<T> rightList) {
- if (rightHead == this) {
+ if (rightList == list) {
throw new IllegalArgumentException("You cannot link to yourself");
}
- if (!rightHead.isHeadNode()) {
- throw new IllegalArgumentException("You only insert nodes that are
the first in a list");
+ if (list == null) {
+ throw new IllegalArgumentException("This node is not yet in a
list");
}
- LinkedNode rightTail = rightHead.prev;
+ T rightHead = rightList.head;
+ T rightTail = rightList.head.prev;
+ list.reparent(rightList);
+
+ // given we linked this<->next and are inserting list in between
+ rightHead.prev = getThis(); // link this<-list
+ rightTail.next = next; // link list->next
+ next.prev = rightTail; // link list<-next
+ next = rightHead; // this->list
+ list.size++;
+ }
- if (tail) {
- tail = false;
- } else {
- rightTail.tail = false;
+ /**
+ * @param node
+ * the node to link after this node.
+ * @return
+ * @return this
+ */
+ public void linkBefore(T node) {
+
+ if (node == this) {
+ throw new IllegalArgumentException("You cannot link to yourself");
+ }
+ if (node.list != null) {
+ throw new IllegalArgumentException("You only insert nodes that are
not in a list");
}
+ if (list == null) {
+ throw new IllegalArgumentException("This node is not yet in a
list");
+ }
+
+ node.list = list;
- rightHead.prev = this; // link the head of the right side.
- rightTail.next = next; // link the tail of the right side
- next.prev = rightTail; // link the head of the left side
- next = rightHead; // link the tail of the left side.
+ // given we linked prev<->this and are inserting node in between
+ node.next = getThis(); // node->this
+ node.prev = prev; // prev<-node
+ prev.next = node; // prev->node
+ prev = node; // node<-this
- return this;
+ if (this == list.head) {
+ list.head = node;
+ }
+ list.size++;
}
/**
- * @param leftHead the node to link after this node.
+ * @param leftList
+ * the node to link after this node.
* @return
* @return this
*/
- public LinkedNode linkBefore(LinkedNode leftHead) {
+ public void linkBefore(LinkedNodeList<T> leftList) {
- if (leftHead == this) {
+ if (leftList == list) {
throw new IllegalArgumentException("You cannot link to yourself");
}
- if (!leftHead.isHeadNode()) {
- throw new IllegalArgumentException("You only insert nodes that are
the first in a list");
+ if (list == null) {
+ throw new IllegalArgumentException("This node is not yet in a
list");
}
- // The left side is no longer going to be a tail..
- LinkedNode leftTail = leftHead.prev;
- leftTail.tail = false;
+ T leftHead = leftList.head;
+ T leftTail = leftList.head.prev;
+ list.reparent(leftList);
+
+ // given we linked prev<->this and are inserting list in between
+ leftTail.next = getThis(); // list->this
+ leftHead.prev = prev; // prev<-list
+ prev.next = leftHead; // prev->list
+ prev = leftTail; // list<-this
+
+ if (isHeadNode()) {
+ list.head = leftHead;
+ }
+ }
- leftTail.next = this; // link the tail of the left side.
- leftHead.prev = prev; // link the head of the left side.
- prev.next = leftHead; // link the tail of the right side.
- prev = leftTail; // link the head of the right side.
+ public void linkToTail(LinkedNodeList<T> target) {
+ if (list != null) {
+ throw new IllegalArgumentException("This node is already linked to
a node");
+ }
- return leftHead;
+ if (target.head == null) {
+ next = prev = target.head = getThis();
+ list = target;
+ list.size++;
+ } else {
+ target.head.prev.linkAfter(getThis());
+ }
+ }
+
+ public void linkToHead(LinkedNodeList<T> target) {
+ if (list != null) {
+ throw new IllegalArgumentException("This node is already linked to
a node");
+ }
+
+ if (target.head == null) {
+ next = prev = target.head = getThis();
+ list = target;
+ list.size++;
+ } else {
+ target.head.linkBefore(getThis());
+ }
}
/**
* Removes this node out of the linked list it is chained in.
*/
public void unlink() {
+
// If we are allready unlinked...
- if (prev == this) {
- reset();
+ if (list == null) {
return;
}
- if (tail) {
- prev.tail = true;
+ if (getThis() == prev) {
+ // We are the only item in the list
+ list.head = null;
+ } else {
+ // given we linked prev<->this<->next
+ next.prev = prev; // prev<-next
+ prev.next = next; // prev->next
+
+ if (isHeadNode()) {
+ list.head = next;
+ }
}
+ list.size--;
+ list = null;
+ }
+
+ /**
+ * Splits the list into 2 lists. This node becomes the tail of this list.
+ * Then 2nd list is returned.
+ *
+ * @return An empty list if this is a tail node.
+ */
+ public LinkedNodeList<T> splitAfter() {
+
+ if (isTailNode()) {
+ return new LinkedNodeList<T>();
+ }
+
+ // Create the new list
+ LinkedNodeList<T> newList = new LinkedNodeList<T>();
+ newList.head = next;
+
+ // Update the head and tail of the new list so that they point to each
+ // other.
+ newList.head.prev = list.head.prev; // new list: tail<-head
+ newList.head.prev.next = newList.head; // new list: tail->head
+ next = list.head; // old list: tail->head
+ list.head.prev = getThis(); // old list: tail<-head
+
+ // Update all the nodes in the new list so that they know of their new
+ // list owner.
+ T n = newList.head;
+ newList.size++;
+ list.size--;
+ do {
+ n.list = newList;
+ n = n.next;
+ newList.size++;
+ list.size--;
+ } while (n != newList.head);
+
+ return newList;
+ }
+
+ /**
+ * Splits the list into 2 lists. This node becomes the head of this list.
+ * Then 2nd list is returned.
+ *
+ * @return An empty list if this is a head node.
+ */
+ public LinkedNodeList<T> splitBefore() {
+
+ if (isHeadNode()) {
+ return new LinkedNodeList<T>();
+ }
+
+ // Create the new list
+ LinkedNodeList<T> newList = new LinkedNodeList<T>();
+ newList.head = list.head;
+ list.head = getThis();
+
+ T newListTail = prev;
+
+ prev = newList.head.prev; // old list: tail<-head
+ prev.next = getThis(); // old list: tail->head
+ newList.head.prev = newListTail; // new list: tail<-head
+ newListTail.next = newList.head; // new list: tail->head
+
+ // Update all the nodes in the new list so that they know of their new
+ // list owner.
+ T n = newList.head;
+ newList.size++;
+ list.size--;
+ do {
+ n.list = newList;
+ n = n.next;
+ newList.size++;
+ list.size--;
+ } while (n != newList.head);
+
+ return newList;
+ }
- // Update the peers links..
- next.prev = prev;
- prev.next = next;
-
- // Update our links..
- reset();
- }
-
- public void reset() {
- next = this;
- prev = this;
- tail = true;
+ public boolean isLinked() {
+ return list != null;
}
}
Added:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNodeList.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNodeList.java?rev=687406&view=auto
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNodeList.java
(added)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/LinkedNodeList.java
Wed Aug 20 11:18:18 2008
@@ -0,0 +1,103 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.kahadb.util;
+
+/**
+ * Provides a list of LinkedNode objects.
+ *
+ * @author chirino
+ */
+public class LinkedNodeList<T extends LinkedNode<T>> {
+
+ T head;
+ int size;
+
+ public LinkedNodeList() {
+ }
+
+ public boolean isEmpty() {
+ return head == null;
+ }
+
+ public void addLast(T node) {
+ node.linkToTail(this);
+ }
+
+ public void addFirst(T node) {
+ node.linkToHead(this);
+ }
+
+ public T getHead() {
+ return head;
+ }
+
+ public T getTail() {
+ return head.prev;
+ }
+
+ public void addLast(LinkedNodeList<T> list) {
+ if (list.isEmpty()) {
+ return;
+ }
+ if (head == null) {
+ reparent(list);
+ head = list.head;
+ list.head = null;
+ } else {
+ getTail().linkAfter(list);
+ }
+ }
+
+ public void addFirst(LinkedNodeList<T> list) {
+ if (list.isEmpty()) {
+ return;
+ }
+ if (head == null) {
+ reparent(list);
+ head = list.head;
+ list.head = null;
+ } else {
+ getHead().linkBefore(list);
+ }
+ }
+
+ public T reparent(LinkedNodeList<T> list) {
+ size += list.size;
+ T n = list.head;
+ do {
+ n.list = this;
+ n = n.next;
+ } while (n != list.head);
+ list.head = null;
+ list.size = 0;
+ return n;
+ }
+
+ /**
+ * Move the head to the tail and returns the new head node.
+ *
+ * @return
+ */
+ public T rotate() {
+ return head = head.getNext();
+ }
+
+ public int size() {
+ return size;
+ }
+
+}
Added:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/Sequence.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/Sequence.java?rev=687406&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/Sequence.java
(added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/Sequence.java
Wed Aug 20 11:18:18 2008
@@ -0,0 +1,58 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.kahadb.util;
+
+/**
+ * Represents a range of numbers.
+ *
+ * @author chirino
+ */
+public class Sequence extends LinkedNode<Sequence> {
+ long first;
+ long last;
+
+ public Sequence(long value) {
+ first = last = value;
+ }
+
+ public Sequence(long first, long last) {
+ this.first = first;
+ this.last = last;
+ }
+
+ public boolean isAdjacentToLast(long value) {
+ return last + 1 == value;
+ }
+
+ public boolean isAdjacentToFirst(long value) {
+ return first - 1 == value;
+ }
+
+ public boolean contains(long value) {
+ return first <= value && value <= last;
+ }
+
+ public long range() {
+ return first == last ? 1 : (last - first) + 1;
+ }
+
+ @Override
+ public String toString() {
+ return first == last ? "" + first : first + "-" + last;
+ }
+
+}
\ No newline at end of file
Added:
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/SequenceSet.java
URL:
http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/SequenceSet.java?rev=687406&view=auto
==============================================================================
---
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/SequenceSet.java
(added)
+++
activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/util/SequenceSet.java
Wed Aug 20 11:18:18 2008
@@ -0,0 +1,150 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.kahadb.util;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Keeps track of a added long values. Collapses ranges of numbers using a
+ * Sequence representation. Use to keep track of received message ids to find
+ * out if a message is duplicate or if there are any missing messages.
+ *
+ * @author chirino
+ */
+public class SequenceSet {
+ LinkedNodeList<Sequence> sequences = new LinkedNodeList<Sequence>();
+
+ /**
+ *
+ * @param value
+ * the value to add to the list
+ * @return false if the value was a duplicate.
+ */
+ synchronized public boolean add(long value) {
+
+ if (sequences.isEmpty()) {
+ sequences.addFirst(new Sequence(value));
+ return true;
+ }
+
+ Sequence sequence = sequences.getHead();
+ while (sequence != null) {
+
+ if (sequence.isAdjacentToLast(value)) {
+ // grow the sequence...
+ sequence.last = value;
+ // it might connect us to the next sequence..
+ if (sequence.getNext() != null) {
+ Sequence next = sequence.getNext();
+ if (next.isAdjacentToFirst(value)) {
+ // Yep the sequence connected.. so join them.
+ sequence.last = next.last;
+ next.unlink();
+ }
+ }
+ return true;
+ }
+
+ if (sequence.isAdjacentToFirst(value)) {
+ // grow the sequence...
+ sequence.first = value;
+
+ // it might connect us to the previous
+ if (sequence.getPrevious() != null) {
+ Sequence prev = sequence.getPrevious();
+ if (prev.isAdjacentToLast(value)) {
+ // Yep the sequence connected.. so join them.
+ sequence.first = prev.first;
+ prev.unlink();
+ }
+ }
+ return true;
+ }
+
+ // Did that value land before this sequence?
+ if (value < sequence.first) {
+ // Then insert a new entry before this sequence item.
+ sequence.linkBefore(new Sequence(value));
+ return true;
+ }
+
+ // Did that value land within the sequence? The it's a duplicate.
+ if (sequence.contains(value)) {
+ return false;
+ }
+
+ sequence = sequence.getNext();
+ }
+
+ // Then the value is getting appended to the tail of the sequence.
+ sequences.addLast(new Sequence(value));
+ return true;
+ }
+
+ /**
+ * @return all the id Sequences that are missing from this set that are not
+ * in between the range provided.
+ */
+ synchronized public List<Sequence> getMissing(long first, long last) {
+ ArrayList<Sequence> rc = new ArrayList<Sequence>();
+ if (first > last) {
+ throw new IllegalArgumentException("First cannot be more than
last");
+ }
+ if (sequences.isEmpty()) {
+ // We are missing all the messages.
+ rc.add(new Sequence(first, last));
+ return rc;
+ }
+
+ Sequence sequence = sequences.getHead();
+ while (sequence != null && first <= last) {
+ if (sequence.contains(first)) {
+ first = sequence.last + 1;
+ } else {
+ if (first < sequence.first) {
+ if (last < sequence.first) {
+ rc.add(new Sequence(first, last));
+ return rc;
+ } else {
+ rc.add(new Sequence(first, sequence.first - 1));
+ first = sequence.last + 1;
+ }
+ }
+ }
+ sequence = sequence.getNext();
+ }
+
+ if (first <= last) {
+ rc.add(new Sequence(first, last));
+ }
+ return rc;
+ }
+
+ /**
+ * @return all the Sequence that are in this list
+ */
+ synchronized public List<Sequence> getReceived() {
+ ArrayList<Sequence> rc = new ArrayList<Sequence>(sequences.size());
+ Sequence sequence = sequences.getHead();
+ while (sequence != null) {
+ rc.add(new Sequence(sequence.first, sequence.last));
+ sequence = sequence.getNext();
+ }
+ return rc;
+ }
+}
\ No newline at end of file
