LRUCache

A cache utilizing a simple LRU (Least Recently Used) policy. The items managed by this cache must respond to the key method. Attempts to optimize reads rather than inserts!

LRU semantics are enforced by inserting the items in a queue. The lru item is always at the tail. Two special sentinels (head, tail) are used to simplify (?) the code.

Methods
Classes and Modules
Module LRUCache::Item
Class LRUCache::Sentinel
Attributes
[R] head the head sentinel and the tail sentinel, tail.prev points to the lru item.
[RW] max_items the maximum number of items in the cache.
[R] tail the head sentinel and the tail sentinel, tail.prev points to the lru item.
Public Class methods
new(max_items)

[ show source ]

# File lib/facets/more/lrucache.rb, line 52
  def initialize(max_items)
    @max_items = max_items
    lru_clear()
  end
Public Instance methods
[](key)

Lookup an item in the cache.

[ show source ]

# File lib/facets/more/lrucache.rb, line 59
  def [](key)
    if item = super
      return lru_touch(item)
    end
  end
[]=(key, item)

The inserted item is considered mru!

[ show source ]

# File lib/facets/more/lrucache.rb, line 67
  def []=(key, item)
    item = super
    item.lru_key = key
    lru_insert(item)
  end
clear()

Clear the cache.

[ show source ]

# File lib/facets/more/lrucache.rb, line 83
  def clear
    super
    lru_clear()
  end
delete(key)

Delete an item from the cache.

[ show source ]

# File lib/facets/more/lrucache.rb, line 75
  def delete(key)
    if item = super
      lru_delete(item)
    end
  end
first()

The first (mru) element in the cache.

[ show source ]

# File lib/facets/more/lrucache.rb, line 90
  def first
    @head.lru_next
  end
last()

The last (lru) element in the cache.

This method is also aliased as lru

[ show source ]

# File lib/facets/more/lrucache.rb, line 96
  def last
    @tail.lru_prev
  end
lru()

Alias for last

Private Instance methods
lru_append(parent, child)

Append a child item to a parent item in the lru list (Re)inserts the child in the list.

[ show source ]

# File lib/facets/more/lrucache.rb, line 122
  def lru_append(parent, child)
    lru_join(child, parent.lru_next)
    lru_join(parent, child)
  end
lru_clear()

Clear the lru.

[ show source ]

# File lib/facets/more/lrucache.rb, line 143
  def lru_clear
    @head = Sentinel.new
    @tail = Sentinel.new
    lru_join(@head, @tail)
  end
lru_delete(item)

Delete an item from the lru list.

[ show source ]

# File lib/facets/more/lrucache.rb, line 105
  def lru_delete(item)
    lru_join(item.lru_prev, item.lru_next)
    return item
  end
lru_insert(item)

Insert an item

[ show source ]

# File lib/facets/more/lrucache.rb, line 129
  def lru_insert(item)
    delete(last.lru_key) if size() > @max_items
    lru_append(@head, item)
  end
lru_join(x, y)

Join two items in the lru list. Return y to allow for chaining.

[ show source ]

# File lib/facets/more/lrucache.rb, line 113
  def lru_join(x, y)
    x.lru_next = y
    y.lru_prev = x
    return y
  end
lru_touch(item)

Touch an item, make mru! Returns the item.

[ show source ]

# File lib/facets/more/lrucache.rb, line 137
  def lru_touch(item)
    lru_append(@head, lru_delete(item))
  end