Package net.sf.saxon.expr.sort

Class LFUCache<K,V>

java.lang.Object
net.sf.saxon.expr.sort.LFUCache<K,V>
public class LFUCache<K,V> extends Object
A "Least Frequently Used" cache. When the cache grows too large, we discard entries whose reference counters are below some threshold. This is cheaper than an LRU (least recently used) algorithm, because access to the map doesn't require any locking against concurrent activity. Unlike classic LFU algorithms where the cache size has a fixed upper bound, we allow it to grow beyond the target size and then do a bulk deletion of infrequently used entries. We delete all entries whose usage counter is below some threshold, learning the best threshold to apply from experience of previous reorganisations. There is no synchronization. The underlying map itself is thread-safe, but we make no attempt to prevent two concurrent threads garbage collecting at the same time: if this happens, no harm is caused, because it's only a cache and lost entries will simply be recomputed. Equally, the incrementing of counters isn't synchronized because they don't need to be exact.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LFUCache(int cacheSize)
    Creates a new LCU cache, suitable for use only within a single thread.
    LFUCache(int cacheSize, boolean concurrent)
    Creates a new LCU cache, with the option of making it thread-safe

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Clear the cache
    boolean
    containsKey(K key)
    Ask whether a given key is present in the cache.
    The usage count of the entry is incremented if the entry exists.
    V
    get(K key)
    Retrieves an entry from the cache.
    The usage count of the entry is incremented.
    void
    put(K key, V value)
    Adds an entry to this cache.
    int
    size()
    Get the number of entries in the cache

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • LFUCache

      public LFUCache(int cacheSize)
      Creates a new LCU cache, suitable for use only within a single thread.
      Parameters:
      cacheSize - the target number of entries to be kept in this cache.

    • LFUCache

      public LFUCache(int cacheSize, boolean concurrent)
      Creates a new LCU cache, with the option of making it thread-safe
      Parameters:
      cacheSize - the maximum number of entries that will be kept in this cache.
      concurrent - set to true if concurrent access is required, so that the underlying map will be thread-safe

  • Method Details

    • get

      public V get(K key)
      Retrieves an entry from the cache.
      The usage count of the entry is incremented.
      Parameters:
      key - the key whose associated value is to be returned.
      Returns:
      the value associated to this key, or null if no value with this key exists in the cache.

    • containsKey

      public boolean containsKey(K key)
      Ask whether a given key is present in the cache.
      The usage count of the entry is incremented if the entry exists.
      Parameters:
      key - the key to be tested
      Returns:
      true if the key is present

    • put

      public void put(K key, V value)
      Adds an entry to this cache. It is assumed that the caller has already checked that the cache doesn't already contain a suitable entry, so we treat each entry as a new one. If the cache is exceeds a threshold size of three times the target size, it is rebuilt with infrequently used entries purged.
      Parameters:
      key - the key with which the specified value is to be associated.
      value - a value to be associated with the specified key.

    • clear

      public void clear()
      Clear the cache

    • size

      public int size()
      Get the number of entries in the cache
      Returns:
      the number of entries