Mercurial > hg > Members > shoshi > TreeCMSv2

changeset 27:aecc55e87143 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
test commit
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Thu, 18 Aug 2011 17:37:03 +0900
parents 9cb971a68cc5
children
files src/treecms/memory/NodeTable.java src/treecms/memory/OnMemoryMonotonicTree.java src/treecms/memory/OnMemoryMonotonicTreeNode.java src/treecms/merger/Merger.java src/treecms/merger/ReplaceMerger.java src/treecms/tree/id/IncrementalIDProvider.java src/treecms/tree/id/NodeIDProvider.java
diffstat 7 files changed, 142 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/memory/NodeTable.java	Thu Aug 18 17:37:03 2011 +0900
@@ -0,0 +1,16 @@
+package treecms.memory;
+
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+
+import treecms.api.Node;
+
+public class NodeTable<T extends Node> 
+{
+	private final Map<String,T> cache;
+	
+	public NodeTable(T _root)
+	{
+		cache = new ConcurrentHashMap<String,T>();
+	}
+}
--- a/src/treecms/memory/OnMemoryMonotonicTree.java	Mon Jul 18 20:22:53 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTree.java	Thu Aug 18 17:37:03 2011 +0900
@@ -1,30 +1,59 @@
 package treecms.memory;
 
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicReference;
 import treecms.api.MonotonicTree;
 import treecms.api.MonotonicTreeNode;
 import treecms.api.Node;
+import treecms.api.NodeID;
+import treecms.merger.Merger;
 import treecms.tree.id.NodeIDProvider;
 
+/**
+ * provides monotonic tree modification method in local (== not thread-safe) 
+ */
 public class OnMemoryMonotonicTree implements MonotonicTree
 {
+	private final Merger<OnMemoryNode> m_merger;
 	private final OnMemoryMonotonicTree m_tree;
-	private volatile OnMemoryMonotonicTreeNode m_root;
+	private final AtomicReference<OnMemoryNode> m_tip;
+	
+	private final AtomicReference<OnMemoryNode> m_snapshot;
+	private final OnMemoryMonotonicTreeNode m_editing;
 	
-	private OnMemoryMonotonicTree(NodeIDProvider _provider,OnMemoryMonotonicTree _tree)
+	private OnMemoryMonotonicTree(NodeIDProvider _provider,OnMemoryMonotonicTree _tree,Merger<OnMemoryNode> _merger)
 	{
+		m_merger = _merger;
 		m_tree = _tree;
-		m_root = new OnMemoryMonotonicTreeNode(new OnMemoryNode(_provider.create(),null),null);
+		m_tip = new AtomicReference<OnMemoryNode>();
+		m_snapshot = new AtomicReference<OnMemoryNode>();
+		
+		//if remote tree (target tree) is exist , then import root node form remote tree.
+		if(m_tree != null){
+			m_tip.set(m_tree.m_tip.get());
+		}else{
+			m_tip.set(new OnMemoryNode(_provider.create(),null));
+		}
+		m_snapshot.set(m_tip.get());
+		
+		//create editing node.
+		m_editing = new OnMemoryMonotonicTreeNode(m_snapshot.get(),null);
 	}
 	
-	public static OnMemoryMonotonicTree createInstance(NodeIDProvider _provider,OnMemoryMonotonicTree _tree)
+	public static OnMemoryMonotonicTree createInstance(NodeIDProvider _provider,OnMemoryMonotonicTree _tree,Merger<OnMemoryNode> _merger)
 	{
-		OnMemoryMonotonicTree tree = new OnMemoryMonotonicTree(_provider,_tree);
+		OnMemoryMonotonicTree tree = new OnMemoryMonotonicTree(_provider,_tree,_merger);
 		return tree;
 	}
 	
 	public OnMemoryNode get(String _fid)
 	{
-		return (OnMemoryNode)search(_fid,m_root.getNode());
+		if(_fid == null){
+			throw new NullPointerException("the parameter _fid must not be null.");
+		}
+		
+		OnMemoryNode root = (OnMemoryNode)m_editing.getNode();
+		return (OnMemoryNode)search(_fid,root);
 	}
 	
 	private Node search(String _fid,Node _node)
@@ -44,38 +73,77 @@
 	}
 	
 	@Override
