Mercurial > hg > blitz_stable

comparison src/com/go/trove/util/Depot.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }