mnemonic-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ga...@apache.org
Subject incubator-mnemonic git commit: MNEMONIC-255: Add Insert and Search functionality for balanced BST
Date Tue, 02 May 2017 22:29:52 GMT
Repository: incubator-mnemonic
Updated Branches:
  refs/heads/master fa04538db -> 5c54177dd


MNEMONIC-255: Add Insert and Search functionality for balanced BST


Project: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/commit/5c54177d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/tree/5c54177d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/diff/5c54177d

Branch: refs/heads/master
Commit: 5c54177dd80d224c9c111d8cb1a0bb05d5e63c4b
Parents: fa04538
Author: Johnu George <johnugeo@cisco.com>
Authored: Tue May 2 12:07:04 2017 -0700
Committer: Johnu George <johnugeo@cisco.com>
Committed: Tue May 2 12:07:04 2017 -0700

----------------------------------------------------------------------
 build-tools/test.conf                           |   3 +
 .../mnemonic/collections/DurableTree.java       | 130 ++++++
 .../collections/DurableTreeFactory.java         |  64 +++
 .../mnemonic/collections/DurableTreeImpl.java   | 449 +++++++++++++++++++
 .../apache/mnemonic/collections/TreeNode.java   | 208 +++++++++
 .../mnemonic/collections/DurableTreeNGTest.java | 216 +++++++++
 6 files changed, 1070 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/build-tools/test.conf
----------------------------------------------------------------------
diff --git a/build-tools/test.conf b/build-tools/test.conf
index 3663847..5a0ba5e 100644
--- a/build-tools/test.conf
+++ b/build-tools/test.conf
@@ -39,6 +39,9 @@ mvn -Dtest=DurableHashMapNGTest  test -pl mnemonic-collections -DskipTests=false
 # a testcase for module "mnemonic-collection" that requires 'pmalloc' memory service to pass
 mvn -Dtest=DurableArrayNGTest  test -pl mnemonic-collections -DskipTests=false
 
+# a testcase for module "mnemonic-collection" that requires 'pmalloc' memory service to pass
+mvn -Dtest=DurableTreeNGTest  test -pl mnemonic-collections -DskipTests=false
+
 # a testcase for module "mnemonic-computing-services/mnemonic-utilities-service" that requires
'pmalloc' memory service to pass
 mvn -Dtest=DurableSinglyLinkedListNGPrintTest test -pl mnemonic-computing-services/mnemonic-utilities-service
-DskipTests=false
 

