Mercurial > hg > Members > shoshi > TreeCMSv2
changeset 24:68021f7091e1
commit
author | shoshi |
---|---|
date | Sun, 12 Jun 2011 20:41:20 +0900 |
parents | 77a894c0b919 |
children | c1e7ec6b3d44 |
files | src/treecms/memory/OnMemoryMonotonicTreeNode.java src/treecms/test/SynchronizedTest1.java src/treecms/tree/util/CopyOnWriteTreeMap.java src/treecms/tree/util/LockableReference.java |
diffstat | 4 files changed, 345 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- 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) {
--- /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(); + } + } + } + } +}
--- /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); + } + } +}
--- 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(); }