class DbmsBuffers::GClockBuffer
The generalized clock buffer arranges entries in a logical clock and a single hand. When the buffer is full and a not-yet-inserted entry needs space, the hand goes clockwise until it finds an entry with clock_value = 0. The found entry is evicted, removed from the buffer, and the new values is inserted with clock_value 1. All entries the hand passes where clock_value = 1, this value is decremented, but they are not replaced yet (they have a second chance). When an element is accessed, its value is incremented by 1.
Attributes
pointer[R]
size[R]
Public Class Methods
new(size)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 17 def initialize(size) @size = size @buffer = [] @pointer = 0 end
Public Instance Methods
access(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 23 def access(value) try_touch(value) || try_insert_new(value) || try_replace(value) end
clock_value_of(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 27 def clock_value_of(value) @buffer[index(value)].clock_value end
contains?(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 35 def contains?(value) @buffer.any? { |entry| value == entry.value } end
entries()
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 31 def entries @buffer.clone end
used()
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 39 def used @buffer.size end
Private Instance Methods
advance_pointer()
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 78 def advance_pointer @pointer = (@pointer + 1) % @size end
index(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 82 def index(value) @buffer.index { |entry| entry.value == value } end
touch(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 86 def touch(value) @buffer.find { |entry| entry.value == value }.clock_value += 1 end
try_insert_new(value)
click to toggle source
If buffer slots are free, inserts value and returns true.
# File lib/dbms_buffers/gclock.rb, line 54 def try_insert_new(value) return false if used == @size entry = GClockBufferEntry.new(value, 1) @buffer[@pointer] = entry advance_pointer true end
try_replace(value)
click to toggle source
# File lib/dbms_buffers/gclock.rb, line 64 def try_replace(value) entry = @buffer[@pointer] if entry.clock_value.zero? entry.value = value entry.clock_value = 1 advance_pointer return true end entry.clock_value -= 1 advance_pointer try_replace value end
try_touch(value)
click to toggle source
If value is contained in the buffer, it's value is set to 1 and true is returned, otherwise false
# File lib/dbms_buffers/gclock.rb, line 47 def try_touch(value) result = contains? value touch(value) if result result end