Depot


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:--> 14 <!-- $-->, <!--$$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 }
619
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags