<s> package org . eclipse . jdt . internal . core . util ; import java . text . NumberFormat ; import java . util . Enumeration ; import java . util . Hashtable ; public class LRUCache implements Cloneable { protected static class LRUCacheEntry { public Object key ; public Object value ; public int timestamp ; public int space ; public LRUCacheEntry previous ; public LRUCacheEntry next ; public LRUCacheEntry ( Object key , Object value , int space ) { this . key = key ; this . value = value ; this . space = space ; } public String toString ( ) { return "" + this . key + "-->" + this . value + "]" ; } } public class Stats { private int [ ] counters = new int [ 20 ] ; private long [ ] timestamps = new long [ 20 ] ; private int counterIndex = - 1 ; private void add ( int counter ) { for ( int i = 0 ; i <= this . counterIndex ; i ++ ) { if ( this . counters [ i ] == counter ) return ; } int length = this . counters . length ; if ( ++ this . counterIndex == length ) { int newLength = this . counters . length * 2 ; System . arraycopy ( this . counters , 0 , this . counters = new int [ newLength ] , 0 , length ) ; System . arraycopy ( this . timestamps , 0 , this . timestamps = new long [ newLength ] , 0 , length ) ; } this . counters [ this . counterIndex ] = counter ; this . timestamps [ this . counterIndex ] = System . currentTimeMillis ( ) ; } private String getAverageAge ( long totalTime , int numberOfElements , long currentTime ) { if ( numberOfElements == 0 ) return "N/A" ; long time = totalTime / numberOfElements ; long age = currentTime - time ; long ageInSeconds = age / 1000 ; int seconds = 0 ; int minutes = 0 ; int hours = 0 ; int days = 0 ; if ( ageInSeconds > 60 ) { long ageInMin = ageInSeconds / 60 ; seconds = ( int ) ( ageInSeconds - ( 60 * ageInMin ) ) ; if ( ageInMin > 60 ) { long ageInHours = ageInMin / 60 ; minutes = ( int ) ( ageInMin - ( 60 * ageInHours ) ) ; if ( ageInHours > 24 ) { long ageInDays = ageInHours / 24 ; hours = ( int ) ( ageInHours - ( 24 * ageInDays ) ) ; days = ( int ) ageInDays ; } else { hours = ( int ) ageInHours ; } } else { minutes = ( int ) ageInMin ; } } else { seconds = ( int ) ageInSeconds ; } StringBuffer buffer = new StringBuffer ( ) ; if ( days > 0 ) { buffer . append ( days ) ; buffer . append ( " days " ) ; } if ( hours > 0 ) { buffer . append ( hours ) ; buffer . append ( " hours " ) ; } if ( minutes > 0 ) { buffer . append ( minutes ) ; buffer . append ( " minutes " ) ; } buffer . append ( seconds ) ; buffer . append ( " seconds" ) ; return buffer . toString ( ) ; } private long getTimestamps ( int counter ) { for ( int i = 0 ; i <= this . counterIndex ; i ++ ) { if ( this . counters [ i ] >= counter ) return this . timestamps [ i ] ; } return - 1 ; } public synchronized String printStats ( ) { int numberOfElements = LRUCache . this . currentSpace ; if ( numberOfElements == 0 ) { return "" ; } StringBuffer buffer = new StringBuffer ( ) ; buffer . append ( "" ) ; buffer . append ( numberOfElements ) ; final int numberOfGroups = 5 ; int numberOfElementsPerGroup = numberOfElements / numberOfGroups ; buffer . append ( "n(" ) ; buffer . append ( numberOfGroups ) ; buffer . append ( " groups of " ) ; buffer . append ( numberOfElementsPerGroup ) ; buffer . append ( " elements)" ) ; buffer . append ( "" ) ; int groupNumber = 1 ; int elementCounter = 0 ; LRUCacheEntry entry = LRUCache . this . entryQueueTail ; long currentTime = System . currentTimeMillis ( ) ; long accumulatedTime = 0 ; while ( entry != null ) { long timeStamps = getTimestamps ( entry . timestamp ) ; if ( timeStamps > 0 ) { accumulatedTime += timeStamps ; elementCounter ++ ; } if ( elementCounter >= numberOfElementsPerGroup && ( groupNumber < numberOfGroups ) ) { buffer . append ( "nGroup " ) ; buffer . append ( groupNumber ) ; if ( groupNumber == 1 ) { buffer . append ( " (oldest)t: " ) ; } else { buffer . append ( "tt: " ) ; } groupNumber ++ ; buffer . append ( getAverageAge ( accumulatedTime , elementCounter , currentTime ) ) ; elementCounter = 0 ; accumulatedTime = 0 ; } entry = entry . previous ; } buffer . append ( "nGroup " ) ; buffer . append ( numberOfGroups ) ; buffer . append ( "" ) ; buffer . append ( getAverageAge ( accumulatedTime , elementCounter , currentTime ) ) ; return buffer . toString ( ) ; } private void removeCountersOlderThan ( int counter ) { for ( int i = 0 ; i <= this . counterIndex ; i ++ ) { if ( this . counters [ i ] >= counter ) { if ( i > 0 ) { int length = this . counterIndex - i + 1 ; System . arraycopy ( this . counters , i , this . counters , 0 , length ) ; System . arraycopy ( this . timestamps , i , this . timestamps , 0 , length ) ; this . counterIndex = length ; } return ; } } } public Object getOldestElement ( ) { return LRUCache . this . getOldestElement ( ) ; } public long getOldestTimestamps ( ) { return getTimestamps ( getOldestTimestampCounter ( ) ) ; } public synchronized void snapshot ( ) { removeCountersOlderThan ( getOldestTimestampCounter ( ) ) ; add ( getNewestTimestampCounter ( ) ) ; } } protected int currentSpace ; protected int spaceLimit ; protected int timestampCounter ; protected Hashtable entryTable ; protected LRUCacheEntry entryQueue ; protected LRUCacheEntry entryQueueTail ; protected static final int DEFAULT_SPACELIMIT = 100 ; public LRUCache ( ) { this ( DEFAULT_SPACELIMIT ) ; } public LRUCache ( int size ) { this . timestampCounter = this . currentSpace = 0 ; this . entryQueue = this . entryQueueTail = null ; this . entryTable = new Hashtable ( size ) ; this . spaceLimit = size ; } public Object clone ( ) { LRUCache newCache = newInstance ( this . spaceLimit ) ; LRUCacheEntry qEntry ; qEntry = this . entryQueueTail ; while ( qEntry != null ) { newCache . privateAdd ( qEntry . key , qEntry . value , qEntry . space ) ; qEntry = qEntry . previous ; } return newCache ; } public double fillingRatio ( ) { return ( this . currentSpace ) * 100.0 / this . spaceLimit ; } public void flush ( ) { this . currentSpace = 0 ; LRUCacheEntry entry = this . entryQueueTail ; this . entryTable = new Hashtable ( ) ; this . entryQueue = this . entryQueueTail = null ; while ( entry != null ) { entry = entry . previous ; } } public void flush ( Object key ) { LRUCacheEntry entry ; entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry == null ) return ; privateRemoveEntry ( entry , false ) ; } public Object getKey ( Object key ) { LRUCacheEntry entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry == null ) { return key ; } return entry . key ; } public Object get ( Object key ) { LRUCacheEntry entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry == null ) { return null ; } updateTimestamp ( entry ) ; return entry . value ; } public int getCurrentSpace ( ) { return this . currentSpace ; } public int getNewestTimestampCounter ( ) { return this . entryQueue == null ? 0 : this . entryQueue . timestamp ; } public int getOldestTimestampCounter ( ) { return this . entryQueueTail == null ? 0 : this . entryQueueTail . timestamp ; } public Object getOldestElement ( ) { return this . entryQueueTail == null ? null : this . entryQueueTail . key ; } public int getSpaceLimit ( ) { return this . spaceLimit ; } public Enumeration keys ( ) { return this . entryTable . keys ( ) ; } public ICacheEnumeration keysAndValues ( ) { return new ICacheEnumeration ( ) { Enumeration values = LRUCache . this . entryTable . elements ( ) ; LRUCacheEntry entry ; public boolean hasMoreElements ( ) { return this . values . hasMoreElements ( ) ; } public Object nextElement ( ) { this . entry = ( LRUCacheEntry ) this . values . nextElement ( ) ; return this . entry . key ; } public Object getValue ( ) { if ( this . entry == null ) { throw new java . util . NoSuchElementException ( ) ; } return this . entry . value ; } } ; } protected boolean makeSpace ( int space ) { int limit ; limit = getSpaceLimit ( ) ; if ( this . currentSpace + space <= limit ) { return true ; } if ( space > limit ) { return false ; } while ( this . currentSpace + space > limit && this . entryQueueTail != null ) { privateRemoveEntry ( this . entryQueueTail , false ) ; } return true ; } protected LRUCache newInstance ( int size ) { return new LRUCache ( size ) ; } public Object peek ( Object key ) { LRUCacheEntry entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry == null ) { return null ; } return entry . value ; } protected void privateAdd ( Object key , Object value , int space ) { LRUCacheEntry entry ; entry = new LRUCacheEntry ( key , value , space ) ; privateAddEntry ( entry , false ) ; } protected void privateAddEntry ( LRUCacheEntry entry , boolean shuffle ) { if ( ! shuffle ) { this . entryTable . put ( entry . key , entry ) ; this . currentSpace += entry . space ; } entry . timestamp = this . timestampCounter ++ ; entry . next = this . entryQueue ; entry . previous = null ; if ( this . entryQueue == null ) { this . entryQueueTail = entry ; } else { this . entryQueue . previous = entry ; } this . entryQueue = entry ; } protected void privateRemoveEntry ( LRUCacheEntry entry , boolean shuffle ) { LRUCacheEntry previous , next ; previous = entry . previous ; next = entry . next ; if ( ! shuffle ) { this . entryTable . remove ( entry . key ) ; this . currentSpace -= entry . space ; } if ( previous == null ) { this . entryQueue = next ; } else { previous . next = next ; } if ( next == null ) { this . entryQueueTail = previous ; } else { next . previous = previous ; } } public Object put ( Object key , Object value ) { int newSpace , oldSpace , newTotal ; LRUCacheEntry entry ; newSpace = spaceFor ( value ) ; entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry != null ) { oldSpace = entry . space ; newTotal = getCurrentSpace ( ) - oldSpace + newSpace ; if ( newTotal <= getSpaceLimit ( ) ) { updateTimestamp ( entry ) ; entry . value = value ; entry . space = newSpace ; this . currentSpace = newTotal ; return value ; } else { privateRemoveEntry ( entry , false ) ; } } if ( makeSpace ( newSpace ) ) { privateAdd ( key , value , newSpace ) ; } return value ; } public Object removeKey ( Object key ) { LRUCacheEntry entry = ( LRUCacheEntry ) this . entryTable . get ( key ) ; if ( entry == null ) { return null ; } Object value = entry . value ; privateRemoveEntry ( entry , false ) ; return value ; } public void setSpaceLimit ( int limit ) { if ( limit < this . spaceLimit ) { makeSpace ( this . spaceLimit - limit ) ; } this . spaceLimit = limit ; } protected int spaceFor ( Object value ) { if ( value instanceof ILRUCacheable ) { return ( ( ILRUCacheable ) value ) . getCacheFootprint ( ) ; } else { return 1 ; } } public String toString ( ) { return toStringFillingRation ( "LRUCache" ) + toStringContents ( ) ; } protected String toStringContents ( ) { StringBuffer result = new StringBuffer ( ) ; int length = this . entryTable . size ( ) ; Object [ ] unsortedKeys = new Object [ length ] ; String [ ] unsortedToStrings = new String [ length ] ; Enumeration e = keys ( ) ; for ( int i = 0 ; i < length ; i ++ ) { Object key = e . nextElement ( ) ; unsortedKeys [ i ] = key ; unsortedToStrings [ i ] = ( key instanceof org . eclipse . jdt . internal . core . JavaElement ) ? ( ( org . eclipse . jdt . internal . core . JavaElement ) key ) . getElementName ( ) : key . toString ( ) ; } ToStringSorter sorter = new ToStringSorter ( ) ; sorter . sort ( unsortedKeys , unsortedToStrings ) ; for ( int i = 0 ; i < length ; i ++ ) { String toString = sorter . sortedStrings [ i ] ; Object value = get ( sorter . sortedObjects [ i ] ) ; result . append ( toString ) ; result . append ( " -> " ) ; result . append ( value ) ; result . append ( "n" ) ; } return result . toString ( ) ; } public String toStringFillingRation ( String cacheName ) { StringBuffer buffer = new StringBuffer ( cacheName ) ; buffer . append ( '[' ) ; buffer . append ( getSpaceLimit ( ) ) ; buffer . append ( "]: " ) ; buffer . append ( NumberFormat . getInstance ( ) . format ( fillingRatio ( ) ) ) ; buffer . append ( "% full" ) ; return buffer . toString ( ) ; } protected void updateTimestamp ( LRUCacheEntry entry ) { entry . timestamp = this . timestampCounter ++ ; if ( this . entryQueue != entry ) { privateRemoveEntry ( entry , true ) ; privateAddEntry ( entry , true ) ; } return ; } } </s>