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

blob_address[RW]
equal[R]
larger[R]
node_address[R]
parent[R]
size[RW]
smaller[R]

Public Class Methods

create(tree, blob_address = 0, size = 0, parent = nil) click to toggle source

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
load(tree, node_address, unused = nil) click to toggle source

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
new(tree, node_address, blob_address = 0, size = 0, parent = nil, smaller = nil, equal = nil, larger = nil) click to toggle source

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

==(node) click to toggle source

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_space(address, size) click to toggle source

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(flat_file, count) click to toggle source

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
delete_node() click to toggle source
# 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
each() { |node, mode, stack| ... } click to toggle source

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
find_equal_or_larger_space(size) click to toggle source

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_largest_node() click to toggle source

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
find_matching_space(size) click to toggle source

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_smallest_node() click to toggle source

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
has_space?(address, size) click to toggle source

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
parent=(p) click to toggle source
# File lib/perobs/SpaceTreeNode.rb, line 454
def parent=(p)
  @parent = p ? SpaceTreeNodeLink.new(@tree, p) : nil
  @tree.cache.insert(self)
end
save() click to toggle source

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
set_size_and_address(size, address) click to toggle source
# File lib/perobs/SpaceTreeNode.rb, line 432
def set_size_and_address(size, address)
  @size = size
  @blob_address = address
  @tree.cache.insert(self)
end
text_tree_prefix() click to toggle source

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
to_a() click to toggle source

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
to_s() click to toggle source

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
to_tree_s() click to toggle source

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
uid() click to toggle source

@return [Integer] The node address since it uniquely identifies the

Node.
# File lib/perobs/SpaceTreeNode.rb, line 294
def uid
  @node_address
end