class Innodb::List

Constants

ADDRESS_SIZE

An “address”, which consists of a page number and byte offset within the page. This points to the list “node” pointers (prev and next) of the node, not necessarily the node object.

BASE_NODE_SIZE

A list base node consists of a list length followed by two addresses: the “first” node address, and the “last” node address.

BaseNode
NODE_SIZE

A list node consists of two addresses: the “previous” node address, and the “next” node address.

Node

Attributes

base[R]
space[R]

Public Class Methods

get_address(cursor) click to toggle source

Read a node address from a cursor. Return nil if the address is an end or “NULL” pointer (the page number is UINT32_MAX), or the address if valid.

# File lib/innodb/list.rb, line 30
def self.get_address(cursor)
  page = cursor.name("page") { Innodb::Page.maybe_undefined(cursor.read_uint32) }
  offset = cursor.name("offset") { cursor.read_uint16 }

  Innodb::Page::Address.new(page: page, offset: offset) if page
end
get_base_node(cursor) click to toggle source

Read a base node, consisting of a list length followed by two addresses (:first and :last) from a cursor. Either address may be nil. An empty list has a :length of 0 and :first and :last are nil. A list with only a single item will have a :length of 1 and :first and :last will point to the same address.

# File lib/innodb/list.rb, line 60
def self.get_base_node(cursor)
  BaseNode.new(
    length: cursor.name("length") { cursor.read_uint32 },
    first: cursor.name("first") { get_address(cursor) },
    last: cursor.name("last") { get_address(cursor) }
  )
end
get_node(cursor) click to toggle source

Read a node, consisting of two consecutive addresses (:prev and :next) from a cursor. Either address may be nil, indicating the end of the linked list.

# File lib/innodb/list.rb, line 44
def self.get_node(cursor)
  Node.new(
    prev: cursor.name("prev") { get_address(cursor) },
    next: cursor.name("next") { get_address(cursor) }
  )
end
new(space, base) click to toggle source
# File lib/innodb/list.rb, line 71
def initialize(space, base)
  @space = space
  @base = base
end

Public Instance Methods

each(&block) click to toggle source

Iterate through all nodes in the list.

# File lib/innodb/list.rb, line 134
def each(&block)
  return enum_for(:each) unless block_given?

  list_cursor.each_node(&block)
end
empty?() click to toggle source

Is the list currently empty?

# File lib/innodb/list.rb, line 104
def empty?
  length.zero?
end
first() click to toggle source

Return the first object in the list using the list base node “first” address pointer.

# File lib/innodb/list.rb, line 110
def first
  object_from_address(@base.first)
end
include?(item) click to toggle source

Return whether the given item is present in the list. This depends on the item and the items in the list implementing some sufficient == method. This is implemented rather inefficiently by constructing an array and leaning on Array#include? to do the real work.

# File lib/innodb/list.rb, line 129
def include?(item)
  each.to_a.include?(item)
end
last() click to toggle source

Return the first object in the list using the list base node “last” address pointer.

# File lib/innodb/list.rb, line 116
def last
  object_from_address(@base.last)
end
length() click to toggle source

Return the number of items in the list.

# File lib/innodb/list.rb, line 99
def length
  @base.length
end
list_cursor(node = :min, direction = :forward) click to toggle source

Return a list cursor for the list.

# File lib/innodb/list.rb, line 121
def list_cursor(node = :min, direction = :forward)
  ListCursor.new(self, node, direction)
end
next(object) click to toggle source

Return the object pointed to by the “next” address pointer of the provided object.

# File lib/innodb/list.rb, line 92
def next(object)
  raise "Class #{object.class} does not respond to next_address" unless object.respond_to?(:next_address)

  object_from_address(object.next_address)
end
object_from_address(_address) click to toggle source

Abstract object_from_address method which must be implemented by sub-classes in order to return a useful object given an object address.

# File lib/innodb/list.rb, line 78
def object_from_address(_address)
  raise "#{self.class} must implement object_from_address"
end
prev(object) click to toggle source

Return the object pointed to by the “previous” address pointer of the provided object.

# File lib/innodb/list.rb, line 84
def prev(object)
  raise "Class #{object.class} does not respond to prev_address" unless object.respond_to?(:prev_address)

  object_from_address(object.prev_address)
end