class LRUHash

Hash with LRU expiry policy. There are at most max_size elements in a LruHash. When adding more elements old elements are removed according to LRU policy.

Constants

FETCH
Node

A single node in the doubly linked LRU list of nodes

Attributes

default[RW]
default_proc[RW]
max_size[R]
release_proc[RW]

Public Class Methods

new(max_size, default_value = nil, &block) click to toggle source
# File lib/bio/system/lruhash.rb, line 19
def initialize(max_size, default_value = nil, &block)
  @max_size = normalize_max(max_size)
  @default = default_value
  @default_proc = block

  @h = {}
  @head = Node.new
  @tail = front(Node.new)
end

Public Instance Methods

[](key) click to toggle source
# File lib/bio/system/lruhash.rb, line 79
def [](key)
  fetch(key) do |k|
    @default_proc ? @default_proc[self, k] : default
  end
end
[]=(key, value)
Alias for: store
assoc(key) click to toggle source
# File lib/bio/system/lruhash.rb, line 115
def assoc(key)
  n = @h[key]

  if n
    front(n)
    [n.key, n.value]
  end
end
clear() click to toggle source
# File lib/bio/system/lruhash.rb, line 182
def clear
  until empty?
    delete_oldest
  end

  self
end
delete(key) click to toggle source
# File lib/bio/system/lruhash.rb, line 162
def delete(key)
  n = @h[key] and remove_node(n).value
end
delete_if() { |key, value| ... } click to toggle source
# File lib/bio/system/lruhash.rb, line 166
def delete_if
  each_node do |n|
    remove_node n if yield n.key, n.value
  end
end
each()
Alias for: each_pair
each_key() { |key| ... } click to toggle source
# File lib/bio/system/lruhash.rb, line 41
def each_key
  if block_given?
    each_node do |n|
      yield n.key
    end
  else
    enum_for :each_key
  end
end
each_pair() { |key, value| ... } click to toggle source
# File lib/bio/system/lruhash.rb, line 29
def each_pair
  if block_given?
    each_node do |n|
      yield [n.key, n.value]
    end
  else
    enum_for :each_pair
  end
end
Also aliased as: each
each_value() { |value| ... } click to toggle source
# File lib/bio/system/lruhash.rb, line 51
def each_value
  if block_given?
    each_node do |n|
      yield n.value
    end
  else
    enum_for :each_value
  end
end
empty?() click to toggle source
# File lib/bio/system/lruhash.rb, line 65
def empty?
  @head.succ.equal? @tail
end
fetch(key, &b) click to toggle source
# File lib/bio/system/lruhash.rb, line 69
def fetch(key, &b)
  n = @h[key]

  if n
    front(n).value
  else
    (b || FETCH)[key]
  end
end
has_key?(key) click to toggle source
# File lib/bio/system/lruhash.rb, line 93
def has_key?(key)
  @h.has_key? key
end
Also aliased as: key?, member?, include?
has_value?(value) click to toggle source
# File lib/bio/system/lruhash.rb, line 101
def has_value?(value)
  each_pair do |k, v|
    return true if value.eql? v
  end

  false
end
Also aliased as: value?
include?(key)
Alias for: has_key?
inspect()
Alias for: to_s
key(value) click to toggle source
# File lib/bio/system/lruhash.rb, line 134
def key(value)
  pair = rassoc(value) and pair.first
end
key?(key)
Alias for: has_key?
keys() click to toggle source
# File lib/bio/system/lruhash.rb, line 85
def keys
  @h.keys
end
max_size=(limit) click to toggle source
# File lib/bio/system/lruhash.rb, line 172
def max_size=(limit)
  limit = normalize_max(limit)

  while size > limit
    delete_oldest
  end

  @max_size = limit
end
member?(key)
Alias for: has_key?
rassoc(value) click to toggle source
# File lib/bio/system/lruhash.rb, line 124
def rassoc(value)
  each_node do |n|
    if value.eql? n.value
      front(n)
      return [n.key, n.value]
    end
  end
  nil
end
size() click to toggle source
# File lib/bio/system/lruhash.rb, line 61
def size
  @h.size
end
store(key, value) click to toggle source
# File lib/bio/system/lruhash.rb, line 138
def store(key, value)
  # same optimization as in Hash
  key = key.dup.freeze if String === key && !key.frozen?

  n = @h[key]

  unless n
    if size == max_size
      # reuse node to optimize memory usage
      n = delete_oldest
      n.key = key
      n.value = value
    else
      n = Node.new key, value
    end

    @h[key] = n
  end

  front(n).value = value
end
Also aliased as: []=
to_s() click to toggle source
# File lib/bio/system/lruhash.rb, line 190
def to_s
  s = nil
  each_pair {|k, v| (s ? (s << ', ') : s = '{') << k.to_s << '=>' << v.to_s}
  s ? (s << '}') : '{}'
end
Also aliased as: inspect
value?(value)
Alias for: has_value?
values() click to toggle source
# File lib/bio/system/lruhash.rb, line 89
def values
  @h.map {|k,n| n.value}
end
values_at(*key_list) click to toggle source
# File lib/bio/system/lruhash.rb, line 111
def values_at(*key_list)
  key_list.map {|k| self[k]}
end

Private Instance Methods

delete_oldest() click to toggle source

remove the oldest node returning the node

# File lib/bio/system/lruhash.rb, line 254
def delete_oldest
  n = @tail.pred
  raise "Cannot delete from empty hash" if @head.equal? n
  remove_node n
end
each_node() { |n| ... } click to toggle source

iterate nodes

# File lib/bio/system/lruhash.rb, line 227
def each_node
  n = @head.succ

  until n.equal? @tail
    succ = n.succ
    yield n
    n = succ
  end

  self
end
front(node) click to toggle source

move node to front

# File lib/bio/system/lruhash.rb, line 240
def front(node)
  node.insert_after(@head)
end
normalize_max(n) click to toggle source

Normalize the argument in order to be usable as max_size criterion is that n.to_i must be an Integer and it must be larger than zero.

# File lib/bio/system/lruhash.rb, line 263
def normalize_max(n)
  n = n.to_i
  raise ArgumentError, 'Invalid max_size: %p' % n unless Integer === n && n > 0
  n
end
remove_node(node) click to toggle source

remove the node and invoke release_proc if set

# File lib/bio/system/lruhash.rb, line 246
def remove_node(node)
  n = @h.delete(node.key)
  n.unlink
  release_proc and release_proc[n.key, n.value]
  n
end