Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A bounded hash that expires keys using LRU (roughly)
# frozen_string_literal: true
require "delegate"
require "set"
# Hash that can only hold a certain number of keys, keys expire on a LRU basis
class BoundedHash < DelegateClass(Hash)
NO_OP = proc {}
def initialize(size = 100, &block)
@size = size
@keys = []
@keyset = Set.new
@init_block = block_given? ? block : NO_OP
super({})
end
def []=(key, value)
__getobj__[key] = value
if @keyset.include?(key)
lru_swap!(key)
else
@keys.insert(0, key)
@keyset << key
end
return value unless @keys.length > @size
# housekeeping
oldest = @keys.pop
@keyset.delete(oldest)
__getobj__.delete(oldest)
value
end
def [](key)
lru_swap!(key)
__getobj__.fetch(key) { @init_block.call(self, key) }
end
def clear
@keys.clear
@keyset.clear
__getobj__.clear
end
private
def lru_swap!(key)
return unless @keyset.include?(key)
return if @keys[0] == key
index = @keys.index(key)
@keys[0], @keys[index] = @keys[index], @keys[0]
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.