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
Public Class Methods
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 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 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 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 the SpaceTree
file.
# File lib/perobs/SpaceTree.rb, line 71 def close @cache.flush(true) @nodes.close @root_address = nil @cache.clear end
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
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 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 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
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
@return true if file is currently open.
# File lib/perobs/SpaceTree.rb, line 79 def is_open? !@root_address.nil? end
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
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 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
Flush all pending writes to the file system.
# File lib/perobs/SpaceTree.rb, line 84 def sync @cache.flush(true) @nodes.sync end
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
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