Class: Innodb::List
- Inherits:
-
Object
- Object
- Innodb::List
- Defined in:
- lib/innodb/list.rb
Overview
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.
Defined Under Namespace
Classes: History, Inode, ListCursor, UndoPage, Xdes
Constant Summary collapse
- 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.
4 + 2
- NODE_SIZE =
A list node consists of two addresses: the “previous” node address, and the “next” node address.
2 * ADDRESS_SIZE
- 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.
4 + (2 * ADDRESS_SIZE)
Instance Attribute Summary collapse
-
#base ⇒ Object
readonly
Returns the value of attribute base.
-
#space ⇒ Object
readonly
Returns the value of attribute space.
Class Method Summary collapse
-
.get_address(cursor) ⇒ Object
Read a node address from a cursor.
-
.get_base_node(cursor) ⇒ Object
Read a base node, consisting of a list length followed by two addresses (:first and :last) from a cursor.
-
.get_node(cursor) ⇒ Object
Read a node, consisting of two consecutive addresses (:prev and :next) from a cursor.
Instance Method Summary collapse
-
#each ⇒ Object
Iterate through all nodes in the list.
-
#first ⇒ Object
Return the first object in the list using the list base node “first” address pointer.
-
#include?(item) ⇒ Boolean
Return whether the given item is present in the list.
-
#initialize(space, base) ⇒ List
constructor
A new instance of List.
-
#last ⇒ Object
Return the first object in the list using the list base node “last” address pointer.
-
#length ⇒ Object
Return the number of items in the list.
-
#list_cursor(node = :min, direction = :forward) ⇒ Object
Return a list cursor for the list.
-
#next(object) ⇒ Object
Return the object pointed to by the “next” address pointer of the provided object.
-
#object_from_address(address) ⇒ Object
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) ⇒ Object
Return the object pointed to by the “previous” address pointer of the provided object.
Constructor Details
#initialize(space, base) ⇒ List
Returns a new instance of List.
60 61 62 63 |
# File 'lib/innodb/list.rb', line 60 def initialize(space, base) @space = space @base = base end |
Instance Attribute Details
#base ⇒ Object (readonly)
Returns the value of attribute base.
66 67 68 |
# File 'lib/innodb/list.rb', line 66 def base @base end |
#space ⇒ Object (readonly)
Returns the value of attribute space.
65 66 67 |
# File 'lib/innodb/list.rb', line 65 def space @space end |
Class Method Details
.get_address(cursor) ⇒ Object
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.
16 17 18 19 20 21 22 23 24 25 26 27 |
# File 'lib/innodb/list.rb', line 16 def self.get_address(cursor) page = cursor.name("page") { Innodb::Page.maybe_undefined(cursor.get_uint32) } offset = cursor.name("offset") { cursor.get_uint16 } if page { :page => page, :offset => offset, } end end |
.get_base_node(cursor) ⇒ Object
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.
52 53 54 55 56 57 58 |
# File 'lib/innodb/list.rb', line 52 def self.get_base_node(cursor) { :length => cursor.name("length") { cursor.get_uint32 }, :first => cursor.name("first") { get_address(cursor) }, :last => cursor.name("last") { get_address(cursor) }, } end |
.get_node(cursor) ⇒ Object
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.
36 37 38 39 40 41 |
# File 'lib/innodb/list.rb', line 36 def self.get_node(cursor) { :prev => cursor.name("prev") { get_address(cursor) }, :next => cursor.name("next") { get_address(cursor) }, } end |
Instance Method Details
#each ⇒ Object
Iterate through all nodes in the list.
125 126 127 128 129 130 131 132 133 |
# File 'lib/innodb/list.rb', line 125 def each unless block_given? return enum_for(:each) end list_cursor.each_node do |node| yield node end end |
#first ⇒ Object
Return the first object in the list using the list base node “first” address pointer.
101 102 103 |
# File 'lib/innodb/list.rb', line 101 def first object_from_address(@base[:first]) end |
#include?(item) ⇒ Boolean
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.
120 121 122 |
# File 'lib/innodb/list.rb', line 120 def include?(item) each.to_a.include? item end |
#last ⇒ Object
Return the first object in the list using the list base node “last” address pointer.
107 108 109 |
# File 'lib/innodb/list.rb', line 107 def last object_from_address(@base[:last]) end |
#length ⇒ Object
Return the number of items in the list.
95 96 97 |
# File 'lib/innodb/list.rb', line 95 def length @base[:length] end |
#list_cursor(node = :min, direction = :forward) ⇒ Object
Return a list cursor for the list.
112 113 114 |
# File 'lib/innodb/list.rb', line 112 def list_cursor(node=:min, direction=:forward) ListCursor.new(self, node, direction) end |
#next(object) ⇒ Object
Return the object pointed to by the “next” address pointer of the provided object.
86 87 88 89 90 91 92 |
# File 'lib/innodb/list.rb', line 86 def next(object) unless object.respond_to? :next_address raise "Class #{object.class} does not respond to next_address" end object_from_address(object.next_address) end |
#object_from_address(address) ⇒ Object
Abstract #object_from_address method which must be implemented by sub-classes in order to return a useful object given an object address.
70 71 72 |
# File 'lib/innodb/list.rb', line 70 def object_from_address(address) raise "#{self.class} must implement object_from_address" end |
#prev(object) ⇒ Object
Return the object pointed to by the “previous” address pointer of the provided object.
76 77 78 79 80 81 82 |
# File 'lib/innodb/list.rb', line 76 def prev(object) unless object.respond_to? :prev_address raise "Class #{object.class} does not respond to prev_address" end object_from_address(object.prev_address) end |