Skip to content

Instantly share code, notes, and snippets.

@godspeedyoo
Created March 4, 2018 00:06
Show Gist options
  • Save godspeedyoo/5d40d3e79f4e1d1fd4dabfed36d9c8cc to your computer and use it in GitHub Desktop.
Save godspeedyoo/5d40d3e79f4e1d1fd4dabfed36d9c8cc to your computer and use it in GitHub Desktop.
LRU cache in ruby with doubly linked list
class LRU
attr_reader :max, :head, :tail, :data
def initialize(max = 5)
@max = max
@data = {}
end
def set(key, value)
evict if data.size == max
node = Node.new(value)
if head
head.prev_node = node
node.next_node = head
# head should now become tail when growing from size 1 to 2
if head.next_node.nil?
@tail = head
end
end
@head = node
data[key] = node
end
def get(key)
node = data[key]
return node if node == head
return node if node.nil?
if tail == node
# set new tail
node.prev_node.next_node = nil
@tail = node.prev_node
else
node.prev_node.next_node = node.next_node
node.next_node.prev_node = node.prev_node
end
node.prev_node = nil
node.next_node = head
@head = node
node
end
private
def evict
if tail
remove_key_of(tail)
tail = tail.prev_node if tail
tail.next_node = nil
else
remove_key_of(tail)
@head = nil
end
end
def remove_key_of(node)
data.delete(data.key(node))
end
class Node
attr_accessor :value, :prev_node, :next_node
def initialize(value)
@value = value
end
end
end
lru = LRU.new(1)
lru.set('google', 'http://www.google.com')
### SET
# when there is no data, sets value as head
puts "1: #{lru.head.value == 'http://www.google.com'}"
# when data is full, sets new value as head
lru.set('reddit', 'http://www.reddit.com')
puts "2: #{lru.head.value == 'http://www.reddit.com'}"
# when data is not full and head already exists, sets tail correctly
lru = LRU.new(2)
lru.set('google', 'http://www.google.com')
lru.set('reddit', 'http://www.reddit.com')
puts "3: #{lru.tail.value == 'http://www.google.com'}"
### GET
# gets the correct value
puts "4: #{lru.get('reddit').value == 'http://www.reddit.com'}"
puts "5: #{lru.get('google').value == 'http://www.google.com'}"
# when getting a key that is not head, sets that as new head
puts "6: #{lru.head.value == 'http://www.google.com'}"
lru.get('google') # access google, head should become google
puts "7: #{lru.head.value == 'http://www.google.com'}"
# returns nil if not found in cache
puts "8: #{lru.get('invalid') == nil}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment