Class: Innodb::List

Inherits:
Object
  • Object
show all
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.

Direct Known Subclasses

Inode, Xdes

Defined Under Namespace

Classes: Cursor, Inode, 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

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(space, base) ⇒ List

Returns a new instance of List.



55
56
57
58
 
# File 'lib/innodb/list.rb', line 55

def initialize(space, base)
  @space  = space
  @base   = base
end

Instance Attribute Details

#base ⇒ Object (readonly)

Returns the value of attribute base.



61
62
63
 
# File 'lib/innodb/list.rb', line 61

def base
  @base
end

#space ⇒ Object (readonly)

Returns the value of attribute space.



60
61
62
 
# File 'lib/innodb/list.rb', line 60

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.



13
14
15
16
17
18
19
20
21
22
 
# File 'lib/innodb/list.rb', line 13

def self.get_address(cursor)
  page    = Innodb::Page.maybe_undefined(cursor.get_uint32)
  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.



47
48
49
50
51
52
53
 
# File 'lib/innodb/list.rb', line 47

def self.get_base_node(cursor)
  {
    :length => cursor.get_uint32,
    :first  => get_address(cursor),
    :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.



31
32
33
34
35
36
 
# File 'lib/innodb/list.rb', line 31

def self.get_node(cursor)
  {
    :prev => get_address(cursor),
    :next => get_address(cursor),
  }
end

Instance Method Details

#cursor(node = nil) ⇒ Object

Return a list cursor for the list.



102
103
104
 
# File 'lib/innodb/list.rb', line 102

def cursor(node=nil)
  Cursor.new(self, node)
end

#each ⇒ Object

Iterate through all nodes in the list.



107
108
109
110
111
112
113
114
115
116
 
# File 'lib/innodb/list.rb', line 107

def each
  unless block_given?
    return enum_for(:each)
  end

  c = cursor
  while e = c.next
    yield e
  end
end

#first ⇒ Object

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



91
92
93
 
# File 'lib/innodb/list.rb', line 91

def first
  object_from_address(@base[:first])
end

#last ⇒ Object

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



97
98
99
 
# File 'lib/innodb/list.rb', line 97

def last
  object_from_address(@base[:last])
end

#next(object) ⇒ Object

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



81
82
83
84
85
86
87
 
# File 'lib/innodb/list.rb', line 81

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.



65
66
67
 
# File 'lib/innodb/list.rb', line 65

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.



71
72
73
74
75
76
77
 
# File 'lib/innodb/list.rb', line 71

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