# LRU based Hash by Robert Klemme # # Copied from http://github.com/rklemme/muppet-laboratories # # License: unclear, not in repository, need to ask Permission # Added by Pjotr Prins (pjotr.prins@thebird.nl) require 'enumerator' # 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. class LRUHash include Enumerable attr_reader :max_size attr_accessor :default, :default_proc, :release_proc 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 def each_pair if block_given? each_node do |n| yield [n.key, n.value] end else enum_for :each_pair end end alias each each_pair def each_key if block_given? each_node do |n| yield n.key end else enum_for :each_key end end def each_value if block_given? each_node do |n| yield n.value end else enum_for :each_value end end def size @h.size end def empty? @head.succ.equal? @tail end def fetch(key, &b) n = @h[key] if n front(n).value else (b || FETCH)[key] end end def [](key) fetch(key) do |k| @default_proc ? @default_proc[self, k] : default end end def keys @h.keys end def values @h.map {|k,n| n.value} end def has_key?(key) @h.has_key? key end alias key? has_key? alias member? has_key? alias include? has_key? def has_value?(value) each_pair do |k, v| return true if value.eql? v end false end alias value? has_value? def values_at(*key_list) key_list.map {|k| self[k]} end def assoc(key) n = @h[key] if n front(n) [n.key, n.value] end end def rassoc(value) each_node do |n| if value.eql? n.value front(n) return [n.key, n.value] end end nil end def key(value) pair = rassoc(value) and pair.first end 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 alias []= store def delete(key) n = @h[key] and remove_node(n).value end def delete_if each_node do |n| remove_node n if yield n.key, n.value end end def max_size=(limit) limit = normalize_max(limit) while size > limit delete_oldest end @max_size = limit end def clear until empty? delete_oldest end self end def to_s s = nil each_pair {|k, v| (s ? (s << ', ') : s = '{') << k.to_s << '=>' << v.to_s} s ? (s << '}') : '{}' end alias inspect to_s FETCH = Proc.new {|k| raise KeyError, 'key not found'} # A single node in the doubly linked LRU list of nodes Node = Struct.new :key, :value, :pred, :succ do def unlink pred.succ = succ if pred succ.pred = pred if succ self.succ = self.pred = nil self end def insert_after(node) raise 'Cannot insert after self' if equal? node return self if node.succ.equal? self unlink self.succ = node.succ self.pred = node node.succ.pred = self if node.succ node.succ = self self end end private # iterate nodes def each_node n = @head.succ until n.equal? @tail succ = n.succ yield n n = succ end self end # move node to front def front(node) node.insert_after(@head) end # remove the node and invoke release_proc # if set def remove_node(node) n = @h.delete(node.key) n.unlink release_proc and release_proc[n.key, n.value] n end # remove the oldest node returning the node def delete_oldest n = @tail.pred raise "Cannot delete from empty hash" if @head.equal? n remove_node n end # 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. def normalize_max(n) n = n.to_i raise ArgumentError, 'Invalid max_size: %p' % n unless Integer === n && n > 0 n end end