Java > Open Source Codes > org > apache > derby > impl > services > cache > Clock


1 /*
2
3    Derby - Class org.apache.derby.impl.services.cache.Clock
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.services.cache;
23
24 import org.apache.derby.iapi.services.cache.CacheManager;
25 import org.apache.derby.iapi.services.cache.Cacheable;
26 import org.apache.derby.iapi.services.cache.CacheableFactory;
27 import org.apache.derby.iapi.services.cache.SizedCacheable;
28 import org.apache.derby.iapi.services.context.ContextManager;
29 import org.apache.derby.iapi.services.daemon.DaemonService;
30 import org.apache.derby.iapi.services.daemon.Serviceable;
31
32 import org.apache.derby.iapi.error.StandardException;
33
34 import org.apache.derby.iapi.services.monitor.Monitor;
35
36 import org.apache.derby.iapi.services.sanity.SanityManager;
37
38 import org.apache.derby.iapi.services.cache.ClassSize;
39 import org.apache.derby.iapi.util.Matchable;
40 import org.apache.derby.iapi.util.Operator;
41 import org.apache.derby.iapi.reference.SQLState;
42
43 import java.util.ArrayList ;
44 import java.util.Hashtable ;
45 import java.util.Properties ;
46
47
48 /**
49     A cache manager that uses a Hashtable and a ArrayList. The ArrayList holds
50     CachedItem objects, each with a holder object. The Hashtable is keyed
51     by the identity of the holder object (Cacheable.getIdentity()) and
52     the data portion is a pointer to the CachedItem. CachedItems that have
53     holder objects with no identity do not have entries in the hashtable.
54     <P>
55     CachedItems can in various state.
56     <UL>
57     <LI>isValid - the entry has a valid identity
58     <LI>inCreate - the entry is being created or being faulted in from persistent store
59     <LI>inClean - the entry is being written out to persistent store
60     <LI>isKept - the entry is currently being looked at/updated, do not remove or
61                 clean it.
62     </OL>
63
64     <P>Multithreading considerations:<BR>
65     A clock cache manager must be MT-safe.
66     All member variables are accessed single threaded (synchronized on this) or
67     set once or readonly. Assumptions: holders size() and addElement must be
68     synchronized.
69     <BR>
70     CachedItem is never passed out of the clock cache manager, only the
71     Cacheable object is. The cachedItem is responsible for the setting and
72     clearing of its own member fields (RESOLVE: now they are done in cache
73     manager, need to be moved to the cachedItem). The cache manager will
74     following the following rules while accessing a cacheditem:
75     <UL>
76     <LI>invalid item is never returned from the cache
77     <LI>setValidState and isValid() is only called single threaded through the cache manager.
78     <LI>keep() and isKept() is only called single threaded through the cache
79     manager once the item has been added to the holders array
80     <LI>item that isKept() won't be cleaned or removed or invalidated from the cache.
81     <LI>item that is inClean() or inCreate(), the cache manager
82     will wait on the cachedItem to finish cleaning or creating before it
83     returns the cached item outside of the cache.
84     </UL>
85     <BR>
86     The cacheable must be cleaned thru the cache if it is managed by a cache.
87     On CacheItem, a inClean state is maintain to stablelize the content of the
88     cacheable while it is being cleaned. Only unkept items are cleaned. If an
89     item is found to be inClean, it will wait until it exits the inClean state.
90     If a cached item calls it own clean method without notifying the cache, it
91     has to stablize its content for the duration of the clean.
92     <BR>
93     It is assumed that the cacheable object maintain its own MT-safeness.<BR>
94
95     @see CachedItem
96     @see Cacheable
97
98 */
99
100 final class Clock extends Hashtable implements CacheManager, Serviceable {
101
102     /*
103     ** Fields
104     */
105     public final CacheStat stat;
106     private DaemonService cleaner; // the background worker thread who is going to
107 // do pre-flush for this cache.
108 private final ArrayList holders;
109     private int validItemCount = 0;
110     private long maximumSize;
111     private boolean useByteCount; // regulate the total byte count or the entry count
112 private long currentByteCount = 0;
113     /* currentByteCount should be the sum of entry.getSize() for all entries in the cache.
114      * That is, it should be the sum of getItemSize( item, false) for each item in the holders
115      * vector.
116      */
117
118     private static final int ITEM_OVERHEAD = ClassSize.estimateBaseFromCatalog( CachedItem.class)
119         + ClassSize.getRefSize() // one ref per item in the holder ArrayList
120 + ClassSize.estimateHashEntrySize();
121
122     private final CacheableFactory holderFactory;
123
124     private boolean active; // true if active for find/create
125 private String name; // name of the cache, mainly for debugging purposes.
126 private int clockHand; // the sweep of the clock hand
127
128     
129     private int myClientNumber; // use this number to talk to cleaner service
130 private boolean wokenToClean; // true if the client was woken to clean, false if to shrink
131 private boolean cleanerRunning;
132     private boolean needService;
133
134     /**
135         Construct a new clock cache manager.
136
137         <P>MT - not needed for constructor.
138
139         @param holderFactory the cacheable object class
140         @param name the name of the cache
141         @param initialSize the initial number of cachable object this cache
142         holds.
143         @param maximumSize the maximum size of the cache. The cache may grow
144         from initialSize to maximumSize if the cache policy notices that there
145         is not enough free buffers availiable. Once the cache hits maximumSize
146         it will not grow. If the cache is full, an exception will be thrown
147
148     */
149     Clock(CacheableFactory holderFactory,
150                   String name,
151                   int initialSize,
152                   long maximumSize,
153                   boolean useByteCount)
154     {
155         super(initialSize, (float) 0.95);
156         this.maximumSize = maximumSize;
157         this.holderFactory = holderFactory;
158         this.useByteCount = useByteCount;
159
160         if (SanityManager.DEBUG) {
161           if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
162             SanityManager.DEBUG(ClockFactory.CacheTrace, "initializing " + name + " cache to size " + initialSize);
163           }
164         }
165
166         //int delta = initialSize / 2;
167 //if (delta < 5)
168 // delta = 5;
169
170         holders = new ArrayList (initialSize);
171         this.name = name;
172         active = true;
173
174         this.stat = new CacheStat();
175         stat.initialSize = initialSize;
176         stat.maxSize = maximumSize;
177     }
178
179     /**
180         Find the object or materialize one in the cache. If it has not been
181         created in the persistent store yet, return null.
182
183         <P>MT - must be MT-safe. The cache is single threaded through finding
184         the item in cache and finding a free item if it is not in cache, thus
185         preventing another thread from creating the same item while is is being
186         faulted in. (RESOLVE - this is really low performance if the cache
187         cleaner cannot keep a steady supply of free items and we have to do an
188         I/O while blocking the cache). If it needs to be faulted in, the
189         inCreate bit is set. The item is kept before it exits the sync block.
190         <BR>
191         If the item is in cache but in the middle of being faulted in or
192         cleaned, it needs to wait until this is done being before returning.
193         <BR>
194         The keep status prevents other threads from removing this item.
195         The inCreate status prevents other threads from looking at or writing
196         out this item while it is being faulted in.
197         (RESOLVE: need to handle the case where the object is marked for
198         removal and being waited on)
199
200         @param key the key to the object
201         @return a cacheable object that is kept in the cache.
202         @exception StandardException Cloudscape Standard error policy
203     */
204     public Cacheable find(Object key) throws StandardException {
205         CachedItem item;
206         boolean add;
207
208         /*
209         ** We will only loop if someone else tried to add the
210         ** same key as we did and they failed. In this case
211         ** we start all over. An example of this would be an
212         ** attempt to cache an object that failed due to a
213         ** transient error (e.g. deadlock), which should not
214         ** prevent another thread from trying to add the
215         ** key to the cache (e.g. it might be the one holding
216         ** the lock that caused the other thread to deadlock).
217         */
218         while (true)
219         {
220             add = false;
221
222             synchronized (this) {
223     
224                 if (!active)
225                     return null;
226     
227                 item = (CachedItem) get(key);
228     
229                 if (item != null) {
230                     item.keepAfterSearch();
231                     
232                     stat.findHit++;
233
234                     if (SanityManager.DEBUG) {
235                       if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
236                       {
237                         SanityManager.DEBUG(ClockFactory.CacheTrace, name + ": Found key " +
238                                             key + " already in cache, item " + item);
239                       }
240                     }
241                 }
242             }
243     
244             // no entry was found, need to add one
245 if (item == null) {
246     
247                 // get a free item
248 item = findFreeItem();
249
250                 stat.findMiss++;
251     
252                 if (SanityManager.DEBUG) {
253                   if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
254                   {
255                     SanityManager.DEBUG(ClockFactory.CacheTrace, name + ": Find key " +
256                                         key + " Not in cache, get free item " + item);
257                   }
258                 }
259     
260     
261                 if (SanityManager.DEBUG)
262                     SanityManager.ASSERT(item != null, "found null item");
263     
264                 synchronized (this) {
265                     CachedItem inCacheItem = (CachedItem) get(key);
266     
267                     if (inCacheItem != null) {
268                         // some-one beat us to adding an item into the cache,
269 // just use that one
270 item.unkeepForCreate();
271     
272                         item = inCacheItem;
273                         item.keepAfterSearch();
274                     } else {
275                         // yes, we really are the ones to add it
276 put(key, item);
277                         add = true;
278                         if (SanityManager.DEBUG) {
279
280                             if (SanityManager.DEBUG_ON("memoryLeakTrace")) {
281
282                                 if (size() > ((11 * maximumSize) / 10))
283                                     System.out.println("memoryLeakTrace:Cache:" + name + " " + size());
284                             }
285                         }
286                     }
287                 }
288             }
289             
290             if (add) {
291     
292                 if (SanityManager.DEBUG) {
293                   if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
294                   {
295                     SanityManager.DEBUG(ClockFactory.CacheTrace, name + " Added " +
296                                         key + " to cache, item " + item);
297                   }
298                 }
299     
300                 stat.findFault++;
301
302                 return addEntry(item, key, false, (Object ) null);
303             }
304                 
305             Cacheable entry = item.use();
306             if (entry == null) {
307                 // item was not added by the other user successfully ...
308 synchronized (this) {
309                     item.unkeep();
310                 }
311
312                 // try to hash the key again (see
313 // comment at head of loop)
314 continue;
315             }
316     
317             return entry;
318         }
319     }
320
321
322     /**
323         Find an object in the cache. Do not fault in or create the object if
324         is is not found in the cache.
325
326         <P>MT - must be MT-safe. The cache is single threaded through finding
327         the item in cache. If it needs to wait for it to be faulted in or
328         cleaned it is synchronized/waited on the cached item itself.
329
330         @param key the key to the object
331         @return a cacheable object that is kept in the cache.
332     */
333
334     public Cacheable findCached(Object key) throws StandardException {
335
336
337         CachedItem item;
338
339         synchronized (this) {
340
341             if (!active)
342                 return null;
343         
344             item = (CachedItem) get(key);
345
346             if (item == null) {
347                 stat.findCachedMiss++;
348                 return null;
349             } else
350                 stat.findCachedHit++;
351             
352             item.keepAfterSearch();
353         }
354
355         Cacheable entry = item.use();
356         if (entry == null) {
357             // item was not added by the other user successfully ...
358 synchronized (this) {
359                 item.unkeep();
360             }
361         }
362
363         return entry;
364     }
365
366
367     /**
368      * Mark a set of entries as having been used. Normally this is done as a side effect
369      * of find() or findCached. Entries that are no longer in the cache are ignored.
370      *
371      * @param keys the key of the used entry.
372      */
373     public void setUsed( Object [] keys)
374     {
375         CachedItem item;
376
377         for( int i = 0; i < keys.length;)
378         {
379             // Do not hold the synchronization lock for too long.
380 synchronized (this)
381             {
382                 if (!active)
383                     return;
384
385                 int endIdx = i + 32;
386                 if( endIdx > keys.length)
387                     endIdx = keys.length;
388                 for( ; i < endIdx; i++)
389                 {
390                     if( keys[i] == null)
391                         return;
392                     
393                     item = (CachedItem) get(keys[i]);
394                     if( null != item)
395                         item.setUsed( true);
396                 }
397             }
398         }
399     } // end of setUsed
400
401     /**
402         Create a new object with the said key.
403
404         <P>MT - must be MT-safe. Single thread thru verifying no such item
405         exist in cache and finding a free item, keep the item and set inCreate
406         state. The actual creating of the object is done outside
407         the sync block and is protected by the isKept and inCreate bits.
408
409         @param key the key to the object
410         @return a cacheable object that is kept in the cache.
411
412         @exception StandardException Cloudscape Standard error policy
413     */
414     public Cacheable create(Object key, Object createParameter) throws StandardException {
415
416         // assume the item is not already in the cache
417 CachedItem item = findFreeItem();
418
419         stat.create++;
420
421         synchronized (this) {
422
423             if (!active)
424                 return null;
425
426             if (get(key) != null) {
427
428                 item.unkeepForCreate();
429
430                 throw StandardException.newException(SQLState.OBJECT_EXISTS_IN_CACHE, this.name, key);
431             }
432
433             put(key, item);
434
435             if (SanityManager.DEBUG) {
436
437                 if (SanityManager.DEBUG_ON("memoryLeakTrace")) {
438
439                     if (size() > ((11 * maximumSize) / 10))
440                         System.out.println("memoryLeakTrace:Cache:" + name + " " + size());
441                 }
442             }
443         }
444
445         Cacheable entry = addEntry(item, key, true, createParameter);
446     
447         if (SanityManager.DEBUG) {
448             if (entry != null)
449                 SanityManager.ASSERT(item.getEntry() == entry);
450         }
451
452         return entry;
453     }
454
455
456     /**
457         The caller is no longer looking at or updating the entry. Since there
458         could be more than one piece of code looking at this entry, release
459         does not mean nobody is looking at or updating the entry, just one
460         less. If the cacheable is marked for remove (someone is waiting to
461         remove the persistent object once nobody is looking at it), then notify
462         the waiter if this is the last one looking at it.
463         <BR>
464         Unless there is a good reason to do otherwise, release should be used
465         to release a cachable and not directly call cachedItem unkeep, since
466         unkeep does not handle the case of remove.
467
468
469         <P>MT - must be MT-safe. Getting and deleteing item from the hashtable
470         is in the same synchronized block. If the cacheable object is waiting
471         to be removed, that is synchronized thru the cachedItem itself
472         (RESOLVE: need to move this sync block to cachedItem instead)
473
474         @param entry the cached entry
475
476      */
477     public void release(Cacheable entry) {
478         boolean removeItem;
479         CachedItem item;
480         long toShrink = 0;
481
482         synchronized (this) {
483
484             item = (CachedItem) get(entry.getIdentity());
485
486             if (SanityManager.DEBUG) {
487                 SanityManager.ASSERT(item != null, "item null");
488                 SanityManager.ASSERT(item.getEntry() == entry, "entry not equals keyed entry");
489                 SanityManager.ASSERT(item.isKept(), "item is not kept in release(Cachable)");
490             }
491
492             removeItem = item.unkeep();
493
494             if (removeItem) {
495                 
496                 remove(entry.getIdentity());
497
498                 // we keep the item here to stop another thread trying to evict it
499 // while we are destroying it.
500 item.keepForClean();
501             }
502
503             if (cleaner == null) {
504                 // try to shrink the cache on a release
505 toShrink = shrinkSize( getCurrentSize());
506             }
507         }
508
509         if (removeItem) {
510
511             item.notifyRemover();
512         }
513
514         if (toShrink > 0)
515             performWork(true /* shrink only */);
516     }
517
518     protected void release(CachedItem item) {
519
520         boolean removeItem;
521
522         synchronized (this) {
523
524             if (SanityManager.DEBUG) {
525                 SanityManager.ASSERT(item.isKept(), "item is not kept in released(CachedItem)");
526             }
527
528             removeItem = item.unkeep();
529
530             if (removeItem) {
531                 
532                 remove(item.getEntry().getIdentity());
533
534                 // we keep the item here to stop another thread trying to evict it
535 // while we are destroying it.
536 item.keepForClean();
537             }
538         }
539
540         if (removeItem) {
541
542             item.notifyRemover();
543         }
544     }
545
546     /**
547         Remove an object from the cache. The item will be placed into the NoIdentity
548         state through clean() (if required) and clearIdentity(). The removal of the
549         object will be delayed until it is not kept by anyone.
550
551         After this call the caller must throw away the reference to item.
552
553         <P>MT - must be MT-safe. Single thread thru finding and setting the
554         remove state of the item, the actual removal of the cacheable is
555         synchronized on the cachedItem itself.
556
557         @exception StandardException Standard Cloudscape error policy.
558     */
559     public void remove(Cacheable entry) throws StandardException {
560
561         boolean removeNow;
562         CachedItem item;
563         long origItemSize = 0;
564
565         stat.remove++;
566
567         synchronized (this) {
568
569             
570
571             item = (CachedItem) get(entry.getIdentity());
572
573             if (SanityManager.DEBUG) {
574                 SanityManager.ASSERT(item != null);
575                 SanityManager.ASSERT(item.getEntry() == entry);
576                 SanityManager.ASSERT(item.isKept());
577             }
578             if( useByteCount)
579                 origItemSize = getItemSize( item);
580
581             item.setRemoveState();
582             removeNow = item.unkeep();
583
584             if (removeNow) {
585                 remove(entry.getIdentity());
586                 item.keepForClean();
587             }
588         }
589
590         try {
591             // if removeNow is false then this thread may sleep
592 item.remove(removeNow);
593
594         } finally {
595
596             synchronized (this)
597             {
598                 // in the case where this thread didn't call keepForClean() the thread
599 // that woke us would have called keepForClean.
600 item.unkeep();
601                 item.setValidState(false);
602                 validItemCount--;
603                 item.getEntry().clearIdentity();
604                 if( useByteCount)
605                     currentByteCount += getItemSize( item) - origItemSize;
606             }
607         }
608
609     }
610
611     /**
612         Clean all objects in the cache.
613     */
614     public void cleanAll() throws StandardException {
615         stat.cleanAll++;
616         cleanCache((Matchable) null);
617     }
618
619     /**
620         Clean all objects that match a partial key.
621     */
622     public void clean(Matchable partialKey) throws StandardException {
623
624         cleanCache(partialKey);
625     }
626
627     /**
628         Age as many objects as possible out of the cache.
629
630         <BR>MT - thread safe
631
632         @see CacheManager#ageOut
633     */
634     public void ageOut() {
635
636         stat.ageOut++;
637         synchronized (this) {
638
639             int size = holders.size();
640             long toShrink = shrinkSize( getCurrentSize());
641             boolean shrunk = false;
642
643             for (int position = 0; position < size; position++) {
644                 CachedItem item = (CachedItem) holders.get(position);
645
646                 if (item.isKept())
647                     continue;
648                 if (!item.isValid())
649                     continue;
650
651                 if (item.getEntry().isDirty()) {
652                     continue;
653                 }
654
655                 long itemSize = removeIdentity(item);
656
657                 if (toShrink > 0) {
658
659                     if (SanityManager.DEBUG) {
660                         if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
661                         SanityManager.DEBUG(ClockFactory.CacheTrace, name +
662                                             " shrinking item " + item + " at position " + position);
663                         }
664                     }
665                     
666                     toShrink -= itemSize;
667                     shrunk = true;
668                 }
669
670             } // end of for loop
671
672             if (shrunk)
673                 trimToSize();
674
675         } // out of sync block
676 } // end of ageOut
677
678     /**
679         MT - synchronization provided by caller
680
681         @exception StandardException Standard Cloudscape error policy.
682     */
683     public void shutdown() throws StandardException {
684
685         if (cleaner != null) {
686             cleaner.unsubscribe(myClientNumber);
687             cleaner = null;
688         }
689
690         synchronized (this) {
691             active = false;
692         }
693
694         ageOut();
695         cleanAll();
696         ageOut();
697     }
698
699     /**
700         MT - synchronization provided by caller
701
702         can use this Daemomn service if needed
703     */
704     public void useDaemonService(DaemonService daemon)
705     {
706         // if we were using another cleaner, unsubscribe first
707 if (cleaner != null)
708             cleaner.unsubscribe(myClientNumber);
709
710         cleaner = daemon;
711         myClientNumber = cleaner.subscribe(this, true /* onDemandOnly */);
712     }
713     /**
714         Discard all objects that match the partial key.
715
716         <BR>MT - thread safe
717     */
718     public boolean discard(Matchable partialKey) {
719
720         // we miss something because it was kept
721 boolean noMisses = true;
722
723         synchronized (this) {
724
725             int size = holders.size();
726             long toShrink = shrinkSize( getCurrentSize());
727             boolean shrunk = false;
728
729             for (int position = 0; position < size; position++) {
730                 CachedItem item = (CachedItem) holders.get(position);
731
732                 if (!item.isValid())
733                     continue;
734
735                 Object key = item.getEntry().getIdentity();
736
737                 if (partialKey != null && !partialKey.match(key))
738                     continue;
739
740                 if (item.isKept())
741                 {
742                     noMisses = false;
743                     continue;
744                 }
745
746                 long itemSize = removeIdentity(item);
747
748                 if (toShrink > 0) {
749
750                     if (SanityManager.DEBUG) {
751                         if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
752                         SanityManager.DEBUG(ClockFactory.CacheTrace, name +
753                                             " shrinking item " + item + " at position " + position);
754                         }
755                     }
756
757                     // and we shrunk one item
758 toShrink -= itemSize;
759                     shrunk = true;
760                 }
761             }
762
763             if (shrunk)
764                 trimToSize();
765         }
766
767         return noMisses;
768     }
769
770     /**
771         Add a new CachedItem and a holder object to the cache. The holder object
772         is returned kept.
773
774         <P>MT - need to be MT-safe. The insertion of the key into the hash
775         table is synchronized on this.
776
777     */
778     private Cacheable addEntry(CachedItem item, Object key, boolean forCreate, Object createParameter)
779         throws StandardException {
780
781         Cacheable entry = null;
782         long origEntrySize = 0;
783         if( useByteCount)
784             origEntrySize = getItemSize( item);
785
786         try
787         {
788             if (SanityManager.DEBUG) {
789               if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
790               {
791                 SanityManager.DEBUG(ClockFactory.CacheTrace, name +
792                                     " item " + item + " take on identity " + key);
793               }
794             }
795             
796             // tell the object it needs to create itself
797 entry = item.takeOnIdentity(this, holderFactory, key, forCreate, createParameter);
798         }
799         finally
800         {
801             boolean notifyWaiters;
802             synchronized (this) {
803
804                 Object removed = remove(key);
805                 if (SanityManager.DEBUG) {
806                     SanityManager.ASSERT(removed == item);
807                 }
808
809                 if (entry != null) {
810                     // put the actual key into the hash table, not the one that was passed in
811 // for the find or create. This is because the caller may re-use the key
812 // for another cache operation, which would corrupt our hashtable
813 put(entry.getIdentity(), item);
814                     if( useByteCount)
815                         currentByteCount += ((SizedCacheable) entry).getSize() - origEntrySize;
816                     item.setValidState(true);
817                     validItemCount++;
818                     notifyWaiters = true;
819                 } else {
820                     item.unkeep();
821                     notifyWaiters = item.isKept();
822                 }
823             }
824
825             // whatever the outcome, we have to notify waiters ...
826 if (notifyWaiters)
827                 item.settingIdentityComplete();
828         }
829
830         return entry;
831     }
832
833    
834     protected CachedItem findFreeItem() throws StandardException {
835
836         // Need to avoid thrashing the cache when we start out
837 // so if the cache is smaller than its maximum size
838 // then that's a good indication we should grow.
839
840         long currentSize = getCurrentSize();
841
842
843         if (currentSize >= maximumSize) {
844             // look at 20%
845 CachedItem item = rotateClock(0.2f);
846             if (item != null)
847                 return item;
848         }
849
850         // However, if the cache contains a large number of invalid
851 // items then we should see if we can avoid growing.
852 // This avoids simple use of Cloudscape looking like
853 // a memory leak, as the page cache fills the holders array
854 // with page objects including the 4k (or 32k) pages.
855 // size() is the number of valid entries in the hash table
856
857
858         // no need to sync on getting the sizes since if they are
859 // wrong we will discover it in the loop.
860 if (validItemCount < holders.size()) {
861
862             synchronized (this) {
863
864                 // 1) find out how many invalid items there are in the
865 // cache
866 // 2) search for a free invalid item
867 // 3) stop searching when there are no more invalid
868 // items to find
869
870                 int invalidItems = holders.size() - validItemCount;
871
872                 // Invalid items might occur in the cache when
873 // a) a new item is created in growCache(), but it
874 // is not in use yet, or
875 // b) an item is deleted (usually when a table is
876 // dropped)
877
878                 // It is critical to break out of the loop as soon as
879 // possible since we are blocking others trying to
880 // access the page cache. New items are added to the
881 // end of the page cache, so the search for invalid
882 // items should start from the end.
883
884                 for (int i = holders.size() - 1; (invalidItems > 0) && (i >= 0) ; i--) {
885                     CachedItem item = (CachedItem) holders.get(i);
886
887                     if (item.isKept()) {
888                         if (!item.isValid()) invalidItems--;
889                         continue;
890                     }
891
892                     // found a free item, just use it
893 if (!item.isValid()) {
894                         item.keepForCreate();
895                         return item;
896                     }
897                 }
898             }
899         }
900
901
902         return growCache();
903     }
904
905     /**
906         Go through the list of holder objects and find a free one.
907         <P>MT - must be MT-safe. The moving of the clockHand and finding of an
908         eviction candidate is synchronized. The cleaning of the cachable is
909         handled by the cacheable itself.
910     */
911     protected CachedItem rotateClock(float percentOfClock) throws StandardException
912     {
913         // statistics -- only used in debug
914 int evictions = 0;
915         int cleaned = 0;
916         int resetUsed = 0;
917         int iskept = 0;
918
919         // When we are managing the entry count (useByteCount == false) this method just
920 // has to find or manufacture an available item (a cache slot). When we are managing
921 // the total byte count then this method must find both available space and an
922 // available item.
923 CachedItem availableItem = null;
924
925         boolean kickCleaner = false;
926
927         try {
928
929
930             // this can be approximate
931 int itemCount = holders.size();
932             int itemsToCheck;
933             if (itemCount < 20)
934                 itemsToCheck = 2 * itemCount;
935             else
936                 itemsToCheck = (int) (((float) itemCount) * percentOfClock);
937
938
939             // if we can grow then shrinking is OK too, if we can't grow
940 // then shrinking the cache won't help us find an item.
941 long toShrink = shrinkSize(getCurrentSize());
942
943 restartClock:
944             for (; itemsToCheck > 0;) {
945
946                 CachedItem item = null;
947
948                 synchronized (this) {
949
950                     if (SanityManager.DEBUG) {
951                       if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
952                       {
953                         SanityManager.DEBUG(ClockFactory.CacheTrace, name + " rotateClock starting " +
954                                             clockHand + " itemsToCheck " + itemsToCheck);
955                       }
956                     }
957
958                     // size of holders cannot change while in the synchronized block.
959 int size = holders.size();
960                     for (; itemsToCheck > 0; item = null, itemsToCheck--, incrClockHand())
961                     {
962                         //
963 // This uses a very simple clock algorithm.
964 //
965 // The cache consist of a circular list of cachedItems. Each cached item
966 // has a 'recentlyUsed' bit which is set every time that item is kept.
967 // Each clock cache manager keeps a global variable clockHand which
968 // refers to the item that is most recently replaced.
969 //
970 // to find a free item, the clock Hand moves to the next cached Item.
971 // If it is kept, or in the middle of being created, the clock hand
972 // moves on.
973 // If it is recentlyUsed, clear the recently used bit and moves on.
974 // If it is not recentlyUsed, clean the item and use
975 //
976 // If all the cached item is kept, then create a new entry.
977 // So it is possible, although very unlikely, that, in time, the cache
978 // will grow beyond the maximum size.
979
980                         
981
982                         if (clockHand >= size) {
983                             if (size == 0)
984                                 break;
985                             clockHand = 0;
986                         }
987
988                         item = (CachedItem) holders.get(clockHand);
989
990                         if (item.isKept())
991                         {
992                             if (SanityManager.DEBUG) // stats only in debug mode
993 iskept++;
994                             continue;
995                         }
996
997                         if (!item.isValid()) // found a free item, just use it
998 {
999                             if( null != availableItem)
1000                                // We have found an available item, now we are looking for bytes
1001 continue;
1002                            if (SanityManager.DEBUG) {
1003                              if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
1004                              {
1005                                SanityManager.DEBUG(ClockFactory.CacheTrace,
1006                                                    name + " found free item at " + clockHand + " item " + item);
1007                              }
1008                            }
1009
1010                            item.keepForCreate();
1011                            if( useByteCount && getCurrentSize() > maximumSize)
1012                            {
1013                                availableItem = item;
1014                                // now look for bytes.
1015 continue;
1016                            }
1017                            // since we are using this item, move the clock past it.
1018 incrClockHand();
1019
1020                            return item;
1021                        }
1022
1023                        if (item.recentlyUsed())
1024                        {
1025
1026                            if (SanityManager.DEBUG) // stats only in debug mode
1027 resetUsed++;
1028                            item.setUsed(false);
1029                            continue;
1030                        }
1031
1032
1033                        if (toShrink > 0) {
1034                            if (!cleanerRunning) {
1035
1036                                // try an get the cleaner to shrink the cache
1037 kickCleaner = true;
1038                                cleanerRunning = true;
1039                                needService = true;
1040                            }
1041                        }
1042
1043                        // we are seeing valid, not recently used buffers. Evict this.
1044 if (SanityManager.DEBUG) {
1045                            evictions++;
1046
1047                            if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
1048                            {
1049                                SanityManager.DEBUG(ClockFactory.CacheTrace,
1050                                                    name + " evicting item at " +
1051                                                    clockHand + " item " + item);
1052                            }
1053                        }
1054
1055                        if (!item.getEntry().isDirty()) {
1056
1057                            if (SanityManager.DEBUG) {
1058                              if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
1059                              {
1060                                SanityManager.DEBUG(ClockFactory.CacheTrace,
1061                                                    name + " Evicting Item " +
1062                                                    item + ", not dirty");
1063                              }
1064                            }
1065
1066                            // a valid, unkept, clean item, clear its identity
1067 // and use it.
1068 long itemSize = removeIdentity(item);
1069
1070                            if( useByteCount)
1071                            {
1072                                toShrink -= itemSize;
1073                                if( getCurrentSize() > maximumSize && 0 < toShrink)
1074                                {
1075                                    if( null == availableItem)
1076                                    {
1077                                        item.keepForCreate();
1078                                        availableItem = item;
1079                                    }
1080                                    continue;
1081                                }
1082                            }
1083                            // since we are using it move the clock past it
1084 incrClockHand();
1085
1086                            if( null != availableItem)
1087                                return availableItem;
1088
1089                            // item is kept but not valid when returned
1090 item.keepForCreate();
1091                            return item;
1092                        }
1093                        // item is valid, unkept, and dirty. clean it.
1094 if ((cleaner != null) && !cleanerRunning) {
1095                            kickCleaner = true;
1096                            wokenToClean = true;
1097                            cleanerRunning = true; // at least it soon will be
1098 }
1099                        item.keepForClean();
1100
1101                        // leave the clock hand where it is so that we will pick it
1102 // up if no-one else uses the cache. Other hunters will
1103 // skip over it as it is kept, and thus move the clock
1104 // hand past it.
1105 break;
1106                    }
1107                    if (item == null) {
1108                        return availableItem;
1109                    }
1110
1111                } // out of synchronized block
1112
1113                // clean the entry outside of a sync block
1114 try
1115                {
1116                    if ( SanityManager.DEBUG) {
1117                        if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
1118                        SanityManager.DEBUG(ClockFactory.CacheTrace,name + " cleaning item " + item);
1119                        }
1120                    }
1121
1122                    item.clean(false);
1123
1124                    if (SanityManager.DEBUG) // stats only in debug mode
1125 {
1126                        cleaned++;
1127                    }
1128                }
1129                finally {
1130                    release(item);
1131                    item = null;
1132                }
1133
1134                // at this point the item we cleaned could be in any state
1135 // so we can't just re-use it. Continue searching
1136 continue restartClock;
1137            }
1138            return availableItem;
1139        } finally {
1140
1141
1142            if (SanityManager.DEBUG)
1143            {
1144                // report statistics
1145 if (
1146                    SanityManager.DEBUG_ON(ClockFactory.CacheTrace))
1147                    SanityManager.DEBUG(ClockFactory.CacheTrace, name + " evictions " + evictions +
1148                                        ", cleaned " + cleaned +
1149                                        ", resetUsed " + resetUsed +
1150                                        ", isKept " + iskept +
1151                                        ", size " + holders.size());
1152            }
1153
1154            if (kickCleaner && (cleaner != null))
1155            {
1156                if (SanityManager.DEBUG) {
1157                    if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
1158                    SanityManager.DEBUG(DaemonService.DaemonTrace, name + " client # " + myClientNumber + " calling cleaner ");
1159                    }
1160                }
1161
1162                cleaner.serviceNow(myClientNumber);
1163
1164                if (SanityManager.DEBUG) {
1165                  if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
1166                    SanityManager.DEBUG(DaemonService.DaemonTrace, name + Thread.currentThread().getName() + " cleaner called");
1167                  }
1168                }
1169            }
1170        }
1171    } // end of rotateClock
1172
1173    /**
1174        Synchronously increment clock hand position
1175    */
1176    private int incrClockHand()
1177    {
1178        if (++clockHand >= holders.size())
1179            clockHand = 0;
1180        return clockHand;
1181    }
1182
1183    /*
1184     * Serviceable methods
1185     */
1186
1187    public int performWork(ContextManager contextMgr /* ignored */) {
1188
1189        int ret = performWork(false);
1190        synchronized (this) {
1191            cleanerRunning = false;
1192        }
1193        return ret;
1194    }
1195
1196    
1197    /**
1198        <P>MT - read only.
1199    */
1200    public boolean serviceASAP()
1201    {
1202        return needService;
1203    }
1204
1205
1206    // @return true, if this work needs to be done on a user thread immediately
1207 public boolean serviceImmediately()
1208    {
1209        return false;
1210    }
1211
1212
1213    public synchronized int getNumberInUse() {
1214
1215            int size = holders.size();
1216            int inUse = 0;
1217
1218            for (int position = 0; position < size; position++) {
1219
1220                CachedItem item = (CachedItem) holders.get(position);
1221
1222                if (item.isValid()) {
1223                    inUse++;
1224                }
1225
1226            }
1227            return inUse;
1228    }
1229/*
1230    public int getNumberKept() {
1231
1232        synchronized (this) {
1233
1234            int size = holders.size();
1235            int inUse = 0;
1236
1237            for (int position = 0; position < size; position++) {
1238
1239                CachedItem item = (CachedItem) holders.get(position);
1240
1241                if (item.isValid() && item.isKept()) {
1242                    inUse++;
1243                }
1244
1245            }
1246            return inUse;
1247        }
1248    }
1249*/
1250
1251    /**
1252        Grow the cache and return a unused, kept item.
1253
1254        @exception StandardException Thrown if the cache cannot be grown.
1255    */
1256
1257    private CachedItem growCache() {
1258
1259        CachedItem item = new CachedItem();
1260        item.keepForCreate();
1261
1262        // if we run out of memory below here we don't
1263 // know what state the holders could be in
1264 // so don't trap it
1265 synchronized (this) {
1266            holders.add(item);
1267            // Do not adjust currentByteCount until we put the entry into the CachedItem.
1268 }
1269
1270        return item;
1271    }
1272
1273
1274    /**
1275        Clear an item's identity. Item must be
1276        unkept and valid. This is called for
1277        dirty items from the discard code.
1278
1279        Caller must hold the cache synchronization.
1280
1281        @return the amount by which this shrinks the cache.
1282    */
1283    protected long removeIdentity(CachedItem item) {
1284
1285        long shrink = 1;
1286        
1287        if (SanityManager.DEBUG) {
1288            SanityManager.ASSERT(!item.isKept(), "item is kept");
1289            SanityManager.ASSERT(item.isValid(), "item is not valid");
1290
1291        }
1292
1293        if( useByteCount)
1294            shrink = ((SizedCacheable) item.getEntry()).getSize();
1295        remove(item.getEntry().getIdentity());
1296        item.setValidState(false);
1297        validItemCount--;
1298        item.getEntry().clearIdentity();
1299        if( useByteCount)
1300        {
1301            shrink -= ((SizedCacheable) item.getEntry()).getSize();
1302            currentByteCount -= shrink;
1303        }
1304        return shrink;
1305    }
1306
1307    /**
1308        Write out all dirty buffers.
1309
1310        <P>MT - must be MT safe.
1311        Single thread on the part that finds the next dirty buffer to write
1312        out, the synchronization of cleaning of the individual cachable is
1313        provided by the cacheable itself.
1314     */
1315    protected void cleanCache(Matchable partialKey) throws StandardException {
1316    
1317        int position;
1318
1319        synchronized(this)
1320        {
1321            // this is at many dirty buffers as the cleaner is ever going to
1322 // see
1323 position = holders.size() - 1;
1324        }
1325
1326
1327outerscan:
1328        for (;;) {
1329
1330            CachedItem item = null;
1331
1332            synchronized (this) {
1333
1334                // the cache may have shrunk by quite a bit since we last came
1335 // in here
1336 int size = holders.size();
1337                if (position >= size)
1338                    position = size - 1;
1339
1340innerscan:
1341                // go from position (the last cached item in the holder array
1342 // to 0 (the first). Otherwise, if we go from 0 to
1343 // position, some other thread may come in and shrink items
1344 // which are between 0 and position. Since a shrink moves all
1345 // items up, we may skip some items without cleaning.
1346 for ( ; position >= 0; position--, item = null) {
1347
1348                    item = (CachedItem) holders.get(position);
1349
1350                    if (!item.isValid())
1351                        continue innerscan;
1352
1353                    if (!item.getEntry().isDirty())
1354                        continue innerscan;
1355
1356                    if (partialKey != null) {
1357
1358                        Object key = item.getEntry().getIdentity();
1359
1360                        if (!partialKey.match(key))
1361                            continue;
1362                    }
1363
1364                    item.keepForClean();
1365                    break innerscan;
1366                }
1367            } // end of synchronized block
1368
1369            if (position < 0)
1370            {
1371                return;
1372            }
1373
1374            try {
1375
1376                item.clean(false);
1377            } finally {
1378                release(item);
1379            }
1380            position--;
1381            
1382        } // for (;;)
1383 }
1384
1385
1386    protected long shrinkSize(long currentSize) {
1387
1388        long maxSize = getMaximumSize();
1389
1390        long toShrink = currentSize - maxSize;
1391        if (toShrink <= 0)
1392            return 0;
1393
1394        // only shrink 10% of the maximum size
1395 long shrinkLimit = maxSize / 10;
1396        if (shrinkLimit == 0)
1397            shrinkLimit = 2;
1398
1399        if (toShrink < shrinkLimit)
1400            return toShrink;
1401        else
1402            return shrinkLimit;
1403    }
1404
1405    /**
1406        The background cleaner tries to make sure that there are serveral
1407        cleaned or invalied buffers ahead of the clock hand so that when they
1408        are evicted, they don't need to be cleaned.
1409
1410        The way this routine work is as follows, starting at the current clock
1411        hand position, go forward around the cache buffers, moving the same
1412        route that the clock hand moves. It keep tracks of the number of
1413        invalid or not recently used buffers it sees along the way. If it sees
1414        a not recently used buffer, it will clean it. After it has seen N
1415        invalid or not recently used buffers, or it has gone around and visited
1416        all buffers in the cache, it finished.
1417
1418        It does not clean recently used buffers.
1419
1420        <P>MT - must be MT-safe. It takes a snapshot of the current clock hand
1421        position (a synchronous call). Getting and looking at the next
1422        serveral cached item is synchronized on this (RESOLVE: probably doesn't
1423        need to be). Cleaning of the cacheable is handle by the cacheable itself.
1424
1425    */
1426    protected int performWork(boolean shrinkOnly)
1427    {
1428        long target;
1429        long toShrink;
1430        int maxLooks;
1431
1432        synchronized(this)
1433        {
1434            if (!active) {
1435                needService = false;
1436                return Serviceable.DONE;
1437            }
1438            else {
1439                long currentSize = getCurrentSize();
1440                target = currentSize / 20; // attempt to get 5% of the cache clean
1441 toShrink = wokenToClean ? 0 : shrinkSize(currentSize);
1442            }
1443
1444            if (target == 0) {
1445                wokenToClean = false;
1446                needService = false;
1447                return Serviceable.DONE;
1448            }
1449
1450            if (!wokenToClean && (toShrink <= 0)) {
1451                needService = false;
1452                return Serviceable.DONE;
1453            }
1454
1455            maxLooks = useByteCount ? (holders.size()/10) : (int) (target * 2);
1456        }
1457
1458        // try to clean the next N (target) cached item,
1459 long clean = 0;
1460        int cleaned = 0; // only used in debug
1461 CachedItem item = null;
1462        int currentPosition = 0;
1463
1464        String ThreadName = null;
1465
1466        if (SanityManager.DEBUG) {
1467          if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace))
1468          {
1469            ThreadName = Thread.currentThread().getName();
1470            SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " Cleaning " + name + " clientNumber " + myClientNumber);
1471          }
1472        }
1473
1474
1475        synchronized(this)
1476        {
1477            int itemCount = holders.size();
1478            currentPosition = clockHand;
1479                    
1480            // see if the cache needs to shrink
1481 boolean shrunk = false;
1482            long currentSize = getCurrentSize();
1483
1484            for (; shrinkOnly ? (currentSize > maximumSize && toShrink > 0) : (clean < target); item = null)
1485            {
1486                if (++currentPosition >= itemCount) {
1487                    if (itemCount == 0)
1488                        break;
1489
1490                    currentPosition = 0;
1491
1492                }
1493
1494                if (maxLooks-- <= 0)
1495                {
1496                    if (SanityManager.DEBUG) {
1497                        if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
1498                        SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " done one round of " + name);
1499                        }
1500                    }
1501
1502                    break; // done one round
1503 }
1504
1505                item = (CachedItem) holders.get(currentPosition);
1506
1507                if (item.isKept())
1508                    continue;
1509
1510                if (!item.isValid())
1511                {
1512                    if (toShrink > 0) {
1513
1514                        if (SanityManager.DEBUG) {
1515                            if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
1516                        SanityManager.DEBUG(ClockFactory.CacheTrace, name +
1517                                            " shrinking item " + item + " at position " + currentPosition);
1518                            }
1519                        }
1520
1521                        toShrink -= currentSize;
1522                        holders.remove(currentPosition);
1523                        if( useByteCount)
1524                            currentByteCount -= getItemSize( item);
1525                        currentSize = getCurrentSize();
1526                        toShrink += currentSize;
1527                        itemCount--;
1528
1529                        // account for the fact all the items have shifted down
1530 currentPosition--;
1531
1532                        shrunk = true;
1533                    }
1534                    continue;
1535                }
1536
1537                if (item.recentlyUsed())
1538                    continue;
1539
1540                // found a valid, not kept, and not recently used item
1541 // this item will be cleaned
1542 int itemSize = getItemSize( item);
1543                clean += itemSize;
1544                if (!item.getEntry().isDirty()) {
1545
1546                    if (toShrink > 0) {
1547                        if (SanityManager.DEBUG) {
1548                            if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
1549                            SanityManager.DEBUG(ClockFactory.CacheTrace, name +
1550                                            " shrinking item " + item + " at position " + currentPosition);
1551                            }
1552                        }
1553
1554                        toShrink -= currentSize;
1555                        removeIdentity(item);
1556                        holders.remove(currentPosition);
1557                        if( useByteCount)
1558                            currentByteCount -= getItemSize( item);
1559                        currentSize = getCurrentSize();
1560                        toShrink += currentSize;
1561                        itemCount--;
1562                        shrunk = true;
1563
1564                        // account for the fact all the items have shifted down
1565 currentPosition--;
1566                    }
1567                    continue;
1568                }
1569
1570                if (shrinkOnly)
1571                    continue;
1572
1573                // found one that needs cleaning, keep it to clean
1574 item.keepForClean();
1575                break;
1576            } // end of for loop
1577
1578            if (shrunk)
1579                trimToSize();
1580
1581            if (item == null) {
1582                wokenToClean = false;
1583                needService = false;
1584                return Serviceable.DONE;
1585            }
1586        } // end of sync block
1587
1588        try
1589        {
1590            if (SanityManager.DEBUG) {
1591                if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
1592                SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " cleaning entry in " + name);
1593                }
1594            }
1595
1596            item.clean(false);
1597            if (SanityManager.DEBUG) // only need stats for debug
1598 cleaned++;
1599                
1600        } catch (StandardException se) {
1601            // RESOLVE - should probably throw the error into the log.
1602 }
1603        finally
1604        {
1605            release(item);
1606            item = null;
1607        }
1608
1609        if (SanityManager.DEBUG) {
1610            if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
1611            SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " Found " + clean + " clean items, cleaned " +
1612                                cleaned + " items in " + name );
1613            }
1614        }
1615
1616        needService = true;
1617        return Serviceable.REQUEUE; // return is actually ignored.
1618 } // end of performWork
1619
1620    private int getItemSize( CachedItem item)
1621    {
1622        if( ! useByteCount)
1623            return 1;
1624        SizedCacheable entry = (SizedCacheable) item.getEntry();
1625        if( null == entry)
1626            return 0;
1627        return entry.getSize();
1628    } // end of getItemSize
1629
1630    /**
1631        Return statistics about cache that may be implemented.
1632    **/
1633    public synchronized long[] getCacheStats()
1634    {
1635        stat.currentSize = getCurrentSize();
1636        return stat.getStats();
1637    }
1638
1639    /**
1640        Reset the statistics to 0.
1641    **/
1642    public void resetCacheStats()
1643    {
1644        stat.reset();
1645    }
1646
1647     /**
1648     * @return the current maximum size of the cache.
1649     */
1650    public synchronized long getMaximumSize()
1651    {
1652        return maximumSize;
1653    }
1654   
1655    /**
1656     * Change the maximum size of the cache. If the size is decreased then cache entries
1657     * will be thrown out.
1658     *
1659     * @param newSize the new maximum cache size
1660     *
1661     * @exception StandardException Cloudscape Standard error policy
1662     */
1663    public void resize( long newSize) throws StandardException
1664    {
1665        boolean shrink;
1666
1667        synchronized( this)
1668        {
1669            maximumSize = newSize;
1670            stat.maxSize = maximumSize;
1671            shrink = ( shrinkSize( getCurrentSize()) > 0);
1672        }
1673        if( shrink)
1674        {
1675            performWork(true /* shrink only */);
1676            /* performWork does not remove recently used entries nor does it mark them as
1677             * not recently used. Therefore if the cache has not shrunk enough we will call rotateClock
1678             * to free up some entries.
1679             */
1680            if( shrinkSize( getCurrentSize()) > 0)
1681            {
1682                CachedItem freeItem = rotateClock( (float) 2.0);
1683                /* rotateClock(2.0) means that the clock will rotate through the cache as much as
1684                 * twice. If it does not find sufficient unused items the first time through it
1685                 * will almost certainly find enough of them the second time through, because it
1686                 * marked all the items as not recently used in the first pass.
1687                 *
1688                 * If the cache is very heavily used by other threads then a lot of the items marked as
1689                 * unused in the first pass may be used before rotateClock passes over them again. In this
1690                 * unlikely case rotateClock( 2.0) may not be able to clear out enough space to bring the
1691                 * current size down to the maximum. However the cache size should come down as rotateClock
1692                 * is called in the normal course of operation.
1693                 */
1694                if( freeItem != null)
1695                    freeItem.unkeepForCreate();
1696            }
1697        }
1698                
1699    } // end of resize;
1700
1701    private synchronized long getCurrentSize()
1702    {
1703        if( ! useByteCount)
1704            return holders.size();
1705        return currentByteCount + holders.size()*ITEM_OVERHEAD;
1706    }
1707
1708    /**
1709     * Perform an operation on (approximately) all entries that matches the filter,
1710     * or all entries if the filter is null. Entries that are added while the
1711     * cache is being scanned might or might not be missed.
1712     *
1713     * @param filter
1714     * @param operator
1715     */
1716    public void scan( Matchable filter, Operator operator)
1717    {
1718        int itemCount = 1;
1719        Cacheable entry = null;
1720        CachedItem item = null;
1721
1722        // Do not call the operator while holding the synchronization lock.
1723 // However we cannot access an item's links without holding the synchronization lock,
1724 // nor can we assume that an item is still in the cache unless we hold the synchronization
1725 // lock or the item is marked as kept.
1726 for( int position = 0;; position++)
1727        {
1728            synchronized( this)
1729            {
1730                if( null != item)
1731                {
1732                    release( item);
1733                    item = null;
1734                }
1735                    
1736                for( ; position < holders.size(); position++)
1737                {
1738                    item = (CachedItem) holders.get( position);
1739                    if( null != item)
1740                    {
1741                        try
1742                        {
1743                            entry = item.use();
1744                        }
1745                        catch( StandardException se)
1746                        {
1747                            continue;
1748                        }
1749                    
1750                        if( null != entry && (null == filter || filter.match( entry)))
1751                        {
1752                            item.keepForClean();
1753                            break;
1754                        }
1755                    }
1756                }
1757                if( position >= holders.size())
1758                    return;
1759
1760            } // end of synchronization
1761 operator.operate( entry);
1762            // Do not release the item until we have re-acquired the synchronization lock.
1763 // Otherwise the item may be removed and its next link invalidated.
1764 }
1765    } // end of scan
1766
1767    private int trimRequests = 0;
1768    
1769    /* Trim out invalid items from holders if there are a lot of them. This is expensive if
1770     * holders is large.
1771     * The caller must hold the cache synchronization lock.
1772     */
1773    private void trimToSize()
1774    {
1775        int size = holders.size();
1776
1777        // Trimming is expensive, don't do it often.
1778 trimRequests++;
1779        if( trimRequests < size/8)
1780            return;
1781        trimRequests = 0;
1782        
1783        // move invalid items to the end.
1784 int endPosition = size - 1;
1785
1786        int invalidCount = 0;
1787        for (int i = 0; i <= endPosition; i++)
1788        {
1789            CachedItem item = (CachedItem) holders.get(i);
1790
1791            if (item.isKept())
1792                continue;
1793
1794            if (item.isValid())
1795                continue;
1796
1797            invalidCount++;
1798
1799            // swap with an item later in the list
1800 // try to keep free items at the end of the holders array.
1801 for (; endPosition > i; endPosition--) {
1802                CachedItem last = (CachedItem) holders.get(endPosition);
1803                if (last.isValid()) {
1804                    holders.set(i, last);
1805                    holders.set(endPosition, item);
1806                    endPosition--;
1807                    break;
1808                }
1809            }
1810        }
1811        // small cache - don't shrink.
1812 if (size < 32)
1813            return;
1814        
1815        // now decide if we need to shrink the holder array or not.
1816 int validItems = size - invalidCount;
1817
1818        // over 75% entries used, don't shrink.
1819 if (validItems > ((3 * size) / 4))
1820            return;
1821
1822        // keep 10% new items.
1823 int newSize = validItems + (validItems / 10);
1824
1825        if (newSize >= size)
1826            return;
1827
1828        // remove items, starting at the end, where
1829 // hopefully most of the free items are.
1830 for (int r = size - 1; r > newSize; r--) {
1831            CachedItem remove = (CachedItem) holders.get(r);
1832            if (remove.isKept() || remove.isValid()) {
1833                continue;
1834            }
1835
1836            if (useByteCount) {
1837                currentByteCount -= getItemSize(remove);
1838            }
1839
1840            holders.remove(r);
1841        }
1842
1843        holders.trimToSize();
1844        // move the clock hand to the start of the invalid items.
1845 clockHand = validItems + 1;
1846
1847    } // end of trimToSize
1848}
1849

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags