class DbmsBuffers::ClockBuffer

The clock buffer, also known as second-change 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. This 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 that has clock_value = 0, this value is set to 1 again.

Attributes

pointer[R]
size[R]

Public Class Methods

new(size) click to toggle source
# File lib/dbms_buffers/clock.rb, line 18
def initialize(size)
  @size = size
  @buffer = []
  @pointer = 0
end

Public Instance Methods

access(value) click to toggle source
# File lib/dbms_buffers/clock.rb, line 24
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/clock.rb, line 28
def clock_value_of(value)
  @buffer[index(value)].clock_value
end
contains?(value) click to toggle source
# File lib/dbms_buffers/clock.rb, line 36
def contains?(value)
  @buffer.any? { |entry| value == entry.value }
end
entries() click to toggle source
# File lib/dbms_buffers/clock.rb, line 32
def entries
  @buffer.clone
end
used() click to toggle source
# File lib/dbms_buffers/clock.rb, line 40
def used
  @buffer.size
end

Private Instance Methods

advance_pointer() click to toggle source
# File lib/dbms_buffers/clock.rb, line 79
def advance_pointer
  @pointer = (@pointer + 1) % @size
end
index(value) click to toggle source
# File lib/dbms_buffers/clock.rb, line 83
def index(value)
  @buffer.index { |entry| entry.value == value }
end
touch(value) click to toggle source
# File lib/dbms_buffers/clock.rb, line 87
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/clock.rb, line 55
def try_insert_new(value)
  return false if used == @size

  entry = ClockBufferEntry.new(value, 1)
  @buffer[@pointer] = entry
  advance_pointer

  true
end
try_replace(value) click to toggle source
# File lib/dbms_buffers/clock.rb, line 65
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 = 0
  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/clock.rb, line 48
def try_touch(value)
  result = contains? value
  touch(value) if result
  result
end