29ac787a30f343af886277efac700688c6cf244d
[idea/community.git] / platform / util / src / com / intellij / openapi / util / UserDataHolderBase.java
1 /*
2  * Copyright 2000-2009 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.openapi.util;
17
18
19 import com.intellij.util.concurrency.AtomicFieldUpdater;
20 import com.intellij.util.containers.StripedLockConcurrentHashMap;
21 import org.jetbrains.annotations.NotNull;
22 import org.jetbrains.annotations.Nullable;
23 import org.jetbrains.annotations.TestOnly;
24
25 import java.util.ConcurrentModificationException;
26 import java.util.Map;
27 import java.util.concurrent.ConcurrentMap;
28
29 public class UserDataHolderBase implements UserDataHolderEx, Cloneable {
30   private static final Key<Map<Key, Object>> COPYABLE_USER_MAP_KEY = Key.create("COPYABLE_USER_MAP_KEY");
31
32   /**
33    * Concurrent writes to this field are via CASes only, using the {@link updater}
34    * When map becomes empty, this field set to null atomically
35    *
36    * Basic state transitions are as follows:
37    *
38    * (adding keyvalue)            (putUserData(key,value))
39    * [myUserMap=null]                  ->              [myUserMap=(key->value)]
40    *
41    * (adding another)             (putUserData(key2,value2))
42    * [myUserMap=(key->value)]          ->              [myUserMap=(key->value, key2->value2)]
43    *
44    * (removing keyvalue)          (putUserData(k2,null))
45    * [myUserMap=(key->value, k2->v2)]  ->              [myUserMap=(key->value)]
46    *
47    * (removing last entry)        (putUserData(key,null))
48    * [myUserMap=(key->value)]          ->              [myUserMap=null]
49    *
50    */
51   private volatile ConcurrentMap<Key, Object> myUserMap = null;
52
53   protected Object clone() {
54     try {
55       UserDataHolderBase clone = (UserDataHolderBase)super.clone();
56       clone.myUserMap = null;
57       copyCopyableDataTo(clone);
58       return clone;
59     }
60     catch (CloneNotSupportedException e) {
61       throw new RuntimeException(e);
62
63     }
64   }
65
66   @TestOnly
67   public String getUserDataString() {
68     final ConcurrentMap<Key, Object> userMap = myUserMap;
69     if (userMap == null) {
70       return "";
71     }
72     final Map copyableMap = getUserData(COPYABLE_USER_MAP_KEY);
73     return userMap.toString() + (copyableMap == null ? "" : copyableMap.toString());
74   }
75
76   public void copyUserDataTo(UserDataHolderBase other) {
77     ConcurrentMap<Key, Object> map = myUserMap;
78     if (map == null) {
79       other.myUserMap = null;
80     }
81     else {
82       ConcurrentMap<Key, Object> fresh = createDataMap(map.size());
83       fresh.putAll(map);
84       other.myUserMap = fresh;
85     }
86   }
87
88   public <T> T getUserData(@NotNull Key<T> key) {
89     final Map<Key, Object> map = myUserMap;
90     return map == null ? null : (T)map.get(key);
91   }
92
93   public <T> void putUserData(@NotNull Key<T> key, @Nullable T value) {
94     while (true) {
95       try {
96         if (value == null) {
97           ConcurrentMap<Key, Object> map = myUserMap;
98           if (map == null) break;
99           T previous = (T)map.remove(key);
100           boolean removed = previous != null;
101           if (removed) {
102             nullifyMapFieldIfEmpty();
103           }
104         }
105         else {
106           Map<Key, Object> map = getOrCreateMap();
107           map.put(key, value);
108         }
109         break;
110       }
111       catch (ConcurrentModificationException ignored) {
112       }
113     }
114   }
115
116   protected ConcurrentMap<Key, Object> createDataMap(int initialCapacity) {
117     return new StripedLockConcurrentHashMap<Key, Object>(initialCapacity);
118   }
119
120   public <T> T getCopyableUserData(Key<T> key) {
121     return getCopyableUserDataImpl(key);
122   }
123
124   protected final <T> T getCopyableUserDataImpl(Key<T> key) {
125     Map map = getUserData(COPYABLE_USER_MAP_KEY);
126     return map == null ? null : (T)map.get(key);
127   }
128
129   public <T> void putCopyableUserData(Key<T> key, T value) {
130     putCopyableUserDataImpl(key, value);
131   }
132
133   private Map<Key, Object> getOrCreateCopyableMap(boolean create) {
134     Map<Key, Object> copyMap = getUserData(COPYABLE_USER_MAP_KEY);
135     if (copyMap == null && create) {
136       copyMap = createDataMap(1);
137       copyMap = putUserDataIfAbsent(COPYABLE_USER_MAP_KEY, copyMap);
138     }
139
140     return copyMap;
141   }
142
143   protected final <T> void putCopyableUserDataImpl(Key<T> key, T value) {
144     while (true) {
145       try {
146         Map<Key, Object> copyMap = getOrCreateCopyableMap(value != null);
147         if (copyMap == null) break;
148
149         if (value == null) {
150           copyMap.remove(key);
151           if (copyMap.isEmpty()) {
152             ((StripedLockConcurrentHashMap<Key, Object>)copyMap).blockModification();
153             ConcurrentMap<Key, Object> newCopyMap;
154             if (copyMap.isEmpty()) {
155               newCopyMap = null;
156             }
157             else {
158               newCopyMap = createDataMap(copyMap.size());
159               newCopyMap.putAll(copyMap);
160             }
161             boolean replaced = replace(COPYABLE_USER_MAP_KEY, copyMap, newCopyMap);
162             if (!replaced) continue;
163           }
164         }
165         else {
166           copyMap.put(key, value);
167         }
168         break;
169       }
170       catch (ConcurrentModificationException ignored) {
171         // someone blocked modification, retry
172       }
173     }
174   }
175
176   private ConcurrentMap<Key, Object> getOrCreateMap() {
177     while (true) {
178       ConcurrentMap<Key, Object> map = myUserMap;
179       if (map != null) return map;
180       map = createDataMap(2);
181       boolean updated = updater.compareAndSet(this, null, map);
182       if (updated) {
183         return map;
184       }
185     }
186   }
187
188   public <T> boolean replace(@NotNull Key<T> key, @Nullable T oldValue, @Nullable T newValue) {
189     while (true) {
190       try {
191         ConcurrentMap<Key, Object> map = getOrCreateMap();
192         if (oldValue == null) {
193           return newValue == null || map.putIfAbsent(key, newValue) == null;
194         }
195         if (newValue == null) {
196           boolean removed = map.remove(key, oldValue);
197           if (removed) {
198             nullifyMapFieldIfEmpty();
199           }
200           return removed;
201         }
202         return map.replace(key, oldValue, newValue);
203       }
204       catch (ConcurrentModificationException ignored) {
205         // someone blocked modification, retry
206       }
207     }
208   }
209                                                             
210   @NotNull
211   public <T> T putUserDataIfAbsent(@NotNull final Key<T> key, @NotNull final T value) {
212     Object v = getOrCreateMap().get(key);
213     if (v != null) return (T)v;
214     while (true) {
215       try {
216         T prev = (T)getOrCreateMap().putIfAbsent(key, value);
217         return prev == null ? value : prev;
218       }
219       catch (ConcurrentModificationException ignored) {
220         // someone blocked modification, retry
221       }
222     }
223   }
224
225   public void copyCopyableDataTo(@NotNull UserDataHolderBase clone) {
226     Map<Key, Object> copyableMap = getUserData(COPYABLE_USER_MAP_KEY);
227     if (copyableMap != null) {
228       ConcurrentMap<Key, Object> copy = createDataMap(copyableMap.size());
229       copy.putAll(copyableMap);
230       copyableMap = copy;
231     }
232     clone.putUserData(COPYABLE_USER_MAP_KEY, copyableMap);
233   }
234
235   protected void clearUserData() {
236     myUserMap = null;
237   }
238
239   private static final AtomicFieldUpdater<UserDataHolderBase, ConcurrentMap> updater = AtomicFieldUpdater.forFieldOfType(UserDataHolderBase.class, ConcurrentMap.class);
240   private void nullifyMapFieldIfEmpty() {
241     try {
242       while (true) {
243         StripedLockConcurrentHashMap<Key, Object> map = (StripedLockConcurrentHashMap<Key, Object>)myUserMap;
244         if (map == null || !map.isEmpty()) break;
245         map.blockModification(); // we block the map and either replace it with null or fail with replace, in both cases the map is thrown away
246         ConcurrentMap<Key, Object> newMap;
247         if (map.isEmpty()) {
248           newMap = null;
249         }
250         else {
251           // someone managed to add something in the meantime
252           // atomically replace the blocked map with newly created map filled with the data sneaked in
253           newMap = createDataMap(map.size());
254           newMap.putAll(map);
255         }
256         boolean replaced = updater.compareAndSet(this, map, newMap);
257         if (replaced) break;
258         // else someone has replaced map already and pushing back the changes is his responsibility
259       }
260     }
261     catch (ConcurrentModificationException ignored) {
262       // somebody has already blocked the map, back off  
263     }
264   }
265 }