Class: PEROBS::SpaceTree

Inherits:
Object
  • Object
show all
Defined in:
lib/perobs/SpaceTree.rb

Overview

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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dir, progressmeter) ⇒ SpaceTree

Manage the free spaces tree in the specified directory

Parameters:

  • dir (String) —

    directory path of an existing directory



47
48
49
50
51
52
53
54
55
56
57
58
 
# 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(128, 5000, SpaceTreeNode, self)
end

Instance Attribute Details

#cache ⇒ Object (readonly)

Returns the value of attribute cache.



43
44
45
 
# File 'lib/perobs/SpaceTree.rb', line 43

def cache
  @cache
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



43
44
45
 
# File 'lib/perobs/SpaceTree.rb', line 43

def nodes
  @nodes
end

#progressmeter ⇒ Object (readonly)

Returns the value of attribute progressmeter.



43
44
45
 
# File 'lib/perobs/SpaceTree.rb', line 43

def progressmeter
  @progressmeter
end

Instance Method Details

#add_space(address, size) ⇒ Object

Add a new space with a given address and size.

Parameters:

  • address (Integer) —

    Starting address of the space

  • size (Integer) —

    size of the space in bytes



110
111
112
113
114
115
116
117
118
119
120
121
 
# 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) ⇒ Object

Check if the index is OK and matches the flat_file data (if given).

Parameters:

  • flat_file (FlatFile) (defaults to: nil) —

    Flat file to compare with

Returns:

  • True if space list matches, flase otherwise



167
168
169
170
171
 
# 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 ⇒ Object

Clear all pools and forget any registered spaces.



149
150
151
152
153
 
# File 'lib/perobs/SpaceTree.rb', line 149

def clear
  @nodes.clear
  @cache.clear
  @root_address = SpaceTreeNode::create(self).node_address
end

#close ⇒ Object

Close the SpaceTree file.



71
72
73
74
75
76
 
# File 'lib/perobs/SpaceTree.rb', line 71

def close
  @cache.flush(true)
  @nodes.close
  @root_address = nil
  @cache.clear
end

#delete_node(address) ⇒ Object

Delete the node at the given address in the SpaceTree file.

Parameters:

  • address (Integer) —

    address in file



143
144
145
146
 
# File 'lib/perobs/SpaceTree.rb', line 143

def delete_node(address)
  @cache.delete(address)
  @nodes.delete_blob(address)
end

#each ⇒ Object

Iterate over all entries and yield address and size.



174
175
176
177
178
179
180
 
# 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 ⇒ Object

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



103
104
105
 
# File 'lib/perobs/SpaceTree.rb', line 103

def erase
  @nodes.erase
end

#get_space(size) ⇒ Array

Get a space that has at least the requested size.

Parameters:

  • size (Integer) —

    Required size in bytes

Returns:

  • (Array) —

    Touple with address and actual size of the space.



126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# 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) ⇒ Boolean

Check if there is a space in the free space lists that matches the address and the size.

Parameters:

  • address (Integer) —

    Address of the space

  • size (Integer) —

    Length of the space in bytes

Returns:

  • (Boolean) —

    True if space is found, false otherwise



160
161
162
 
# File 'lib/perobs/SpaceTree.rb', line 160

def has_space?(address, size)
  root.has_space?(address, size)
end

#is_open? ⇒ Boolean

Returns true if file is currently open.

Returns:

  • (Boolean) —

    true if file is currently open.



79
80
81
 
# File 'lib/perobs/SpaceTree.rb', line 79

def is_open?
  !@root_address.nil?
end

#open ⇒ Object

Open the SpaceTree file.



61
62
63
64
65
66
67
68
 
# 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 ⇒ Object

Return the SpaceTreeNode that is the root of the SpaceTree.



97
98
99
 
# File 'lib/perobs/SpaceTree.rb', line 97

def root
  @root_address ? @cache.get(@root_address) : nil
end

#set_root(node) ⇒ Object

Set a new root node for the SpaceTree

Parameters:



91
92
93
94
 
# File 'lib/perobs/SpaceTree.rb', line 91

def set_root(node)
  @root_address = node.node_address
  @nodes.first_entry = node.node_address
end

#sync ⇒ Object

Flush all pending writes to the file system.



84
85
86
87
 
# File 'lib/perobs/SpaceTree.rb', line 84

def sync
  @cache.flush(true)
  @nodes.sync
end

#to_a ⇒ Array

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

Returns:



190
191
192
 
# File 'lib/perobs/SpaceTree.rb', line 190

def to_a
  root.to_a
end

#to_s ⇒ String

Complete internal tree data structure as textual tree.

Returns:

  • (String) 


184
185
186
 
# File 'lib/perobs/SpaceTree.rb', line 184

def to_s
  root.to_tree_s
end