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) ⇒ 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
 
# File 'lib/perobs/SpaceTree.rb', line 47

def initialize(dir)
  @dir = dir

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

  @cache = SpaceTreeNodeCache.new(self, 128)
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

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



102
103
104
105
106
107
108
109
110
111
 
# File 'lib/perobs/SpaceTree.rb', line 102

def add_space(address, size)
  if size <= 0
    PEROBS.log.fatal "Size (#{size}) must be larger than 0."
  end
  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



157
158
159
160
 
# File 'lib/perobs/SpaceTree.rb', line 157

def check(flat_file = nil)
  @nodes.check
  root.check(flat_file)
end

#clear ⇒ Object

Clear all pools and forget any registered spaces.



139
140
141
142
143
 
# File 'lib/perobs/SpaceTree.rb', line 139

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

#close ⇒ Object

Close the SpaceTree file.



68
69
70
71
72
73
 
# File 'lib/perobs/SpaceTree.rb', line 68

def close
  @cache.flush
  @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



133
134
135
136
 
# File 'lib/perobs/SpaceTree.rb', line 133

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

#each ⇒ Object

Iterate over all entries and yield address and size.



163
164
165
166
167
168
169
 
# File 'lib/perobs/SpaceTree.rb', line 163

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.



95
96
97
 
# File 'lib/perobs/SpaceTree.rb', line 95

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.



116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/perobs/SpaceTree.rb', line 116

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



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

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

#open ⇒ Object

Open the SpaceTree file.



58
59
60
61
62
63
64
65
 
# File 'lib/perobs/SpaceTree.rb', line 58

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.



89
90
91
 
# File 'lib/perobs/SpaceTree.rb', line 89

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

#set_root(node) ⇒ Object

Set a new root node for the SpaceTree

Parameters:



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

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.



76
77
78
79
 
# File 'lib/perobs/SpaceTree.rb', line 76

def sync
  @cache.flush
  @nodes.sync
end

#to_a ⇒ Array

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

Returns:



179
180
181
 
# File 'lib/perobs/SpaceTree.rb', line 179

def to_a
  root.to_a
end

#to_s ⇒ String

Complete internal tree data structure as textual tree.

Returns:

  • (String) 


173
174
175
 
# File 'lib/perobs/SpaceTree.rb', line 173

def to_s
  root.to_tree_s
end