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