# HG changeset patch
# User shoshi
# Date 1307878880 -32400
# Node ID 68021f7091e1ebf8cbe6083d7b895a4dc836c8ae
# Parent  77a894c0b91913f485d997e62096b9fa0e8469e0
commit

diff -r 77a894c0b919 -r 68021f7091e1 src/treecms/memory/OnMemoryMonotonicTreeNode.java
--- a/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Thu Jun 09 01:03:48 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Sun Jun 12 20:41:20 2011 +0900
@@ -23,6 +23,7 @@
 	private final ConcurrentMap<String,MonotonicTreeNode> m_cache;
 	
 	private final OnMemoryNode m_node;
+	private final LockableReference<OnMemoryNode> m_tip;
 	
 	public OnMemoryMonotonicTreeNode(OnMemoryNode _node,OnMemoryMonotonicTreeNode _parent,NodeTable _table)
 	{
diff -r 77a894c0b919 -r 68021f7091e1 src/treecms/test/SynchronizedTest1.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/test/SynchronizedTest1.java	Sun Jun 12 20:41:20 2011 +0900
@@ -0,0 +1,51 @@
+package treecms.test;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+
+public class SynchronizedTest1
+{
+	public static void main(String _args[]) throws InterruptedException, IOException
+	{
+		Object lock = new Object();
+		
+		new MyThread(lock).start();
+		new MyThread(lock).start();
+		new MyThread(lock).start();
+		new MyThread(lock).start();
+		new MyThread(lock).start();
+		new MyThread(lock).start();
+		
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		br.readLine();
+		
+		synchronized(lock){
+			lock.notifyAll();
+		}
+		
+		Thread.sleep(100);
+	}
+	
+	private static class MyThread extends Thread
+	{
+		private final Object m_lock;
+		
+		public MyThread(Object _lock)
+		{
+			m_lock = _lock;
+		}
+		
+		public void run()
+		{
+			synchronized(m_lock){
+				try{
+					m_lock.wait();
+					System.out.println("done wating..");
+				}catch(InterruptedException _e){
+					_e.printStackTrace();
+				}
+			}
+		}
+	}
+}
diff -r 77a894c0b919 -r 68021f7091e1 src/treecms/tree/util/CopyOnWriteTreeMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/CopyOnWriteTreeMap.java	Sun Jun 12 20:41:20 2011 +0900
@@ -0,0 +1,239 @@
+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.locks.ReentrantLock;
+
+public class CopyOnWriteTreeMap<K extends Comparable<K>,V>
+{
+	private volatile TreeNode<K,V> m_read;
+	private volatile TreeNode<K,V> m_write;
+	
+	private final Object m_writeLock;
+	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 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.get(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 == null){
+				System.out.println("val("+key+") is null");
+			}
+		}
+	}
+	
+	public CopyOnWriteTreeMap()
+	{
+		m_read = m_write = null;
+		m_writeLock = new Object();
+	}
+	
+	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> cur;
+		synchronized(m_writeLock){
+			if(m_write == null){
+				m_write = new TreeNode<K,V>(_key,_value);
+				m_write.unlock();
+				m_read = m_write;
+				return;
+			}
+		
+			m_write = m_write.copy();
+			cur = m_write;
+		}
+		
+		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 = m_write;
+				return;
+			}
+		}
+		
+		m_read = m_write;
+	}
+	
+	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 77a894c0b919 -r 68021f7091e1 src/treecms/tree/util/LockableReference.java
--- a/src/treecms/tree/util/LockableReference.java	Thu Jun 09 01:03:48 2011 +0900
+++ b/src/treecms/tree/util/LockableReference.java	Sun Jun 12 20:41:20 2011 +0900
@@ -1,30 +1,77 @@
 package treecms.tree.util;
 
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.concurrent.atomic.AtomicReference;
 import java.util.concurrent.locks.ReentrantLock;
 
 public class LockableReference<V> 
 {
-	private volatile V m_ref;
-	private volatile ReentrantLock m_lock;
+	public static void main(String _args[]) throws InterruptedException
+	{
+		//test code for LockableReference<V>
+		
+		Integer i = new Integer(10);
+		final LockableReference<Integer> ref = new LockableReference<Integer>(i);
+		
+		Runnable r = new Runnable(){
+			@Override
+			public void run()
+			{
+				String name = Thread.currentThread().getName();
+				System.out.println(name + ": acquire lock");
+				ref.lock();
+				System.out.println(name + ": locked");
+				System.out.println(name + ": ref is " + ref.get());
+				ref.put(2);
+				BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+				try {
+					br.readLine();
+				}catch(IOException _e){
+					_e.printStackTrace();
+				}
+				ref.unlock();
+			}
+		};
+		
+		Thread th1 = new Thread(r);
+		Thread th2 = new Thread(r);
+		
+		th1.start();
+		th2.start();
+		
+		th1.join();
+		th2.join();
+	}
+	
+	private final AtomicReference<V> m_ref;
+	private final ReentrantLock m_lock;
 	
 	public LockableReference(V _ref)
 	{
-		m_ref = _ref;
-		m_lock = new ReentrantLock();
+		m_ref = new AtomicReference<V>(_ref);
+		m_lock = new ReentrantLock(true);
 	}
 	
 	public V get()
 	{
+		V ret;
 		m_lock.lock();
-		V ref = m_ref;
+		ret = m_ref.get();
 		m_lock.unlock();
-		return ref;
+		return ret;
+	}
+	
+	public boolean isLocked()
+	{
+		return m_lock.isLocked();
 	}
 	
 	public void put(V _ref)
 	{
 		m_lock.lock();
-		m_ref = _ref;
+		m_ref.set(_ref);
 		m_lock.unlock();
 	}