class PEROBS::SpaceTreeNode
The SpaceTree
keeps a complete list of all empty spaces in the FlatFile
. Spaces are stored with size and address. The Tree is Tenerary Tree. The nodes can link to other nodes with smaller spaces, same spaces and bigger spaces.
Constants
- NODE_BYTES
Each node can hold a reference to the parent, a lower, equal or larger size node and the actual value and the address in the
FlatFile
. Each of these entries is 8 bytes long.- NODE_BYTES_FORMAT
The pack/unpack format.
Attributes
Public Class Methods
Create a new SpaceTreeNode
. This method should be used for the creation of new nodes instead of calling the constructor directly. @param tree [SpaceTree] The tree the node should belong to @param blob_address
[Integer] Address of the free space blob @param size [Integer] Size of the free space blob @param parent [SpaceTreeNode] Parent node in the tree
# File lib/perobs/SpaceTreeNode.rb, line 85 def SpaceTreeNode::create(tree, blob_address = 0, size = 0, parent = nil) node_address = tree.nodes.free_address node = SpaceTreeNode.new(tree, node_address, blob_address, size, parent) tree.cache.insert(node) node end
Restore a node from the backing store at the given address and tree. @param tree [SpaceTree] The tree the node belongs to @param node_address
[Integer] The address in the file.
# File lib/perobs/SpaceTreeNode.rb, line 97 def SpaceTreeNode::load(tree, node_address, unused = nil) unless node_address > 0 PEROBS.log.fatal "node_address (#{node_address}) must be larger than 0" end unless (bytes = tree.nodes.retrieve_blob(node_address)) PEROBS.log.fatal "SpaceTreeNode at address #{node_address} does " + "not exist" end blob_address, size, parent_node_address, smaller_node_address, equal_node_address, larger_node_address = bytes.unpack(NODE_BYTES_FORMAT) parent = parent_node_address != 0 ? SpaceTreeNodeLink.new(tree, parent_node_address) : nil smaller = smaller_node_address != 0 ? SpaceTreeNodeLink.new(tree, smaller_node_address) : nil equal = equal_node_address != 0 ? SpaceTreeNodeLink.new(tree, equal_node_address) : nil larger = larger_node_address != 0 ? SpaceTreeNodeLink.new(tree, larger_node_address) : nil node = SpaceTreeNode.new(tree, node_address, blob_address, size, parent, smaller, equal, larger) tree.cache.insert(node, false) node end
Create a new SpaceTreeNode
object. If node_address
is not nil, the data will be read from the SpaceTree
file at the given node_address. @param tree [SpaceTree] Tree that the object should belong to @param node_address
[Integer] Address of the node in the file @param blob_address
[Integer] Address of the free space blob @param size [Integer] Size of the free space blob @param parent [SpaceTreeNode] Parent node in the tree @param smaller [SpaceTreeNode] smaller node in the tree @param equal [SpaceTreeNode] equal node in the tree @param larger [SpaceTreeNode] larger node in the tree
# File lib/perobs/SpaceTreeNode.rb, line 61 def initialize(tree, node_address, blob_address = 0, size = 0, parent = nil, smaller = nil, equal = nil, larger = nil) @tree = tree if node_address <= 0 PEROBS.log.fatal "Node address (#{node_address}) must be larger than 0" end @node_address = node_address if blob_address < 0 PEROBS.log.fatal "Blob address (#{node_address}) must be larger than 0" end @blob_address = blob_address @size = size @parent = parent @smaller = smaller @equal = equal @larger = larger end
Public Instance Methods
Compare this node to another node. @return [Boolean] true if node address is identical, false otherwise
# File lib/perobs/SpaceTreeNode.rb, line 460 def ==(node) node && @node_address == node.node_address end
Add a new node for the given address and size to the tree. @param address [Integer] address of the free space @param size [Integer] size of the free space
# File lib/perobs/SpaceTreeNode.rb, line 140 def add_space(address, size) node = self loop do if node.size == 0 # This happens only for the root node if the tree is empty. node.set_size_and_address(size, address) break elsif size < node.size # The new size is smaller than this node. if node.smaller # There is already a smaller node, so pass it on. node = node.smaller else # There is no smaller node yet, so we create a new one as a # smaller child of the current node. node.set_link('@smaller', SpaceTreeNode::create(@tree, address, size, node)) break end elsif size > node.size # The new size is larger than this node. if node.larger # There is already a larger node, so pass it on. node = node.larger else # There is no larger node yet, so we create a new one as a larger # child of the current node. node.set_link('@larger', SpaceTreeNode::create(@tree, address, size, node)) break end else # Same size as current node. Insert new node as equal child at top of # equal list. new_node = SpaceTreeNode::create(@tree, address, size, node) new_node.set_link('@equal', node.equal) node.set_link('@equal', new_node) break end end end
Check this node and all sub nodes for possible structural or logical errors. @param flat_file [FlatFile] If given, check that the space is also
present in the given flat file.
@param count [Integer] The total number of entries in the tree @return [false,true] True if OK, false otherwise
# File lib/perobs/SpaceTreeNode.rb, line 523 def check(flat_file, count) node_counter = 0 max_depth = 0 @tree.progressmeter.start('Checking space list entries', count) do |pm| each do |node, mode, stack| max_depth = stack.size if stack.size > max_depth case mode when :smaller if node.smaller return false unless node.check_node_link('smaller', stack) smaller_node = node.smaller if smaller_node.size >= node.size PEROBS.log.error "Smaller SpaceTreeNode size " + "(#{smaller_node}) is not smaller than #{node}" return false end end when :equal if node.equal return false unless node.check_node_link('equal', stack) equal_node = node.equal if equal_node.smaller || equal_node.larger PEROBS.log.error "Equal node #{equal_node} must not have " + "smaller/larger childs" return false end if node.size != equal_node.size PEROBS.log.error "Equal SpaceTreeNode size (#{equal_node}) " + "is not equal parent node #{node}" return false end end when :larger if node.larger return false unless node.check_node_link('larger', stack) larger_node = node.larger if larger_node.size <= node.size PEROBS.log.error "Larger SpaceTreeNode size " + "(#{larger_node}) is not larger than #{node}" return false end end when :on_exit if flat_file && !flat_file.has_space?(node.blob_address, node.size) PEROBS.log.error "SpaceTreeNode has space at offset " + "#{node.blob_address} of size #{node.size} that isn't " + "available in the FlatFile." return false end pm.update(node_counter += 1) end end end PEROBS.log.debug "#{node_counter} SpaceTree nodes checked" PEROBS.log.debug "Maximum tree depth is #{max_depth}" return true end
Check the integrity of the given sub-node link and the parent link pointing back to this node. @param link [String] 'smaller', 'equal' or 'larger' @param stack [Array] List of parent nodes [ address, mode ] touples @return [Boolean] true of OK, false otherwise
# File lib/perobs/SpaceTreeNode.rb, line 593 def check_node_link(link, stack) if (node = instance_variable_get('@' + link)) # Node links must only be of class SpaceTreeNodeLink unless node.nil? || node.is_a?(SpaceTreeNodeLink) PEROBS.log.error "Node link #{link} of node #{to_s} " + "is of class #{node.class}" return false end # Link must not point back to self. if node == self PEROBS.log.error "#{link} address of node " + "#{node.to_s} points to self #{to_s}" return false end # Link must not point to any of the parent nodes. if stack.include?(node) PEROBS.log.error "#{link} address of node #{to_s} " + "points to parent node #{node}" return false end # Parent link of node must point back to self. if node.parent != self PEROBS.log.error "@#{link} node #{node.to_s} does not have parent " + "link pointing " + "to parent node #{to_s}. Pointing at " + "#{node.parent.nil? ? 'nil' : node.parent.to_s} instead." return false end end true end
# File lib/perobs/SpaceTreeNode.rb, line 340 def delete_node if @equal # Replace the current node with the next @equal node. @equal.set_link('@smaller', @smaller) if @smaller @equal.set_link('@larger', @larger) if @larger relink_parent(@equal) elsif @smaller && @larger.nil? # We have no @larger node, so we can just replace the current node # with the @smaller node. relink_parent(@smaller) elsif @larger && @smaller.nil? # We have no @smaller node, wo we can just replace the current node # with the @larger node. relink_parent(@larger) elsif @smaller && @larger # Find the largest node in the smaller sub-node. This node will # replace the current node. node = @smaller.find_largest_node if node != @smaller # If the found node is not the direct @smaller node, attach the # smaller sub-node of the found node to the parent of the found # node. node.relink_parent(node.smaller) # The @smaller sub node of the current node is attached to the # @smaller link of the found node. node.set_link('@smaller', @smaller) end # Attach the @larger sub-node of the current node to the @larger link # of the found node. node.set_link('@larger', @larger) # Point the link in the parent of the current node to the found node. relink_parent(node) else # The node is a leaf node. relink_parent(nil) end @tree.delete_node(@node_address) if @parent end
Depth-first iterator for all nodes. The iterator yields the given block at 5 points for any found node. The mode variable indicates the point. :on_enter Coming from the parent we've entered the node for the first
time
:smaller We are about to follow the link to the smaller sub-node :equal We are about to follow the link to the equal sub-node :larger We are about to follow the link to the larger sub-node :on_exit We have completed this node
# File lib/perobs/SpaceTreeNode.rb, line 306 def each # We use a non-recursive implementation to traverse the tree. This stack # keeps track of all the known still to be checked nodes. stack = [ [ self, :on_enter ] ] while !stack.empty? node, mode = stack.pop # Empty trees only have a dummy node that has no parent, and a size # and address of 0. break if node.size == 0 && node.blob_address == 0 && node.parent.nil? case mode when :on_enter yield(node, mode, stack) stack.push([ node, :smaller ]) when :smaller yield(node, mode, stack) if node.smaller stack.push([ node, :equal ]) stack.push([ node.smaller, :on_enter]) if node.smaller when :equal yield(node, mode, stack) if node.equal stack.push([ node, :larger ]) stack.push([ node.equal, :on_enter]) if node.equal when :larger yield(node, mode, stack) if node.larger stack.push([ node, :on_exit]) stack.push([ node.larger, :on_enter]) if node.larger when :on_exit yield(node, mode, stack) end end end
Return an address/size touple that matches the requested size or is larger than the requested size plus the overhead for another blob. Return nil if nothing was found. @param size [Integer] size of the free space @return [Array or nil] address, size touple or nil
# File lib/perobs/SpaceTreeNode.rb, line 242 def find_equal_or_larger_space(size) node = self loop do if node.size < size if node.larger # The current space is not yet large enough. If we have a larger sub # node check that one next. node = node.larger else break end elsif node.size == size || node.size >= size * 2 + FlatFileBlobHeader::LENGTH # We've found a space that is either a perfect match or is large # enough to hold at least one more record. Remove it from the list and # return it. actual_size = node.size address = node.blob_address node.delete_node return [ address, actual_size ] elsif node.smaller # The current space is larger than size but not large enough for an # additional record. So check if we have a perfect match in the # smaller brach if available. node = node.smaller else break end end return nil end
Find the node with the largest size in this sub-tree. @return [SpaceTreeNode]
# File lib/perobs/SpaceTreeNode.rb, line 420 def find_largest_node node = self loop do if node.larger node = node.larger else # We've found a 'leaf' node. return node end end end
Return an address/size touple that matches exactly the requested size. Return nil if nothing was found. @param size [Integer] size of the free space @return [Array or nil] address, size touple or nil
# File lib/perobs/SpaceTreeNode.rb, line 211 def find_matching_space(size) node = self loop do if node.size < size if node.larger # The current space is not yet large enough. If we have a larger sub # node check that one next. node = node.larger else break end elsif node.size == size # We've found a space that is an exact match. Remove it from the # list and return it. address = node.blob_address node.delete_node return [ address, size ] else break end end return nil end
Find the node with the smallest size in this sub-tree. @return [SpaceTreeNode]
# File lib/perobs/SpaceTreeNode.rb, line 406 def find_smallest_node node = self loop do if node.smaller node = node.smaller else # We've found a 'leaf' node. return node end end end
Check if this node or any sub-node has an entry for the given address and size. @param address [Integer] address of the free space @param size [Integer] size of the free space @return [Boolean] True if found, otherwise false
# File lib/perobs/SpaceTreeNode.rb, line 190 def has_space?(address, size) node = self loop do if node.blob_address == address return size == node.size elsif size < node.size && node.smaller node = node.smaller elsif size > node.size && node.larger node = node.larger elsif size == node.size && node.equal node = node.equal else return false end end end
# File lib/perobs/SpaceTreeNode.rb, line 454 def parent=(p) @parent = p ? SpaceTreeNodeLink.new(@tree, p) : nil @tree.cache.insert(self) end
Replace the link in the parent node of the current node that points to the current node with the given node. @param node [SpaceTreeNode]
# File lib/perobs/SpaceTreeNode.rb, line 382 def relink_parent(node) if @parent if @parent.smaller == self @parent.set_link('@smaller', node) elsif @parent.equal == self @parent.set_link('@equal', node) elsif @parent.larger == self @parent.set_link('@larger', node) else PEROBS.log.fatal "Cannot relink unknown child node with address " + "#{node.node_address} from #{parent.to_s}" end else if node @tree.set_root(node) node.parent = nil else set_size_and_address(0, 0) end end end
Save the node into the blob file.
# File lib/perobs/SpaceTreeNode.rb, line 128 def save bytes = [ @blob_address, @size, @parent ? @parent.node_address : 0, @smaller ? @smaller.node_address : 0, @equal ? @equal.node_address : 0, @larger ? @larger.node_address : 0].pack(NODE_BYTES_FORMAT) @tree.nodes.store_blob(@node_address, bytes) end
# File lib/perobs/SpaceTreeNode.rb, line 438 def set_link(name, node_or_address) if node_or_address # Set the link to the given SpaceTreeNode or node address. instance_variable_set(name, node = node_or_address.is_a?(SpaceTreeNodeLink) ? node_or_address : SpaceTreeNodeLink.new(@tree, node_or_address)) # Link the node back to this node via the parent variable. node.parent = self else # Clear the node link. instance_variable_set(name, nil) end @tree.cache.insert(self) end
# File lib/perobs/SpaceTreeNode.rb, line 432 def set_size_and_address(size, address) @size = size @blob_address = address @tree.cache.insert(self) end
The indentation and arch routing for the text tree. @return [String]
# File lib/perobs/SpaceTreeNode.rb, line 658 def text_tree_prefix if (node = @parent) str = '+' else # Prefix start for root node line str = 'o' end while node last_child = false if node.parent if node.parent.smaller == node last_child = node.parent.equal.nil? && node.parent.larger.nil? elsif node.parent.equal == node last_child = node.parent.larger.nil? elsif node.parent.larger == node last_child = true end else # Padding for the root node str = ' ' + str break end str = (last_child ? ' ' : '| ') + str node = node.parent end str end
Collects address and size touples of all nodes in the tree with a depth-first strategy and stores them in an Array
. @return [Array] Array
with [ address, size ] touples.
# File lib/perobs/SpaceTreeNode.rb, line 467 def to_a ary = [] each do |node, mode, stack| if mode == :on_enter ary << [ node.blob_address, node.size ] end end ary end
Textual version of the node data. It has the form node_address
:[blob_address, size] ^parent_node_address <smaller_node_address >larger_node_address @return [String]
# File lib/perobs/SpaceTreeNode.rb, line 483 def to_s s = "#{@node_address}:[#{@blob_address}, #{@size}]" if @parent begin s += " ^#{@parent.node_address}" rescue s += ' ^@' end end if @smaller begin s += " <#{@smaller.node_address}" rescue s += ' <@' end end if @equal begin s += " =#{@equal.node_address}" rescue s += ' =@' end end if @larger begin s += " >#{@larger.node_address}" rescue s += ' >@' end end s end
Convert the node and all child nodes into a tree like text form. @return [String]
# File lib/perobs/SpaceTreeNode.rb, line 633 def to_tree_s str = '' each do |node, mode, stack| if mode == :on_enter begin branch_mark = node.parent.nil? ? '' : node.parent.smaller == node ? '<' : node.parent.equal == node ? '=' : node.parent.larger == node ? '>' : '@' str += "#{node.text_tree_prefix}#{branch_mark}-" + "#{node.smaller || node.equal || node.larger ? 'v-' : '--'}" + "#{node.to_s}\n" rescue str += "#{node.text_tree_prefix}- @@@@@@@@@@\n" end end end str end
@return [Integer] The node address since it uniquely identifies the
Node.
# File lib/perobs/SpaceTreeNode.rb, line 294 def uid @node_address end
Remove a smaller/equal/larger link from the current node. @param child_node [SpaceTreeNodeLink] node to remove
# File lib/perobs/SpaceTreeNode.rb, line 278 def unlink_node(child_node) if @smaller == child_node @smaller = nil elsif @equal == child_node @equal = nil elsif @larger == child_node @larger = nil else PEROBS.log.fatal "Cannot unlink unknown child node with address " + "#{child_node.node_address} from #{to_s}" end @tree.cache.insert(self) end