lib/perobs/BTreeNode.rb in perobs-3.0.2 vs lib/perobs/BTreeNode.rb in perobs-4.0.0
- old
+ new
@@ -38,11 +38,10 @@
# 1 number of child references but no values. The is_leaf flag is used to
# mark a node as leaf or branch node.
class BTreeNode
attr_reader :node_address, :parent, :is_leaf, :keys, :values, :children
- attr_accessor :dirty
# Create a new BTreeNode object for the given tree with the given parent
# or recreate the node with the given node_address from the backing store.
# If node_address is nil a new node will be created. If not, node_address
# must be an existing address that can be found in the backing store to
@@ -51,58 +50,142 @@
# @param parent [BTreeNode] reference to parent node
# @param node_address [Integer] the address of the node to read from the
# backing store
# @param is_leaf [Boolean] true if the node should be a leaf node, false
# if not
- def initialize(tree, parent = nil, node_address = nil, is_leaf = true)
+ def initialize(tree, node_address = nil, parent = nil, is_leaf = true,
+ keys = [], values = [], children = [])
@tree = tree
- @parent = nil
if node_address == 0
PEROBS.log.fatal "Node address may not be 0"
end
@node_address = node_address
- @keys = []
+ @parent = parent ? BTreeNodeLink.new(tree, parent) : nil
+ @keys = keys
if (@is_leaf = is_leaf)
- @values = []
- else
+ @values = values
@children = []
+ else
+ @children = children
+ @values = []
end
- if node_address
- unless node_address.is_a?(Integer)
- PEROBS.log.fatal "node_address is not Integer: #{node_address.class}"
- end
+ ObjectSpace.define_finalizer(
+ self, BTreeNode._finalize(@tree, @node_address, object_id))
+ @tree.node_cache.insert(self, false)
+ end
- # This must be an existing node. Try to read it and fill the instance
- # variables.
- unless read_node
- PEROBS.log.fatal "SpaceTree node at address #{node_address} " +
- "does not exist"
- end
+ # This method generates the destructor for the objects of this class. It
+ # is done this way to prevent the Proc object hanging on to a reference to
+ # self which would prevent the object from being collected. This internal
+ # method is not intended for users to call.
+ def BTreeNode::_finalize(tree, node_address, ruby_object_id)
+ proc { tree.node_cache._collect(node_address, ruby_object_id) }
+ end
+
+ # Create a new SpaceTreeNode. This method should be used for the creation
+ # of new nodes instead of calling the constructor directly.
+ # @param tree [BTree] The tree the new node should belong to
+ # @param parent [BTreeNode] The parent node
+ # @param is_leaf [Boolean] True if the node has no children, false
+ # otherwise
+ def BTreeNode::create(tree, parent = nil, is_leaf = true)
+ unless parent.nil? || parent.is_a?(BTreeNode) ||
+ parent.is_a?(BTreeNodeLink)
+ PEROBS.log.fatal "Parent node must be a BTreeNode but is of class " +
+ "#{parent.class}"
+ end
+
+ address = tree.nodes.free_address
+ node = BTreeNode.new(tree, address, parent, is_leaf)
+ # This is a new node. Make sure the data is written to the file.
+ tree.node_cache.insert(node)
+
+ node
+ end
+
+ # Restore a node from the backing store at the given address and tree.
+ # @param tree [BTree] The tree the node belongs to
+ # @param node_address [Integer] The address in the blob file.
+ def BTreeNode::load(tree, address)
+ unless address.is_a?(Integer)
+ PEROBS.log.fatal "address is not Integer: #{address.class}"
+ end
+
+ unless (bytes = tree.nodes.retrieve_blob(address))
+ PEROBS.log.fatal "SpaceTree node at address #{address} " +
+ "does not exist"
+ end
+
+ unless Zlib::crc32(bytes) != 0
+ PEROBS.log.fatal "Checksum failure in BTreeNode entry @#{address}"
+ end
+ ary = bytes.unpack(BTreeNode::node_bytes_format(tree))
+ # Read is_leaf
+ if ary[0] != 0 && ary[0] != 1
+ PEROBS.log.fatal "First byte of a BTreeNode entry must be 0 or 1"
+ end
+ is_leaf = ary[0] == 0 ? false : true
+ # This is the number of keys this node has.
+ key_count = ary[1]
+ data_count = ary[2]
+ # Read the parent node address
+ parent = ary[3] == 0 ? nil : BTreeNodeLink.new(tree, ary[3])
+ # Read the keys
+ keys = ary[4, key_count]
+
+ children = nil
+ values = nil
+ if is_leaf
+ # Read the values
+ values = ary[4 + tree.order, data_count]
else
- unless parent.nil? || parent.is_a?(BTreeNode) ||
- parent.is_a?(BTreeNodeLink)
- PEROBS.log.fatal "Parent node must be a BTreeNode but is of class " +
- "#{parent.class}"
+ # Read the child addresses
+ children = []
+ data_count.times do |i|
+ child_address = ary[4 + tree.order + i]
+ unless child_address > 0
+ PEROBS.log.fatal "Child address must be larger than 0"
+ end
+ children << BTreeNodeLink.new(tree, child_address)
end
-
- # This is a new node. Make sure the data is written to the file.
- @node_address = @tree.nodes.free_address
- self.parent = parent
end
+
+ node = BTreeNode.new(tree, address, parent, is_leaf, keys, values,
+ children)
+ tree.node_cache.insert(node, false)
+
+ node
end
+ # @return [String] The format used for String.pack.
+ def BTreeNode::node_bytes_format(tree)
+ # This does not include the 4 bytes for the CRC32 checksum
+ "CSSQQ#{tree.order}Q#{tree.order + 1}"
+ end
+
+ # @return [Integer] The number of bytes needed to store a node.
def BTreeNode::node_bytes(order)
1 + # is_leaf
2 + # actual key count
2 + # actual value or children count (aka data count)
8 + # parent address
8 * order + # keys
8 * (order + 1) + # values or child addresses
4 # CRC32 checksum
end
+ # Save the node into the blob file.
+ def save
+ write_node
+ end
+
+ # The node address uniquely identifies a BTreeNode.
+ def uid
+ @node_address
+ end
+
# Insert or replace the given value by using the key as unique address.
# @param key [Integer] Unique key to retrieve the value
# @param value [Integer] value to insert
def insert(key, value)
node = self
@@ -184,18 +267,18 @@
# half.
# @return [BTreeNodeLink] common parent of the two nodes
def split_node
unless @parent
# The node is the root node. We need to create a parent node first.
- self.parent = @tree.new_node(nil, nil, false)
+ self.parent = BTreeNode::create(@tree, nil, false)
@parent.set_child(0, self)
@tree.set_root(@parent)
end
# Create the new sibling that will take the 2nd half of the
# node content.
- sibling = @tree.new_node(@parent, nil, @is_leaf)
+ sibling = BTreeNode::create(@tree, @parent, @is_leaf)
# Determine the index of the middle element that gets moved to the
# parent. The order must be an uneven number, so adding 1 will get us
# the middle element.
mid = @tree.order / 2 + 1
# Insert the middle element key into the parent node
@@ -227,11 +310,10 @@
def insert_element(key, value_or_child)
if @keys.size >= @tree.order
PEROBS.log.fatal "Cannot insert into a full BTreeNode"
end
- mark_as_modified
i = search_key_index(key)
if @keys[i] == key
# Overwrite existing entries
@keys[i] = key
if is_leaf
@@ -246,19 +328,19 @@
@values.insert(i, value_or_child)
else
@children.insert(i + 1, BTreeNodeLink.new(@tree, value_or_child))
end
end
+ @tree.node_cache.insert(self)
end
# Remove the element at the given index.
def remove_element(index)
# We need this key to find the link in the parent node.
first_key = @keys[0]
removed_value = nil
- mark_as_modified
# Delete the key at the specified index.
unless @keys.delete_at(index)
PEROBS.log.fatal "Could not remove element #{index} from BTreeNode " +
"@#{@node_address}"
end
@@ -267,10 +349,11 @@
removed_value = @values.delete_at(index)
else
# The corresponding child has can be found at 1 index higher.
@children.delete_at(index + 1)
end
+ @tree.node_cache.insert(self)
# Find the lower and upper siblings and the index of the key for this
# node in the parent node.
lower_sibling, upper_sibling, parent_index =
find_closest_siblings(first_key)
@@ -299,11 +382,10 @@
PEROBS.log.fatal "Source #{@is_leaf} and destination " +
"#{dest_node.is_leaf} node must be of same kind"
end
dest_node.keys[dst_idx, count] = @keys[src_idx, count]
- dest_node.dirty = true
if @is_leaf
# For leaves we copy the keys and corresponding values.
dest_node.values[dst_idx, count] = @values[src_idx, count]
else
# For branch nodes we copy all but the first specified key (that
@@ -311,35 +393,36 @@
# moved-up key.
(count + 1).times do |i|
dest_node.set_child(dst_idx + i, @children[src_idx + i])
end
end
+ @tree.node_cache.insert(dest_node)
end
def parent=(p)
@parent = p ? BTreeNodeLink.new(@tree, p) : nil
- mark_as_modified
+ @tree.node_cache.insert(self)
end
def set_child(index, child)
if child
@children[index] = BTreeNodeLink.new(@tree, child)
@children[index].parent = self
else
@children[index] = nil
end
- mark_as_modified
+ @tree.node_cache.insert(self)
end
def trim(idx)
- mark_as_modified
@keys = @keys[0..idx - 1]
if @is_leaf
@values = @values[0..idx - 1]
else
@children = @children[0..idx]
end
+ @tree.node_cache.insert(self)
end
# Search the keys of the node that fits the given key. The result is
# either the index of an exact match or the index of the position where
# the given key would have to be inserted.
@@ -596,12 +679,10 @@
PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{msg}\n" +
@tree.to_s
end
def write_node
- return unless @dirty
-
ary = [
@is_leaf ? 1 : 0,
@keys.size,
@is_leaf ? @values.size : @children.size,
@parent ? @parent.node_address : 0
@@ -618,68 +699,15 @@
PEROBS.log.fatal "write_node: Child must not be nil" unless child
end
ary += @children.map{ |c| c.node_address } +
::Array.new(@tree.order + 1 - @children.size, 0)
end
- bytes = ary.pack(node_bytes_format)
+ bytes = ary.pack(BTreeNode::node_bytes_format(@tree))
bytes += [ Zlib::crc32(bytes) ].pack('L')
@tree.nodes.store_blob(@node_address, bytes)
- @dirty = false
end
- def mark_as_modified
- @tree.mark_node_as_modified(self)
- @dirty = true
- end
-
private
-
- def read_node
- return false unless (bytes = @tree.nodes.retrieve_blob(@node_address))
-
- unless Zlib::crc32(bytes) != 0
- PEROBS.log.error "Checksum failure in BTreeNode entry @#{node_address}"
- return false
- end
- ary = bytes.unpack(node_bytes_format)
- # Read is_leaf
- if ary[0] != 0 && ary[0] != 1
- PEROBS.log.error "First byte of a BTreeNode entry must be 0 or 1"
- return false
- end
- @is_leaf = ary[0] == 0 ? false : true
- # This is the number of keys this node has.
- key_count = ary[1]
- data_count = ary[2]
- # Read the parent node address
- @parent = ary[3] == 0 ? nil : BTreeNodeLink.new(@tree, ary[3])
- # Read the keys
- @keys = ary[4, key_count]
-
- if @is_leaf
- # Read the values
- @values = ary[4 + @tree.order, data_count]
- else
- # Read the child addresses
- @children = []
- data_count.times do |i|
- address = ary[4 + @tree.order + i]
- unless address > 0
- PEROBS.log.fatal "Child address must not be 0"
- end
- @children << BTreeNodeLink.new(@tree, address)
- end
- end
-
- @dirty = false
-
- true
- end
-
- def node_bytes_format
- # This does not include the 4 bytes for the CRC32 checksum
- "CSSQQ#{@tree.order}Q#{@tree.order + 1}"
- end
def find_closest_siblings(key)
# The root node has no siblings.
return [ nil, nil, nil ] unless @parent