Mailing-List: contact commits-help@activemq.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@activemq.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r677944 [5/11] - in /activemq/sandbox/kahadb: ./ src/
 src/main/
 src/main/java/ src/main/java/org/ src/main/java/org/apache/
 src/main/java/org/apache/kahadb/ src/main/java/org/apache/kahadb/impl/
 src/main/java/org/apache/kahadb/impl/async/ s...
Date: Fri, 18 Jul 2008 15:49:52 -0000
To: commits@activemq.apache.org
From: chirino@apache.org
Message-Id: <20080718154958.5801B2388A96@eris.apache.org>

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/DiskIndexLinkedList.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/DiskIndexLinkedList.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/DiskIndexLinkedList.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/DiskIndexLinkedList.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,357 @@
+/**
+ * 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.impl.index;
+
+import java.io.IOException;
+
+import org.apache.kahadb.StoreEntry;
+
+/**
+ * A linked list used by IndexItems
+ * 
+ * @version $Revision: 636078 $
+ */
+public class DiskIndexLinkedList implements IndexLinkedList {
+    protected IndexManager indexManager;
+    protected transient IndexItem root;
+    protected transient IndexItem last;
+    protected transient int size;
+
+    /**
+     * Constructs an empty list.
+     */
+    public DiskIndexLinkedList(IndexManager im, IndexItem header) {
+        this.indexManager = im;
+        this.root = header;
+    }
+
+    public synchronized IndexItem getRoot() {
+        return root;
+    }
+
+    public void setRoot(IndexItem e) {
+        this.root = e;
+    }
+
+    /**
+     * Returns the first element in this list.
+     * 
+     * @return the first element in this list.
+     */
+    public synchronized IndexItem getFirst() {
+        if (size == 0) {
+            return null;
+        }
+        return getNextEntry(root);
+    }
+
+    /**
+     * Returns the last element in this list.
+     * 
+     * @return the last element in this list.
+     */
+    public synchronized IndexItem getLast() {
+        if (size == 0) {
+            return null;
+        }
+        if (last != null) {
+            last.next = null;
+            last.setNextItem(IndexItem.POSITION_NOT_SET);
+        }
+        return last;
+    }
+
+    /**
+     * Removes and returns the first element from this list.
+     * 
+     * @return the first element from this list.
+     */
+    public synchronized StoreEntry removeFirst() {
+        if (size == 0) {
+            return null;
+        }
+        IndexItem result = getNextEntry(root);
+        remove(result);
+        return result;
+    }
+
+    /**
+     * Removes and returns the last element from this list.
+     * 
+     * @return the last element from this list.
+     */
+    public synchronized Object removeLast() {
+        if (size == 0) {
+            return null;
+        }
+        StoreEntry result = last;
+        remove(last);
+        return result;
+    }
+
+    /**
+     * Inserts the given element at the beginning of this list.
+     * 
+     * @param o the element to be inserted at the beginning of this list.
+     */
+    public synchronized void addFirst(IndexItem item) {
+        if (size == 0) {
+            last = item;
+        }
+        size++;
+    }
+
+    /**
+     * Appends the given element to the end of this list. (Identical in function
+     * to the <tt>add</tt> method; included only for consistency.)
+     * 
+     * @param o the element to be inserted at the end of this list.
+     */
+    public synchronized void addLast(IndexItem item) {
+        size++;
+        last = item;
+    }
+
+    /**
+     * Returns the number of elements in this list.
+     * 
+     * @return the number of elements in this list.
+     */
+    public synchronized int size() {
+        return size;
+    }
+
+    /**
+     * is the list empty?
+     * 
+     * @return true if there are no elements in the list
+     */
+    public synchronized boolean isEmpty() {
+        return size == 0;
+    }
+
+    /**
+     * Appends the specified element to the end of this list.
+     * 
+     * @param o element to be appended to this list.
+     * @return <tt>true</tt> (as per the general contract of
+     *         <tt>Collection.add</tt>).
+     */
+    public synchronized boolean add(IndexItem item) {
+        addLast(item);
+        return true;
+    }
+
+    /**
+     * Removes all of the elements from this list.
+     */
+    public synchronized void clear() {
+        last = null;
+        size = 0;
+    }
+
+    // Positional Access Operations
+    /**
+     * Returns the element at the specified position in this list.
+     * 
+     * @param index index of element to return.
+     * @return the element at the specified position in this list.
+     * @throws IndexOutOfBoundsException if the specified index is is out of
+     *                 range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     */
+    public synchronized IndexItem get(int index) {
+        return entry(index);
+    }
+
+    /**
+     * Inserts the specified element at the specified position in this list.
+     * Shifts the element currently at that position (if any) and any subsequent
+     * elements to the right (adds one to their indices).
+     * 
+     * @param index index at which the specified element is to be inserted.
+     * @param element element to be inserted.
+     * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
+     */
+    public synchronized void add(int index, IndexItem element) {
+        if (index == size) {
+            last = element;
+        }
+        size++;
+    }
+
+    /**
+     * Removes the element at the specified position in this list. Shifts any
+     * subsequent elements to the left (subtracts one from their indices).
+     * Returns the element that was removed from the list.
+     * 
+     * @param index the index of the element to removed.
+     * @return the element previously at the specified position.
+     * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     */
+    public synchronized Object remove(int index) {
+        IndexItem e = entry(index);
+        remove(e);
+        return e;
+    }
+
+    /**
+     * Return the indexed entry.
+     */
+    private IndexItem entry(int index) {
+        if (index < 0 || index >= size) {
+            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
+        }
+        IndexItem e = root;
+
+        for (int i = 0; i <= index; i++) {
+            e = getNextEntry(e);
+        }
+        if (e != null && last != null && last.equals(e)) {
+            last = e;
+        }
+        return e;
+    }
+
+    // Search Operations
+    /**
+     * Returns the index in this list of the first occurrence of the specified
+     * element, or -1 if the List does not contain this element. More formally,
+     * returns the lowest index i such that
+     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if there
+     * is no such index.
+     * 
+     * @param o element to search for.
+     * @return the index in this list of the first occurrence of the specified
+     *         element, or -1 if the list does not contain this element.
+     */
+    public synchronized int indexOf(StoreEntry o) {
+        int index = 0;
+        if (size > 0) {
+            for (IndexItem e = getNextEntry(root); e != null; e = getNextEntry(e)) {
+                if (o.equals(e)) {
+                    return index;
+                }
+                index++;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Retrieve the next entry after this entry
+     * 
+     * @param entry
+     * @return next entry
+     */
+    public synchronized IndexItem getNextEntry(IndexItem current) {
+		IndexItem result = null;
+		if (current != null) {
+			current = (IndexItem) refreshEntry(current);
+			if (current.getNextItem() >= 0) {
+				try {
+					result = indexManager.getIndex(current.getNextItem());
+				} catch (IOException e) {
+					throw new RuntimeException("Failed to get next index from "
+							+ indexManager + " for " + current, e);
+				}
+			}
+		}
+		// essential last get's updated consistently
+		if (result != null && last != null && last.equals(result)) {
+			last=result;
+		}
+		return result;
+	}
+
+    /**
+	 * Retrive the prev entry after this entry
+	 * 
+	 * @param entry
+	 * @return prev entry
+	 */
+    public synchronized IndexItem getPrevEntry(IndexItem current) {
+		IndexItem result = null;
+		if (current != null) {
+			if (current.getPreviousItem() >= 0) {
+				current = (IndexItem) refreshEntry(current);
+				try {
+					result = indexManager.getIndex(current.getPreviousItem());
+				} catch (IOException e) {
+					throw new RuntimeException(
+							"Failed to  get current index for " + current, e);
+				}
+			}
+		}
+		// essential root get's updated consistently
+		if (result != null && root != null && root.equals(result)) {
+			return null;
+		}
+		return result;
+	}
+
+    public synchronized StoreEntry getEntry(StoreEntry current) {
+        StoreEntry result = null;
+        if (current != null && current.getOffset() >= 0) {
+            try {
+                result = indexManager.getIndex(current.getOffset());
+            } catch (IOException e) {
+                throw new RuntimeException("Failed to index", e);
+            }
+        }
+        // essential root get's updated consistently
+        if (result != null && root != null && root.equals(result)) {
+            return root;
+        }
+        return result;
+    }
+
+    /**
+     * Update the indexes of a StoreEntry
+     * 
+     * @param current
+     */
+    public synchronized StoreEntry refreshEntry(StoreEntry current) {
+        StoreEntry result = null;
+        if (current != null && current.getOffset() >= 0) {
+            try {
+                result = indexManager.refreshIndex((IndexItem)current);
+            } catch (IOException e) {
+                throw new RuntimeException("Failed to index", e);
+            }
+        }
+        // essential root get's updated consistently
+        if (result != null && root != null && root.equals(result)) {
+            return root;
+        }
+        return result;
+    }
+
+    public synchronized void remove(IndexItem e) {
+        if (e==null || e == root || e.equals(root)) {
+            return;
+        }
+        if (e == last || e.equals(last)) {
+            if (size > 1) {
+                last = (IndexItem)refreshEntry(last);
+                last = getPrevEntry(last);
+            } else {
+                last = null;
+            }
+        }
+        size--;
+    }
+}

Propchange: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/DiskIndexLinkedList.java
------------------------------------------------------------------------------
    svn:executable = *

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/Index.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/Index.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/Index.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/Index.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,100 @@
+/**
+ * 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.impl.index;
+
+import java.io.IOException;
+
+import org.apache.kahadb.Marshaller;
+import org.apache.kahadb.StoreEntry;
+
+/**
+ * Simplier than a Map
+ * 
+ * @version $Revision: 1.2 $
+ */
+public interface Index {
+
+    /**
+     * clear the index
+     * 
+     * @throws IOException
+     * 
+     */
+    void clear() throws IOException;
+
+    /**
+     * @param key
+     * @return true if it contains the key
+     * @throws IOException
+     */
+    boolean containsKey(Object key) throws IOException;
+
+    /**
+     * remove the index key
+     * 
+     * @param key
+     * @return StoreEntry removed
+     * @throws IOException
+     */
+    StoreEntry remove(Object key) throws IOException;
+
+    /**
+     * store the key, item
+     * 
+     * @param key
+     * @param entry
+     * @throws IOException
+     */
+    void store(Object key, StoreEntry entry) throws IOException;
+
+    /**
+     * @param key
+     * @return the entry
+     * @throws IOException
+     */
+    StoreEntry get(Object key) throws IOException;
+
+    /**
+     * @return true if the index is transient
+     */
+    boolean isTransient();
+
+    /**
+     * load indexes
+     */
+    void load();
+
+    /**
+     * unload indexes
+     * 
+     * @throws IOException
+     */
+    void unload() throws IOException;
+
+    /**
+     * Set the marshaller for key objects
+     * 
+     * @param marshaller
+     */
+    void setKeyMarshaller(Marshaller marshaller);
+    
+    /**
+     * return the size of the index
+     * @return
+     */
+    int getSize();
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexItem.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexItem.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexItem.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexItem.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,332 @@
+/**
+ * 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.impl.index;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+
+import org.apache.kahadb.StoreEntry;
+import org.apache.kahadb.StoreLocation;
+import org.apache.kahadb.impl.data.DataItem;
+import org.apache.kahadb.impl.data.Item;
+
+/**
+ * A an Item with a relative position and location to other Items in the Store
+ * 
+ * @version $Revision: 1.2 $
+ */
+public class IndexItem implements Item, StoreEntry {
+
+    public static final int INDEX_SIZE = 51;
+    public static final int INDEXES_ONLY_SIZE = 19;
+
+    protected long offset = POSITION_NOT_SET;
+
+    // used by linked list
+    IndexItem next;
+    IndexItem prev;
+
+    private long previousItem = POSITION_NOT_SET;
+    private long nextItem = POSITION_NOT_SET;
+    private boolean active = true;
+
+    // TODO: consider just using a DataItem for the following fields.
+    private long keyOffset = POSITION_NOT_SET;
+    private int keyFile = (int)POSITION_NOT_SET;
+    private int keySize;
+
+    private long valueOffset = POSITION_NOT_SET;
+    private int valueFile = (int)POSITION_NOT_SET;
+    private int valueSize;
+
+    /**
+     * Default Constructor
+     */
+    public IndexItem() {
+    }
+
+    void reset() {
+        previousItem = POSITION_NOT_SET;
+        nextItem = POSITION_NOT_SET;
+        keyOffset = POSITION_NOT_SET;
+        keyFile = (int)POSITION_NOT_SET;
+        keySize = 0;
+        valueOffset = POSITION_NOT_SET;
+        valueFile = (int)POSITION_NOT_SET;
+        valueSize = 0;
+        active = true;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getKeyDataItem()
+     */
+    public StoreLocation getKeyDataItem() {
+        DataItem result = new DataItem();
+        result.setOffset(keyOffset);
+        result.setFile(keyFile);
+        result.setSize(keySize);
+        return result;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getValueDataItem()
+     */
+    public StoreLocation getValueDataItem() {
+        DataItem result = new DataItem();
+        result.setOffset(valueOffset);
+        result.setFile(valueFile);
+        result.setSize(valueSize);
+        return result;
+    }
+
+    public void setValueData(StoreLocation item) {
+        valueOffset = item.getOffset();
+        valueFile = item.getFile();
+        valueSize = item.getSize();
+    }
+
+    public void setKeyData(StoreLocation item) {
+        keyOffset = item.getOffset();
+        keyFile = item.getFile();
+        keySize = item.getSize();
+    }
+
+    /**
+     * @param dataOut
+     * @throws IOException
+     */
+    public void write(DataOutput dataOut) throws IOException {
+        dataOut.writeShort(MAGIC);
+        dataOut.writeBoolean(active);
+        dataOut.writeLong(previousItem);
+        dataOut.writeLong(nextItem);
+        dataOut.writeInt(keyFile);
+        dataOut.writeLong(keyOffset);
+        dataOut.writeInt(keySize);
+        dataOut.writeInt(valueFile);
+        dataOut.writeLong(valueOffset);
+        dataOut.writeInt(valueSize);
+    }
+
+    void updateIndexes(DataOutput dataOut) throws IOException {
+        dataOut.writeShort(MAGIC);
+        dataOut.writeBoolean(active);
+        dataOut.writeLong(previousItem);
+        dataOut.writeLong(nextItem);
+    }
+
+    /**
+     * @param dataIn
+     * @throws IOException
+     */
+    public void read(DataInput dataIn) throws IOException {
+        if (dataIn.readShort() != MAGIC) {
+            throw new BadMagicException();
+        }
+        active = dataIn.readBoolean();
+        previousItem = dataIn.readLong();
+        nextItem = dataIn.readLong();
+        keyFile = dataIn.readInt();
+        keyOffset = dataIn.readLong();
+        keySize = dataIn.readInt();
+        valueFile = dataIn.readInt();
+        valueOffset = dataIn.readLong();
+        valueSize = dataIn.readInt();
+    }
+
+    void readIndexes(DataInput dataIn) throws IOException {
+        if (dataIn.readShort() != MAGIC) {
+            throw new BadMagicException();
+        }
+        active = dataIn.readBoolean();
+        previousItem = dataIn.readLong();
+        nextItem = dataIn.readLong();
+    }
+
+    /**
+     * @param newPrevEntry
+     */
+    public void setPreviousItem(long newPrevEntry) {
+        previousItem = newPrevEntry;
+    }
+
+    /**
+     * @return prev item
+     */
+    long getPreviousItem() {
+        return previousItem;
+    }
+
+    /**
+     * @param newNextEntry
+     */
+    public void setNextItem(long newNextEntry) {
+        nextItem = newNextEntry;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getNextItem()
+     */
+    public long getNextItem() {
+        return nextItem;
+    }
+
+    /**
+     * @param newObjectOffset
+     */
+    void setKeyOffset(long newObjectOffset) {
+        keyOffset = newObjectOffset;
+    }
+
+    /**
+     * @return key offset
+     */
+    long getKeyOffset() {
+        return keyOffset;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getKeyFile()
+     */
+    public int getKeyFile() {
+        return keyFile;
+    }
+
+    /**
+     * @param keyFile The keyFile to set.
+     */
+    void setKeyFile(int keyFile) {
+        this.keyFile = keyFile;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getValueFile()
+     */
+    public int getValueFile() {
+        return valueFile;
+    }
+
+    /**
+     * @param valueFile The valueFile to set.
+     */
+    void setValueFile(int valueFile) {
+        this.valueFile = valueFile;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getValueOffset()
+     */
+    public long getValueOffset() {
+        return valueOffset;
+    }
+
+    /**
+     * @param valueOffset The valueOffset to set.
+     */
+    public void setValueOffset(long valueOffset) {
+        this.valueOffset = valueOffset;
+    }
+
+    /**
+     * @return Returns the active.
+     */
+    boolean isActive() {
+        return active;
+    }
+
+    /**
+     * @param active The active to set.
+     */
+    void setActive(boolean active) {
+        this.active = active;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getOffset()
+     */
+    public long getOffset() {
+        return offset;
+    }
+
+    /**
+     * @param offset The offset to set.
+     */
+    public void setOffset(long offset) {
+        this.offset = offset;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getKeySize()
+     */
+    public int getKeySize() {
+        return keySize;
+    }
+
+    public void setKeySize(int keySize) {
+        this.keySize = keySize;
+    }
+
+    /**
+     * @return
+     * @see org.apache.kahadb.StoreEntry#getValueSize()
+     */
+    public int getValueSize() {
+        return valueSize;
+    }
+
+    public void setValueSize(int valueSize) {
+        this.valueSize = valueSize;
+    }
+    
+    void copyIndex(IndexItem other) {
+        this.offset=other.offset;
+        this.active=other.active;
+        this.previousItem=other.previousItem;
+        this.nextItem=other.nextItem;
+    }
+
+    /**
+     * @return print of 'this'
+     */
+    public String toString() {
+        String result = "offset=" + offset + ", key=(" + keyFile + ", " + keyOffset + ", " + keySize + ")" + ", value=(" + valueFile + ", " + valueOffset + ", " + valueSize + ")"
+                        + ", previousItem=" + previousItem + ", nextItem=" + nextItem;
+        return result;
+    }
+
+    public boolean equals(Object obj) {
+        boolean result = obj == this;
+        if (!result && obj != null && obj instanceof IndexItem) {
+            IndexItem other = (IndexItem)obj;
+            result = other.offset == this.offset;
+        }
+        return result;
+    }
+
+    public int hashCode() {
+        return (int)offset;
+    }
+}

Propchange: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexItem.java
------------------------------------------------------------------------------
    svn:executable = *

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexLinkedList.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexLinkedList.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexLinkedList.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexLinkedList.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,199 @@
+/**
+ * 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.impl.index;
+
+import org.apache.kahadb.StoreEntry;
+
+/**
+ * Inteface to LinkedList of Indexes
+ * 
+ * @version $Revision: 598330 $
+ */
+public interface IndexLinkedList {
+    
+    /**
+     * Set the new Root
+     * @param newRoot
+     */
+    void setRoot(IndexItem newRoot);
+
+    /**
+     * @return the root used by the List
+     */
+    IndexItem getRoot();
+
+    /**
+     * Returns the first element in this list.
+     * 
+     * @return the first element in this list.
+     */
+    IndexItem getFirst();
+
+    /**
+     * Returns the last element in this list.
+     * 
+     * @return the last element in this list.
+     */
+    IndexItem getLast();
+
+    /**
+     * Removes and returns the first element from this list.
+     * 
+     * @return the first element from this list.
+     */
+    StoreEntry removeFirst();
+
+    /**
+     * Removes and returns the last element from this list.
+     * 
+     * @return the last element from this list.
+     */
+    Object removeLast();
+
+    /**
+     * Inserts the given element at the beginning of this list.
+     * 
+     * @param item
+     */
+    void addFirst(IndexItem item);
+
+    /**
+     * Appends the given element to the end of this list. (Identical in function
+     * to the <tt>add</tt> method; included only for consistency.)
+     * 
+     * @param item
+     */
+    void addLast(IndexItem item);
+
+    /**
+     * Returns the number of elements in this list.
+     * 
+     * @return the number of elements in this list.
+     */
+    int size();
+
+    /**
+     * is the list empty?
+     * 
+     * @return true if there are no elements in the list
+     */
+    boolean isEmpty();
+
+    /**
+     * Appends the specified element to the end of this list.
+     * 
+     * @param item
+     * 
+     * @return <tt>true</tt> (as per the general contract of
+     *         <tt>Collection.add</tt>).
+     */
+    boolean add(IndexItem item);
+
+    /**
+     * Removes all of the elements from this list.
+     */
+    void clear();
+
+    // Positional Access Operations
+    /**
+     * Returns the element at the specified position in this list.
+     * 
+     * @param index index of element to return.
+     * @return the element at the specified position in this list.
+     * 
+     * @throws IndexOutOfBoundsException if the specified index is is out of
+     *                 range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     */
+    IndexItem get(int index);
+
+    /**
+     * Inserts the specified element at the specified position in this list.
+     * Shifts the element currently at that position (if any) and any subsequent
+     * elements to the right (adds one to their indices).
+     * 
+     * @param index index at which the specified element is to be inserted.
+     * @param element element to be inserted.
+     * 
+     * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
+     */
+    void add(int index, IndexItem element);
+
+    /**
+     * Removes the element at the specified position in this list. Shifts any
+     * subsequent elements to the left (subtracts one from their indices).
+     * Returns the element that was removed from the list.
+     * 
+     * @param index the index of the element to removed.
+     * @return the element previously at the specified position.
+     * 
+     * @throws IndexOutOfBoundsException if the specified index is out of range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     */
+    Object remove(int index);
+
+    // Search Operations
+    /**
+     * Returns the index in this list of the first occurrence of the specified
+     * element, or -1 if the List does not contain this element. More formally,
+     * returns the lowest index i such that
+     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if there
+     * is no such index.
+     * 
+     * @param o element to search for.
+     * @return the index in this list of the first occurrence of the specified
+     *         element, or -1 if the list does not contain this element.
+     */
+    int indexOf(StoreEntry o);
+
+    /**
+     * Retrieve the next entry after this entry
+     * 
+     * @param entry
+     * @return next entry
+     */
+    IndexItem getNextEntry(IndexItem entry);
+
+    /**
+     * Retrive the prev entry after this entry
+     * 
+     * @param entry
+     * @return prev entry
+     */
+    IndexItem getPrevEntry(IndexItem entry);
+
+    /**
+     * remove an entry
+     * 
+     * @param e
+     */
+    void remove(IndexItem e);
+
+    /**
+     * Ensure we have the up to date entry
+     * 
+     * @param entry
+     * @return the entry
+     */
+    StoreEntry getEntry(StoreEntry entry);
+
+    /**
+     * Update the indexes of a StoreEntry
+     * 
+     * @param current
+     * @return update StoreEntry
+     */
+    StoreEntry refreshEntry(StoreEntry current);
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexManager.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexManager.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexManager.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/IndexManager.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,225 @@
+/**
+ * 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.impl.index;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.nio.channels.FileLock;
+import java.util.concurrent.atomic.AtomicLong;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.kahadb.impl.DataManager;
+import org.apache.kahadb.util.IOHelper;
+
+/**
+ * Optimized Store reader
+ * 
+ * @version $Revision: 1.1.1.1 $
+ */
+public final class IndexManager {
+
+    public static final String NAME_PREFIX = "index-";
+    private static final Log LOG = LogFactory.getLog(IndexManager.class);
+    private final String name;
+    private File directory;
+    private File file;
+    private RandomAccessFile indexFile;
+    private StoreIndexReader reader;
+    private StoreIndexWriter writer;
+    private DataManager redoLog;
+    private String mode;
+    private long length;
+    private IndexItem firstFree;
+    private IndexItem lastFree;
+    private boolean dirty;
+    private final AtomicLong storeSize;
+    private int freeSize = 0;
+
+    public IndexManager(File directory, String name, String mode, DataManager redoLog, AtomicLong storeSize) throws IOException {
+        this.directory = directory;
+        this.name = name;
+        this.mode = mode;
+        this.redoLog = redoLog;
+        this.storeSize=storeSize;
+        initialize();
+    }
+
+    public synchronized boolean isEmpty() {
+        return lastFree == null && length == 0;
+    }
+
+    public synchronized IndexItem getIndex(long offset) throws IOException {
+        IndexItem result = null;
+        if (offset >= 0) {
+            result = reader.readItem(offset);
+        }
+        return result;
+    }
+
+    public synchronized IndexItem refreshIndex(IndexItem item) throws IOException {
+        reader.updateIndexes(item);
+        return item;
+    }
+
+    public synchronized void freeIndex(IndexItem item) throws IOException {
+        item.reset();
+        item.setActive(false);
+        if (lastFree == null) {
+            firstFree = item;
+            lastFree = item;
+        } else {
+            lastFree.setNextItem(item.getOffset());
+            if (lastFree.equals(firstFree)) {
+                firstFree=new IndexItem();
+                firstFree.copyIndex(lastFree);
+                writer.updateIndexes(firstFree);
+            }
+            writer.updateIndexes(lastFree);
+            lastFree=item;
+        }
+        writer.updateIndexes(item);
+        freeSize++;
+        dirty = true;
+    }
+
+    public synchronized void storeIndex(IndexItem index) throws IOException {
+        writer.storeItem(index);
+        dirty = true;
+    }
+
+    public synchronized void updateIndexes(IndexItem index) throws IOException {
+        try {
+            writer.updateIndexes(index);
+        } catch (Throwable e) {
+            LOG.error(name + " error updating indexes ", e);
+        }
+        dirty = true;
+    }
+
+    public synchronized void redo(final RedoStoreIndexItem redo) throws IOException {
+        writer.redoStoreItem(redo);
+        dirty = true;
+    }
+
+    public synchronized IndexItem createNewIndex() throws IOException {
+        IndexItem result = getNextFreeIndex();
+        if (result == null) {
+            // allocate one
+            result = new IndexItem();
+            result.setOffset(length);
+            length += IndexItem.INDEX_SIZE;
+            storeSize.addAndGet(IndexItem.INDEX_SIZE);
+        }
+        return result;
+    }
+
+    public synchronized void close() throws IOException {
+        if (indexFile != null) {
+            indexFile.close();
+            indexFile = null;
+        }
+    }
+
+    public synchronized void force() throws IOException {
+        if (indexFile != null && dirty) {
+            indexFile.getFD().sync();
+            dirty = false;
+        }
+    }
+
+    public synchronized boolean delete() throws IOException {
+        firstFree = null;
+        lastFree = null;
+        if (indexFile != null) {
+            indexFile.close();
+            indexFile = null;
+        }
+        return file.delete();
+    }
+
+    private synchronized IndexItem getNextFreeIndex() throws IOException {
+        IndexItem result = null;
+        if (firstFree != null) {
+            if (firstFree.equals(lastFree)) {
+                result = firstFree;
+                firstFree = null;
+                lastFree = null;
+            } else {
+                result = firstFree;
+                firstFree = getIndex(firstFree.getNextItem());
+                if (firstFree == null) {
+                    lastFree = null;
+                }
+            }
+            result.reset();
+            writer.updateIndexes(result);
+            freeSize--;
+        }
+        return result;
+    }
+
+    synchronized long getLength() {
+        return length;
+    }
+    
+    public final long size() {
+        return length;
+    }
+
+    public synchronized void setLength(long value) {
+        this.length = value;
+        storeSize.addAndGet(length);
+    }
+    
+    public synchronized FileLock getLock() throws IOException {
+        return indexFile.getChannel().tryLock();
+    }
+
+
+    public String toString() {
+        return "IndexManager:(" + NAME_PREFIX + name + ")";
+    }
+
+    protected void initialize() throws IOException {
+        file = new File(directory, NAME_PREFIX + IOHelper.toFileSystemSafeName(name) );
+        IOHelper.mkdirs(file.getParentFile());        
+        indexFile = new RandomAccessFile(file, mode);
+        reader = new StoreIndexReader(indexFile);
+        writer = new StoreIndexWriter(indexFile, name, redoLog);
+        long offset = 0;
+        while ((offset + IndexItem.INDEX_SIZE) <= indexFile.length()) {
+            IndexItem index = reader.readItem(offset);
+            if (!index.isActive()) {
+                index.reset();
+                if (lastFree != null) {
+                    lastFree.setNextItem(index.getOffset());
+                    updateIndexes(lastFree);
+                    lastFree = index;
+                } else {
+                    lastFree = index;
+                    firstFree = index;
+                }
+               freeSize++;
+            }
+            offset += IndexItem.INDEX_SIZE;
+        }
+        length = offset;
+        storeSize.addAndGet(length);
+    }
+}

Added: 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=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/RedoStoreIndexItem.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,102 @@
+/**
+ * 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.impl.index;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+
+import org.apache.kahadb.Marshaller;
+
+public class RedoStoreIndexItem implements Externalizable {
+
+    public static final Marshaller MARSHALLER = new Marshaller() {
+        public Object readPayload(DataInput in) throws IOException {
+            RedoStoreIndexItem item = new RedoStoreIndexItem();
+            item.readExternal(in);
+            return item;
+        }
+
+        public void writePayload(Object object, DataOutput out) throws IOException {
+            RedoStoreIndexItem item = (RedoStoreIndexItem)object;
+            item.writeExternal(out);
+        }
+    };
+
+    private static final long serialVersionUID = -4865508871719676655L;
+    private String indexName;
+    private IndexItem indexItem;
+    private long offset;
+
+    public RedoStoreIndexItem() {
+    }
+
+    public RedoStoreIndexItem(String indexName, long offset, IndexItem item) {
+        this.indexName = indexName;
+        this.offset = offset;
+        this.indexItem = item;
+    }
+
+    public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
+        readExternal((DataInput)in);
+    }
+
+    public void readExternal(DataInput in) throws IOException {
+        // indexName = in.readUTF();
+        offset = in.readLong();
+        indexItem = new IndexItem();
+        indexItem.read(in);
+    }
+
+    public void writeExternal(ObjectOutput out) throws IOException {
+        writeExternal((DataOutput)out);
+    }
+
+    public void writeExternal(DataOutput out) throws IOException {
+        // out.writeUTF(indexName);
+        out.writeLong(offset);
+        indexItem.write(out);
+    }
+
+    public String getIndexName() {
+        return indexName;
+    }
+
+    public void setIndexName(String indexName) {
+        this.indexName = indexName;
+    }
+
+    public IndexItem getIndexItem() {
+        return indexItem;
+    }
+
+    public void setIndexItem(IndexItem item) {
+        this.indexItem = item;
+    }
+
+    public long getOffset() {
+        return offset;
+    }
+
+    public void setOffset(long offset) {
+        this.offset = offset;
+    }
+
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexReader.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexReader.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexReader.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexReader.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,62 @@
+/**
+ * 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.impl.index;
+
+import java.io.IOException;
+import java.io.RandomAccessFile;
+
+import org.apache.kahadb.util.DataByteArrayInputStream;
+
+/**
+ * Optimized Store reader
+ * 
+ * @version $Revision: 1.1.1.1 $
+ */
+class StoreIndexReader {
+    protected RandomAccessFile file;
+    protected DataByteArrayInputStream dataIn;
+    protected byte[] buffer = new byte[IndexItem.INDEX_SIZE];
+
+    /**
+     * Construct a Store reader
+     * 
+     * @param file
+     */
+    StoreIndexReader(RandomAccessFile file) {
+        this.file = file;
+        this.dataIn = new DataByteArrayInputStream();
+    }
+
+    protected IndexItem readItem(long offset) throws IOException {
+        file.seek(offset);
+        file.readFully(buffer);
+        dataIn.restart(buffer);
+        IndexItem result = new IndexItem();
+        result.setOffset(offset);
+        result.read(dataIn);
+        return result;
+    }
+
+    void updateIndexes(IndexItem indexItem) throws IOException {
+        if (indexItem != null) {
+            file.seek(indexItem.getOffset());
+            file.readFully(buffer, 0, IndexItem.INDEXES_ONLY_SIZE);
+            dataIn.restart(buffer);
+            indexItem.readIndexes(dataIn);
+        }
+    }
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexWriter.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexWriter.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexWriter.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/StoreIndexWriter.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,84 @@
+/**
+ * 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.impl.index;
+
+import java.io.IOException;
+import java.io.RandomAccessFile;
+
+import org.apache.kahadb.impl.DataManager;
+import org.apache.kahadb.util.DataByteArrayOutputStream;
+
+/**
+ * Optimized Store writer
+ * 
+ * @version $Revision: 1.1.1.1 $
+ */
+class StoreIndexWriter {
+
+    protected final DataByteArrayOutputStream dataOut = new DataByteArrayOutputStream();
+    protected final RandomAccessFile file;
+    protected final String name;
+    protected final DataManager redoLog;
+
+    /**
+     * Construct a Store index writer
+     * 
+     * @param file
+     */
+    StoreIndexWriter(RandomAccessFile file) {
+        this(file, null, null);
+    }
+
+    public StoreIndexWriter(RandomAccessFile file, String indexName, DataManager redoLog) {
+        this.file = file;
+        this.name = indexName;
+        this.redoLog = redoLog;
+    }
+
+    void storeItem(IndexItem indexItem) throws IOException {
+
+        if (redoLog != null) {
+            RedoStoreIndexItem redo = new RedoStoreIndexItem(name, indexItem.getOffset(), indexItem);
+            redoLog.storeRedoItem(redo);
+        }
+
+        dataOut.reset();
+        indexItem.write(dataOut);
+        file.seek(indexItem.getOffset());
+        file.write(dataOut.getData(), 0, IndexItem.INDEX_SIZE);
+    }
+
+    void updateIndexes(IndexItem indexItem) throws IOException {
+        if (redoLog != null) {
+            RedoStoreIndexItem redo = new RedoStoreIndexItem(name, indexItem.getOffset(), indexItem);
+            redoLog.storeRedoItem(redo);
+        }
+
+        dataOut.reset();
+        indexItem.updateIndexes(dataOut);
+        file.seek(indexItem.getOffset());
+        file.write(dataOut.getData(), 0, IndexItem.INDEXES_ONLY_SIZE);
+    }
+
+    public void redoStoreItem(RedoStoreIndexItem redo) throws IOException {
+        dataOut.reset();
+        redo.getIndexItem().write(dataOut);
+        file.seek(redo.getOffset());
+        file.write(dataOut.getData(), 0, IndexItem.INDEX_SIZE);
+    }
+
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndex.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndex.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndex.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndex.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,131 @@
+/**
+ * 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.impl.index;
+
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.kahadb.IndexMBean;
+import org.apache.kahadb.Marshaller;
+import org.apache.kahadb.StoreEntry;
+
+/**
+ * Index implementation using a HashMap
+ * 
+ * @version $Revision: 1.2 $
+ */
+public class VMIndex implements Index, IndexMBean {
+    private static final Log LOG = LogFactory.getLog(VMIndex.class);
+    private IndexManager indexManager;
+    private Map<Object, StoreEntry> map = new HashMap<Object, StoreEntry>();
+
+    public VMIndex(IndexManager manager) {
+        this.indexManager = manager;
+    }
+
+    /**
+     * 
+     * @see org.apache.kahadb.impl.index.Index#clear()
+     */
+    public void clear() {
+        map.clear();
+    }
+
+    /**
+     * @param key
+     * @return true if the index contains the key
+     * @see org.apache.kahadb.impl.index.Index#containsKey(java.lang.Object)
+     */
+    public boolean containsKey(Object key) {
+        return map.containsKey(key);
+    }
+
+    /**
+     * @param key
+     * @return store entry
+     * @see org.apache.kahadb.impl.index.Index#removeKey(java.lang.Object)
+     */
+    public StoreEntry remove(Object key) {
+        StoreEntry result = map.remove(key);
+        if (result != null) {
+            try {
+                result = indexManager.refreshIndex((IndexItem)result);
+            } catch (IOException e) {
+                LOG.error("Failed to refresh entry", e);
+                throw new RuntimeException("Failed to refresh entry");
+            }
+        }
+        return result;
+    }
+
+    /**
+     * @param key
+     * @param entry
+     * @see org.apache.kahadb.impl.index.Index#store(java.lang.Object,
+     *      org.apache.kahadb.impl.index.IndexItem)
+     */
+    public void store(Object key, StoreEntry entry) {
+        map.put(key, entry);
+    }
+
+    /**
+     * @param key
+     * @return the entry
+     */
+    public StoreEntry get(Object key) {
+        StoreEntry result = map.get(key);
+        if (result != null) {
+            try {
+                result = indexManager.refreshIndex((IndexItem)result);
+            } catch (IOException e) {
+                LOG.error("Failed to refresh entry", e);
+                throw new RuntimeException("Failed to refresh entry");
+            }
+        }
+        return result;
+    }
+
+    /**
+     * @return true if the index is transient
+     */
+    public boolean isTransient() {
+        return true;
+    }
+
+    /**
+     * load indexes
+     */
+    public void load() {
+    }
+
+    /**
+     * unload indexes
+     */
+    public void unload() {
+        map.clear();
+    }
+
+    public void setKeyMarshaller(Marshaller marshaller) {
+    }
+    
+    public int getSize() {
+        return map.size();
+    }
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndexLinkedList.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndexLinkedList.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndexLinkedList.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndexLinkedList.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,293 @@
+/**
+ * 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.impl.index;
+
+import org.apache.kahadb.StoreEntry;
+
+/**
+ * A linked list used by IndexItems
+ * 
+ * @version $Revision: 1.2 $
+ */
+public final class VMIndexLinkedList implements Cloneable, IndexLinkedList {
+    private transient IndexItem root;
+    private transient int size;
+
+    /**
+     * Constructs an empty list.
+     * @param header 
+     */
+    public VMIndexLinkedList(IndexItem header) {
+        this.root = header;
+        this.root.next=this.root.prev=this.root;
+    }
+    
+    public  void setRoot(IndexItem newRoot) {
+        this.root=newRoot;
+    }
+
+    public synchronized IndexItem getRoot() {
+        return root;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#getFirst()
+     */
+    public synchronized IndexItem getFirst() {
+        if (size == 0) {
+            return null;
+        }
+        return root.next;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#getLast()
+     */
+    public synchronized IndexItem getLast() {
+        if (size == 0) {
+            return null;
+        }
+        return root.prev;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#removeFirst()
+     */
+    public synchronized StoreEntry removeFirst() {
+        if (size == 0) {
+            return null;
+        }
+        StoreEntry result = root.next;
+        remove(root.next);
+        return result;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#removeLast()
+     */
+    public synchronized Object removeLast() {
+        if (size == 0) {
+            return null;
+        }
+        StoreEntry result = root.prev;
+        remove(root.prev);
+        return result;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#addFirst(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized void addFirst(IndexItem item) {
+        addBefore(item, root.next);
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#addLast(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized void addLast(IndexItem item) {
+        addBefore(item, root);
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#size()
+     */
+    public synchronized int size() {
+        return size;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#isEmpty()
+     */
+    public synchronized boolean isEmpty() {
+        return size == 0;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#add(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized boolean add(IndexItem item) {
+        addBefore(item, root);
+        return true;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#clear()
+     */
+    public synchronized void clear() {
+        root.next=root.prev=root;
+        size = 0;
+    }
+
+    // Positional Access Operations
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#get(int)
+     */
+    public synchronized IndexItem get(int index) {
+        return entry(index);
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#add(int,
+     *      org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized void add(int index, IndexItem element) {
+        addBefore(element, index == size ? root : entry(index));
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#remove(int)
+     */
+    public synchronized Object remove(int index) {
+        IndexItem e = entry(index);
+        remove(e);
+        return e;
+    }
+
+    /**
+     * Return the indexed entry.
+     */
+    private IndexItem entry(int index) {
+        if (index < 0 || index >= size) {
+            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
+        }
+        IndexItem e = root;
+        if (index < size / 2) {
+            for (int i = 0; i <= index; i++) {
+                e = e.next;
+            }
+        } else {
+            for (int i = size; i > index; i--) {
+                e = e.prev;
+            }
+        }
+        return e;
+    }
+
+    // Search Operations
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#indexOf(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized int indexOf(StoreEntry o) {
+        int index = 0;
+        for (IndexItem e = root.next; e != root; e = e.next) {
+            if (o == e) {
+                return index;
+            }
+            index++;
+        }
+        return -1;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#getNextEntry(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized IndexItem getNextEntry(IndexItem entry) {
+        return entry.next != root ? entry.next : null;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#getPrevEntry(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized IndexItem getPrevEntry(IndexItem entry) {
+        return entry.prev != root ? entry.prev : null;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#addBefore(org.apache.activemq.kaha.impl.IndexItem,
+     *      org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized void addBefore(IndexItem insert, IndexItem e) {
+        insert.next = e;
+        insert.prev = e.prev;
+        insert.prev.next = insert;
+        insert.next.prev = insert;
+        size++;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see org.apache.activemq.kaha.impl.IndexLinkedList#remove(org.apache.activemq.kaha.impl.IndexItem)
+     */
+    public synchronized void remove(IndexItem e) {
+        if (e == root || e.equals(root)) {
+            return;
+        }
+        
+        e.prev.next = e.next;
+        e.next.prev = e.prev;
+        size--;
+    }
+
+    /**
+     * @return clone
+     */
+    public synchronized Object clone() {
+        IndexLinkedList clone = new VMIndexLinkedList(this.root);
+        for (IndexItem e = root.next; e != root; e = e.next) {
+            clone.add(e);
+        }
+        return clone;
+    }
+
+    public synchronized StoreEntry getEntry(StoreEntry current) {
+        return current;
+    }
+
+    /**
+     * Update the indexes of a StoreEntry
+     * 
+     * @param current
+     */
+    public synchronized StoreEntry refreshEntry(StoreEntry current) {
+        return current;
+    }
+}

Propchange: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/VMIndexLinkedList.java
------------------------------------------------------------------------------
    svn:executable = *

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashBin.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashBin.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashBin.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashBin.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,341 @@
+/**
+ * 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.impl.index.hash;
+
+import java.io.IOException;
+
+/**
+ * Bin in a HashIndex
+ * 
+ * @version $Revision: 1.1.1.1 $
+ */
+class HashBin {
+    private HashIndex hashIndex;
+    private int id;
+    private int maximumEntries;
+    private int size;
+    private int numberOfPages =0;
+    private HashPageInfo root = null;
+    private HashPageInfo tail = null;
+
+    /**
+     * Constructor
+     * 
+     * @param hashIndex
+     * @param id
+     * @param maximumEntries
+     */
+    HashBin(HashIndex hashIndex, int id, int maximumEntries) {
+        this.hashIndex = hashIndex;
+        this.id = id;
+        this.maximumEntries = maximumEntries;
+    }
+
+    public String toString() {
+        return "HashBin[" + getId() + "]";
+    }
+
+    public boolean equals(Object o) {
+        boolean result = false;
+        if (o instanceof HashBin) {
+            HashBin other = (HashBin)o;
+            result = other.id == id;
+        }
+        return result;
+    }
+
+    public int hashCode() {
+        return (int)getId();
+    }
+
+     int  getId() {
+        return id;
+    }
+
+     void setId(int id) {
+        this.id = id;
+    }
+
+     boolean isEmpty() {
+        return true;
+    }
+
+     int getMaximumEntries() {
+        return this.maximumEntries;
+    }
+
+     void setMaximumEntries(int maximumEntries) {
+        this.maximumEntries = maximumEntries;
+    }
+
+     int size() {
+        return size;
+    }
+
+     HashPageInfo addHashPageInfo(long id, int size) throws IOException {
+        HashPageInfo info = new HashPageInfo(hashIndex);
+        info.setId(id);
+        info.setSize(size);
+        if (root == null) {
+            root=info;
+        }else {
+            tail.linkAfter(info);
+        }
+        tail=info;
+        this.numberOfPages++;
+        this.size += size;
+        return info;
+    }
+
+     public HashEntry find(HashEntry key) throws IOException {
+        HashEntry result = null;
+        try {
+            int low = 0;
+            int high = size()-1;
+            while (low <= high) {
+                int mid = (low + high) >> 1;
+                HashEntry te = getHashEntry(mid);
+                int cmp = te.compareTo(key);
+                if (cmp == 0) {
+                    result = te;
+                    break;
+                } else if (cmp < 0) {
+                    low = mid + 1;
+                } else {
+                    high = mid - 1;
+                }
+            }
+        } finally {
+            end();
+        }
+        return result;
+    }
+
+     boolean put(HashEntry newEntry) throws IOException {
+        boolean replace = false;
+        try {
+            int low = 0;
+            int high = size()-1;
+            while (low <= high) {
+                int mid = (low + high) >> 1;
+                HashEntry midVal = getHashEntry(mid);
+                int cmp = midVal.compareTo(newEntry);
+                if (cmp < 0) {
+                    low = mid + 1;
+                } else if (cmp > 0) {
+                    high = mid - 1;
+                } else {
+                    replace = true;
+                    midVal.setIndexOffset(newEntry.getIndexOffset());
+                    break;
+                }
+            }
+            if (!replace) {
+                addHashEntry(low, newEntry);
+                size++;
+            }
+        } finally {
+            end();
+        }
+        return replace;
+    }
+
+     HashEntry remove(HashEntry entry) throws IOException {
+        HashEntry result = null;
+        try {
+            int low = 0;
+            int high = size() - 1;
+            while (low <= high) {
+                int mid = (low + high) >> 1;
+                HashEntry te = getHashEntry(mid);
+                int cmp = te.compareTo(entry);
+                if (cmp == 0) {
+                    result = te;
+                    removeHashEntry(mid);
+                    size--;
+                    break;
+                } else if (cmp < 0) {
+                    low = mid + 1;
+                } else {
+                    high = mid - 1;
+                }
+            }
+        } finally {
+            end();
+        }
+        return result;
+    }
+
+    private void addHashEntry(int index, HashEntry entry) throws IOException {
+        HashPageInfo pageToUse = null;
+        int offset = 0;
+        if (index >= getMaximumBinSize()) {
+            while(index >= getMaximumBinSize()) {
+                HashPage hp = hashIndex.createPage(id);
+                pageToUse = addHashPageInfo(hp.getId(), 0);
+                pageToUse.setPage(hp);
+            }
+            offset = 0;
+        } else {
+            int count = 0;
+            int countSoFar=0;
+            int pageNo = 0;
+            HashPageInfo page = root;
+            while (page != null) {
+                count += page.size();
+                pageToUse=page;
+                if (index < count ) {
+                    offset = index - countSoFar;
+                    break;
+                }
+                if (index == count && page.size()+1 <= maximumEntries) {
+                    offset = page.size();
+                    break;
+                }
+                countSoFar += page.size();
+                pageNo++;
+                page = (HashPageInfo) page.getNext();
+            }
+            while(pageNo >= this.numberOfPages) {
+                HashPage hp  = hashIndex.createPage(id);
+                pageToUse = addHashPageInfo(hp.getId(), 0);               
+            }            
+        }
+        pageToUse.begin();  
+        pageToUse.addHashEntry(offset, entry);
+        doOverFlow(index);
+    }
+
+    private HashEntry removeHashEntry(int index) throws IOException {
+        HashPageInfo page = getRetrievePage(index);
+        int offset = getRetrieveOffset(index);
+        HashEntry result = page.removeHashEntry(offset);
+        
+        if (page.isEmpty()) {
+            if (root.equals(page)) {
+                root=(HashPageInfo) root.getNext();
+            }
+            if (tail.equals(page)) {
+                tail=(HashPageInfo) page.getPrevious();
+            }
+            page.unlink();
+            this.numberOfPages--;
+            hashIndex.releasePage(page.getPage());
+        }
+        doUnderFlow(index);
+        return result;
+    }
+
+    private HashEntry getHashEntry(int index) throws IOException {
+        HashPageInfo page = getRetrievePage(index);
+        page.begin();
+        int offset = getRetrieveOffset(index);
+        HashEntry result = page.getHashEntry(offset);
+        return result;
+    }
+    
+
+    private int getMaximumBinSize() {
+        return maximumEntries * this.numberOfPages;
+    }
+
+    private HashPageInfo getRetrievePage(int index) throws IOException {
+        HashPageInfo result = null;
+        int count = 0;
+        HashPageInfo page = root;
+        while (page != null) {
+            count += page.size();
+            result = page;
+            if (index < count) {
+                break;
+            }
+            page = (HashPageInfo) page.getNext();
+        }
+        
+        result.begin();
+        return result;
+    }
+
+    private int getRetrieveOffset(int index) throws IOException {
+        int result = 0;
+        int count = 0;
+        HashPageInfo page = root;
+        while (page != null) {
+            if ((index + 1) <= (count + page.size())) {
+                result = index - count;
+                break;
+            }
+            count += page.size();
+            page = (HashPageInfo) page.getNext();
+        }
+        return result;
+    }
+
+    private void doOverFlow(int index) throws IOException {
+        HashPageInfo info = getRetrievePage(index);
+        if (info.size() > maximumEntries) {
+            // overflowed
+            info.begin();
+            HashEntry entry = info.removeHashEntry(info.size() - 1);
+            doOverFlow(getNextPage(info), entry);
+        }
+    }
+
+    private void doOverFlow(HashPageInfo next, HashEntry entry) throws IOException {
+        HashPageInfo info = null;
+        if (next == null) {
+            HashPage page = hashIndex.createPage(id);
+            info = addHashPageInfo(page.getId(), 0);
+            info.setPage(page);
+        } else {
+            info = next;
+        }
+        info.begin();
+        info.addHashEntry(0, entry);
+        if (info.size() > maximumEntries) {
+            // overflowed
+            HashEntry overflowed = info.removeHashEntry(info.size() - 1);
+            doOverFlow(getNextPage(info), overflowed);
+        }
+    }
+    
+    private HashPageInfo getNextPage(HashPageInfo start) {
+        return (HashPageInfo) start.getNext();
+    }
+
+    private void doUnderFlow(int index) {
+    }
+
+    String dump() throws IOException {
+        String str = "[" + this.numberOfPages+"]";
+        HashPageInfo page = root;
+        while (page != null) {
+            page.begin();
+            str +=page.dump();
+            page.end();
+            page = (HashPageInfo) page.getNext();
+        }
+        return str;
+    }
+    private void end() throws IOException {
+        HashPageInfo page = root;
+        while (page != null) {
+            page.end();
+            page = (HashPageInfo) page.getNext();
+        }
+    }
+}

Added: activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashEntry.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashEntry.java?rev=677944&view=auto
==============================================================================
--- activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashEntry.java (added)
+++ activemq/sandbox/kahadb/src/main/java/org/apache/kahadb/impl/index/hash/HashEntry.java Fri Jul 18 08:49:48 2008
@@ -0,0 +1,101 @@
+/**
+ * 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.impl.index.hash;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+
+import org.apache.kahadb.Marshaller;
+
+/**
+ * Key and index for DiskBased Hash Index
+ * 
+ * @version $Revision: 1.1.1.1 $
+ */
+class HashEntry implements Comparable {
+
+    static final int NOT_SET = -1;
+    private Comparable key;
+    private long indexOffset;
+
+    public int compareTo(Object o) {
+        if (o instanceof HashEntry) {
+            HashEntry other = (HashEntry)o;
+            return key.compareTo(other.key);
+        } else {
+            return key.compareTo(o);
+        }
+    }
+
+    public boolean equals(Object o) {
+        return compareTo(o) == 0;
+    }
+
+    public int hashCode() {
+        return key.hashCode();
+    }
+
+    public String toString() {
+        return "HashEntry(" + key + "," + indexOffset + ")";
+    }
+
+    HashEntry copy() {
+        HashEntry copy = new HashEntry();
+        copy.key = this.key;
+        copy.indexOffset = this.indexOffset;
+        return copy;
+    }
+
+    /**
+     * @return the key
+     */
+    Comparable getKey() {
+        return this.key;
+    }
+
+    /**
+     * @param key the key to set
+     */
+    void setKey(Comparable key) {
+        this.key = key;
+    }
+
+    /**
+     * @return the indexOffset
+     */
+    long getIndexOffset() {
+        return this.indexOffset;
+    }
+
+    /**
+     * @param indexOffset the indexOffset to set
+     */
+    void setIndexOffset(long indexOffset) {
+        this.indexOffset = indexOffset;
+    }
+
+    void write(Marshaller keyMarshaller, DataOutput dataOut) throws IOException {
+        dataOut.writeLong(indexOffset);
+        keyMarshaller.writePayload(key, dataOut);
+    }
+
+    void read(Marshaller keyMarshaller, DataInput dataIn) throws IOException {
+        indexOffset = dataIn.readLong();
+        key = (Comparable)keyMarshaller.readPayload(dataIn);
+    }
+}