Class: LruRedux::Cache

Inherits:
Object
  • Object
show all
Defined in:
lib/lru_redux/cache19.rb,
lib/lru_redux/cache.rb

Overview

Ruby 1.9 makes our life easier, Hash is already ordered

This is an ultra efficient 1.9 freindly implementation

Direct Known Subclasses

ThreadSafeCache

Instance Method Summary collapse

Constructor Details

#initialize(max_size) ⇒ Cache

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



10
11
12
13
14
15
 
# File 'lib/lru_redux/cache.rb', line 10

def initialize(max_size)
  @max_size = max_size
  @data = {}
  @head = nil
  @tail = nil
end

Instance Method Details

#[](key) ⇒ Object 



45
46
47
48
49
50
51
 
# File 'lib/lru_redux/cache.rb', line 45

def [](key)
  node = @data[key]
  if node
    move_to_head(node)
    node[2]
  end
end

#[]=(key, val) ⇒ Object 



53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/lru_redux/cache.rb', line 53

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
  val
end

#clear ⇒ Object 



113
114
115
116
 
# File 'lib/lru_redux/cache.rb', line 113

def clear
  @data.clear
  @head = @tail = nil
end

#count ⇒ Object 



118
119
120
 
# File 'lib/lru_redux/cache.rb', line 118

def count
  @data.size
end

#delete(k) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/lru_redux/cache.rb', line 90

def delete(key)
  node = @data.delete(key)
  return unless node

  if node[3].nil?
    @head = @head[0]
    if @head.nil?
      @tail = nil
    else
      @head[3] = nil
    end
  elsif node[0].nil?
    @tail = @tail[3]
    @tail[0] = nil
  else
    prev = node[0]
    nex = node[3]

    prev[3] = nex if prev
    nex[0] = prev if nex
  end
end

#each ⇒ Object Also known as: each_unsafe 



65
66
67
68
69
70
 
# File 'lib/lru_redux/cache.rb', line 65

def each
  a = to_a
  a.each do |pair|
    yield pair
  end
end

#fetch(key) ⇒ Object 



35
36
37
38
39
40
41
42
43
 
# File 'lib/lru_redux/cache.rb', line 35

def fetch(key)
  node = @data[key]
  if node
    move_to_head(node)
    node[2]
  else
    yield if block_given?
  end
end

#getset(key) ⇒ Object 



25
26
27
28
29
30
31
32
33
 
# File 'lib/lru_redux/cache.rb', line 25

def getset(key)
  node = @data[key]
  if node
    move_to_head(node)
    node[2]
  else
    self[key] = yield
  end
end

#max_size=(size) ⇒ Object

Raises:

  • (ArgumentError) 


17
18
19
20
21
22
23
 
# File 'lib/lru_redux/cache.rb', line 17

def max_size=(size)
  raise ArgumentError.new(:max_size) if @max_size < 1
  @max_size = size
  while pop_tail
    # no op
  end
end

#to_a ⇒ Object 



82
83
84
85
86
87
88
 
# File 'lib/lru_redux/cache.rb', line 82

def to_a
  a = []
  self.each_unsafe do |k,v|
    a << [k,v]
  end
  a
end

#valid? ⇒ Boolean

for cache validation only, ensures all is sound

Returns:

  • (Boolean) 


123
124
125
126
127
128
129
130
 
# File 'lib/lru_redux/cache.rb', line 123

def valid?
  count = 0
  self.each_unsafe do |k,v|
    return false if @data[k][2] != v
    count += 1
  end
  count == @data.size
end