class SetAssociativeCache

Public Class Methods

new(params = {}) click to toggle source
# File lib/set_associative_cache.rb, line 18
def initialize(params = {})
  _validate_params(params)

  @hash_map = _initialize_hash_map(params)
  @linked_list = LinkedList.new
  @cache_type = params[:type] || :LRU
  @replacement_algo = params[:replacement_algo] || _select_replacement_algo
  @capacity = _initialize_capacity(params)
  @value_class = params[:value_class]
end

Public Instance Methods

add(value) click to toggle source

Handles adding new values and updating existing values.

# File lib/set_associative_cache.rb, line 30
def add(value)
  search_node = value.class == LinkedListNode ? value : LinkedListNode.new(value)
  @value_class ||= search_node.value.class

  raise "Error in SetAssociativeCache#add - value class '#{value.class}' should be '#{@value_class}'" \
    unless search_node.value.class == @value_class
  key = @hash_map.create_key(search_node)
  node = @hash_map[key]

  if node
    # update value if needed (ex. if a part of the value was updated but the key stayed the same)
    node.value = value;

    @linked_list.remove(node)
  else
    node = LinkedListNode.new(value)
    @hash_map.add(node)
    instance_exec([], &@replacement_algo) if @hash_map.length > @capacity
  end

  @linked_list.prepend(node)
  @last_addition = node

  node
end
each() { |node| ... } click to toggle source

Loops over the nodes from head to tail in the linked list

# File lib/set_associative_cache.rb, line 64
def each
  @linked_list.each { |node| yield node }
end
first() click to toggle source

Returns the newest / most recent node in the cache

# File lib/set_associative_cache.rb, line 74
def first
  @linked_list.first
end
get_node(value) click to toggle source

Finds the node whose value matches a the corresponding key if it exists.

# File lib/set_associative_cache.rb, line 57
def get_node(value)
  node = value.class == LinkedListNode ? value : LinkedListNode.new(value)
  key = @hash_map.create_key(node)
  @hash_map[key]
end
include?(value) click to toggle source
# File lib/set_associative_cache.rb, line 83
def include?(value)
  get_node(value) ? true : false
end
last() click to toggle source

Returns the oldest / least recent node in the cache

# File lib/set_associative_cache.rb, line 79
def last
  @linked_list.last
end
length() click to toggle source

Returns the number of values in the cache

# File lib/set_associative_cache.rb, line 69
def length
  @hash_map.length
end

Private Instance Methods

_initialize_capacity(params) click to toggle source
# File lib/set_associative_cache.rb, line 121
def _initialize_capacity(params)
  if params[:capacity]
    raise "Error in SetAssociativeCache#initialize - :capacity must be at least 4" unless params[:capacity] >= 4
    return params[:capacity]
  end

  Float::INFINITY
end
_initialize_hash_map(params) click to toggle source
# File lib/set_associative_cache.rb, line 100
def _initialize_hash_map(params)
  if params[:key_generator_prc]
    raise "Error invalid type for :key_generator_prc, expected Proc, got '#{params[:key_generator_prc].class}'" unless params[:key_generator_prc].class == Proc
    key_generator_prc = Proc.new { |node| params[:key_generator_prc].call(node.value).hash }
  else HashMap.new
    key_generator_prc = Proc.new { |node| node.value.hash }
  end

  HashMap.new(&key_generator_prc)
end
_select_replacement_algo() click to toggle source
# File lib/set_associative_cache.rb, line 111
def _select_replacement_algo
  if @cache_type == :LRU
    return @@lru_replacement_proc
  elsif @cache_type == :MRU
    return @@mru_replacement_proc
  else
    raise "Unrecognized cache :type provided '#{@cache_type}' and no :replacement_algo was given"
  end
end
_validate_params(params) click to toggle source
# File lib/set_associative_cache.rb, line 89
def _validate_params(params)
  raise "Error in SetAssociativeCache#initialize - params input should be a hash" unless params.class == Hash
  raise "Error in SetAssociativeCache#initialize - params keys should all be symbols" unless params.all? { |key, _| key.class == Symbol }

  params.each do |key, val|
    raise "Error in SetAssociativeCache#initialize - Unrecognized param '#{key}'" unless @@param_types.has_key?(key)
    raise "Error in SetAssociativeCache#initialize - Invalid type for params[:#{key}], expected #{@@param_types[key]}, got #{val.class}" \
      unless @@param_types[key] == val.class
  end
end