Class Innodb::List
In: lib/innodb/list.rb
Parent: Object

An abstract InnoDB "free list" or FLST (renamed to just "list" here as it frequently is used for structures that aren‘t free lists). This class must be sub-classed to provide an appropriate object_from_address method.

Methods

each   first   get_address   get_base_node   get_node   include?   last   length   list_cursor   new   next   object_from_address   prev  

Classes and Modules

Class Innodb::List::History
Class Innodb::List::Inode
Class Innodb::List::ListCursor
Class Innodb::List::UndoPage
Class Innodb::List::Xdes

Constants

ADDRESS_SIZE = 4 + 2   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.
NODE_SIZE = 2 * ADDRESS_SIZE   A list node consists of two addresses: the "previous" node address, and the "next" node address.
BASE_NODE_SIZE = 4 + (2 * ADDRESS_SIZE)   A list base node consists of a list length followed by two addresses: the "first" node address, and the "last" node address.

Attributes

base  [R] 
space  [R] 

Public Class methods

get_address(cursor)

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.

get_base_node(cursor)

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.

get_node(cursor)

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.

Public Instance methods

each() {|node| ...}

Iterate through all nodes in the list.

first()

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

include?(item)

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.

last()

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

length()

Return the number of items in the list.

list_cursor(node=:min, direction=:forward)

Return a list cursor for the list.

next(object)

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

object_from_address(address)

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

prev(object)

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

[Validate]