class PEROBS::BigArray
The BigArray
class implements an Array
that stores the data in segments. It only loads the currently needed parts of the Array
into memory. To provide an efficient access to the data by index a B+Tree like data structure is used. Each segment is stored in a leaf node of the B+Tree.
Public Class Methods
Internal constructor. Use Store.new()
instead. @param p [Handle] @param node_size [Integer] The size of the tree nodes. This determines
how many entries must be read/written for each operation. The default of 150 was emperically found to be a performance sweet spot. Smaller values will improve write operations. Larger values will improve read operations. 20 - 500 is a reasonable range to try.
PEROBS::Object::new
# File lib/perobs/BigArray.rb, line 54 def initialize(p, node_size = 150) super(p) unless node_size > 3 PEROBS.log.fatal "Node size (#{node_size}) must be larger than 3" end unless node_size % 2 == 0 PEROBS.log.fatal "Node size (#{node_size}) must be an even number" end self.node_size = node_size clear end
Public Instance Methods
# File lib/perobs/BigArray.rb, line 100 def <<(value) self[@entry_counter] = value end
Return the value stored at the given index. @param index [Integer] Position in the array @return [Integer or nil] found value or nil
# File lib/perobs/BigArray.rb, line 125 def [](index) begin index = validate_index_range(index) rescue IndexError return nil end return nil if index >= @entry_counter @root.get(index) end
Store
the value at the given index. If the index already exists the old value will be overwritten. @param index [Integer] Position in the array @param value [Integer] value
# File lib/perobs/BigArray.rb, line 78 def []=(index, value) index = validate_index_range(index) @store.transaction do if index < @entry_counter # Overwrite of an existing element @root.set(index, value) elsif index == @entry_counter # Append right at the end @root.insert(index, value) self.entry_counter += 1 else # Append with nil padding @entry_counter.upto(index - 1) do |i| @root.insert(i, nil) end @root.insert(index, value) self.entry_counter = index + 1 end end end
Check if the tree file contains any errors. @return [Boolean] true if no erros were found, false otherwise
# File lib/perobs/BigArray.rb, line 255 def check(&block) @root.check(&block) end
Remove all entries from the BigArray
.
# File lib/perobs/BigArray.rb, line 68 def clear self.root = self.first_leaf = self.last_leaf = @store.new(BigArrayNode, myself, true) self.entry_counter = 0 end
Delete the element at the specified index, returning that element, or nil if the index is out of range. @param index [Integer] Index in the BigArray
@return [Object] found value or nil
# File lib/perobs/BigArray.rb, line 148 def delete_at(index) if index < 0 index = @entry_counter + index end return nil if index < 0 || index >= @entry_counter deleted_value = nil @store.transaction do deleted_value = @root.delete_at(index) self.entry_counter -= 1 # Eliminate single entry nodes at the top. while !@root.is_leaf? && @root.size == 1 @root = @root.children.first @root.parent = nil end end deleted_value end
Delete all entries for which the passed block yields true. The implementation is optimized for large bulk deletes. It rebuilds a new BTree
for the elements to keep. If only few elements are deleted the overhead of rebuilding the BTree
is rather high. @yield [key, value]
# File lib/perobs/BigArray.rb, line 175 def delete_if old_root = @root clear old_root.each do |k, v| if !yield(k, v) insert(k, v) end end end
Iterate over all entries in the tree. Entries are always sorted by the key. @yield [key, value]
# File lib/perobs/BigArray.rb, line 214 def each(&block) node = @first_leaf while node break unless node.each(&block) node = node.next_sibling end end
Return true if the BigArray
has no stored entries.
# File lib/perobs/BigArray.rb, line 193 def empty? @entry_counter == 0 end
Return the first entry of the Array
.
# File lib/perobs/BigArray.rb, line 198 def first return nil unless @first_leaf @first_leaf.values.first end
Check if there is an entry for the given key. @param key [Integer] Unique key @return [Boolean] True if key is present, false otherwise.
# File lib/perobs/BigArray.rb, line 140 def has_key?(key) @root.has_key?(key) end
Insert the value at the given index. If the index already exists the old value will be overwritten. @param index [Integer] Position in the array @param value [Integer] value
# File lib/perobs/BigArray.rb, line 108 def insert(index, value) index = validate_index_range(index) if index < @entry_counter # Insert in between existing elements @store.transaction do @root.insert(index, value) self.entry_counter += 1 end else self[index] = value end end
Return the last entry of the Array
.
# File lib/perobs/BigArray.rb, line 205 def last return nil unless @last_leaf @last_leaf.values.last end
@return [Integer] The number of entries stored in the tree.
# File lib/perobs/BigArray.rb, line 186 def length @entry_counter end
Iterate over all entries in the tree in reverse order. Entries are always sorted by the key. @yield [key, value]
# File lib/perobs/BigArray.rb, line 225 def reverse_each(&block) node = @last_leaf while node break unless node.reverse_each(&block) node = node.prev_sibling end end
Gather some statistics regarding the tree structure. @return [Stats] Structs with gathered data
# File lib/perobs/BigArray.rb, line 261 def statistics stats = Stats.new(0, 0, nil, nil) @root.statistics(stats) stats end
@return [String] Human reable form of the tree. This is only intended for debugging and should only be used with small BigArray
objects.
# File lib/perobs/BigArray.rb, line 249 def to_s @root.to_s end
Private Instance Methods
# File lib/perobs/BigArray.rb, line 269 def validate_index_range(index) if index < 0 if -index > @entry_counter raise IndexError, "index #{index} too small for array; " + "minimum #{-@entry_counter}" end index = @entry_counter + index end index end