Mercurial > hg > Members > shoshi > TreeCMSv2

comparison src/treecms/tree/util/CopyOnWriteTreeMap2.java @ 25:c1e7ec6b3d44

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Tue, 12 Jul 2011 14:39:35 +0900
parents
children
comparison
equal deleted inserted replaced
24:68021f7091e1 25:c1e7ec6b3d44
1 package treecms.tree.util;
2
3 import java.util.Collections;
4 import java.util.Comparator;
5 import java.util.LinkedList;
6 import java.util.Map;
7 import java.util.Random;
8 import java.util.TreeMap;
9 import java.util.concurrent.Callable;
10 import java.util.concurrent.ConcurrentLinkedQueue;
11 import java.util.concurrent.CountDownLatch;
12 import java.util.concurrent.ExecutorService;
13 import java.util.concurrent.Executors;
14 import java.util.concurrent.TimeUnit;
15 import java.util.concurrent.atomic.AtomicReference;
16 import java.util.concurrent.locks.ReentrantLock;
17
18 public class CopyOnWriteTreeMap2<K extends Comparable<K>,V>
19 {
20 private volatile TreeNode<K,V> m_read;
21 private final AtomicReference<TreeNode<K,V>> m_write;
22
23 public static void main(String _args[]) throws InterruptedException
24 {
25 final CopyOnWriteTreeMap<String,String> map = new CopyOnWriteTreeMap<String,String>();
26 //final Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
27 //final CopyOnWriteTreeMap2<String,String> map = new CopyOnWriteTreeMap2<String,String>();
28 final LinkedList<String> keys = new LinkedList<String>();
29
30 Random r = new Random();
31 for(int i = 0;i < 5000;i ++){
32 String str = Long.toHexString(r.nextLong());
33 // map.put(str,str);
34 keys.add(str);
35 }
36
37 ExecutorService service = Executors.newFixedThreadPool(5);
38
39 Callable<Object> task = new Callable<Object>(){
40 @Override
41 public Object call() throws Exception
42 {
43 long mill = System.currentTimeMillis();
44 for(String str : keys){
45 map.put(str,str);
46 }
47 System.out.println(System.currentTimeMillis() - mill);
48
49 return null;
50 }
51 };
52
53 service.submit(task);
54 service.submit(task);
55 service.submit(task);
56 service.submit(task);
57 service.submit(task);
58
59 service.shutdown();
60 service.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
61
62 for(String key : keys){
63 String val = map.get(key);
64 if(!val.equals(key)){
65 System.out.println("val("+key+") is ok");
66 }
67 }
68 }
69
70 public CopyOnWriteTreeMap2()
71 {
72 m_read = null;
73 m_write = new AtomicReference<TreeNode<K,V>>();
74 }
75
76 public V get(K _key)
77 {
78 if(m_read == null){
79 return null;
80 }
81
82 TreeNode<K,V> tn = m_read;
83
84 while(tn != null){
85 K key = tn.key();
86 int result = key.compareTo(_key);
87 if(result == 0){
88 //find
89 return tn.value();
90 }else if(result > 0){
91 //go right
92 TreeNode<K,V> r = tn.getRight();
93 tn = r;
94 }else{
95 //go left
96 TreeNode<K,V> l = tn.getLeft();
97 tn = l;
98 }
99 }
100
101 return null;
102 }
103
104 public void put(K _key,V _value) throws InterruptedException
105 {
106 TreeNode<K,V> root;
107 TreeNode<K,V> cur;
108 while(true){
109 root = m_write.get();
110 if(root == null){
111 root = new TreeNode<K,V>(_key,_value);
112 root.unlock();
113 if(m_write.compareAndSet(null,root)){
114 m_read = root;
115 return;
116 }
117 continue;
118 }
119
120 cur = root.copy();
121 if(m_write.compareAndSet(root,cur)){
122 break;
123 }
124 }
125
126 while(true){
127 K key = cur.key();
128 int result = key.compareTo(_key);
129
130 if(result > 0){
131 TreeNode<K,V> r = cur.getRight();
132 if(r == null){
133 r = new TreeNode<K,V>(_key,_value);
134 cur.setRight(r);
135 r.unlock();
136 cur.unlock();
137 break;
138 }
139 TreeNode<K,V> cp = r.copy();
140 cur.setRight(cp);
141 cur.unlock();
142 cur = cp;
143
144 }else if(result < 0){
145 TreeNode<K,V> l = cur.getLeft();
146 if(l == null){
147 l = new TreeNode<K,V>(_key,_value);
148 cur.setLeft(l);
149 l.unlock();
150 cur.unlock();
151 break;
152 }
153 TreeNode<K,V> cp = l.copy();
154 cur.setLeft(cp);
155 cur.unlock();
156 cur = cp;
157 }else{
158 cur.setValue(_value);
159 cur.unlock();
160 m_read = root;
161 return;
162 }
163 }
164
165 m_read = root;
166 }
167
168 private static class TreeNode<K,V>
169 {
170 TreeNode<K,V> m_left;
171 TreeNode<K,V> m_right;
172
173 private K m_key;
174 private V m_value;
175 private volatile boolean m_flag;
176 private final CountDownLatch m_latch;
177
178 public TreeNode(K _key,V _value)
179 {
180 this(_key,_value,null,null);
181 }
182
183 private TreeNode(K _key,V _value,TreeNode<K,V> _left,TreeNode<K,V> _right)
184 {
185 m_key = _key;
186 m_value = _value;
187 m_left = _left;
188 m_right = _right;
189 m_latch = new CountDownLatch(1);
190 m_flag = true;
191 }
192
193 public K key()
194 {
195 return m_key;
196 }
197
198 public V value()
199 {
200 return m_value;
201 }
202
203 public void setValue(V _value)
204 {
205 m_value = _value;
206 }
207
208 public void setKey(K _key)
209 {
210 m_key = _key;
211 }
212
213 public void setLeft(TreeNode<K,V> _left)
214 {
215 m_left = _left;
216 }
217
218 public void setRight(TreeNode<K,V> _right)
219 {
220 m_right = _right;
221 }
222
223 public TreeNode<K,V> getLeft()
224 {
225 return m_left;
226 }
227
228 public TreeNode<K,V> getRight()
229 {
230 return m_right;
231 }
232
233 public void unlock() throws InterruptedException
234 {
235 m_flag = false;
236 m_latch.countDown();
237 }
238
239 public TreeNode<K,V> copy() throws InterruptedException
240 {
241 if(m_flag){
242 m_latch.await();
243 }
244 return new TreeNode<K,V>(m_key,m_value,m_left,m_right);
245 }
246 }
247 }