-	public boolean commit(boolean _force)
+	public boolean commit(boolean _doForceCommit)
 	{
-		if(m_tree == null){
-			return true;
+		//if commit target is exist.
+		if(m_tree != null){
+			//if force commit is enabled.
+			if(_doForceCommit){
+				//force commit is just replace the target root to own root.
+				return true; //always returns true.
+			}
+			
+			//trying to compare and swap tip to editing root. (trying to commit)
+			OnMemoryNode root = (OnMemoryNode)m_editing.getNode();
+			if(m_tip.compareAndSet(m_snapshot.get(),root)){
+				return true;
+			}
+			
+			//failed to CAS modified tree
 		}
+		return false;
+	}
+	
+	/**
+	 *  this method may fail when failed to commit tree.
+	 */
+	public boolean push()
+	{
+		//pushing local root node to remote tree.
+		OnMemoryNode local = (OnMemoryNode)this.m_editing.getNode();
+		OnMemoryNode snapshot = this.m_snapshot.get();
 		
-		return true;
+		//compare remote tip and own snapshot
+		boolean ret = m_tree.m_tip.compareAndSet(snapshot,local);
+		
+		//if that is false , that means need to merge.
+		return ret;
 	}
 
 	@Override
 	public boolean pull()
 	{
+		//need to compare and swap here? or just replace
+		OnMemoryNode newRoot = m_tree.m_tip.get();
+		m_tip.set(newRoot);
+		m_editing.
 		return true;
 	}
 
 	@Override
 	public boolean check()
 	{
-		if(m_tree != null){
-			
+		if(m_tree == null){
+			return false;
 		}
-		return m_tree.getRoot().getNode().equals(m_root.getNode());
+		
+		OnMemoryNode root = m_root.get();
+		return m_tree.m_root.get().equals(root);
 	}
 
 	@Override
 	public void merge()
 	{
+		OnMemoryNode tree1 = m_root.get();
+		OnMemoryNode tree2 = (OnMemoryNode)m_editing.get().getNode();
+		OnMemoryNode merged = m_merger.merge(tree1,tree2);
+		
+		m_editing.set(new OnMemoryMonotonicTreeNode(merged,null));
 	}
 
 	@Override
 	public MonotonicTreeNode getRoot()
 	{
-		return m_root;
+		return m_editing.get();
 	}
 }
--- a/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Mon Jul 18 20:22:53 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Thu Aug 18 17:37:03 2011 +0900
@@ -16,7 +16,7 @@
 public class OnMemoryMonotonicTreeNode implements MonotonicTreeNode
 {
 	private final OnMemoryMonotonicTreeNode m_parent;
-	private OnMemoryNode m_node;
+	private volatile OnMemoryNode m_node;
 	
 	public OnMemoryMonotonicTreeNode(OnMemoryNode _node,OnMemoryMonotonicTreeNode _parent)
 	{
@@ -117,6 +117,8 @@
 		OnMemoryMonotonicTreeNode parent = (OnMemoryMonotonicTreeNode)getParent();
 		if(parent != null){
 			return m_parent.transmit(m_node,clone);
+		}else{
+			
 		}
 		
 		return true;
--- a/src/treecms/merger/Merger.java	Mon Jul 18 20:22:53 2011 +0900
+++ b/src/treecms/merger/Merger.java	Thu Aug 18 17:37:03 2011 +0900
@@ -1,10 +1,11 @@
 package treecms.merger;
 
+import treecms.api.Node;
 import treecms.api.NodeAttributes;
 import treecms.api.NodeChildren;
 import treecms.api.NodeContext;
 
-public interface Merger<T extends NodeAttributes & NodeContext & NodeChildren<T>>
+public interface Merger<T extends Node>
 {
 	public T merge(T _tree1,T _tree2);
 }
--- a/src/treecms/merger/ReplaceMerger.java	Mon Jul 18 20:22:53 2011 +0900
+++ b/src/treecms/merger/ReplaceMerger.java	Thu Aug 18 17:37:03 2011 +0900
@@ -1,10 +1,8 @@
 package treecms.merger;
 
-import treecms.api.NodeAttributes;
-import treecms.api.NodeChildren;
-import treecms.api.NodeContext;
+import treecms.api.Node;
 
-public class ReplaceMerger<T extends NodeAttributes & NodeContext & NodeChildren<T>> implements Merger<T>
+public class ReplaceMerger<T extends Node> implements Merger<T>
 {
 	public T merge(T _tree1,T _tree2)
 	{
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/id/IncrementalIDProvider.java	Thu Aug 18 17:37:03 2011 +0900
@@ -0,0 +1,29 @@
+package treecms.tree.id;
+
+import java.util.concurrent.atomic.AtomicLong;
+import treecms.api.NodeID;
+
+public class IncrementalIDProvider implements NodeIDProvider
+{
+	private final String m_prefix;
+	private final AtomicLong m_count;
+	
+	public IncrementalIDProvider(String _prefix,long _count)
+	{
+		m_prefix = _prefix;
+		m_count = new AtomicLong(_count);
+	}
+	
+	@Override
+	public NodeID create()
+	{
+		String fid = String.format("%s-%s",m_prefix,m_count.getAndIncrement());
+		return new IncrementalID(fid);
+	}
+	
+	@Override
+	public String toString()
+	{
+		return String.format("prefix=%s,count=%d",m_prefix,m_count.get());
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/id/NodeIDProvider.java	Thu Aug 18 17:37:03 2011 +0900
@@ -0,0 +1,8 @@
+package treecms.tree.id;
+
+import treecms.api.NodeID;
+
+public interface NodeIDProvider
+{
+	public NodeID create();
+}