clock.java

derby database source code.good for you.

		long toShrink = currentSize - maxSize;
		if (toShrink <= 0)
			return 0;

		// only shrink 10% of the maximum size
		long shrinkLimit = maxSize / 10;
		if (shrinkLimit == 0)
			shrinkLimit = 2;

		if (toShrink < shrinkLimit)
			return toShrink;
		else
			return shrinkLimit;
	}

	/**
		The background cleaner tries to make sure that there are serveral
		cleaned or invalied buffers ahead of the clock hand so that when they
		are evicted, they don't need to be cleaned.

		The way this routine work is as follows, starting at the current clock
		hand position, go forward around the cache buffers, moving the same
		route that the clock hand moves.  It keep tracks of the number of
		invalid or not recently used buffers it sees along the way.  If it sees
		a not recently used buffer, it will clean it.  After it has seen N
		invalid or not recently used buffers, or it has gone around and visited
		all buffers in the cache, it finished.

		It does not clean recently used buffers.

		<P>MT - must be MT-safe.  It takes a snapshot of the current clock hand
		position (a synchronous call).  Getting and looking at the next
		serveral cached item is synchronized on this (RESOLVE: probably doesn't
		need to be).  Cleaning of the cacheable is handle by the cacheable itself.

	*/
	protected int performWork(boolean shrinkOnly)
	{
		long target;
		long toShrink;
        int maxLooks;

		synchronized(this)
		{
			if (!active) {
				needService = false;
				return Serviceable.DONE;
			}
			else {
				long currentSize = getCurrentSize();
				target = currentSize / 20;  // attempt to get 5% of the cache clean
				toShrink = wokenToClean ? 0 : shrinkSize(currentSize);
			}

			if (target == 0) {
				wokenToClean = false;
				needService = false;
				return Serviceable.DONE;
			}

			if (!wokenToClean && (toShrink <= 0)) {
				needService = false;
				return Serviceable.DONE;
			}

            maxLooks = useByteCount ? (holders.size()/10) : (int) (target * 2);
		}

		// try to clean the next N (target) cached item, 
		long clean = 0;
		int cleaned = 0; // only used in debug
		CachedItem item = null;
        int currentPosition = 0;

		String ThreadName = null;

		if (SanityManager.DEBUG) {
		  if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace))
		  {
			ThreadName = Thread.currentThread().getName();
			SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " Cleaning " + name + " clientNumber " + myClientNumber);
		  }
		}


		synchronized(this)
		{
			int itemCount = holders.size();
			currentPosition = clockHand;
					
			// see if the cache needs to shrink
			boolean shrunk = false;
            long currentSize = getCurrentSize();

			for (; shrinkOnly ? (currentSize > maximumSize && toShrink > 0) : (clean < target); item = null)
			{				
				if (++currentPosition >= itemCount) {
					if (itemCount == 0)
						break;

					currentPosition = 0;

				}

				if (maxLooks-- <= 0)
				{
					if (SanityManager.DEBUG) {
						if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
						SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " done one round of " + name);
						}
					}

					break;			// done one round
				}

				item = (CachedItem) holders.get(currentPosition);

				if (item.isKept())
					continue;

				if (!item.isValid())
				{
					if (toShrink > 0) {

						if (SanityManager.DEBUG) {
							if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
						SanityManager.DEBUG(ClockFactory.CacheTrace, name + 
											" shrinking item " + item + " at position " + currentPosition);
							}
						}

                        toShrink -= currentSize;
						holders.remove(currentPosition);
                        if( useByteCount)
                            currentByteCount -= getItemSize( item);
                        currentSize = getCurrentSize();
                        toShrink += currentSize;
                        itemCount--;

						// account for the fact all the items have shifted down
						currentPosition--;

						shrunk = true;
					}		
					continue;
				}

				if (item.recentlyUsed())
					continue;

				// found a valid, not kept, and not recently used item
				// this item will be cleaned
                int itemSize = getItemSize( item);
				clean += itemSize;
				if (!item.getEntry().isDirty()) {

					if (toShrink > 0) {
						if (SanityManager.DEBUG) {
							if (SanityManager.DEBUG_ON(ClockFactory.CacheTrace)) {
							SanityManager.DEBUG(ClockFactory.CacheTrace, name + 
											" shrinking item " + item + " at position " + currentPosition);
							}
						}

                        toShrink -= currentSize;
						removeIdentity(item);
						holders.remove(currentPosition);
                        if( useByteCount)
                            currentByteCount -= getItemSize( item);
                        currentSize = getCurrentSize();
                        toShrink += currentSize;
                        itemCount--;
                        shrunk = true;

						// account for the fact all the items have shifted down
						currentPosition--;
					}		
					continue;
				}

				if (shrinkOnly)
					continue;

				// found one that needs cleaning, keep it to clean
				item.keepForClean();
				break;
			} // end of for loop

			if (shrunk)
				trimToSize();

			if (item == null) {
				wokenToClean = false;
				needService = false;
				return Serviceable.DONE;
			}
		} // end of sync block

		try
		{
			if (SanityManager.DEBUG) {
				if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
				SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " cleaning entry  in " + name);
				}
			}

			item.clean(false);
			if (SanityManager.DEBUG) // only need stats for debug
				   cleaned++;
				
		} catch (StandardException se) {
			// RESOLVE - should probably throw the error into the log.
		}
		finally
		{
			release(item);
			item = null;
		}

		if (SanityManager.DEBUG) {
			if (SanityManager.DEBUG_ON(DaemonService.DaemonTrace)) {
			SanityManager.DEBUG(DaemonService.DaemonTrace, ThreadName + " Found " + clean + " clean items, cleaned " +
								cleaned + " items in " + name );
			}
		}

		needService = true;
		return Serviceable.REQUEUE; // return is actually ignored.
	} // end of performWork

    private int getItemSize( CachedItem item)
    {
        if( ! useByteCount)
            return 1;
        SizedCacheable entry = (SizedCacheable) item.getEntry();
        if( null == entry)
            return 0;
        return entry.getSize();
    } // end of getItemSize
    
	/**
		Return statistics about cache that may be implemented.
	**/
	public synchronized long[] getCacheStats()
    {
		stat.currentSize = getCurrentSize();
		return stat.getStats();
    }

	/**
		Reset the statistics to 0.
	**/
	public void resetCacheStats()
    {
		stat.reset();
	}

     /**
     * @return the current maximum size of the cache.
     */
	public synchronized long getMaximumSize()
    {
        return maximumSize;
    }
   
    /**
     * Change the maximum size of the cache. If the size is decreased then cache entries
     * will be thrown out.
     *
     * @param newSize the new maximum cache size
     *
     * @exception StandardException Cloudscape Standard error policy
     */
	public void resize( long newSize) throws StandardException
    {
        boolean shrink;

        synchronized( this)
        {
            maximumSize = newSize;
            stat.maxSize = maximumSize;
            shrink = ( shrinkSize( getCurrentSize()) > 0);
        }
        if( shrink)
        {
            performWork(true /* shrink only */);
            /* performWork does not remove recently used entries nor does it mark them as
             * not recently used. Therefore if the cache has not shrunk enough we will call rotateClock
             * to free up some entries.
             */
            if( shrinkSize( getCurrentSize()) > 0)
            {
                CachedItem freeItem = rotateClock( (float) 2.0);
                /* rotateClock(2.0) means that the clock will rotate through the cache as much as
                 * twice.  If it does not find sufficient unused items the first time through it
                 * will almost certainly find enough of them the second time through, because it
                 * marked all the items as not recently used in the first pass.
                 *
                 * If the cache is very heavily used by other threads then a lot of the items marked as
                 * unused in the first pass may be used before rotateClock passes over them again. In this
                 * unlikely case rotateClock( 2.0) may not be able to clear out enough space to bring the
                 * current size down to the maximum. However the cache size should come down as rotateClock
                 * is called in the normal course of operation.
                 */
                if( freeItem != null)
                    freeItem.unkeepForCreate();
            }
        }
                
    } // end of resize;
    
    private synchronized long getCurrentSize()
    {
        if( ! useByteCount)
            return holders.size();
        return currentByteCount + holders.size()*ITEM_OVERHEAD;
    }

    /**
     * Perform an operation on (approximately) all entries that matches the filter,
     * or all entries if the filter is null.  Entries that are added while the
     * cache is being scanned might or might not be missed.
     *
     * @param filter
     * @param operator
     */
    public void scan( Matchable filter, Operator operator)
    {
        int itemCount = 1;
        Cacheable entry = null;
        CachedItem item = null;

        // Do not call the operator while holding the synchronization lock.
        // However we cannot access an item's links without holding the synchronization lock,
        // nor can we assume that an item is still in the cache unless we hold the synchronization
        // lock or the item is marked as kept.
        for( int position = 0;; position++)
        {
            synchronized( this)
            {
                if( null != item)
                {
                    release( item);
                    item = null;
                }
                    
                for( ; position < holders.size(); position++)
                {
                    item = (CachedItem) holders.get( position);
                    if( null != item)
                    {
                        try
                        {
                            entry = item.use();
                        }
                        catch( StandardException se)
                        {
                            continue;
                        }
                    
                        if( null != entry && (null == filter || filter.match( entry)))
                        {
                            item.keepForClean();
                            break;
                        }
                    }
                }
                if( position >= holders.size())
                    return;

            } // end of synchronization
            operator.operate( entry);
            // Do not release the item until we have re-acquired the synchronization lock.
            // Otherwise the item may be removed and its next link invalidated.
        }
    } // end of scan

    private int trimRequests = 0;
    
    /* Trim out invalid items from holders if there are a lot of them. This is expensive if
     * holders is large.
     * The caller must hold the cache synchronization lock.
     */
    private void trimToSize()
    {
        int size = holders.size();

        // Trimming is expensive, don't do it often.
        trimRequests++;
        if( trimRequests < size/8)
            return;
        trimRequests = 0;
        
		// move invalid items to the end.
		int endPosition = size - 1;

		int invalidCount = 0;
        for (int i = 0; i <= endPosition; i++)
        {
            CachedItem item = (CachedItem) holders.get(i);

			if (item.isKept())
				continue;

            if (item.isValid())
				continue;

			invalidCount++;

			// swap with an item later in the list
			// try to keep free items at the end of the holders array.
			for (; endPosition > i; endPosition--) {
				CachedItem last = (CachedItem) holders.get(endPosition);
				if (last.isValid()) {
					holders.set(i, last);
					holders.set(endPosition, item);
					endPosition--;
					break;
				}
			}
		}
		// small cache - don't shrink.
		if (size < 32)
			return;
		
		// now decide if we need to shrink the holder array or not.
		int validItems = size - invalidCount;

		// over 75% entries used, don't shrink.
		if (validItems > ((3 * size) / 4))
			return;

		// keep 10% new items.
		int newSize = validItems + (validItems / 10);

		if (newSize >= size)
			return;

		// remove items, starting at the end,  where
		// hopefully most of the free items are.
		for (int r = size - 1; r > newSize; r--) {
			CachedItem remove = (CachedItem) holders.get(r);
			if (remove.isKept() || remove.isValid()) {
				continue;
			}

			if (useByteCount) {
				currentByteCount -= getItemSize(remove);
			}

			holders.remove(r);
		}

		holders.trimToSize();
		// move the clock hand to the start of the invalid items.
		clockHand = validItems + 1;

    } // end of trimToSize
}