Class: DLinked::CacheList

Inherits:
List
  • Object
show all
Defined in:
lib/d_linked/cache_list.rb

Overview

DLinked::CacheList

A specialized doubly linked list subclass used as the central key management component for an in-memory LRU cache.

It integrates a hash map (‘@lru_nodes`) to provide **O(1)** operations for:

  • Prepending/Adding a new key (MRU).

  • Touching/Moving an existing key to the head (MRU).

  • Evicting the least recently used key (LRU).

  • Removing an item by key.

It maintains the standard list behavior of the superclass List but focuses on key-based operations rather than simple value manipulation.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Attributes inherited from List

#size

Instance Method Summary collapse

Methods inherited from List

#+, #[], #[]=, #append, #concat, #delete, #each, #empty?, #first, #index, #insert, #last, #pop, #prepend, #reverse_each, #shift, #slice, #slice!, #to_a, #to_s

Constructor Details

#initialize ⇒ void

Initializes a new CacheList instance.



41
42
43
44
 
# File 'lib/d_linked/cache_list.rb', line 41

def initialize
  super
  @lru_nodes = {}
end

Instance Attribute Details

#lru_nodes ⇒ Object (readonly)

Returns the value of attribute lru_nodes.



34
35
36
 
# File 'lib/d_linked/cache_list.rb', line 34

def lru_nodes
  @lru_nodes
end

Instance Method Details

#clear ⇒ void

This method returns an undefined value.

Clears both the doubly linked list and the internal LRU map.



124
125
126
127
 
# File 'lib/d_linked/cache_list.rb', line 124

def clear
  @lru_nodes.clear
  super
end

#move_to_head_by_key(key) ⇒ true, false

  1. Expose the O(1) touch operation

Moves an existing key from its current position to the head (MRU). This is a core O(1) LRU “touch” operation.

Parameters:

  • key (Object) —

    The key of the item to move.

Returns:

  • (true, false) —

    Returns true if the move was successful, false if the key was not found.



97
98
99
100
101
102
103
104
 
# File 'lib/d_linked/cache_list.rb', line 97

def move_to_head_by_key(key)
  node = @lru_nodes[key]
  return false unless node

  # Calls the internal O(1) relocation method
  _move_to_head(node) 
  true
end

#pop_key ⇒ Object?

  1. Expose a key-based pop method (for eviction)

Removes the Least Recently Used (LRU) item from the tail of the list. This performs an O(1) removal and updates the internal hash map.

Returns:

  • (Object, nil) —

    Returns the key of the removed LRU item, or nil if the list is empty.



81
82
83
84
85
86
87
88
 
# File 'lib/d_linked/cache_list.rb', line 81

def pop_key
  # O(1) - Base class's pop operation on the tail node
  node = list_pop_logic 
  return nil unless node
  
  @lru_nodes.delete(node.key)
  return node.key
end

#prepend_key(key, value) ⇒ true

  1. Expose a key-based prepend method

Adds a new key-value pair to the head of the list (Most Recently Used / MRU). This operation is atomic, adding the node to the list and storing the node reference in the internal hash map.

Parameters:

  • key (Object) —

    The cache key to be managed by the LRU list.

  • value (Object) —

    The value to store inside the list node (usually the same as the key in an LRU list).

Returns:

  • (true) —

    Returns true on successful insertion.

Raises:

  • (RuntimeError) —

    If the key already exists in the LRU map.



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/d_linked/cache_list.rb', line 58

def prepend_key(key, value)
  if @lru_nodes.key?(key)
    raise "Key #{key} already exists in the LRU list."
  end

  # The specialized Node creation must happen here
  node = Node.new(value, nil, @head, key) 

  # Use the base class's list logic
  list_prepend_logic(node)

  # Store the node reference in the map (O(1))
  @lru_nodes[key] = node 

  true 
end

#remove_by_key(key) ⇒ true, false

  1. Expose O(1) removal

Removes an item from the list by its key. This is an O(1) operation using the stored node reference.

Parameters:

  • key (Object) —

    The key of the item to remove.

Returns:

  • (true, false) —

    Returns true if the key was removed, false if the key was not found.



113
114
115
116
117
118
119
120
 
# File 'lib/d_linked/cache_list.rb', line 113

def remove_by_key(key)
  node = @lru_nodes.delete(key)
  return false unless node
  
  # Calls the internal O(1) node deletion method
  _remove_node(node)
  true
end