class SkullIsland::LRUCache

A very simple Least Recently Used (LRU) cache implementation. Stores data in a Hash, uses a dedicated Array for storing and sorting keys (and implementing the LRU algorithm), and doesn't bother storing access information for cache data. It stores hit and miss counts for the entire cache (not for individual keys). It also uses three mutexes for thread-safety: a write lock, a read lock, and a metadata lock.

Attributes

keys[R]
max_size[R]

Public Class Methods

new(max_size = 10_000) click to toggle source

@raise [Exceptions::InvalidCacheSize] if the max_size isn't an Integer

# File lib/skull_island/lru_cache.rb, line 14
def initialize(max_size = 10_000)
  raise Exceptions::InvalidCacheSize unless max_size.is_a?(Integer)

  @max_size     = max_size
  @hits         = 0
  @misses       = 0
  @keys         = []
  @data         = {}
  @read_mutex   = Mutex.new
  @write_mutex  = Mutex.new
  @meta_mutex   = Mutex.new
end

Public Instance Methods

[](key)
Alias for: retrieve
[]=(key, value)
Alias for: store
delete(key)
Alias for: invalidate
each(&block) click to toggle source

Allow iterating over the cached items, represented as key+value pairs

# File lib/skull_island/lru_cache.rb, line 57
def each(&block)
  to_hash.each(&block)
end
flush() click to toggle source

Similar to {#truncate} (in fact, it calls it) but it also clears the statistical metadata. @return [Boolean] was the flush operation successful?

# File lib/skull_island/lru_cache.rb, line 86
def flush
  if truncate
    @meta_mutex.synchronize do
      @hits = 0
      @misses = 0
    end
    true
  else
    false
  end
end
has?(key) click to toggle source

Does the cache contain the requested item? This doesn't count against cache misses @param key [Symbol] the index of the potentially cached object

# File lib/skull_island/lru_cache.rb, line 30
def has?(key)
  @meta_mutex.synchronize { @keys.include?(key) }
end
Also aliased as: has_key?, include?
has_key?(key)
Alias for: has?
include?(key)
Alias for: has?
invalidate(key) click to toggle source

Invalidate a cached item by its index / key. Returns `nil` if the object doesn't exist. @param key [Symbol] the cached object's index

# File lib/skull_island/lru_cache.rb, line 64
def invalidate(key)
  invalidate_key(key)
  @write_mutex.synchronize { @data.delete(key) }
end
Also aliased as: delete
marshal_dump() click to toggle source
# File lib/skull_island/lru_cache.rb, line 160
def marshal_dump
  [@max_size, @hits, @misses, @keys, @data]
end
marshal_load(array) click to toggle source
# File lib/skull_island/lru_cache.rb, line 164
def marshal_load(array)
  @max_size, @hits, @misses, @keys, @data = array
end
retrieve(key) click to toggle source

Retrieve an item from the cache. Returns `nil` if the item does not exist. Relies on {#store} returning the stored value to ensure the LRU algorithm is maintained safely. @param key [Symbol] the index to retrieve

# File lib/skull_island/lru_cache.rb, line 147
def retrieve(key)
  if has?(key)
    @meta_mutex.synchronize { @hits += 1 }
    # Looks dumb, but it actually only reorganizes the keys Array
    store(key, @read_mutex.synchronize { @data[key] })
  else
    @meta_mutex.synchronize { @misses += 1 }
    nil
  end
end
Also aliased as: []
size() click to toggle source

The number of items in the cache @return [Fixnum] key count

# File lib/skull_island/lru_cache.rb, line 39
def size
  @meta_mutex.synchronize { @keys.size }
end
statistics() click to toggle source

Provides a hash of the current metadata for the cache. It provides the current cache size (`:size`),the number of cache hits (`:hits`), and the number of cache misses (`:misses`). @return [Hash] cache statistics

# File lib/skull_island/lru_cache.rb, line 102
def statistics
  {
    size: size,
    hits: @meta_mutex.synchronize { @hits },
    misses: @meta_mutex.synchronize { @misses }
  }
end
store(key, value) click to toggle source

Store some data (`value`) indexed by a `key`. If an object exists with the same key, and the value is different, it will be overwritten. Storing a value causes its key to be moved to the end of the keys array (meaning it is the __most recently used__ item), and this happens on store regardless of whether or not the key previously existed. This behavior is relied upon by {#retrieve} to allow reorganization of the keys without necessarily modifying the data it indexes. Uses recursion for overwriting existing items.

@param key [Symbol] the index to use for referencing this cached item @param value [Object] the data to cache

# File lib/skull_island/lru_cache.rb, line 121
def store(key, value)
  if has?(key)
    if @read_mutex.synchronize { @data[key] == value }
      invalidate_key(key)
      @meta_mutex.synchronize { @keys << key }
      value
    else
      invalidate(key)
      store(key, value)
    end
  else
    invalidate(@keys.first) until size < @max_size

    @write_mutex.synchronize do
      @meta_mutex.synchronize { @keys << key }
      @data[key] = value
    end
  end
end
Also aliased as: []=
to_hash() click to toggle source

Convert the contents of the cache to a Hash @return [Hash] the cached data

# File lib/skull_island/lru_cache.rb, line 45
def to_hash
  @read_mutex.synchronize { @data.dup }
end
truncate() click to toggle source

Remove all items from the cache without clearing statistics @return [Boolean] was the truncate operation successful?

# File lib/skull_island/lru_cache.rb, line 73
def truncate
  @read_mutex.synchronize do
    @write_mutex.synchronize do
      @meta_mutex.synchronize { @keys = [] }
      @data = {}
    end
    @data.empty?
  end
end
values() click to toggle source

Return a raw Array of the cache data without its keys. Not particularly useful but it may be useful in the future. @return [Array] just the cached values

# File lib/skull_island/lru_cache.rb, line 52
def values
  @read_mutex.synchronize { @data.values }
end

Private Instance Methods

invalidate_key(key) click to toggle source

Invalidate just the key of a cached item. Dangerous if used incorrectly.

# File lib/skull_island/lru_cache.rb, line 171
def invalidate_key(key)
  @meta_mutex.synchronize { @keys.delete(key) }
end