# HG changeset patch
# User Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
# Date 1310449175 -32400
# Node ID c1e7ec6b3d444207ced2f5ae00473f9421c04d3f
# Parent  68021f7091e1ebf8cbe6083d7b895a4dc836c8ae
commit

diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/collections/CopyOnWriteArrayList.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/collections/CopyOnWriteArrayList.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,237 @@
+package treecms.collections;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.RandomAccess;
+import java.util.concurrent.locks.ReentrantLock;
+
+
+public class CopyOnWriteArrayList<E> implements List<E> , RandomAccess
+{
+	private volatile Object[] m_array;
+	private final ReentrantLock m_lock;
+	
+	public CopyOnWriteArrayList()
+	{
+		m_array = new Object[0];
+		m_lock = new ReentrantLock();
+	}
+	
+	public CopyOnWriteArrayList(List<E> _list)
+	{
+		this();
+		if(_list instanceof CopyOnWriteArrayList){
+			CopyOnWriteArrayList<E> list = (CopyOnWriteArrayList<E>)_list;
+			m_array = list.m_array;
+		}
+	}
+
+	@Override
+	public int size()
+	{
+		return m_array.length;
+	}
+
+	@Override
+	public boolean isEmpty()
+	{
+		return (size() == 0) ? true : false;
+	}
+
+	@Override
+	public boolean contains(Object _o)
+	{
+		Object[] array = m_array;
+		for(Object item : array){
+			if(item.equals(_o)){
+				return true;
+			}
+		}
+		return false;
+	}
+
+	@Override
+	public Iterator<E> iterator()
+	{
+		List<E> list = (List<E>)Arrays.asList(m_array);
+		return Collections.unmodifiableList(list).iterator();
+	}
+
+	@Override
+	public Object[] toArray()
+	{
+		return Arrays.copyOf(m_array,size());
+	}
+
+	@Override
+	public <T> T[] toArray(T[] _a)
+	{
+		final Object[] ret;
+		int size = size();
+		if(_a.length < size){
+			ret = Arrays.copyOf(m_array,size);
+		}else{
+			System.arraycopy(m_array,0,_a,0,size);
+			ret = _a;
+		}
+		
+		return (T[])ret;
+	}
+
+	@Override
+	public synchronized boolean add(E e)
+	{
+		int size = m_array.length;
+		Object[] newArray = new Object[size + 1];
+		System.arraycopy(m_array,0,newArray,0,size);
+		newArray[size] = e;
+		m_array = newArray;
+		return true;
+	}
+
+	@Override
+	public synchronized boolean remove(Object o)
+	{
+		int size = size();
+		Object[] array = new Object[size - 1];
+		
+		for(int i = 0;i < size;i ++){
+			Object item = m_array[i];
+			if(item.equals(o)){
+				for(i = i + 1;i < size;i ++){
+					array[i - 1] = m_array[i];
+				}
+				
+				m_array = array;
+				return true;
+			}
+			array[i] = item;
+		}
+		
+		return false;
+	}
+
+	@Override
+	public boolean containsAll(Collection<?> c)
+	{
+		boolean ret = true;
+		for(Object e1 : c){
+			ret = ret & contains(e1);
+		}
+		return ret;
+	}
+
+	@Override
+	public synchronized boolean addAll(Collection<? extends E> c)
+	{
+		Object[] array = new Object[size() + c.size()];
+		System.arraycopy(m_array,0,array,0,m_array.length);
+		
+		int i = m_array.length + 1;
+		for(Object e : c){
+			array[i] = e;
+			i++;
+		}
+		return true;
+	}
+
+	@Override
+	public synchronized boolean addAll(int index, Collection<? extends E> c)
+	{
+		Object[] array = new Object[size() + c.size()];
+		System.arraycopy(m_array,0,array,0,index);
+		
+		int i = index + 1;
+		for(Object e : c){
+			array[i] = e;
+			i ++;
+		}
+		
+		System.arraycopy(m_array,index + 1,array,i + 1,size() - index);
+		m_array = array;
+		return true;
+	}
+
+	@Override
+	public boolean removeAll(Collection<?> c)
+	{
+		Object[] array = new Object[size() - c.size()];
+		
+		return false;
+	}
+
+	@Override
+	public boolean retainAll(Collection<?> c)
+	{
+		// TODO Auto-generated method stub
+		return false;
+	}
+
+	@Override
+	public void clear() {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public E get(int index) {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public E set(int index, E element) {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public void add(int index, E element) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public E remove(int index) {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public int indexOf(Object o) {
+		// TODO Auto-generated method stub
+		return 0;
+	}
+
+	@Override
+	public int lastIndexOf(Object o) {
+		// TODO Auto-generated method stub
+		return 0;
+	}
+
+	@Override
+	public ListIterator<E> listIterator()
+	{
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public ListIterator<E> listIterator(int index)
+	{
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public List<E> subList(int fromIndex, int toIndex)
+	{
+		return null;
+	}
+
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/memory/OnMemoryForest.java
--- a/src/treecms/memory/OnMemoryForest.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryForest.java	Tue Jul 12 14:39:35 2011 +0900
@@ -1,17 +1,59 @@
 package treecms.memory;
 
+import java.nio.ByteBuffer;
+import java.util.Map;
+import java.util.Set;
+
 import treecms.api.Forest;
 import treecms.api.MonotonicTree;
+import treecms.api.MonotonicTreeNode;
 import treecms.api.NodeID;
+import treecms.tree.id.IncrementalID;
 import treecms.tree.id.RandomNodeID;
 
 public class OnMemoryForest implements Forest
 {
+	public static void main(String _args[])
+	{
+		OnMemoryForest f = new OnMemoryForest();
+		MonotonicTree main = f.getMainTree();
+		MonotonicTreeNode root = main.getRoot();
+		MonotonicTreeNode ch1 = root.create(null);
+		MonotonicTreeNode ch2 = root.create(null);
+		MonotonicTreeNode ch11 = ch1.create(null);
+		
+		ByteBuffer key1 = ByteBuffer.wrap("hoge".getBytes());
+		ByteBuffer key2 = ByteBuffer.wrap("fuga".getBytes());
+		
+		ch11.put(key1, key1);
+		ch11.put(key2, key2);
+		System.out.println(new String(ch11.get(key1).array()));
+		
+		Set<ByteBuffer> keys = ch11.getKeySet();
+		System.out.println(keys);
+		Map<ByteBuffer,ByteBuffer> map = ch11.asMap();
+		System.out.println(map);
+		
+		ch11.clearAttributes();
+		System.out.println(ch11.getKeySet());
+		System.out.println(ch11.asMap());
+		
+		print(root);
+	}
+	
+	public static void print(MonotonicTreeNode _t)
+	{
+		System.out.println(_t.toString());
+		for(MonotonicTreeNode n : _t.getList()){
+			print(n);
+		}
+	}
+	
 	private final OnMemoryMonotonicTree m_tree;
 	
 	public OnMemoryForest()
 	{
-		NodeID id = new RandomNodeID(null);
+		NodeID id = new IncrementalID("ROOT");
 		OnMemoryNode newNode = new OnMemoryNode(id,null);
 		
 		m_tree = OnMemoryMonotonicTree.createInstance(newNode,null);
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/memory/OnMemoryMonotonicTree.java
--- a/src/treecms/memory/OnMemoryMonotonicTree.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTree.java	Tue Jul 12 14:39:35 2011 +0900
@@ -1,49 +1,33 @@
 package treecms.memory;
-import java.util.concurrent.ConcurrentHashMap;
-
-import java.util.concurrent.ConcurrentMap;
 
 import treecms.api.MonotonicTree;
 import treecms.api.MonotonicTreeNode;
-import treecms.api.Node;
-import treecms.api.NodeID;
-import treecms.api.NodeTable;
-import treecms.tree.util.NodeData;
-import treecms.tree.util.NodeTableImpl;
+import treecms.tree.util.LockableNodeTable;
 
 public class OnMemoryMonotonicTree implements MonotonicTree
 {
 	private final OnMemoryMonotonicTree m_tree;
-	private final NodeTable m_table;
+	private final LockableNodeTable m_table;
 	private final OnMemoryMonotonicTreeNode m_root;
 	
 	private OnMemoryMonotonicTree(OnMemoryNode _root,OnMemoryMonotonicTree _tree)
 	{
 		m_tree = _tree;
-		m_table = new NodeTableImpl();
-		
-		NodeID id = _root.getID();
-		String fid = id.getFamilyID();
-		m_root = new OnMemoryMonotonicTreeNode(fid,null,m_table);
+		m_table = new LockableNodeTable();
+		m_table.register(_root);
+		m_root = new OnMemoryMonotonicTreeNode(_root,null,m_table);
 	}
 	
 	public static OnMemoryMonotonicTree createInstance(OnMemoryNode _root,OnMemoryMonotonicTree _tree)
 	{
 		OnMemoryMonotonicTree tree = new OnMemoryMonotonicTree(_root,_tree);
-		tree.m_root = new OnMemoryMonotonicTreeNode(_root.getID().getFamilyID(),null,tree);
 		return tree;
 	}
 	
 	public OnMemoryNode get(String _fid)
 	{
-		return m_members.get(_fid);
-	}
-	
-	public OnMemoryNode createNode(NodeID _id,NodeData<Node> _data)
-	{
-		OnMemoryNode newNode = new OnMemoryNode(_id,_data);
-		m_members.put(_id.getFamilyID(),newNode);
-		return newNode;
+		OnMemoryNode node = (OnMemoryNode)m_table.tip(_fid);
+		return node;
 	}
 	
 	@Override
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/memory/OnMemoryMonotonicTreeNode.java
--- a/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Tue Jul 12 14:39:35 2011 +0900
@@ -7,37 +7,30 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentMap;
 import treecms.api.MonotonicTreeNode;
 import treecms.api.Node;
 import treecms.api.NodeAttributes;
 import treecms.api.NodeID;
-import treecms.api.NodeTable;
+import treecms.tree.util.LockableNodeTable;
 import treecms.tree.util.NodeData;
 
 public class OnMemoryMonotonicTreeNode implements MonotonicTreeNode
 {
-	private OnMemoryMonotonicTreeNode m_parent;
-	private final NodeTable m_table;
-	private final ConcurrentMap<String,MonotonicTreeNode> m_cache;
-	
-	private final OnMemoryNode m_node;
-	private final LockableReference<OnMemoryNode> m_tip;
+	private volatile OnMemoryMonotonicTreeNode m_parent;
+	private OnMemoryNode m_node;
+	private final LockableNodeTable m_table;
 	
-	public OnMemoryMonotonicTreeNode(OnMemoryNode _node,OnMemoryMonotonicTreeNode _parent,NodeTable _table)
+	public OnMemoryMonotonicTreeNode(OnMemoryNode _node,OnMemoryMonotonicTreeNode _parent,LockableNodeTable _table)
 	{
+		m_node = _node;
+		m_table = _table;
 		m_parent = _parent;
-		m_cache = new ConcurrentHashMap<String,MonotonicTreeNode>();
-		m_table = _table;
-		
-		m_node = _node;
 	}
 	
 	@Override
 	public NodeID getID()
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		return n.getID();
 	}
 
@@ -48,35 +41,34 @@
 			return null;
 		}
 		
-		synchronized(m_parent){
-			OnMemoryNode node = (OnMemoryNode)getNode();
+		OnMemoryNode node = (OnMemoryNode)getNode();
 			
-			//check , does parent contain the node.
-			if(!m_parent.contains(node.getID())){
-				m_parent = null;
-			}
-			return m_parent;
+		//check , does parent contain the node.
+		if(!m_parent.contains(node.getID())){
+			m_parent = null;
 		}
+		
+		return m_parent;
 	}
 	
 	@Override
 	public ByteBuffer get(ByteBuffer _key)
 	{
-		OnMemoryNode node = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		return node.get(_key);
 	}
 
 	@Override
 	public NodeAttributes getAll()
 	{
-		OnMemoryNode node = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		return node.getAll();
 	}
 
 	@Override
-	public synchronized void put(ByteBuffer _key, ByteBuffer _value)
+	public void put(ByteBuffer _key, ByteBuffer _value)
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(n,n);
 		d.put(_key,_value);
 		
@@ -84,9 +76,9 @@
 	}
 
 	@Override
-	public synchronized void putAll(NodeAttributes _map)
+	public void putAll(NodeAttributes _map)
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(n,n);
 		d.putAll(_map);
 		
@@ -94,9 +86,9 @@
 	}
 
 	@Override
-	public synchronized void remove(ByteBuffer _key)
+	public void remove(ByteBuffer _key)
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(n,n);
 		d.remove(_key);
 		
@@ -104,9 +96,9 @@
 	}
 
 	@Override
-	public synchronized void removeAll(Set<ByteBuffer> _keys)
+	public void removeAll(Set<ByteBuffer> _keys)
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(n,n);
 		d.removeAll(_keys);
 		
@@ -114,39 +106,51 @@
 	}
 
 	@Override
-	public synchronized void clearAttributes()
+	public void clearAttributes()
 	{
-		OnMemoryNode n = (OnMemoryNode)m_table.tip(m_fid);
+		OnMemoryNode n = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(n,n);
 		d.clearAttributes();
 		
 		cloneAndTransmit(d);
 	}
 	
-	public synchronized void cloneAndTransmit(NodeData<Node> _d)
+	public void cloneAndTransmit(NodeData<Node> _d)
 	{
-		OnMemoryNode node = (OnMemoryNode)m_table.tip(m_fid);
+		String fid = m_node.getID().getFamilyID();
+		
+		m_table.lock(fid);
+		
+		OnMemoryNode node = (OnMemoryNode)m_table.tip(fid);
 		NodeID newID = node.getID().update();
-		Node clone = new OnMemoryNode(newID,_d);
+		OnMemoryNode clone = new OnMemoryNode(newID,_d);
+		m_table.register(clone);
+		
+		m_table.unlock(fid);
 		
 		OnMemoryMonotonicTreeNode parent = (OnMemoryMonotonicTreeNode)getParent();
 		if(parent != null){ 
 			parent.transmit(node,clone);
 		}
-		m_table.register(clone);
+		
+		m_node = clone;
 	}
 	
-	public synchronized boolean transmit(Node _orig,Node _edit)
+	public boolean transmit(Node _orig,Node _edit)
 	{
-		OnMemoryNode node = (OnMemoryNode)m_table.tip(m_fid);
+		String fid = m_node.getID().getFamilyID();
+		m_table.lock(fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		
 		NodeData<Node> d = new NodeData<Node>(node,node);
 		d.replace(_edit);
+		NodeID newID = node.getID().update();
+		OnMemoryNode clone = new OnMemoryNode(newID,d);
 		
-		NodeID newID = node.getID().update();
-		OnMemoryNode clone = new OnMemoryNode(newID,null);
-		m_table.register(_newNode);
+		m_table.register(clone);
+		m_table.unlock(fid);
 		
+		m_node = clone;
 		
 		OnMemoryMonotonicTreeNode parent = (OnMemoryMonotonicTreeNode)getParent();
 		if(parent != null){
@@ -156,48 +160,38 @@
 	}
 	
 	@Override
-	public synchronized Node getNode()
+	public Node getNode()
 	{
-		return m_table.tip(m_fid);
+		return m_node;
 	}
 	
 	@Override
-	public synchronized List<MonotonicTreeNode> getList()
+	public List<MonotonicTreeNode> getList()
 	{
 		//NodeのリストよりMonotonicTreeNodeのリストを作成する．
-		OnMemoryNode node = m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		int size = node.getList().size();
 		ArrayList<MonotonicTreeNode> list = new ArrayList<MonotonicTreeNode>(size);
 		for(Iterator<Node> it = node.getList().iterator();it.hasNext();){
 			OnMemoryNode n = (OnMemoryNode)it.next();
-			list.add(getCache(n.getID().getFamilyID()));
+			OnMemoryMonotonicTreeNode tn = new OnMemoryMonotonicTreeNode(n,this,m_table);
+			list.add(tn);
 		}
 		
 		return Collections.unmodifiableList(list);
 	}
 	
-	public OnMemoryMonotonicTreeNode getCache(final String _fid)
+	@Override
+	public MonotonicTreeNode remove(int _index)
 	{
-		OnMemoryMonotonicTreeNode newCache = new OnMemoryMonotonicTreeNode(m_fid,this,m_table);
-		OnMemoryMonotonicTreeNode cache = (OnMemoryMonotonicTreeNode)m_cache.putIfAbsent(_fid,newCache);
-		if(cache == null){
-			return newCache;
-		}
+		OnMemoryNode n = (OnMemoryNode)getNode();
+		NodeData<Node> d = new NodeData<Node>(n,n);
+		OnMemoryNode deleted = (OnMemoryNode)d.remove(_index);
 		
-		return cache;
-	}
-
-	@Override
-	public synchronized MonotonicTreeNode remove(int _index)
-	{
-		OnMemoryNode n = m_table.tip(m_fid);
-		NodeData<Node> d = new NodeData<Node>(n,n);
-		OnMemoryNode deleted = (OnMemoryNode) d.remove(_index);
-		
-		if(n != null){
+		if(deleted != null){
 			cloneAndTransmit(d);
 			
-			OnMemoryMonotonicTreeNode tn = getCache(deleted.getID().getFamilyID());
+			OnMemoryMonotonicTreeNode tn = new OnMemoryMonotonicTreeNode(deleted,null,m_table);
 			return tn;
 		}
 		
@@ -205,9 +199,13 @@
 	}
 	
 	@Override
-	public synchronized void clearChildren()
+	public void clearChildren()
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
+		if(node.getList().size() == 0){
+			return;
+		}
+		
 		NodeData<Node> d = new NodeData<Node>(node,node);
 		d.clearChildren();
 		
@@ -217,79 +215,93 @@
 	@Override
 	public Map<ByteBuffer, ByteBuffer> asMap()
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		return node.asMap();
 	}
 
 	@Override
 	public Set<ByteBuffer> getKeySet()
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		return node.getKeySet();
 	}
 
 	@Override
-	public synchronized MonotonicTreeNode get(int _index)
+	public MonotonicTreeNode get(int _index)
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
-		return getCache(node.getID().getFamilyID());
+		OnMemoryNode node = (OnMemoryNode)getNode();
+		OnMemoryMonotonicTreeNode tn = new OnMemoryMonotonicTreeNode(node,this,m_table);
+		return tn;
 	}
 
 	@Override
 	public boolean contains(NodeID _id)
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		return node.contains(_id);
 	}
 
 	@Override
 	public boolean swap(String _fid1,String _fid2)
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
-		return node.swap(_fid1,_fid2);
+		OnMemoryNode node = (OnMemoryNode)getNode();
+		NodeData<Node> d = new NodeData<Node>(node,node);
+		
+		if(d.swap(_fid1,_fid2)){
+			cloneAndTransmit(d);
+			
+			return true;
+		}
+		
+		return false;
 	}
 
 	@Override
 	public Set<String> getFamilyIDSet()
 	{
-		OnMemoryNode node = m_table.tip(m_fid);
-		return node.getFamilyIDSet();
+		Set<String> fids = m_node.getFamilyIDSet();
+		return fids;
 	}
 
 	@Override
-	public synchronized MonotonicTreeNode get(String _fid)
+	public MonotonicTreeNode get(String _fid)
 	{
-		OnMemoryMonotonicTreeNode mono = getCache(_fid);
+		OnMemoryNode node = (OnMemoryNode)m_node.get(_fid);
+		OnMemoryMonotonicTreeNode mono = new OnMemoryMonotonicTreeNode(node,this,m_table);
 		return mono;
 	}
 
 	@Override
-	public synchronized MonotonicTreeNode remove(String _fid)
+	public MonotonicTreeNode remove(String _fid)
 	{
-		OnMemoryMonotonicTreeNode tnode = getCache(_fid);
-		OnMemoryNode node = (OnMemoryNode)tnode.getNode();
+		OnMemoryNode node = (OnMemoryNode)getNode();
 		
 		NodeData<Node> d = new NodeData<Node>(node,node);
-		d.remove(_fid);
+		OnMemoryNode deleted = (OnMemoryNode)d.remove(_fid);
 		
 		cloneAndTransmit(d);
-		return tnode;
+		return new OnMemoryMonotonicTreeNode(deleted,null,m_table);
 	}
 
 	@Override
-	public synchronized MonotonicTreeNode create(NodeAttributes _attr)
+	public MonotonicTreeNode create(NodeAttributes _attr)
 	{
 		NodeID newID = getNode().getID().create();
-		OnMemoryNode newNode = m_table.createNode(newID,new NodeData<Node>(null,_attr));
+		OnMemoryNode newNode = new OnMemoryNode(newID,new NodeData<Node>(null,_attr));
+		m_table.register(newNode);
 		
 		OnMemoryNode thisNode = (OnMemoryNode)getNode();
 		NodeData<Node> d = new NodeData<Node>(thisNode,thisNode);
 		d.add(newNode);
-		
 		cloneAndTransmit(d);
 		
-		OnMemoryMonotonicTreeNode tn = getCache(newID.getFamilyID());
-		
+		OnMemoryMonotonicTreeNode tn = new OnMemoryMonotonicTreeNode(newNode,this,m_table);
 		return tn;
 	}
+	
+	@Override
+	public String toString()
+	{
+		return m_node.toString();
+	}
 }
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/memory/OnMemoryNode.java
--- a/src/treecms/memory/OnMemoryNode.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryNode.java	Tue Jul 12 14:39:35 2011 +0900
@@ -141,4 +141,10 @@
 	{
 		throw new UnsupportedOperationException(ERR_READONLY);
 	}
+	
+	@Override
+	public String toString()
+	{
+		return m_id.toString();
+	}
 }
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/test/AbstractForestTest.java
--- a/src/treecms/test/AbstractForestTest.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/test/AbstractForestTest.java	Tue Jul 12 14:39:35 2011 +0900
@@ -9,142 +9,18 @@
 import treecms.api.MonotonicTree;
 import treecms.api.MonotonicTreeNode;
 import treecms.api.NodeID;
-import treecms.api.SingleNode;
-import treecms.api.Tree;
-import treecms.api.TreeNode;
 import treecms.tree.util.NodeData;
 
-/**
- * Forest実装の基本的なテスト
- * @author shoshi
- */
 public abstract class AbstractForestTest
 {
 	public abstract Forest getInstance();
 	
 	@Test
-	public void testCreate()
-	{
-		Forest forest = getInstance();
-		
-		//正常にSingleNodeを作成できることを確認する（引数なし）
-		SingleNode test1 = forest.create();
-		Assert.assertNotNull(test1);
-		
-		//正常にSingleNodeを作成できることを確認する（引数あり）
-		NodeData<SingleNode> d = new NodeData<SingleNode>();
-		d.add(forest.create());
-		d.put(ByteBuffer.wrap("name".getBytes()),ByteBuffer.wrap("value".getBytes()));
-		SingleNode test2 = forest.create(d);
-		Assert.assertNotNull(test2);
-		
-		//指定したNodeData<SingleNode>が正しく継承されているか確認する
-		List<SingleNode> list1 = d.getList();
-		List<SingleNode> list2 = test2.getList();
-		Assert.assertEquals(true,list1.equals(list2));
-		
-		Map<ByteBuffer,ByteBuffer> map1 = d.asMap();
-		Map<ByteBuffer,ByteBuffer> map2 = test2.asMap();
-		Assert.assertEquals(true,map1.equals(map2));
-	}
-	
-	@Test
-	public void testGet()
-	{
-		Forest forest = getInstance();
-		SingleNode newNode = forest.create();
-		NodeID newID = newNode.getID();
-		
-		SingleNode test1 = forest.get(newID);
-		
-		//同じノードであることを確認する
-		Assert.assertEquals(newNode,test1);
-		
-		//forest.get(NodeID _id)にnullが渡されたときNullPointerExceptionが発生する
-		try{
-			forest.get(null);
-			Assert.fail("no NullPointerException occurs when call forest.get(null)");
-		}catch(NullPointerException _e){
-		}
-	
-		//存在しないNodeIDが指定された場合はnullである
-		NodeID updated = newID.update();
-		SingleNode test2 = forest.get(updated);
-		Assert.assertNull(test2);
-	}
-	
-	@Test
-	public void testGetTip()
-	{
-		Forest forest = getInstance();
-		
-		//SingleNodeを作成した時点で、最新版と比較し一致することを確認する
-		SingleNode newNode = forest.create();
-		NodeID newID = newNode.getID();
-		SingleNode tip = forest.getTip(newID.getUUID());
-		
-		Assert.assertEquals(newNode,tip);
-		
-		//同じUUIDを持つSingleNodeを登録すると、最新版が更新される
-		NodeData<SingleNode> d = new NodeData<SingleNode>(tip,tip);
-		SingleNode test1 = forest.create(tip.getID().update(),d);
-		tip = forest.getTip(test1.getID().getUUID());
-		
-		Assert.assertEquals(test1,tip);
-		
-		//nullが渡された場合は、NullPointerExceptionが発生する
-		try{
-			forest.getTip(null);
-			Assert.fail("no NullPointerException occurs when call forest.getTip(null)");
-		}catch(NullPointerException _e){
-			//OK
-		}
-	}
-	
-	@Test
-	public void testGetTree()
+	public void testGetMainTree()
 	{
 		Forest f = getInstance();
-		
-		//同一のForestから作成されたSingleNodeから正しくTreeが作成できるか確認する。
-		SingleNode n = f.create();
-		Tree t = f.getTree(n);
-		Assert.assertNotNull(t);
-		
-		//作成したTreeからTreeNodeのルートが取得できる。
-		TreeNode root = t.getRoot();
-		Assert.assertNotNull(t.getRoot());
-		
-		//取得したTreeNodeから引数に指定したSingleNodeが取得できるか確認する
-		Assert.assertEquals(n,root.getNode());
-	}
-	
-	@Test
-	public void testGetMonotonicTree()
-	{
-		Forest f = getInstance();
-		SingleNode newNode = f.create();
+		MonotonicTree t = f.getMainTree();
 		
-		Tree newTree = f.getTree(newNode);
-		MonotonicTree newMonoTree = f.getMonotonicTree(newTree);
-		Assert.assertNotNull(newMonoTree);
-		
-		MonotonicTreeNode m = newMonoTree.getRoot();
-		Assert.assertNotNull(m);
-		SingleNode n = m.getNode();
-		Assert.assertEquals(true,n.equals(newNode));
-		
-		Tree t2 = newMonoTree.getTree();
-		Assert.assertNotNull(t2);
-		Assert.assertEquals(true,t2.equals(t2));
-	}
-	
-	@Test
-	public void testGetMainTree()
-	{
-		Forest forest = getInstance();
-		Tree contents = forest.getMainTree();
-		
-		Assert.assertNotNull(contents);
+		Assert.assertNotNull(t);
 	}
 }
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/test/AbstractNodeTest.java
--- a/src/treecms/test/AbstractNodeTest.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/test/AbstractNodeTest.java	Tue Jul 12 14:39:35 2011 +0900
@@ -8,30 +8,17 @@
 import treecms.api.NodeID;
 import treecms.tree.util.NodeChildrenImpl;
 
-/**
- * Node実装の基本的なテスト
- * @author shoshi
- */
 public abstract class AbstractNodeTest
 {
-	/**
-	 * テストに用いるNodeを実装者は返す
-	 * @return Node
-	 */
 	public abstract Node getInstance();
 	
-	/**
-	 * NodeID取得のテスト
-	 */
 	@Test
 	public void testGetID()
 	{
+		Node n = getInstance();
 		Assert.assertNotNull(getInstance().getID());
 	}
 	
-	/**
-	 * Nodeのデータ(子供Nodeや属性のマップ)
-	 */
 	@Test
 	public void testGetData()
 	{
@@ -39,18 +26,12 @@
 		Assert.assertNotNull(getInstance().getAll());
 	}
 	
-	/**
-	 * NodeからForestを取得するテスト
-	 */
 	@Test
 	public void testGetForest()
 	{
 		Assert.assertNotNull(getInstance().getForest());
 	}
 	
-	/**
-	 * Nodeに子供Nodeを追加するテスト
-	 */
 	@Test
 	public void testAddChildren()
 	{
@@ -73,9 +54,6 @@
 		}
 	}
 	
-	/**
-	 * Nodeにセットした属性を取り出すテスト
-	 */
 	@Test
 	public void testSetAndGetAttribute()
 	{
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/test/CopyOnWriteTreeMapTest1.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/test/CopyOnWriteTreeMapTest1.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,46 @@
+package treecms.test;
+
+import java.util.List;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import treecms.tree.util.CopyOnWriteTreeMap;
+
+public class CopyOnWriteTreeMapTest1
+{
+	public static void main(String _args[])
+	{
+		ExecutorService service = Executors.newFixedThreadPool(5);
+		
+		
+	}
+	
+	private static class ReaderTask implements Runnable
+	{
+		private final CopyOnWriteTreeMap m_map;
+		
+		public ReaderTask(CopyOnWriteTreeMap _map,List<String> _keys)
+		{
+			m_map = _map;
+		}
+		
+		@Override
+		public void run()
+		{
+		}
+	}
+	
+	private static class WriterTask implements Runnable
+	{
+		private final CopyOnWriteTreeMap<String,String> m_map;
+		
+		public WriterTask(CopyOnWriteTreeMap<String,String> _map)
+		{
+			m_map = _map;
+		}
+		
+		@Override
+		public void run()
+		{
+		}
+	}
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/test/ReentrantLockTest1.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/test/ReentrantLockTest1.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,39 @@
+package treecms.test;
+
+import java.io.IOException;
+import java.util.concurrent.locks.ReentrantLock;
+
+public class ReentrantLockTest1
+{
+	public static void main(String _args[]) throws Exception
+	{
+		final ReentrantLock lock = new ReentrantLock();
+		
+		Runnable r = new Runnable(){
+			@Override
+			public void run()
+			{
+				String name = Thread.currentThread().getName();
+				synchronized(lock){
+					System.out.println(name + ": acquire lock");
+					try {
+						System.in.read();
+						System.out.println(name + ": is dead");
+						return;
+					} catch (IOException _e) {
+						_e.printStackTrace();
+					}
+				}
+			}
+		};
+		
+		Thread th1 = new Thread(r);
+		Thread th2 = new Thread(r);
+		
+		th1.start();
+		th2.start();
+		
+		th1.join();
+		th2.join();
+	}
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/id/IncrementalID.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/id/IncrementalID.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,81 @@
+package treecms.tree.id;
+
+import java.util.UUID;
+import java.util.concurrent.atomic.AtomicLong;
+
+import treecms.api.NodeID;
+
+public class IncrementalID implements NodeID
+{
+	private final AtomicLong m_counter;
+	private final String m_fid;
+	private final long m_version;
+	
+	public IncrementalID(String _fid)
+	{
+		this(_fid,new AtomicLong(0));
+	}
+	
+	private IncrementalID(String _fid,AtomicLong _counter)
+	{
+		m_fid = _fid;
+		m_counter = _counter;
+		m_version = _counter.getAndIncrement();
+	}
+	
+	@Override
+	public NodeID create()
+	{
+		String fid = UUID.randomUUID().toString();
+		IncrementalID newID = new IncrementalID(fid);
+		return newID;
+	}
+
+	@Override
+	public NodeID update()
+	{
+		IncrementalID newID = new IncrementalID(m_fid,m_counter);
+		return newID;
+	}
+
+	@Override
+	public String getFamilyID()
+	{
+		return m_fid;
+	}
+
+	@Override
+	public String getVersion()
+	{
+		return Long.toHexString(m_counter.get());
+	}
+	
+	@Override
+	public boolean equals(Object _obj)
+	{
+		if(this == _obj){
+			return true;
+		}
+		
+		if(_obj instanceof IncrementalID){
+			IncrementalID id = (IncrementalID)_obj;
+			if(id.m_version == m_version && id.m_fid.equals(m_fid)){
+				return true;
+			}
+		}
+		return false;
+	}
+	
+	@Override
+	public String toString()
+	{
+		return m_fid + "@" + Long.toHexString(m_version);
+	}
+
+	@Override
+	public boolean isFamily(NodeID _id)
+	{
+		return m_fid.equals(_id.getFamilyID());
+	}
+
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/CopyOnWriteLinkedList.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/CopyOnWriteLinkedList.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,9 @@
+package treecms.tree.util;
+
+public class CopyOnWriteLinkedList<T>
+{
+	public CopyOnWriteLinkedList()
+	{
+		
+	}
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/CopyOnWriteTreeMap.java
--- a/src/treecms/tree/util/CopyOnWriteTreeMap.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/tree/util/CopyOnWriteTreeMap.java	Tue Jul 12 14:39:35 2011 +0900
@@ -1,5 +1,6 @@
 package treecms.tree.util;
 
+import java.io.IOException;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.LinkedList;
@@ -20,22 +21,36 @@
 	private volatile TreeNode<K,V> m_write;
 	
 	private final Object m_writeLock;
-	public static void main(String _args[]) throws InterruptedException
+	public static void main(String _args[]) throws InterruptedException, IOException
 	{
-		//final CopyOnWriteTreeMap<String,String> map = new CopyOnWriteTreeMap<String,String>();
-		final Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
+		System.in.read();
+		
+		final CopyOnWriteTreeMap<String,String> map = new CopyOnWriteTreeMap<String,String>();
+		//final Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
 		final LinkedList<String> keys = new LinkedList<String>();
 		
 		Random r = new Random();
-		for(int i = 0;i < 5000;i ++){
+		for(int i = 0;i < 10000;i ++){
 			String str = Long.toHexString(r.nextLong());
-			map.put(str,str);
 			keys.add(str);
 		}
 		
 		ExecutorService service = Executors.newFixedThreadPool(5);
 		
-		Callable<Object> task = new Callable<Object>(){
+		Callable<Object> writer = new Callable<Object>(){
+			@Override
+			public Object call() throws Exception
+			{
+				long mill = System.currentTimeMillis();
+				for(String str : keys){
+					map.put(str,str);
+				}
+				System.out.println("Writer :"+ (System.currentTimeMillis() - mill));
+				return null;
+			}
+		};
+		
+		Callable<Object> reader = new Callable<Object>(){
 			@Override
 			public Object call() throws Exception
 			{
@@ -43,27 +58,23 @@
 				for(String str : keys){
 					map.get(str);
 				}
-				System.out.println(System.currentTimeMillis() - mill);
+				System.out.println("Reader :"+ (System.currentTimeMillis() - mill));
 				
 				return null;
 			}
 		};
 		
-		service.submit(task);
-		service.submit(task);
-		service.submit(task);
-		service.submit(task);
-		service.submit(task);
+		service.submit(reader);
+		service.submit(writer);
+		service.submit(writer);
+		service.submit(writer);
+		service.submit(writer);
+		service.submit(writer);
 		
 		service.shutdown();
 		service.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
 		
-		for(String key : keys){
-			String val = map.get(key);
-			if(val == null){
-				System.out.println("val("+key+") is null");
-			}
-		}
+		System.in.read();
 	}
 	
 	public CopyOnWriteTreeMap()
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/CopyOnWriteTreeMap2.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/CopyOnWriteTreeMap2.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,247 @@
+package treecms.tree.util;
+
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Random;
+import java.util.TreeMap;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.concurrent.locks.ReentrantLock;
+
+public class CopyOnWriteTreeMap2<K extends Comparable<K>,V>
+{
+	private volatile TreeNode<K,V> m_read;
+	private final AtomicReference<TreeNode<K,V>> m_write;
+	
+	public static void main(String _args[]) throws InterruptedException
+	{
+		final CopyOnWriteTreeMap<String,String> map = new CopyOnWriteTreeMap<String,String>();
+		//final Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
+		//final CopyOnWriteTreeMap2<String,String> map = new CopyOnWriteTreeMap2<String,String>();
+		final LinkedList<String> keys = new LinkedList<String>();
+		
+		Random r = new Random();
+		for(int i = 0;i < 5000;i ++){
+			String str = Long.toHexString(r.nextLong());
+		//	map.put(str,str);
+			keys.add(str);
+		}
+		
+		ExecutorService service = Executors.newFixedThreadPool(5);
+		
+		Callable<Object> task = new Callable<Object>(){
+			@Override
+			public Object call() throws Exception
+			{
+				long mill = System.currentTimeMillis();
+				for(String str : keys){
+					map.put(str,str);
+				}
+				System.out.println(System.currentTimeMillis() - mill);
+				
+				return null;
+			}
+		};
+		
+		service.submit(task);
+		service.submit(task);
+		service.submit(task);
+		service.submit(task);
+		service.submit(task);
+		
+		service.shutdown();
+		service.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
+		
+		for(String key : keys){
+			String val = map.get(key);
+			if(!val.equals(key)){
+				System.out.println("val("+key+") is ok");
+			}
+		}
+	}
+	
+	public CopyOnWriteTreeMap2()
+	{
+		m_read = null;
+		m_write = new AtomicReference<TreeNode<K,V>>();
+	}
+	
+	public V get(K _key)
+	{
+		if(m_read == null){
+			return null;
+		}
+		
+		TreeNode<K,V> tn = m_read;
+		
+		while(tn != null){
+			K key = tn.key();
+			int result = key.compareTo(_key);
+			if(result == 0){
+				//find
+				return tn.value();
+			}else if(result > 0){
+				//go right
+				TreeNode<K,V> r = tn.getRight();
+				tn = r;
+			}else{
+				//go left
+				TreeNode<K,V> l = tn.getLeft();
+				tn = l;
+			}
+		}
+		
+		return null;
+	}
+	
+	public void put(K _key,V _value) throws InterruptedException
+	{
+		TreeNode<K,V> root;
+		TreeNode<K,V> cur;
+		while(true){
+			root = m_write.get();
+			if(root == null){
+				root = new TreeNode<K,V>(_key,_value);
+				root.unlock();
+				if(m_write.compareAndSet(null,root)){
+					m_read = root;
+					return;
+				}
+				continue;
+			}
+		
+			cur = root.copy();
+			if(m_write.compareAndSet(root,cur)){
+				break;
+			}
+		}
+		
+		while(true){
+			K key = cur.key(); 
+			int result = key.compareTo(_key);
+			
+			if(result > 0){
+				TreeNode<K,V> r = cur.getRight();
+				if(r == null){
+					r = new TreeNode<K,V>(_key,_value);
+					cur.setRight(r);
+					r.unlock();
+					cur.unlock();
+					break;
+				}
+				TreeNode<K,V> cp = r.copy();
+				cur.setRight(cp);
+				cur.unlock();
+				cur = cp;
+				
+			}else if(result < 0){
+				TreeNode<K,V> l = cur.getLeft();
+				if(l == null){
+					l = new TreeNode<K,V>(_key,_value);
+					cur.setLeft(l);
+					l.unlock();
+					cur.unlock();
+					break;
+				}
+				TreeNode<K,V> cp = l.copy();
+				cur.setLeft(cp);
+				cur.unlock();
+				cur = cp;
+			}else{
+				cur.setValue(_value);
+				cur.unlock();
+				m_read = root;
+				return;
+			}
+		}
+		
+		m_read = root;
+	}
+	
+	private static class TreeNode<K,V>
+	{
+		TreeNode<K,V> m_left;
+		TreeNode<K,V> m_right;
+		
+		private K m_key;
+		private V m_value;
+		private volatile boolean m_flag;
+		private final CountDownLatch m_latch;
+		
+		public TreeNode(K _key,V _value)
+		{
+			this(_key,_value,null,null);
+		}
+		
+		private TreeNode(K _key,V _value,TreeNode<K,V> _left,TreeNode<K,V> _right)
+		{
+			m_key = _key;
+			m_value = _value;
+			m_left = _left;
+			m_right = _right;
+			m_latch = new CountDownLatch(1);
+			m_flag = true;
+		}
+		
+		public K key()
+		{
+			return m_key;
+		}
+		
+		public V value()
+		{
+			return m_value;
+		}
+		
+		public void setValue(V _value)
+		{
+			m_value = _value;
+		}
+		
+		public void setKey(K _key)
+		{
+			m_key = _key;
+		}
+	
+		public void setLeft(TreeNode<K,V> _left)
+		{
+			m_left = _left;
+		}
+		
+		public void setRight(TreeNode<K,V> _right)
+		{
+			m_right = _right;
+		}
+		
+		public TreeNode<K,V> getLeft()
+		{
+			return m_left;
+		}
+		
+		public TreeNode<K,V> getRight()
+		{
+			return m_right;
+		}
+		
+		public void unlock() throws InterruptedException
+		{
+			m_flag = false;
+			m_latch.countDown();
+		}
+		
+		public TreeNode<K,V> copy() throws InterruptedException
+		{
+			if(m_flag){
+				m_latch.await();
+			}
+			return new TreeNode<K,V>(m_key,m_value,m_left,m_right);
+		}
+	}
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/LockableNodeTable.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/LockableNodeTable.java	Tue Jul 12 14:39:35 2011 +0900
@@ -0,0 +1,73 @@
+package treecms.tree.util;
+
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
+import treecms.api.Node;
+import treecms.api.NodeID;
+import treecms.api.NodeTable;
+
+public class LockableNodeTable implements NodeTable
+{
+	private final ConcurrentMap<NodeID,Node> m_nodes;
+	private final ConcurrentMap<String,LockableReference<Node>> m_tips;
+	
+	public LockableNodeTable()
+	{
+		m_nodes = new ConcurrentHashMap<NodeID,Node>();
+		m_tips = new ConcurrentHashMap<String,LockableReference<Node>>();
+	}
+
+	@Override
+	public void register(Node _newNode)
+	{
+		NodeID id = _newNode.getID();
+		m_nodes.put(id,_newNode);
+		
+		LockableReference<Node> ref = m_tips.putIfAbsent(id.getFamilyID(),new LockableReference<Node>(_newNode));
+		if(ref != null){
+			ref.lock();
+			ref.put(_newNode);
+			ref.unlock();
+		}
+	}
+
+	@Override
+	public Node get(NodeID _id)
+	{
+		return m_nodes.get(_id);
+	}
+
+	@Override
+	public Node tip(String _fid)
+	{
+		LockableReference<Node> ref = m_tips.get(_fid);
+		if(ref == null){
+			return null;
+		}
+		return ref.get();
+	}
+	
+	public boolean unlock(String _fid)
+	{
+		LockableReference<Node> ref = m_tips.get(_fid);
+		
+		if(ref == null){
+			return false;
+		}
+		
+		ref.unlock();
+		return true;
+	}
+	
+	public boolean lock(String _fid)
+	{
+		LockableReference<Node> ref = m_tips.get(_fid);
+		if(ref == null){
+			return false;
+		}
+		
+		ref.lock();
+		return true;
+	}
+
+}
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/NodeChildrenImpl.java
--- a/src/treecms/tree/util/NodeChildrenImpl.java	Sun Jun 12 20:41:20 2011 +0900
+++ b/src/treecms/tree/util/NodeChildrenImpl.java	Tue Jul 12 14:39:35 2011 +0900
@@ -76,7 +76,7 @@
 			for(int i = 0;i < size;i ++){
 				T n = m_list.get(i);
 				NodeID nid = n.getID();
-				if(nid.isFamily(nid)){
+				if(nid.isFamily(_node.getID())){
 					m_list.set(i,_node);
 					return old;
 				}
@@ -104,10 +104,9 @@
 		
 		if(Collections.disjoint(getFamilyIDSet(),_list.getFamilyIDSet())){
 		
-			HashMap<String,T> map = new HashMap<String,T>();
 			for(T item : _list.getList()){
 				NodeID id = item.getID();
-				map.put(id.getFamilyID(),item);
+				m_map.put(id.getFamilyID(),item);
 			}
 			
 			return m_list.addAll(_list.getList());
@@ -142,13 +141,16 @@
 	@Override
 	public synchronized boolean contains(NodeID _id)
 	{
-		T n = m_map.get(_id);
+		T n = m_map.get(_id.getFamilyID());
 		if(n == null){
 			return false;
 		}
 		
 		NodeID id = n.getID();
-		return id.equals(_id);
+		
+		String fid1 = id.getFamilyID();
+		String fid2 = _id.getFamilyID();
+		return fid1.equals(fid2);
 	}
 	
 	@Override
@@ -212,4 +214,10 @@
 		}
 		return false;
 	}
+	
+	@Override
+	public String toString()
+	{
+		return m_list.toString();
+	}
 }
diff -r 68021f7091e1 -r c1e7ec6b3d44 src/treecms/tree/util/NodeTableImpl.java
--- a/src/treecms/tree/util/NodeTableImpl.java	Sun Jun 12 20:41:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,40 +0,0 @@
-package treecms.tree.util;
-
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentMap;
-import treecms.api.Node;
-import treecms.api.NodeID;
-import treecms.api.NodeTable;
-
-public class NodeTableImpl implements NodeTable
-{
-	private final ConcurrentMap<NodeID,Node> m_nodes;
-	private final ConcurrentMap<String,Node> m_tips;
-	
-	public NodeTableImpl()
-	{
-		m_nodes = new ConcurrentHashMap<NodeID,Node>();
-		m_tips = new ConcurrentHashMap<String,Node>();
-	}
-
-	@Override
-	public void register(Node _newNode)
-	{
-		NodeID id = _newNode.getID();
-		m_nodes.put(id,_newNode);
-		m_tips.put(id.getFamilyID(),_newNode);
-	}
-
-	@Override
-	public Node get(NodeID _id)
-	{
-		return m_nodes.get(_id);
-	}
-
-	@Override
-	public Node tip(String _fid)
-	{
-		return m_tips.get(_fid);
-	}
-
-}