Mercurial > hg > Members > shoshi > TreeCMSv2
view src/treecms/tree/util/CopyOnWriteTreeMap2.java @ 25:c1e7ec6b3d44
commit
author | Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 12 Jul 2011 14:39:35 +0900 |
parents | |
children |
line wrap: on
line source
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); } } }