Package net.sf.saxon.expr.sort

Class LFUCache<K,​V>

  • public class LFUCache<K,​V>
extends java.lang.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

      All Methods Instance Methods Concrete Methods 
      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 Detail

      • 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 Detail

      • 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