Mercurial > hg > blitz_condensed
comparison src/com/go/trove/util/Depot.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
1 /* ==================================================================== | |
2 * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group | |
3 * ==================================================================== | |
4 * The Tea Software License, Version 1.1 | |
5 * | |
6 * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved. | |
7 * | |
8 * Redistribution and use in source and binary forms, with or without | |
9 * modification, are permitted provided that the following conditions | |
10 * are met: | |
11 * | |
12 * 1. Redistributions of source code must retain the above copyright | |
13 * notice, this list of conditions and the following disclaimer. | |
14 * | |
15 * 2. Redistributions in binary form must reproduce the above copyright | |
16 * notice, this list of conditions and the following disclaimer in | |
17 * the documentation and/or other materials provided with the | |
18 * distribution. | |
19 * | |
20 * 3. The end-user documentation included with the redistribution, | |
21 * if any, must include the following acknowledgment: | |
22 * "This product includes software developed by the | |
23 * Walt Disney Internet Group (http://opensource.go.com/)." | |
24 * Alternately, this acknowledgment may appear in the software itself, | |
25 * if and wherever such third-party acknowledgments normally appear. | |
26 * | |
27 * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must | |
28 * not be used to endorse or promote products derived from this | |
29 * software without prior written permission. For written | |
30 * permission, please contact opensource@dig.com. | |
31 * | |
32 * 5. Products derived from this software may not be called "Tea", | |
33 * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet", | |
34 * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior | |
35 * written permission of the Walt Disney Internet Group. | |
36 * | |
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED | |
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES | |
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
40 * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS | |
41 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | |
45 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
46 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
47 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
48 * ==================================================================== | |
49 * | |
50 * For more information about Tea, please see http://opensource.go.com/. | |
51 */ | |
52 | |
53 package com.go.trove.util; | |
54 | |
55 import java.util.*; | |
56 import com.go.trove.util.tq.*; | |
57 | |
58 /****************************************************************************** | |
59 * Depot implements a simple and efficient caching strategy. It is thread-safe, | |
60 * and it allows requests of different objects to occur concurrently. Depot | |
61 * is best suited as a front-end for accessing objects from a remote device, | |
62 * like a database. If the remote device is not responding, the Depot will | |
63 * continue to serve invalidated objects so that the requester may continue | |
64 * as normal. | |
65 * <p> | |
66 * Depot is designed as a cache in front of an object {@link Factory factory}. | |
67 * Objects may be invalidated, but they are not explicitly removed from the | |
68 * cache until a replacement has been provided by the factory. The factory is | |
69 * invoked from another thread, allowing for the requester to timeout and use | |
70 * an invalidated object. When the factory eventually finishes, its object will | |
71 * be cached. | |
72 * <p> | |
73 * By allowing for eventual completion of the factory, Depot enables | |
74 * applications to dynamically adjust to the varying performance and | |
75 * reliability of remote data providers. | |
76 * <p> | |
77 * Depot will never return an object or null that did not originate from the | |
78 * factory. When retrieving an object that wasn't found cached, a call to the | |
79 * factory will block until it is finished. | |
80 * <p> | |
81 * Objects may be invalided from the Depot | |
82 * {@link PerishablesFactory automatically}. This approach is based on a fixed | |
83 * time expiration and is somewhat inflexible. An ideal invalidation strategy | |
84 * requires asynchronous notification from the actual data providers. | |
85 * | |
86 * @author Brian S O'Neill, Travis Greer | |
87 * @version | |
88 * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 01/07/09 <!-- $--> | |
89 * @see MultiKey | |
90 */ | |
91 public class Depot { | |
92 private Factory mDefaultFactory; | |
93 private Map mValidCache; | |
94 private Map mInvalidCache; | |
95 private TransactionQueue mQueue; | |
96 private long mTimeout; | |
97 | |
98 private Map mRetrievers; | |
99 | |
100 private final Object mExpireLock = new Object(); | |
101 private Map mExpirations; | |
102 | |
103 /** | |
104 * @param factory Default factory from which objects are obtained | |
105 * @param validCache Map to use for caching valid objects | |
106 * @param invalidCache Map to use for caching invalid objects | |
107 * @param tq TransactionQueue for scheduling factory invocations. | |
108 * @param timeout Default timeout (in milliseconds) to apply to "get" | |
109 * method. | |
110 */ | |
111 public Depot(Factory factory, Map validCache, Map invalidCache, | |
112 TransactionQueue tq, long timeout) { | |
113 init(factory, validCache, invalidCache, tq, timeout); | |
114 } | |
115 | |
116 /** | |
117 * @param factory Default factory from which objects are obtained | |
118 * @param cacheSize Number of items guaranteed to be in cache, if negative, | |
119 * cache is completely disabled. | |
120 * @param tq TransactionQueue for scheduling factory invocations. | |
121 * @param timeout Default timeout (in milliseconds) to apply to "get" | |
122 * method. | |
123 */ | |
124 public Depot(Factory factory, int cacheSize, | |
125 TransactionQueue tq, long timeout) { | |
126 Map valid, invalid; | |
127 | |
128 if (cacheSize < 0) { | |
129 valid = Utils.VOID_MAP; | |
130 invalid = Utils.VOID_MAP; | |
131 } | |
132 else { | |
133 valid = new Cache(cacheSize); | |
134 invalid = new Cache((Cache)valid); | |
135 } | |
136 | |
137 init(factory, valid, invalid, tq, timeout); | |
138 } | |
139 | |
140 private void init(Factory factory, Map validCache, Map invalidCache, | |
141 TransactionQueue tq, long timeout) { | |
142 mDefaultFactory = factory; | |
143 mValidCache = Collections.synchronizedMap(validCache); | |
144 mInvalidCache = Collections.synchronizedMap(invalidCache); | |
145 mQueue = tq; | |
146 mTimeout = timeout; | |
147 | |
148 mRetrievers = Collections.synchronizedMap(new HashMap()); | |
149 } | |
150 | |
151 /** | |
152 * Returns the total number objects in the Depot. | |
153 */ | |
154 public int size() { | |
155 synchronized (mValidCache) { | |
156 return mValidCache.size() + mInvalidCache.size(); | |
157 } | |
158 } | |
159 | |
160 public boolean isEmpty() { | |
161 synchronized (mValidCache) { | |
162 return mValidCache.isEmpty() && mInvalidCache.isEmpty(); | |
163 } | |
164 } | |
165 | |
166 /** | |
167 * Returns the number of valid objects in the Depot. | |
168 */ | |
169 public int validSize() { | |
170 return mValidCache.size(); | |
171 } | |
172 | |
173 /** | |
174 * Returns the number of invalid objects in the Depot. | |
175 */ | |
176 public int invalidSize() { | |
177 return mInvalidCache.size(); | |
178 } | |
179 | |
180 /** | |
181 * Retrieve an object from the Depot. If the requested object is in the | |
182 * cache of valid objects, it is returned immediately. If the object is | |
183 * found in the cache of invalid objects, then it will be returned only if | |
184 * the factory cannot create a replacement in a timely manner. If the | |
185 * requested object is not in any cache at all, the factory is called to | |
186 * create the object, and the calling thread will block until the factory | |
187 * has finished. | |
188 * | |
189 * @param key key of object to retrieve | |
190 */ | |
191 public Object get(Object key) { | |
192 return get(mDefaultFactory, key, mTimeout); | |
193 } | |
194 | |
195 /** | |
196 * Retrieve an object from the Depot. If the requested object is in the | |
197 * cache of valid objects, it is returned immediately. If the object is | |
198 * found in the cache of invalid objects, then it will be returned only if | |
199 * the factory cannot create a replacement in a timely manner. If the | |
200 * requested object is not in any cache at all, the factory is called to | |
201 * create the object, and the calling thread will block until the factory | |
202 * has finished. | |
203 * | |
204 * @param key key of object to retrieve | |
205 * @param timeout max time (in milliseconds) to wait for an invalid value | |
206 * to be replaced from the factory, if negative, wait forever. Ignored if | |
207 * no cached value exists at all. | |
208 */ | |
209 public Object get(Object key, long timeout) { | |
210 return get(mDefaultFactory, key, timeout); | |
211 } | |
212 | |
213 /** | |
214 * Retrieve an object from the Depot. If the requested object is in the | |
215 * cache of valid objects, it is returned immediately. If the object is | |
216 * found in the cache of invalid objects, then it will be returned only if | |
217 * the factory cannot create a replacement in a timely manner. If the | |
218 * requested object is not in any cache at all, the factory is called to | |
219 * create the object, and the calling thread will block until the factory | |
220 * has finished. | |
221 * | |
222 * @param factory factory to use to retrieve object if not cached | |
223 * @param key key of object to retrieve | |
224 */ | |
225 public Object get(Factory factory, Object key) { | |
226 return get(factory, key, mTimeout); | |
227 } | |
228 | |
229 /** | |
230 * Retrieve an object from the Depot. If the requested object is in the | |
231 * cache of valid objects, it is returned immediately. If the object is | |
232 * found in the cache of invalid objects, then it will be returned only if | |
233 * the factory cannot create a replacement in a timely manner. If the | |
234 * requested object is not in any cache at all, the factory is called to | |
235 * create the object, and the calling thread will block until the factory | |
236 * has finished. | |
237 * | |
238 * @param factory factory to use to retrieve object if not cached | |
239 * @param key key of object to retrieve | |
240 * @param timeout max time (in milliseconds) to wait for an invalid value | |
241 * to be replaced from the factory, if negative, wait forever. Ignored if | |
242 * no cached value exists at all. | |
243 */ | |
244 public Object get(Factory factory, Object key, long timeout) { | |
245 Retriever r; | |
246 | |
247 key = Utils.intern(key); | |
248 synchronized (key) { | |
249 Object value = mValidCache.get(key); | |
250 if (value != null || mValidCache.containsKey(key)) { | |
251 validTest: { | |
252 if (value instanceof Perishable) { | |
253 if (!((Perishable)value).isValid()) { | |
254 break validTest; | |
255 } | |
256 } | |
257 | |
258 synchronized (mExpireLock) { | |
259 if (mExpirations == null) { | |
260 return value; | |
261 } | |
262 Long expire = (Long)mExpirations.get(key); | |
263 if (expire == null || | |
264 System.currentTimeMillis() <= expire.longValue()) { | |
265 // Value is still valid. | |
266 return value; | |
267 } | |
268 | |
269 // Value has expired. | |
270 mExpirations.remove(key); | |
271 } | |
272 } | |
273 | |
274 mValidCache.remove(key); | |
275 mInvalidCache.put(key, value); | |
276 | |
277 r = retrieve(factory, key, value, false); | |
278 } | |
279 else { | |
280 value = mInvalidCache.get(key); | |
281 | |
282 if (value != null || mInvalidCache.containsKey(key)) { | |
283 r = retrieve(factory, key, value, false); | |
284 } | |
285 else { | |
286 // Wait forever since not even an invalid value exists. | |
287 timeout = -1; | |
288 r = retrieve(factory, key, value, true); | |
289 } | |
290 } | |
291 | |
292 if (r == null) { | |
293 return value; | |
294 } | |
295 else { | |
296 return r.waitForValue(timeout); | |
297 } | |
298 } | |
299 } | |
300 | |
301 /** | |
302 * Invalidate the object referenced by the given key, if it is already | |
303 * cached in this Depot. Invalidated objects are not removed from the | |
304 * Depot until a replacement object has been successfully created from the | |
305 * factory. | |
306 * | |
307 * @param key key of object to invalidate | |
308 */ | |
309 public void invalidate(Object key) { | |
310 key = Utils.intern(key); | |
311 synchronized (key) { | |
312 if (mValidCache.containsKey(key)) { | |
313 Object value = mValidCache.remove(key); | |
314 mInvalidCache.put(key, value); | |
315 } | |
316 } | |
317 } | |
318 | |
319 /** | |
320 * Invalidates objects in the Depot, using a filter. Each key that the | |
321 * filter accepts is invalidated. | |
322 */ | |
323 public void invalidateAll(Filter filter) { | |
324 synchronized (mValidCache) { | |
325 Iterator it = mValidCache.entrySet().iterator(); | |
326 while (it.hasNext()) { | |
327 Map.Entry entry = (Map.Entry)it.next(); | |
328 Object key = entry.getKey(); | |
329 if (filter.accept(key)) { | |
330 it.remove(); | |
331 mInvalidCache.put(key, entry.getValue()); | |
332 } | |
333 } | |
334 } | |
335 } | |
336 | |
337 /** | |
338 * Invalidates all the objects in the Depot. | |
339 */ | |
340 public void invalidateAll() { | |
341 synchronized (mValidCache) { | |
342 synchronized (mInvalidCache) { | |
343 mInvalidCache.putAll(mValidCache); | |
344 mValidCache.clear(); | |
345 } | |
346 } | |
347 } | |
348 | |
349 /** | |
350 * Put a value into the Depot, bypassing the factory. Invalidating an | |
351 * object and relying on the factory to produce a new value is generally | |
352 * preferred. This method will notify any threads waiting on a factory to | |
353 * produce a value, but it will not disrupt the behavior of the factory. | |
354 * | |
355 * @param key key with which to associate the value. | |
356 * @param value value to be associated with key. | |
357 */ | |
358 public void put(Object key, Object value) { | |
359 key = Utils.intern(key); | |
360 synchronized (key) { | |
361 mInvalidCache.remove(key); | |
362 mValidCache.put(key, value); | |
363 Retriever r = (Retriever)mRetrievers.get(key); | |
364 if (r != null) { | |
365 // Bypass the factory produced value so that any waiting | |
366 // threads are notified. | |
367 r.bypassValue(value); | |
368 } | |
369 } | |
370 } | |
371 | |
372 /** | |
373 * Completely removes an item from the Depot's caches. Invalidating an | |
374 * object is preferred, and remove should be called only if the object | |
375 * should absolutely never be used again. | |
376 */ | |
377 public Object remove(Object key) { | |
378 key = Utils.intern(key); | |
379 synchronized (key) { | |
380 if (mValidCache.containsKey(key)) { | |
381 return mValidCache.remove(key); | |
382 } | |
383 if (mInvalidCache.containsKey(key)) { | |
384 return mInvalidCache.remove(key); | |
385 } | |
386 } | |
387 return null; | |
388 } | |
389 | |
390 /** | |
391 * Completely removes all the items from the Depot that the given filter | |
392 * accepts. | |
393 */ | |
394 public void removeAll(Filter filter) { | |
395 synchronized (mValidCache) { | |
396 synchronized (mInvalidCache) { | |
397 Iterator it = mValidCache.keySet().iterator(); | |
398 while (it.hasNext()) { | |
399 Object key = it.next(); | |
400 if (filter.accept(key)) { | |
401 it.remove(); | |
402 } | |
403 } | |
404 it = mInvalidCache.keySet().iterator(); | |
405 while (it.hasNext()) { | |
406 Object key = it.next(); | |
407 if (filter.accept(key)) { | |
408 it.remove(); | |
409 } | |
410 } | |
411 } | |
412 } | |
413 } | |
414 | |
415 /** | |
416 * Completely removes all items from the Depot's caches. Invalidating all | |
417 * the objects is preferred, and clear should be called only if all the | |
418 * cached objects should absolutely never be used again. | |
419 */ | |
420 public void clear() { | |
421 synchronized (mValidCache) { | |
422 synchronized (mInvalidCache) { | |
423 mValidCache.clear(); | |
424 mInvalidCache.clear(); | |
425 } | |
426 } | |
427 } | |
428 | |
429 void setExpiration(Object key, long duration) { | |
430 Long expire = new Long | |
431 (System.currentTimeMillis() + duration); | |
432 synchronized (mExpireLock) { | |
433 if (mExpirations == null) { | |
434 mExpirations = new IdentityMap(); | |
435 } | |
436 mExpirations.put(key, expire); | |
437 } | |
438 } | |
439 | |
440 /** | |
441 * Caller must lock interned key. | |
442 */ | |
443 private Retriever retrieve(Factory factory, | |
444 Object key, | |
445 Object originalValue, | |
446 boolean priority) | |
447 { | |
448 Retriever r = (Retriever)mRetrievers.get(key); | |
449 | |
450 if (r == null) { | |
451 r = new Retriever(factory, key, originalValue); | |
452 if (mQueue.enqueue(r)) { | |
453 mRetrievers.put(key, r); | |
454 } | |
455 else if (priority) { | |
456 // Skip the queue, service it in this thread. | |
457 mRetrievers.put(key, r); | |
458 r.service(); | |
459 } | |
460 else { | |
461 return null; | |
462 } | |
463 } | |
464 | |
465 return r; | |
466 } | |
467 | |
468 /** | |
469 * Implement this interface in order for Depot to retrieve objects when | |
470 * needed, often in a thread other than the requester's. | |
471 * | |
472 * @see PerishablesFactory | |
473 */ | |
474 public interface Factory { | |
475 /** | |
476 * Create an object that is mapped by the given key. This method must | |
477 * be thread-safe, but simply making it synchronized may severely | |
478 * impact the Depot's support of concurrent activity. | |
479 * <p> | |
480 * Create may abort its operation by throwing an InterruptedException. | |
481 * This forces an invalid object to be used or null if none. If an | |
482 * InterruptedException is thrown, nether the invalid object or null | |
483 * will be cached. Null is cached only if the factory returns it | |
484 * directly. | |
485 * | |
486 * @throws InterruptedException explicitly throwing this exception | |
487 * allows the factory to abort creating an object. | |
488 */ | |
489 public Object create(Object key) throws InterruptedException; | |
490 } | |
491 | |
492 /** | |
493 * A special kind of Factory that creates objects that are considered | |
494 * invalid after a specific amount of time has elapsed. | |
495 */ | |
496 public interface PerishablesFactory extends Factory { | |
497 /** | |
498 * Returns the maximum amout of time (in milliseconds) that objects | |
499 * from this factory should remain valid. Returning a value less than | |
500 * or equal to zero causes objects to be immediately invalidated. | |
501 */ | |
502 public long getValidDuration(); | |
503 } | |
504 | |
505 /** | |
506 * Values returned from the Factories may implement this interface if they | |
507 * manually handle expiration. | |
508 */ | |
509 public interface Perishable { | |
510 /** | |
511 * If this Perishable is still valid, but it came from a | |
512 * PerishablesFactory, it may be considered invalid if the valid | |
513 * duration has elapsed. | |
514 */ | |
515 public boolean isValid(); | |
516 } | |
517 | |
518 public interface Filter { | |
519 /** | |
520 * Returns true if the given key should be included in an operation, | |
521 * such as invalidation. | |
522 */ | |
523 public boolean accept(Object key); | |
524 } | |
525 | |
526 private class Retriever implements Transaction { | |
527 private final Factory mFactory; | |
528 private final Object mKey; | |
529 private Object mValue; | |
530 private boolean mDone; | |
531 | |
532 /** | |
533 * @param key Key must already be interned. | |
534 */ | |
535 public Retriever(Factory factory, Object key, Object originalValue) { | |
536 mFactory = factory; | |
537 mKey = key; | |
538 mValue = originalValue; | |
539 } | |
540 | |
541 public Object waitForValue(long timeout) { | |
542 try { | |
543 synchronized (mKey) { | |
544 if (mDone || timeout == 0) { | |
545 return mValue; | |
546 } | |
547 | |
548 if (timeout < 0) { | |
549 timeout = 0; | |
550 } | |
551 | |
552 mKey.wait(timeout); | |
553 } | |
554 } | |
555 catch (InterruptedException e) { | |
556 } | |
557 | |
558 return mValue; | |
559 } | |
560 | |
561 public void bypassValue(Object value) { | |
562 synchronized (mKey) { | |
563 mValue = value; | |
564 mKey.notifyAll(); | |
565 } | |
566 } | |
567 | |
568 public void service() { | |
569 try { | |
570 Thread t = Thread.currentThread(); | |
571 String originalName = t.getName(); | |
572 t.setName(originalName + ' ' + mKey); | |
573 try { | |
574 mValue = mFactory.create(mKey); | |
575 synchronized (mKey) { | |
576 if (mFactory instanceof PerishablesFactory) { | |
577 long duration = ((PerishablesFactory)mFactory) | |
578 .getValidDuration(); | |
579 if (duration <= 0) { | |
580 mInvalidCache.put(mKey, mValue); | |
581 mValidCache.remove(mKey); | |
582 } | |
583 else { | |
584 mInvalidCache.remove(mKey); | |
585 mValidCache.put(mKey, mValue); | |
586 setExpiration(mKey, duration); | |
587 } | |
588 } | |
589 else { | |
590 mInvalidCache.remove(mKey); | |
591 mValidCache.put(mKey, mValue); | |
592 } | |
593 } | |
594 } | |
595 catch (InterruptedException e) { | |
596 } | |
597 finally { | |
598 t.setName(originalName); | |
599 } | |
600 } | |
601 finally { | |
602 done(); | |
603 } | |
604 } | |
605 | |
606 public void cancel() { | |
607 done(); | |
608 } | |
609 | |
610 private void done() { | |
611 mDone = true; | |
612 mRetrievers.remove(mKey); | |
613 synchronized (mKey) { | |
614 mKey.notifyAll(); | |
615 } | |
616 } | |
617 } | |
618 } |