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
Public Class Methods
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
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
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
# File lib/innodb/list.rb, line 71 def initialize(space, base) @space = space @base = base end
Public Instance Methods
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
Is the list currently empty?
# File lib/innodb/list.rb, line 104 def empty? length.zero? end
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
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
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
Return the number of items in the list.
# File lib/innodb/list.rb, line 99 def length @base.length end
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
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
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
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