activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r687406 - in /activemq/sandbox/kahadb/src/main/java/org/apache/kahadb: impl/index/RedoStoreIndexItem.java util/LinkedNode.java util/LinkedNodeList.java util/Sequence.java util/SequenceSet.java
Date Wed, 20 Aug 2008 18:18:18 GMT
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



Mime
View raw message