class Hashery::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.

Based on Robert Klemme's LRUHash class.

LRUHash, Copyright © 2010 Robert Klemme.

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

Initialize new LRUHash instance.

max_size - default_value - block -

# File lib/hashery/lru_hash.rb, line 30
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/hashery/lru_hash.rb, line 114
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/hashery/lru_hash.rb, line 165
def assoc(key)
  n = @h[key]

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

  self
end
delete(key) click to toggle source
# File lib/hashery/lru_hash.rb, line 224
def delete(key)
  n = @h[key] and remove_node(n).value
end
delete_if() { |key, value| ... } click to toggle source
# File lib/hashery/lru_hash.rb, line 231
def delete_if
  each_node do |n|
    remove_node n if yield n.key, n.value
  end
end
each()

Same as each pair.

Alias for: each_pair
each_key() { |key| ... } click to toggle source

Iterate over each key.

# File lib/hashery/lru_hash.rb, line 61
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

Iterate over each pair.

# File lib/hashery/lru_hash.rb, line 43
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

Iterate over each value.

# File lib/hashery/lru_hash.rb, line 74
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/hashery/lru_hash.rb, line 94
def empty?
  @head.succ.equal? @tail
end
fetch(key, &b) click to toggle source
# File lib/hashery/lru_hash.rb, line 101
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/hashery/lru_hash.rb, line 137
def has_key?(key)
  @h.has_key? key
end
Also aliased as: key?, member?, include?
has_value?(value) click to toggle source
# File lib/hashery/lru_hash.rb, line 148
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/hashery/lru_hash.rb, line 190
def key(value)
  pair = rassoc(value) and pair.first
end
key?(key)
Alias for: has_key?
keys() click to toggle source
# File lib/hashery/lru_hash.rb, line 123
def keys
  @h.keys
end
max_size=(limit) click to toggle source
# File lib/hashery/lru_hash.rb, line 240
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/hashery/lru_hash.rb, line 177
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

Size of the hash.

# File lib/hashery/lru_hash.rb, line 87
def size
  @h.size
end
store(key, value) click to toggle source
# File lib/hashery/lru_hash.rb, line 197
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/hashery/lru_hash.rb, line 264
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/hashery/lru_hash.rb, line 130
def values
  @h.map {|k,n| n.value}
end
values_at(*key_list) click to toggle source
# File lib/hashery/lru_hash.rb, line 158
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/hashery/lru_hash.rb, line 314
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/hashery/lru_hash.rb, line 277
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.

node - [Node]

# File lib/hashery/lru_hash.rb, line 294
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.

n - [#to_i] max size

# File lib/hashery/lru_hash.rb, line 327
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

node - [Node]

# File lib/hashery/lru_hash.rb, line 304
def remove_node(node)
  n = @h.delete(node.key)
  n.unlink
  release_proc and release_proc[n.key, n.value]
  n
end