http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
new file mode 100644
index 0000000..18266cf
--- /dev/null
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTree.java
@@ -0,0 +1,130 @@
+/*
+ * 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.mnemonic.collections;
+
+import java.util.Iterator;
+
+import org.apache.mnemonic.Durable;
+import org.apache.mnemonic.EntityFactoryProxy;
+import org.apache.mnemonic.DurableType;
+
+/**
+ * this class defines a non-volatile balanced binary tree(Red-Black tree)
+ *
+ */
+public abstract class DurableTree<E> implements Durable, Iterable<E> {
+  protected transient EntityFactoryProxy[] m_node_efproxies;
+  protected transient DurableType[] m_node_gftypes;
+
+  /**
+   * creation callback for initialization
+   *
+   */
+  @Override
+  public void initializeAfterCreate() {
+    // System.out.println("Initializing After Created");
+  }
+
+  /**
+   * restore callback for initialization
+   *
+   */
+  @Override
+  public void initializeAfterRestore() {
+    // System.out.println("Initializing After Restored");
+  }
+
+  /**
+   * this function will be invoked by its factory to setup generic related info
+   * to avoid expensive operations from reflection
+   *
+   * @param efproxies
+   *          specify a array of factory to proxy the restoring of its generic
+   *          field objects
+   *
+   * @param gftypes
+   *          specify a array of types corresponding to efproxies
+   */
+  @Override
+  public void setupGenericInfo(EntityFactoryProxy[] efproxies, DurableType[] gftypes) {
+    m_node_efproxies = efproxies;
+    m_node_gftypes = gftypes;
+  }
+
+  /**
+   * search item value
+   *
+   * @param item
+   *          the item to be set
+   *
+   * @return true if item is present in the tree else false
+   */
+  public abstract boolean contains(E item);
+
+  /**
+   * find successor item
+   *
+   * @param item
+   *          the item in the traversal
+   *
+   * @return successor item in the inorder traversal
+   */
+  public abstract E successor(E item);
+
+  /**
+   * find predecessor item
+   *
+   * @param item
+   *          the item in the traversal
+   *
+   * @return predecessor item in the inorder traversal
+   */
+  public abstract E predecessor(E item);
+
+  /**
+   * insert a item in the tree
+   *
+   * @param item
+   *          the item to be inserted
+   */
+  public abstract void insert(E item);
+
+  /**
+   * print tree
+   *
+   */
+  public abstract void print();
+
+  /**
+   * check if tree is a valid red black tree
+   *
+   * @return true if tree is a valid RB else false
+   */
+  public abstract boolean isValidTree();
+
+  /**
+   * get an iterator instance of this tree
+   *
+   * @return an iterator of this tree
+   */
+  @Override
+  public Iterator<E> iterator() {
+    return null;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeFactory.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeFactory.java
b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeFactory.java
new file mode 100644
index 0000000..cb479f4
--- /dev/null
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeFactory.java
@@ -0,0 +1,64 @@
+/*
+ * 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.mnemonic.collections;
+
+import org.apache.mnemonic.DurableType;
+import org.apache.mnemonic.EntityFactoryProxy;
+import org.apache.mnemonic.OutOfHybridMemory;
+import org.apache.mnemonic.RestorableAllocator;
+import org.apache.mnemonic.RestoreDurableEntityError;
+
+public class DurableTreeFactory {
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              create(A allocator) throws OutOfHybridMemory {
+    return create(allocator, false);
+  }
+
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              create(A allocator, boolean autoreclaim) throws OutOfHybridMemory {
+    return create(allocator, null, null, autoreclaim);
+  }
+
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              create(A allocator, EntityFactoryProxy[] factoryproxys, DurableType[] gfields,
+                   boolean autoreclaim) throws OutOfHybridMemory {
+    DurableTreeImpl<A, E> entity = new DurableTreeImpl<A, E>();
+    entity.setupGenericInfo(factoryproxys, gfields);
+    entity.createDurableEntity(allocator, factoryproxys, gfields, autoreclaim);
+    return entity;
+  }
+
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              restore(A allocator, long phandler) throws RestoreDurableEntityError {
+    return restore(allocator, phandler, false);
+  }
+
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              restore(A allocator, long phandler, boolean autoreclaim) throws RestoreDurableEntityError
{
+    return restore(allocator, null, null, phandler, autoreclaim);
+  }
+
+  public static <A extends RestorableAllocator<A>, E extends Comparable<E>>
DurableTree<E>
+              restore(A allocator, EntityFactoryProxy[] factoryproxys, DurableType[] gfields,
+                   long phandler, boolean autoreclaim) throws RestoreDurableEntityError {
+    DurableTreeImpl<A, E> entity = new DurableTreeImpl<A, E>();
+    entity.setupGenericInfo(factoryproxys, gfields);
+    entity.restoreDurableEntity(allocator, factoryproxys, gfields, phandler, autoreclaim);
+    return entity;
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
new file mode 100644
index 0000000..f57ef00
--- /dev/null
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/DurableTreeImpl.java
@@ -0,0 +1,449 @@
+/*
+ * 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.mnemonic.collections;
+
+import org.apache.mnemonic.EntityFactoryProxy;
+import org.apache.mnemonic.DurableType;
+import org.apache.mnemonic.MemChunkHolder;
+import org.apache.mnemonic.MemoryDurableEntity;
+import org.apache.mnemonic.OutOfHybridMemory;
+import org.apache.mnemonic.RestorableAllocator;
+import org.apache.mnemonic.RestoreDurableEntityError;
+import org.apache.mnemonic.RetrieveDurableEntityError;
+import org.apache.mnemonic.Utils;
+
+import sun.misc.Unsafe;
+
+@SuppressWarnings("restriction")
+public class DurableTreeImpl<A extends RestorableAllocator<A>, E extends Comparable<E>>
+  extends DurableTree<E> implements MemoryDurableEntity<A> {
+
+  private static long[][] fieldInfo;
+  private Unsafe unsafe;
+  private EntityFactoryProxy[] factoryProxy;
+  private DurableType[] genericType;
+  private volatile boolean autoReclaim;
+  private A allocator;
+  private MemChunkHolder<A> holder;
+  private static final long MAX_OBJECT_SIZE = 8;
+  private TreeNode<E> root;
+  private static final boolean RED = false;
+  private static final boolean BLACK = true;
+
+  /**
+   * adds a specific element to the tree
+   *
+   * @param item
+   *          the item to be added
+   */
+  public void insert(E item) throws OutOfHybridMemory {
+    TreeNode<E> tmp = root;
+    TreeNode<E> node = TreeNodeFactory.create(allocator, factoryProxy, genericType,
autoReclaim);
+    node.setItem(item, false);
+    if (null == root) {
+      root = node;
+      unsafe.putLong(holder.get(), root.getHandler());
+      node.setColor(BLACK);
+    } else {
+      node.setColor(RED);
+      while (true) {
+        int ret = node.compareTo(tmp);
+        if (ret < 0) {
+          if (null == tmp.getLeft()) {
+            tmp.setLeft(node, false);
+            node.setParent(tmp, false);
+            break;
+          } else {
+            tmp = tmp.getLeft();
+          }
+        } else if (ret >= 0) {
+          if (null == tmp.getRight()) {
+            tmp.setRight(node, false);
+            node.setParent(tmp, false);
+            break;
+          } else {
+            tmp = tmp.getRight();
+          }
+        }
+      }
+      fixInsert(node);
+    }
+  }
+
+  protected void fixInsert(TreeNode<E> currentNode) {
+    while (currentNode.getParent() != null && currentNode.getParent().getColor()
== RED) {
+      TreeNode<E> u = null;
+      if ((currentNode.getParent()).equals(currentNode.getParent().getParent().getLeft()))
{
+        u = currentNode.getParent().getParent().getRight();
+
+        if (u != null && u.getColor() == RED) {
+          currentNode.getParent().setColor(BLACK);
+          u.setColor(BLACK);
+          currentNode.getParent().getParent().setColor(RED);
+          currentNode = currentNode.getParent().getParent();
+          continue;
+        }
+        if (currentNode.equals(currentNode.getParent().getRight())) {
+          currentNode = currentNode.getParent();
+          rotateLeft(currentNode);
+        }
+        currentNode.getParent().setColor(BLACK);
+        currentNode.getParent().getParent().setColor(RED);
+        rotateRight(currentNode.getParent().getParent());
+      } else {
+        u = currentNode.getParent().getParent().getLeft();
+        if (u != null && u.getColor() == RED) {
+          currentNode.getParent().setColor(BLACK);
+          u.setColor(BLACK);
+          currentNode.getParent().getParent().setColor(RED);
+          currentNode = currentNode.getParent().getParent();
+          continue;
+        }
+        if (currentNode.equals(currentNode.getParent().getLeft())) {
+          currentNode = currentNode.getParent();
+          rotateRight(currentNode);
+        }
+        currentNode.getParent().setColor(BLACK);
+        currentNode.getParent().getParent().setColor(RED);
+        rotateLeft(currentNode.getParent().getParent());
+      }
+    }
+    root.setColor(BLACK);
+  }
+
+  protected void rotateLeft(TreeNode<E> currentNode) {
+    if (currentNode.getParent() != null) {
+      if (currentNode.equals(currentNode.getParent().getLeft())) {
+        currentNode.getParent().setLeft(currentNode.getRight(), false);
+      } else {
+        currentNode.getParent().setRight(currentNode.getRight(), false);
+      }
+      currentNode.getRight().setParent(currentNode.getParent(), false);
+      currentNode.setParent(currentNode.getRight(), false);
+      if (currentNode.getRight().getLeft() != null) {
+        currentNode.getRight().getLeft().setParent(currentNode, false);
+      }
+      currentNode.setRight(currentNode.getRight().getLeft(), false);
+      currentNode.getParent().setLeft(currentNode, false);
+    } else {
+      TreeNode<E> right = root.getRight();
+      root.setRight(right.getLeft(), false);
+      if (right.getLeft() != null) {
+        right.getLeft().setParent(root, false);
+      }
+      root.setParent(right, false);
+      right.setLeft(root, false);
+      right.setParent(null, false);
+      root = right;
+      unsafe.putLong(holder.get(), root.getHandler());
+    }
+  }
+
+  protected void rotateRight(TreeNode<E> currentNode) {
+    if (currentNode.getParent() != null) {
+      if (currentNode.equals(currentNode.getParent().getLeft())) {
+        currentNode.getParent().setLeft(currentNode.getLeft(), false);
+      } else {
+        currentNode.getParent().setRight(currentNode.getLeft(), false);
+      }
+
+      currentNode.getLeft().setParent(currentNode.getParent(), false);
+      currentNode.setParent(currentNode.getLeft(), false);
+      if (currentNode.getLeft().getRight() != null) {
+        currentNode.getLeft().getRight().setParent(currentNode, false);
+      }
+      currentNode.setLeft(currentNode.getLeft().getRight(), false);
+      currentNode.getParent().setRight(currentNode, false);
+    } else {
+      TreeNode<E> left = root.getLeft();
+      root.setLeft(root.getLeft().getRight(), false);
+      if (left.getRight() != null) {
+        left.getRight().setParent(root, false);
+      }
+      root.setParent(left, false);
+      left.setRight(root, false);
+      left.setParent(null, false);
+      root = left;
+      unsafe.putLong(holder.get(), root.getHandler());
+    }
+  }
+
+
+  /**
+   * checks if tree contains the specified element
+   *
+   * @param item
+   *          the item to be set
+   *
+   * @return tree if set contains the element
+   */
+  public boolean contains(E item) {
+    return findNode(item) == null ? false : true;
+  }
+
+  protected TreeNode<E> findNode(E item) {
+    return findNode(item, root);
+  }
+
+  protected TreeNode<E> findNode(E item, TreeNode node) {
+    if (null == node) {
+      return null;
+    }
+    int ret = node.compareTo(item);
+    if (ret < 0) {
+      return findNode(item, node.getRight());
+    } else if (ret > 0) {
+      return findNode(item, node.getLeft());
+    } else if (ret == 0) {
+      return node;
+    }
+    return null;
+  }
+
+  /**
+   * print tree
+   *
+   */
+  public void print() {
+    print(root);
+  }
+
+  protected void print(TreeNode<E> node) {
+    if (null == node) {
+      return;
+    }
+    print(node.getLeft());
+    node.testOutput();
+    print(node.getRight());
+  }
+
+  /**
+   * find successor item
+   *
+   * @param item
+   *          the item in the traversal
+   *
+   * @return successor item in the inorder traversal
+   */
+  public E successor(E item) {
+    return successor(item, findNode(item));
+  }
+
+  protected E successor(E item, TreeNode<E> node) {
+    if (null == node) {
+      return null;
+    }
+    if (node.getRight() != null) {
+      return findMinimum(node.getRight()).getItem();
+    }
+
+    TreeNode<E> parent = node.getParent();
+    if (null == parent) {
+      return null;
+    }
+    TreeNode currentNode = node;
+    while (parent != null && currentNode.equals(parent.getRight())) {
+      currentNode = parent;
+      parent = currentNode.getParent();
+    }
+    if (null == parent) {
+      return null;
+    } else {
+      return parent.getItem();
+    }
+  }
+
+  protected TreeNode<E> findMinimum(TreeNode<E> node) {
+    TreeNode<E> current = node;
+    while (current.getLeft() != null) {
+      current = current.getLeft();
+    }
+    return current;
+  }
+
+  /**
+   * find predecessor item
+   *
+   * @param item
+   *          the item in the traversal
+   *
+   * @return predecessor item in the inorder traversal
+   */
+  public E predecessor(E item) {
+    return predecessor(item, findNode(item));
+  }
+
+  protected E predecessor(E item, TreeNode<E> node) {
+    if (null == node) {
+      return null;
+    }
+    if (node.getLeft() != null) {
+      return findMaximum(node.getLeft()).getItem();
+    }
+
+    TreeNode<E> parent = node.getParent();
+
+    TreeNode currentNode = node;
+    while (parent != null && currentNode.equals(parent.getLeft())) {
+      currentNode = parent;
+      parent = currentNode.getParent();
+    }
+    if (null == parent) {
+      return null;
+    } else {
+      return parent.getItem();
+    }
+  }
+
+  protected TreeNode<E> findMaximum(TreeNode<E> node) {
+    TreeNode<E> current = node;
+    while (current.getRight() != null) {
+      current = current.getRight();
+    }
+    return current;
+  }
+
+  /**
+   * check if tree is a valid red black tree
+   *
+   * @return true if tree is a valid RB else false
+   */
+  public boolean isValidTree() {
+    return isValidTree(root);
+  }
+
+  protected boolean isValidTree(TreeNode<E> node) {
+    return isBinarySearchTree(node, null, null) && isBalancedBT(node);
+  }
+
+  protected boolean isBinarySearchTree(TreeNode<E> node, E min, E max) {
+    if (null == node) {
+      return true;
+    }
+    if (min != null && node.compareTo(min) < 0) {
+      return false;
+    }
+    if (max != null && node.compareTo(max) > 0) {
+      return false;
+    }
+    return isBinarySearchTree(node.getLeft(), min, node.getItem())
+      && isBinarySearchTree(node.getRight(), node.getItem(), max);
+  }
+
+  protected boolean isBalancedBT(TreeNode<E> node) {
+    int blackNodes = 0;
+    TreeNode<E> tmp = root;
+    while (tmp != null) {
+      if (tmp.getColor() == BLACK) {
+        blackNodes++;
+      }
+      tmp = tmp.getLeft();
+    }
+    return isBalancedBT(root, blackNodes);
+  }
+
+  protected boolean isBalancedBT(TreeNode<E> node, int blackNodes) {
+    if (null == node) {
+      return (0 == blackNodes);
+    }
+    if (node.getColor() == BLACK) {
+      blackNodes--;
+    }
+    return isBalancedBT(node.getLeft(), blackNodes) && isBalancedBT(node.getRight(),
blackNodes);
+  }
+
+  @Override
+  public boolean autoReclaim() {
+    return autoReclaim;
+  }
+
+  @Override
+  public long[][] getNativeFieldInfo() {
+    return fieldInfo;
+  }
+
+  @Override
+  public void destroy() throws RetrieveDurableEntityError {
+    destroy(root);
+    holder.destroy();
+  }
+
+  protected void destroy(TreeNode<E> node) {
+    if (null == node) {
+      return;
+    }
+    destroy(node.getLeft());
+    destroy(node.getRight());
+    node.setLeft(null, false);
+    node.setRight(null, false);
+    node.setParent(null, false);
+    node.destroy();
+  }
+
+  @Override
+  public void cancelAutoReclaim() {
+    autoReclaim = false;
+  }
+
+  @Override
+  public void registerAutoReclaim() {
+    autoReclaim = true;
+  }
+
+  @Override
+  public long getHandler() {
+    return allocator.getChunkHandler(holder);
+  }
+
+  @Override
+  public void restoreDurableEntity(A allocator, EntityFactoryProxy[] factoryProxy,
+      DurableType[] gType, long phandler, boolean autoReclaim) throws RestoreDurableEntityError
{
+    initializeDurableEntity(allocator, factoryProxy, gType, autoReclaim);
+    if (0L == phandler) {
+      throw new RestoreDurableEntityError("Input handler is null on restoreDurableEntity.");
+    }
+    holder = allocator.retrieveChunk(phandler, autoReclaim);
+    long rootHandler = unsafe.getLong(holder.get());
+    root = TreeNodeFactory.restore(allocator, factoryProxy, genericType, rootHandler, autoReclaim);
+    initializeAfterRestore();
+  }
+
+
+  @Override
+  public void initializeDurableEntity(A allocator, EntityFactoryProxy[] factoryProxy,
+      DurableType[] gType, boolean autoReclaim) {
+    this.allocator = allocator;
+    this.factoryProxy = factoryProxy;
+    this.genericType = gType;
+    this.autoReclaim = autoReclaim;
+    try {
+      this.unsafe = Utils.getUnsafe();
+    } catch (Exception e) {
+      e.printStackTrace();
+    }
+  }
+
+  @Override
+  public void createDurableEntity(A allocator, EntityFactoryProxy[] factoryProxy,
+      DurableType[] gType, boolean autoReclaim) throws OutOfHybridMemory {
+    initializeDurableEntity(allocator, factoryProxy, gType, autoReclaim);
+    this.holder = allocator.createChunk(MAX_OBJECT_SIZE, autoReclaim);
+    initializeAfterCreate();
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/TreeNode.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/TreeNode.java
b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/TreeNode.java
new file mode 100644
index 0000000..b2b5784
--- /dev/null
+++ b/mnemonic-collections/src/main/java/org/apache/mnemonic/collections/TreeNode.java
@@ -0,0 +1,208 @@
+/*
+ * 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.mnemonic.collections;
+
+
+import org.apache.mnemonic.Durable;
+import org.apache.mnemonic.EntityFactoryProxy;
+import org.apache.mnemonic.DurableType;
+import org.apache.mnemonic.DurableEntity;
+import org.apache.mnemonic.DurableGetter;
+import org.apache.mnemonic.DurableSetter;
+import org.apache.mnemonic.RetrieveDurableEntityError;
+
+/**
+ * this class defines a non-volatile node for a generic value in a tree structure
+ *
+ */
+@DurableEntity
+public abstract class TreeNode<E extends Comparable<E>> implements Durable, Comparable<TreeNode<E>>
{
+  protected transient EntityFactoryProxy[] m_node_efproxies;
+  protected transient DurableType[] m_node_gftypes;
+
+  /**
+   * creation callback for initialization
+   *
+   */
+  @Override
+  public void initializeAfterCreate() {
+    // System.out.println("Initializing After Created");
+  }
+
+  /**
+   * restore callback for initialization
+   *
+   */
+  @Override
+  public void initializeAfterRestore() {
+    // System.out.println("Initializing After Restored");
+  }
+
+  /**
+   * this function will be invoked by its factory to setup generic related info
+   * to avoid expensive operations from reflection
+   *
+   * @param efproxies
+   *          specify a array of factory to proxy the restoring of its generic
+   *          field objects
+   *
+   * @param gftypes
+   *          specify a array of types corresponding to efproxies
+   */
+  @Override
+  public void setupGenericInfo(EntityFactoryProxy[] efproxies, DurableType[] gftypes) {
+    m_node_efproxies = efproxies;
+    m_node_gftypes = gftypes;
+  }
+
+  /**
+   * get item field of this node
+   *
+   * @return the item field of this node
+   *
+   */
+  @DurableGetter(Id = 1L, EntityFactoryProxies = "m_node_efproxies", GenericFieldTypes =
"m_node_gftypes")
+  public abstract E getItem();
+
+  /**
+   * set item in the node
+   *
+   * @param item
+   *          the item to be set
+   *
+   * @param destroy
+   *          true if want to destroy the exist node
+   */
+  @DurableSetter
+  public abstract void setItem(E item, boolean destroy);
+
+  /**
+   * get left pointer of this node
+   *
+   * @return the left pointer of this node
+   *
+   */
+  @DurableGetter(Id = 2L, EntityFactoryProxies = "m_node_efproxies", GenericFieldTypes =
"m_node_gftypes")
+  public abstract TreeNode<E> getLeft();
+
+  /**
+   * set left pointer in the node
+   *
+   * @param left
+   *          the left pointer to be set
+   *
+   * @param destroy
+   *          true if want to destroy the exist node
+   */
+  @DurableSetter
+  public abstract void setLeft(TreeNode<E> left, boolean destroy);
+
+  /**
+   * get right pointer of this node
+   *
+   * @return the right pointer of this node
+   *
+   */
+  @DurableGetter(Id = 3L, EntityFactoryProxies = "m_node_efproxies", GenericFieldTypes =
"m_node_gftypes")
+  public abstract TreeNode<E> getRight();
+
+  /**
+   * set right pointer in the node
+   *
+   * @param right
+   *          the right pointer to be set
+   *
+   * @param destroy
+   *          true if want to destroy the exist node
+   */
+  @DurableSetter
+  public abstract void setRight(TreeNode<E> right, boolean destroy);
+
+  /**
+   * get parent of this node
+   *
+   * @return the parent pointer of this node
+   *
+   */
+  @DurableGetter(Id = 4L, EntityFactoryProxies = "m_node_efproxies", GenericFieldTypes =
"m_node_gftypes")
+  public abstract TreeNode<E> getParent();
+
+  /**
+   * set parent in the node
+   *
+   * @param parent
+   *          the parent pointer to be set
+   *
+   * @param destroy
+   *          true if want to destroy the exist node
+   */
+  @DurableSetter
+  public abstract void setParent(TreeNode<E> parent, boolean destroy);
+
+
+  /**
+   * get color of this node 1-red, 0-black
+   *
+   * @return the color of this node
+   *
+   */
+  @DurableGetter(Id = 5L, EntityFactoryProxies = "m_node_efproxies", GenericFieldTypes =
"m_node_gftypes")
+  public abstract boolean getColor();
+
+  /**
+   * set color in the node 1-red, 0-black
+   *
+   * @param color
+   *          the color to be set
+   *
+   * @param destroy
+   *          true if want to destroy the exist node
+   */
+  @DurableSetter
+  public abstract void setColor(boolean color);
+
+  @Override
+  public int compareTo(TreeNode<E> other) {
+    return getItem().compareTo(other.getItem());
+  }
+
+  public boolean equals(TreeNode<E> other) {
+    if (null == other) {
+      return false;
+    } else {
+      return getHandler() == other.getHandler();
+    }
+  }
+
+  public int hashCode() {
+    return getItem().hashCode();
+  }
+
+  public int compareTo(E item) {
+    return getItem().compareTo(item);
+  }
+
+  public void testOutput() throws RetrieveDurableEntityError {
+    System.out.println(((getColor() == false) ? "Color: Red " : "Color: Black ")
+                         + "Item: " + getItem()
+                         + " Current: " + getHandler()
+                         + " Left: " + ((getLeft() == null) ? "NULL" : getLeft().getHandler())
+                         + " Right: " + ((getRight() == null) ? "NULL" : getRight().getHandler())
+                         + " Parent: " + ((getParent() == null) ? "NULL" : getParent().getHandler()));
+   }
+}

http://git-wip-us.apache.org/repos/asf/incubator-mnemonic/blob/5c54177d/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
----------------------------------------------------------------------
diff --git a/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
b/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
new file mode 100644
index 0000000..858f792
--- /dev/null
+++ b/mnemonic-collections/src/test/java/org/apache/mnemonic/collections/DurableTreeNGTest.java
@@ -0,0 +1,216 @@
+/*
+ * 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.mnemonic.collections;
+
+//import java.util.Iterator;
+import java.nio.ByteBuffer;
+import java.util.Random;
+
+import org.apache.mnemonic.Utils;
+import org.apache.mnemonic.RestorableAllocator;
+import org.apache.mnemonic.NonVolatileMemAllocator;
+//import org.apache.mnemonic.OutOfHybridMemory;
+import org.apache.mnemonic.EntityFactoryProxy;
+import org.apache.mnemonic.DurableType;
+import org.apache.mnemonic.Reclaim;
+//import org.apache.mnemonic.Durable;
+import org.testng.annotations.AfterClass;
+import org.testng.annotations.BeforeClass;
+import org.testng.annotations.Test;
+import org.testng.AssertJUnit;
+//import org.testng.Assert;
+
+import sun.misc.Unsafe;
+
+/**
+ *
+ *
+ */
+
+public class DurableTreeNGTest {
+  private long cKEYCAPACITY;
+  private NonVolatileMemAllocator m_act;
+  private Random rand;
+  private Unsafe unsafe;
+
+  @BeforeClass
+  public void setUp() throws Exception {
+    rand = Utils.createRandom();
+    unsafe = Utils.getUnsafe();
+    m_act = new NonVolatileMemAllocator(Utils.getNonVolatileMemoryAllocatorService("pmalloc"),
1024 * 1024 * 1024,
+        "./pobj_tree.dat", true);
+    cKEYCAPACITY = m_act.handlerCapacity();
+    m_act.setBufferReclaimer(new Reclaim<ByteBuffer>() {
+      @Override
+      public boolean reclaim(ByteBuffer mres, Long sz) {
+        //System.out.println(String.format("Reclaim Memory Buffer: %X  Size: %s", System.identityHashCode(mres),
+        //    null == sz ? "NULL" : sz.toString()));
+        //System.out.println(" Reclaim String buffer " + mres.asCharBuffer().toString());
+        return false;
+      }
+    });
+    m_act.setChunkReclaimer(new Reclaim<Long>() {
+      @Override
+      public boolean reclaim(Long mres, Long sz) {
+        //System.out.println(String.format("Reclaim Memory Chunk: %X  Size: %s", System.identityHashCode(mres),
+        //    null == sz ? "NULL" : sz.toString()));
+        return false;
+      }
+    });
+
+    for (long i = 0; i < cKEYCAPACITY; ++i) {
+      m_act.setHandler(i, 0L);
+    }
+  }
+
+  protected int randInt() {
+    return rand.nextInt(1024 * 1024);
+  }
+
+  @AfterClass
+  public void tearDown() {
+    m_act.close();
+  }
+
+  @Test(enabled = true)
+  public void testInsertIntegers() {
+    DurableType gtypes[] = {DurableType.INTEGER};
+    DurableTree<Integer> tree = DurableTreeFactory.create(m_act, null, gtypes, false);
+
+    Long handler = tree.getHandler();
+    tree.insert(5);
+    tree.insert(3);
+    tree.insert(4);
+    tree.insert(1);
+    tree.insert(7);
+    tree.insert(6);
+    AssertJUnit.assertTrue(tree.isValidTree());
+
+    AssertJUnit.assertTrue(tree.contains(4));
+    AssertJUnit.assertFalse(tree.contains(8));
+    AssertJUnit.assertTrue(tree.contains(7));
+    AssertJUnit.assertTrue(tree.contains(5));
+
+    AssertJUnit.assertEquals(tree.successor(4).intValue(), 5);
+    AssertJUnit.assertEquals(tree.predecessor(4).intValue(), 3);
+    AssertJUnit.assertNull(tree.predecessor(1));
+    AssertJUnit.assertEquals(tree.successor(1).intValue(), 3);
+    AssertJUnit.assertEquals(tree.predecessor(7).intValue(), 6);
+    AssertJUnit.assertNull(tree.successor(7));
+
+    DurableTree<Integer> restoredTree = DurableTreeFactory.restore(m_act, null, gtypes,
handler, false);
+
+    AssertJUnit.assertTrue(restoredTree.isValidTree());
+
+    AssertJUnit.assertTrue(restoredTree.contains(4));
+    AssertJUnit.assertFalse(restoredTree.contains(8));
+    AssertJUnit.assertTrue(restoredTree.contains(7));
+    AssertJUnit.assertTrue(restoredTree.contains(5));
+
+    AssertJUnit.assertEquals(restoredTree.successor(4).intValue(), 5);
+    AssertJUnit.assertEquals(restoredTree.predecessor(4).intValue(), 3);
+    AssertJUnit.assertNull(restoredTree.predecessor(1));
+    AssertJUnit.assertEquals(restoredTree.successor(1).intValue(), 3);
+    AssertJUnit.assertEquals(restoredTree.predecessor(7).intValue(), 6);
+    AssertJUnit.assertNull(restoredTree.successor(7));
+
+    restoredTree.insert(10);
+    restoredTree.insert(2);
+    AssertJUnit.assertEquals(restoredTree.successor(1).intValue(), 2);
+    AssertJUnit.assertEquals(restoredTree.predecessor(10).intValue(), 7);
+
+    restoredTree.destroy();
+  }
+
+  @Test(enabled = true)
+  public void testInsertString() {
+    DurableType gtypes[] = {DurableType.STRING};
+    DurableTree<String> tree = DurableTreeFactory.create(m_act, null, gtypes, false);
+
+    //strings are sorted lexicographically
+    Long handler = tree.getHandler();
+    tree.insert("bob");
+    tree.insert("Alice");
+    tree.insert("Dog");
+    tree.insert("Fun");
+    tree.insert("Ele");
+    tree.insert("Cat");
+
+    AssertJUnit.assertTrue(tree.isValidTree());
+
+    AssertJUnit.assertTrue(tree.contains("Fun"));
+    AssertJUnit.assertFalse(tree.contains("is"));
+    AssertJUnit.assertTrue(tree.contains("Cat"));
+    AssertJUnit.assertFalse(tree.contains("Bob"));
+
+    AssertJUnit.assertEquals(tree.successor("Ele"), "Fun");
+    AssertJUnit.assertEquals(tree.predecessor("Dog"), "Cat");
+    AssertJUnit.assertNull(tree.predecessor("Alice"));
+    AssertJUnit.assertEquals(tree.successor("Alice"), "Cat");
+    AssertJUnit.assertEquals(tree.predecessor("Fun"), "Ele");
+    AssertJUnit.assertNull(tree.successor("bob"));
+
+    tree.destroy();
+  }
+
+  @Test(enabled = true)
+  public void testInsertRandomBigTrees() {
+    DurableType gtypes[] = {DurableType.INTEGER};
+    DurableTree<Integer> tree = DurableTreeFactory.create(m_act, null, gtypes, false);
+
+    Long handler = tree.getHandler();
+    for (int i = 0; i < 10 * 1024; i++) {
+      int rand = randInt();
+      tree.insert(rand);
+      AssertJUnit.assertTrue(tree.contains(rand));
+    }
+    AssertJUnit.assertTrue(tree.isValidTree());
+    tree.destroy();
+  }
+
+  @Test(enabled = true)
+  public void testInsertDurable() {
+    DurableType gtypes[] = {DurableType.DURABLE};
+    EntityFactoryProxy efproxies[] = {new EntityFactoryProxy() {
+      @Override
+      public <A extends RestorableAllocator<A>> Person<Long> restore(
+          A allocator, EntityFactoryProxy[] factoryproxys,
+          DurableType[] gfields, long phandler, boolean autoreclaim) {
+        return PersonFactory.restore(allocator, factoryproxys, gfields, phandler, autoreclaim);
+      }
+      @Override
+      public <A extends RestorableAllocator<A>> Person<Long> create(
+          A allocator, EntityFactoryProxy[] factoryproxys,
+          DurableType[] gfields, boolean autoreclaim) {
+        return PersonFactory.create(allocator, factoryproxys, gfields, autoreclaim);
+      }
+    } };
+
+    DurableTree<Person<Long>> tree = DurableTreeFactory.create(m_act, efproxies,
gtypes, false);
+    Long handler = tree.getHandler();
+
+    for (int i = 0; i < 10; i++) {
+      Person<Long> person =  (Person<Long>) efproxies[0].create(m_act, null,
null, false);
+      person.setAge((short) (40 - i));
+      tree.insert(person);
+    }
+
+    AssertJUnit.assertTrue(tree.isValidTree());
+    tree.destroy();
+  }
+}



Mime
View raw message