in impl/src/main/java/org/apache/myfaces/util/lang/ConcurrentLRUCache.java [202:443]
private void markAndSweep()
{
// if we want to keep at least 1000 entries, then timestamps of
// current through current-1000 are guaranteed not to be the oldest (but that does
// not mean there are 1000 entries in that group... it's acutally anywhere between
// 1 and 1000).
// Also, if we want to remove 500 entries, then
// oldestEntry through oldestEntry+500 are guaranteed to be
// removed (however many there are there).
if (!markAndSweepLock.tryLock())
{
return;
}
try
{
long oldestEntry = this.oldestEntry;
isCleaning = true;
this.oldestEntry = oldestEntry; // volatile write to make isCleaning visible
long timeCurrent = stats.accessCounter.get();
int sz = stats.size.get();
int numRemoved = 0;
int numKept = 0;
long newestEntry = timeCurrent;
long newNewestEntry = -1;
long newOldestEntry = Long.MAX_VALUE;
int wantToKeep = lowerWaterMark;
int wantToRemove = sz - lowerWaterMark;
@SuppressWarnings("unchecked")
// generic array's are anoying
CacheEntry<K, V>[] eset = new CacheEntry[sz];
int eSize = 0;
// System.out.println("newestEntry="+newestEntry + " oldestEntry="+oldestEntry);
// System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
// " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
for (CacheEntry<K, V> ce : map.values())
{
// set lastAccessedCopy to avoid more volatile reads
ce.lastAccessedCopy = ce.lastAccessed;
long thisEntry = ce.lastAccessedCopy;
// since the wantToKeep group is likely to be bigger than wantToRemove, check it first
if (thisEntry > newestEntry - wantToKeep)
{
// this entry is guaranteed not to be in the bottom
// group, so do nothing.
numKept++;
newOldestEntry = Math.min(thisEntry, newOldestEntry);
}
else if (thisEntry < oldestEntry + wantToRemove)
{ // entry in bottom group?
// this entry is guaranteed to be in the bottom group
// so immediately remove it from the map.
evictEntry(ce.key);
numRemoved++;
}
else
{
// This entry *could* be in the bottom group.
// Collect these entries to avoid another full pass... this is wasted
// effort if enough entries are normally removed in this first pass.
// An alternate impl could make a full second pass.
if (eSize < eset.length - 1)
{
eset[eSize++] = ce;
newNewestEntry = Math.max(thisEntry, newNewestEntry);
newOldestEntry = Math.min(thisEntry, newOldestEntry);
}
}
}
// System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
// " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
// TODO: allow this to be customized in the constructor?
int numPasses = 1; // maximum number of linear passes over the data
// if we didn't remove enough entries, then make more passes
// over the values we collected, with updated min and max values.
while (sz - numRemoved > acceptableWaterMark && --numPasses >= 0)
{
oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
: newOldestEntry;
newOldestEntry = Long.MAX_VALUE;
newestEntry = newNewestEntry;
newNewestEntry = -1;
wantToKeep = lowerWaterMark - numKept;
wantToRemove = sz - lowerWaterMark - numRemoved;
// iterate backward to make it easy to remove items.
for (int i = eSize - 1; i >= 0; i--)
{
CacheEntry<K, V> ce = eset[i];
long thisEntry = ce.lastAccessedCopy;
if (thisEntry > newestEntry - wantToKeep)
{
// this entry is guaranteed not to be in the bottom
// group, so do nothing but remove it from the eset.
numKept++;
// remove the entry by moving the last element to it's position
eset[i] = eset[eSize - 1];
eSize--;
newOldestEntry = Math.min(thisEntry, newOldestEntry);
}
else if (thisEntry < oldestEntry + wantToRemove)
{ // entry in bottom group?
// this entry is guaranteed to be in the bottom group
// so immediately remove it from the map.
evictEntry(ce.key);
numRemoved++;
// remove the entry by moving the last element to it's position
eset[i] = eset[eSize - 1];
eSize--;
}
else
{
// This entry *could* be in the bottom group, so keep it in the eset,
// and update the stats.
newNewestEntry = Math.max(thisEntry, newNewestEntry);
newOldestEntry = Math.min(thisEntry, newOldestEntry);
}
}
// System.out.println("items removed:" + numRemoved + " numKept=" +
// numKept + " esetSz="+ eSize + " sz-numRemoved=" + (sz-numRemoved));
}
// if we still didn't remove enough entries, then make another pass while
// inserting into a priority queue
if (sz - numRemoved > acceptableWaterMark)
{
oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
: newOldestEntry;
newOldestEntry = Long.MAX_VALUE;
newestEntry = newNewestEntry;
newNewestEntry = -1;
wantToKeep = lowerWaterMark - numKept;
wantToRemove = sz - lowerWaterMark - numRemoved;
PQueue<K, V> queue = new PQueue<K, V>(wantToRemove);
for (int i = eSize - 1; i >= 0; i--)
{
CacheEntry<K, V> ce = eset[i];
long thisEntry = ce.lastAccessedCopy;
if (thisEntry > newestEntry - wantToKeep)
{
// this entry is guaranteed not to be in the bottom
// group, so do nothing but remove it from the eset.
numKept++;
// removal not necessary on last pass.
// eset[i] = eset[eSize-1];
// eSize--;
newOldestEntry = Math.min(thisEntry, newOldestEntry);
}
else if (thisEntry < oldestEntry + wantToRemove)
{ // entry in bottom group?
// this entry is guaranteed to be in the bottom group
// so immediately remove it.
evictEntry(ce.key);
numRemoved++;
// removal not necessary on last pass.
// eset[i] = eset[eSize-1];
// eSize--;
}
else
{
// This entry *could* be in the bottom group.
// add it to the priority queue
// everything in the priority queue will be removed, so keep track of
// the lowest value that ever comes back out of the queue.
// first reduce the size of the priority queue to account for
// the number of items we have already removed while executing
// this loop so far.
queue.myMaxSize = sz - lowerWaterMark - numRemoved;
while (queue.size() > queue.myMaxSize
&& queue.size() > 0)
{
CacheEntry otherEntry = queue.pop();
newOldestEntry = Math
.min(otherEntry.lastAccessedCopy,
newOldestEntry);
}
if (queue.myMaxSize <= 0)
{
break;
}
Object o = queue.myInsertWithOverflow(ce);
if (o != null)
{
newOldestEntry = Math.min(
((CacheEntry) o).lastAccessedCopy,
newOldestEntry);
}
}
}
// Now delete everything in the priority queue.
// avoid using pop() since order doesn't matter anymore
for (CacheEntry<K, V> ce : queue.getValues())
{
if (ce == null)
{
continue;
}
evictEntry(ce.key);
numRemoved++;
}
// System.out.println("items removed:" + numRemoved + " numKept=" + numKept +
// " initialQueueSize="+ wantToRemove + " finalQueueSize=" +
// queue.size() + " sz-numRemoved=" + (sz-numRemoved));
}
oldestEntry = newOldestEntry == Long.MAX_VALUE ? oldestEntry
: newOldestEntry;
this.oldestEntry = oldestEntry;
}
finally
{
isCleaning = false; // set before markAndSweep.unlock() for visibility
markAndSweepLock.unlock();
}
}