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

new(p, node_size = 150) click to toggle source

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.
Calls superclass method 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

<<(value) click to toggle source
# File lib/perobs/BigArray.rb, line 100
def <<(value)
  self[@entry_counter] = value
end
[](index) click to toggle source

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
[]=(index, value) click to toggle source

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(&block) click to toggle source

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
clear() click to toggle source

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_at(index) click to toggle source

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_if() { |k, v| ... } click to toggle source

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
each(&block) click to toggle source

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
empty?() click to toggle source

Return true if the BigArray has no stored entries.

# File lib/perobs/BigArray.rb, line 193
def empty?
  @entry_counter == 0
end
first() click to toggle source

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
has_key?(key) click to toggle source

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(index, value) click to toggle source

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
last() click to toggle source

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
length() click to toggle source

@return [Integer] The number of entries stored in the tree.

# File lib/perobs/BigArray.rb, line 186
def length
  @entry_counter
end
Also aliased as: size
reverse_each(&block) click to toggle source

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
size()
Alias for: length
statistics() click to toggle source

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
to_a() click to toggle source

Convert the BigArray into a Ruby Array. This is primarily intended for debugging as real-world BigArray objects are likely too big to fit into memory.

# File lib/perobs/BigArray.rb, line 236
def to_a
  ary = []
  node = @first_leaf
  while node do
    ary += node.values
    node = node.next_sibling
  end

  ary
end
to_s() click to toggle source

@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

validate_index_range(index) click to toggle source
# 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