Class: Hashery::LRUHash

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/hashery/lru_hash.rb

Overview

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 © 2010 Robert Klemme.

Defined Under Namespace

Classes: Node

Constant Summary collapse

FETCH = 
Proc.new {|k| raise KeyError, 'key not found'}

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_size, default_value = nil, &block) ⇒ LRUHash

Initialize new LRUHash instance.

Parameters:

  • max_size —

    -

  • default_value (defaults to: nil) —

    -

  • block —

    -



30
31
32
33
34
35
36
37
38
 
# File 'lib/hashery/lru_hash.rb', line 30

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

Instance Attribute Details

#default ⇒ Object

Returns the value of attribute default.



19
20
21
 
# File 'lib/hashery/lru_hash.rb', line 19

def default
  @default
end

#default_proc ⇒ Object

Returns the value of attribute default_proc.



20
21
22
 
# File 'lib/hashery/lru_hash.rb', line 20

def default_proc
  @default_proc
end

#max_size ⇒ Object

Returns the value of attribute max_size.



17
18
19
 
# File 'lib/hashery/lru_hash.rb', line 17

def max_size
  @max_size
end

#release_proc ⇒ Object

Returns the value of attribute release_proc.



21
22
23
 
# File 'lib/hashery/lru_hash.rb', line 21

def release_proc
  @release_proc
end

Instance Method Details

#[](key) ⇒ Object 



114
115
116
117
118
 
# File 'lib/hashery/lru_hash.rb', line 114

def [](key)
  fetch(key) do |k|
    @default_proc ? @default_proc[self, k] : default
  end
end

#assoc(key) ⇒ Object 



165
166
167
168
169
170
171
172
 
# File 'lib/hashery/lru_hash.rb', line 165

def assoc(key)
  n = @h[key]

  if n
    front(n)
    [n.key, n.value]
  end
end

#clear ⇒ Object 



253
254
255
256
257
258
259
 
# File 'lib/hashery/lru_hash.rb', line 253

def clear
  until empty?
    delete_oldest
  end

  self
end

#delete(key) ⇒ Object 



224
225
226
 
# File 'lib/hashery/lru_hash.rb', line 224

def delete(key)
  n = @h[key] and remove_node(n).value
end

#delete_if ⇒ Object 



231
232
233
234
235
 
# File 'lib/hashery/lru_hash.rb', line 231

def delete_if
  each_node do |n|
    remove_node n if yield n.key, n.value
  end
end

#delete_oldest ⇒ Object (private)

Remove the oldest node returning the node



314
315
316
317
318
 
# File 'lib/hashery/lru_hash.rb', line 314

def delete_oldest
  n = @tail.pred
  raise "Cannot delete from empty hash" if @head.equal? n
  remove_node n
end

#each_key ⇒ Object

Iterate over each key.



61
62
63
64
65
66
67
68
69
 
# File 'lib/hashery/lru_hash.rb', line 61

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

#each_node ⇒ Object (private)

Iterate nodes.



277
278
279
280
281
282
283
284
285
286
287
 
# File 'lib/hashery/lru_hash.rb', line 277

def each_node
  n = @head.succ

  until n.equal? @tail
    succ = n.succ
    yield n
    n = succ
  end

  self
end

#each_pair ⇒ Object Also known as: each

Iterate over each pair.



43
44
45
46
47
48
49
50
51
 
# File 'lib/hashery/lru_hash.rb', line 43

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

#each_value ⇒ Object

Iterate over each value.



74
75
76
77
78
79
80
81
82
 
# File 'lib/hashery/lru_hash.rb', line 74

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


94
95
96
 
# File 'lib/hashery/lru_hash.rb', line 94

def empty?
  @head.succ.equal? @tail
end

#fetch(key, &b) ⇒ Object 



101
102
103
104
105
106
107
108
109
 
# File 'lib/hashery/lru_hash.rb', line 101

def fetch(key, &b)
  n = @h[key]

  if n
    front(n).value
  else
    (b || FETCH)[key]
  end
end

#front(node) ⇒ Object (private)

Move node to front.

Parameters:



294
295
296
 
# File 'lib/hashery/lru_hash.rb', line 294

def front(node)
  node.insert_after(@head)
end

#has_key?(key) ⇒ Boolean Also known as: key?, member?, include?

Returns:

  • (Boolean) 


137
138
139
 
# File 'lib/hashery/lru_hash.rb', line 137

def has_key?(key)
  @h.has_key? key
end

#has_value?(value) ⇒ Boolean Also known as: value?

Returns:

  • (Boolean) 


148
149
150
151
152
153
154
 
# File 'lib/hashery/lru_hash.rb', line 148

def has_value?(value)
  each_pair do |k, v|
    return true if value.eql? v
  end

  false
end

#key(value) ⇒ Object 



190
191
192
 
# File 'lib/hashery/lru_hash.rb', line 190

def key(value)
  pair = rassoc(value) and pair.first
end

#keys ⇒ Object 



123
124
125
 
# File 'lib/hashery/lru_hash.rb', line 123

def keys
  @h.keys
end

#normalize_max(n) ⇒ Object (private)

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.

Parameters:

  • n (#to_i) —

    max size

Raises:

  • (ArgumentError) 


327
328
329
330
331
 
# File 'lib/hashery/lru_hash.rb', line 327

def normalize_max(n)
  n = n.to_i
  raise ArgumentError, 'Invalid max_size: %p' % n unless Integer === n && n > 0
  n
end

#rassoc(value) ⇒ Object 



177
178
179
180
181
182
183
184
185
 
# File 'lib/hashery/lru_hash.rb', line 177

def rassoc(value)
  each_node do |n|
    if value.eql? n.value
      front(n)
      return [n.key, n.value]
    end
  end
  nil
end

#remove_node(node) ⇒ Object (private)

Remove the node and invoke release_proc if set

Parameters:



304
305
306
307
308
309
 
# File 'lib/hashery/lru_hash.rb', line 304

def remove_node(node)
  n = @h.delete(node.key)
  n.unlink
  release_proc and release_proc[n.key, n.value]
  n
end

#size ⇒ Object

Size of the hash.



87
88
89
 
# File 'lib/hashery/lru_hash.rb', line 87

def size
  @h.size
end

#store(key, value) ⇒ Object Also known as: []= 



197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/hashery/lru_hash.rb', line 197

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

#to_s ⇒ Object Also known as: inspect 



264
265
266
267
268
 
# File 'lib/hashery/lru_hash.rb', line 264

def to_s
  s = nil
  each_pair {|k, v| (s ? (s << ', ') : s = '{') << k.to_s << '=>' << v.to_s}
  s ? (s << '}') : '{}'
end

#values ⇒ Object 



130
131
132
 
# File 'lib/hashery/lru_hash.rb', line 130

def values
  @h.map {|k,n| n.value}
end

#values_at(*key_list) ⇒ Object 



158
159
160
 
# File 'lib/hashery/lru_hash.rb', line 158

def values_at(*key_list)
  key_list.map {|k| self[k]}
end