lib/lru_redux/cache.rb in lru_redux-0.8.4 vs lib/lru_redux/cache.rb in lru_redux-1.1.0

@@ -1,163 +1,108 @@
-
-
+# Ruby 1.9 makes our life easier, Hash is already ordered
+#
+# This is an ultra efficient 1.9 freindly implementation
 class LruRedux::Cache
+  def initialize(*args)
+    max_size, _ = args
 
-  # for high efficiency nodes in double linked list are stored in arrays
-  # [prev,key,val,next]
-  #
-  # This makes this much more annoying to code, but gives us a 5-10% edge
+    raise ArgumentError.new(:max_size) if max_size < 1
 
-  def initialize(max_size)
     @max_size = max_size
     @data = {}
-    @head = nil
-    @tail = nil
   end
 
-  def max_size=(size)
-    raise ArgumentError.new(:max_size) if @max_size < 1
-    @max_size = size
-    while pop_tail
-      # no op
-    end
+  def max_size=(max_size)
+    max_size ||= @max_size
+
+    raise ArgumentError.new(:max_size) if max_size < 1
+
+    @max_size = max_size
+
+    @data.shift while @data.size > @max_size
   end
 
+  def ttl=(_)
+    nil
+  end
+
   def getset(key)
-    node = @data[key]
-    if node
-      move_to_head(node)
-      node[2]
+    found = true
+    value = @data.delete(key){ found = false }
+    if found
+      @data[key] = value
     else
-      self[key] = yield
+      result = @data[key] = yield
+      @data.shift if @data.length > @max_size
+      result
     end
   end
 
   def fetch(key)
-    node = @data[key]
-    if node
-      move_to_head(node)
-      node[2]
+    found = true
+    value = @data.delete(key){ found = false }
+    if found
+      @data[key] = value
     else
       yield if block_given?
     end
   end
 
   def [](key)
-    node = @data[key]
-    if node
-      move_to_head(node)
-      node[2]
+    found = true
+    value = @data.delete(key){ found = false }
+    if found
+      @data[key] = value
+    else
+      nil
     end
   end
 
   def []=(key,val)
-    node = @data[key]
-    if node
-      move_to_head(node)
-      node[2] = val
-    else
-      @data[key] = add_to_head(key,val)
-      pop_tail
-    end
+    @data.delete(key)
+    @data[key] = val
+    @data.shift if @data.length > @max_size
     val
   end
 
   def each
-    a = to_a
-    a.each do |pair|
+    array = @data.to_a
+    array.reverse!.each do |pair|
       yield pair
     end
   end
 
-  def each_unsafe
-    n = @head
-    if n
-      while n
-        yield [n[1], n[2]]
-        n = n[0]
-      end
-    end
-  end
+  # used further up the chain, non thread safe each
+  alias_method :each_unsafe, :each
 
   def to_a
-    a = []
-    self.each_unsafe do |k,v|
-      a << [k,v]
-    end
-    a
+    array = @data.to_a
+    array.reverse!
   end
 
   def delete(key)
-    node = @data.delete(key)
+    @data.delete(key)
+  end
 
-    return unless node
+  alias_method :evict, :delete
 
-    prev = node[0]
-    nex = node[3]
-
-    nex  ? nex[0] = prev : @head = prev
-    prev ? prev[3] = nex : @tail = nex
-
-    node[2]
+  def key?(key)
+    @data.key?(key)
   end
 
+  alias_method :has_key?, :key?
+
   def clear
     @data.clear
-    @head = @tail = nil
   end
 
   def count
     @data.size
   end
 
-  # for cache validation only, ensures all is sound
-  def valid?
-    count = 0
-    self.each_unsafe do |k,v|
-      return false if @data[k][2] != v
-      count += 1
-    end
-    count == @data.size
-  end
-
   protected
 
-  def add_to_head(key,val)
-    if @head.nil?
-      @tail = @head = [nil,key,val,nil]
-    else
-      node = [@head,key,val,nil]
-      @head = @head[3] = node
-    end
-  end
-
-  def move_to_head(node)
-    return unless @head && node[1] != @head[1]
-
-    prev = node[0]
-    nex = node[3]
-
-    if prev
-      prev[3] = nex
-    else
-      @tail = nex
-    end
-
-    if nex
-      nex[0] = prev
-    end
-
-    @head[3] = node
-    node[0] = @head
-    @head = node
-  end
-
-  def pop_tail
-    if @data.length > @max_size
-      @data.delete(@tail[1])
-      @tail = @tail[3]
-      @tail[0] = nil
-      true
-    end
+  # for cache validation only, ensures all is sound
+  def valid?
+    true
   end
 end