Gecko [ lorencats.com ]

Name	Size	Permission
association.rb	4.58 KB	-rw-r--r--
casting_hash.rb	3.27 KB	-rw-r--r--
core_ext.rb	2.57 KB	-rw-r--r--
crud_hash.rb	8.64 KB	-rw-r--r--
dictionary.rb	12.46 KB	-rw-r--r--
fuzzy_hash.rb	3.94 KB	-rw-r--r--
ini_hash.rb	8.08 KB	-rw-r--r--
key_hash.rb	1.47 KB	-rw-r--r--
linked_list.rb	4.47 KB	-rw-r--r--
lru_hash.rb	5.6 KB	-rw-r--r--
open_cascade.rb	3.95 KB	-rw-r--r--
open_hash.rb	3.5 KB	-rw-r--r--
ordered_hash.rb	3.18 KB	-rw-r--r--
path_hash.rb	6.82 KB	-rw-r--r--
property_hash.rb	3.53 KB	-rw-r--r--
query_hash.rb	2.19 KB	-rw-r--r--
stash.rb	203 B	-rw-r--r--
static_hash.rb	1.24 KB	-rw-r--r--

Code Editor : lru_hash.rb

require 'enumerator'

module Hashery

# 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 (c) 2010 Robert Klemme.
  #
  class LRUHash

include Enumerable

attr_reader :max_size

attr_accessor :default
    attr_accessor :default_proc
    attr_accessor :release_proc

#
    # Initialize new LRUHash instance.
    #
    # max_size      -
    # default_value -
    # block         -
    #
    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

#
    # Iterate over each pair.
    #
    def each_pair
      if block_given?
        each_node do |n|
          yield [n.key, n.value]
        end
      else
        enum_for :each_pair
      end
    end

#
    # Same as each pair.
    #
    alias each each_pair

#
    # Iterate over each key.
    #
    def each_key
      if block_given?
        each_node do |n|
          yield n.key
        end
      else
        enum_for :each_key
      end
    end

#
    # Iterate over each value.
    #
    def each_value
      if block_given?
        each_node do |n|
          yield n.value
        end
      else
        enum_for :each_value
      end
    end

#
    # Size of the hash.
    #
    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

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.
    #
    # node - [Node]
    #
    def front(node)
      node.insert_after(@head)
    end

#
    # Remove the node and invoke release_proc
    # if set
    #
    # node - [Node]
    #
    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.
    #
    # n - [#to_i] max size
    #
    def normalize_max(n)
      n = n.to_i
      raise ArgumentError, 'Invalid max_size: %p' % n unless Integer === n && n > 0
      n
    end

#
    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

end

${this.title}

Code Editor : lru_hash.rb