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
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
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_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
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?
key(value)
click to toggle source
# File lib/hashery/lru_hash.rb, line 190 def key(value) pair = rassoc(value) and pair.first end
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
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
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