class PEROBS::SpaceTree

The SpaceTree keeps a complete list of all empty spaces in the FlatFile. Spaces are stored with size and address. The Tree is Tenary Tree. The nodes can link to other nodes with smaller spaces, same spaces and bigger spaces. The advantage of the ternary tree is that all nodes have equal size which drastically simplifies the backing store operation.

Attributes

cache[R]
nodes[R]
progressmeter[R]

Public Class Methods

new(dir, progressmeter) click to toggle source

Manage the free spaces tree in the specified directory @param dir [String] directory path of an existing directory

# File lib/perobs/SpaceTree.rb, line 47
def initialize(dir, progressmeter)
  @dir = dir
  @progressmeter = progressmeter

  # This EquiBlobsFile contains the nodes of the SpaceTree.
  @nodes = EquiBlobsFile.new(@dir, 'database_spaces', progressmeter,
                             SpaceTreeNode::NODE_BYTES, 1)

  # Benchmark runs showed a cache size of 128 to be a good compromise
  # between read and write performance trade-offs and memory consumption.
  @cache = PersistentObjectCache.new(256, 256, SpaceTreeNode, self)
end

Public Instance Methods

add_space(address, size) click to toggle source

Add a new space with a given address and size. @param address [Integer] Starting address of the space @param size [Integer] size of the space in bytes

# File lib/perobs/SpaceTree.rb, line 110
def add_space(address, size)
  if size <= 0
    PEROBS.log.fatal "Size (#{size}) must be larger than 0."
  end
  # The following check is fairly costly and should never trigger unless
  # there is a bug in the PEROBS code. Only use this for debugging.
  #if has_space?(address, size)
  #  PEROBS.log.fatal "The space with address #{address} and size " +
  #    "#{size} can't be added twice."
  #end
  root.add_space(address, size)
end
check(flat_file = nil) click to toggle source

Check if the index is OK and matches the flat_file data (if given). @param flat_file [FlatFile] Flat file to compare with @return True if space list matches, flase otherwise

# File lib/perobs/SpaceTree.rb, line 167
def check(flat_file = nil)
  sync
  return false unless @nodes.check
  root.check(flat_file, @nodes.total_entries)
end
clear() click to toggle source

Clear all pools and forget any registered spaces.

# File lib/perobs/SpaceTree.rb, line 149
def clear
  @nodes.clear
  @cache.clear
  @root_address = SpaceTreeNode::create(self).node_address
end
close() click to toggle source

Close the SpaceTree file.

# File lib/perobs/SpaceTree.rb, line 71
def close
  @cache.flush(true)
  @nodes.close
  @root_address = nil
  @cache.clear
end
delete_node(address) click to toggle source

Delete the node at the given address in the SpaceTree file. @param address [Integer] address in file

# File lib/perobs/SpaceTree.rb, line 143
def delete_node(address)
  @cache.delete(address)
  @nodes.delete_blob(address)
end
each() { |blob_address, size| ... } click to toggle source

Iterate over all entries and yield address and size.

# File lib/perobs/SpaceTree.rb, line 174
def each
  root.each do |node, mode, stack|
    if mode == :on_enter
      yield(node.blob_address, node.size)
    end
  end
end
erase() click to toggle source

Erase the SpaceTree file. This method cannot be called while the file is open.

# File lib/perobs/SpaceTree.rb, line 103
def erase
  @nodes.erase
end
get_space(size) click to toggle source

Get a space that has at least the requested size. @param size [Integer] Required size in bytes @return [Array] Touple with address and actual size of the space.

# File lib/perobs/SpaceTree.rb, line 126
def get_space(size)
  if size <= 0
    PEROBS.log.fatal "Size (#{size}) must be larger than 0."
  end

  if (address_size = root.find_matching_space(size))
    # First we try to find an exact match.
    return address_size
  elsif (address_size = root.find_equal_or_larger_space(size))
    return address_size
  else
    return nil
  end
end
has_space?(address, size) click to toggle source

Check if there is a space in the free space lists that matches the address and the size. @param [Integer] address Address of the space @param [Integer] size Length of the space in bytes @return [Boolean] True if space is found, false otherwise

# File lib/perobs/SpaceTree.rb, line 160
def has_space?(address, size)
  root.has_space?(address, size)
end
is_open?() click to toggle source

@return true if file is currently open.

# File lib/perobs/SpaceTree.rb, line 79
def is_open?
  !@root_address.nil?
end
open() click to toggle source

Open the SpaceTree file.

# File lib/perobs/SpaceTree.rb, line 61
def open
  @nodes.open
  @cache.clear
  node = @nodes.total_entries == 0 ?
    SpaceTreeNode::create(self) :
    SpaceTreeNode::load(self, @nodes.first_entry)
  @root_address = node.node_address
end
root() click to toggle source

Return the SpaceTreeNode that is the root of the SpaceTree.

# File lib/perobs/SpaceTree.rb, line 97
def root
  @root_address ? @cache.get(@root_address) : nil
end
set_root(node) click to toggle source

Set a new root node for the SpaceTree @param node [SpaceTreeNode]

# File lib/perobs/SpaceTree.rb, line 91
def set_root(node)
  @root_address = node.node_address
  @nodes.first_entry = node.node_address
end
sync() click to toggle source

Flush all pending writes to the file system.

# File lib/perobs/SpaceTree.rb, line 84
def sync
  @cache.flush(true)
  @nodes.sync
end
to_a() click to toggle source

Convert the tree into an Array of [address, size] touples. @return [Array]

# File lib/perobs/SpaceTree.rb, line 190
def to_a
  root.to_a
end
to_s() click to toggle source

Complete internal tree data structure as textual tree. @return [String]

# File lib/perobs/SpaceTree.rb, line 184
def to_s
  root.to_tree_s
end