Class: PEROBS::BigTree

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

Overview

The BigTree class implements a BTree as a PEROBS object. It allows to manage huge amounts of data in a reasonably efficient way. The number of entries is limited by the space on the backing store, not the main memory. Entries are addressed by a Integer key.

Defined Under Namespace

Classes: Stats

Constant Summary

Constants inherited from ObjectBase

ObjectBase::NATIVE_CLASSES

Instance Attribute Summary

Attributes inherited from Object

#attributes

Attributes inherited from ObjectBase

#_id, #myself, #store

Instance Method Summary collapse

Methods inherited from Object

#_delete_reference_to_id, #_deserialize, #_referenced_object_ids, #attr_init, attr_persist, #init_attr, #inspect, #mark_as_modified

Methods inherited from ObjectBase

#==, #_check_assignment_value, _finalize, #_initialize, #_restore, #_stash, #_sync, #_transfer, read, #restore

Constructor Details

#initialize(p, node_size = 127) ⇒ BigTree

Internal constructor. Use Store.new() instead.

Parameters:

  • p (Handle)
  • node_size (Integer) (defaults to: 127) —

    The size of the tree nodes. This determines how many entries must be read/written for each operation.



49
50
51
52
53
54
55
56
 
# File 'lib/perobs/BigTree.rb', line 49

def initialize(p, node_size = 127)
  super(p)
  unless node_size > 2
    PEROBS.log.fatal "Node size (#{node_size}) must be larger than 2"
  end
  attr_init(:node_size, node_size)
  clear unless instance_variable_defined?('@root')
end

Instance Method Details

#check(&block) ⇒ Boolean

Check if the tree file contains any errors.

Returns:

  • (Boolean) —

    true if no erros were found, false otherwise



167
168
169
 
# File 'lib/perobs/BigTree.rb', line 167

def check(&block)
  @root.check(&block)
end

#clear ⇒ Object

Remove all entries from the BigTree.



59
60
61
62
63
 
# File 'lib/perobs/BigTree.rb', line 59

def clear
  self.root = self.first_leaf = self.last_leaf =
    @store.new(BigTreeNode, myself, true)
  self.entry_counter = 0
end

#delete_if {|key, value| ... } ⇒ Object

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.

Yields:

  • (key, value) 


117
118
119
120
121
122
123
124
125
 
# File 'lib/perobs/BigTree.rb', line 117

def delete_if
  old_root = @root
  clear
  old_root.each do |k, v|
    if !yield(k, v)
      insert(k, v)
    end
  end
end

#each {|key, value| ... } ⇒ Object

Iterate over all entries in the tree. Entries are always sorted by the key.

Yields:

  • (key, value) 


140
141
142
143
144
145
146
 
# File 'lib/perobs/BigTree.rb', line 140

def each(&block)
  node = @first_leaf
  while node
    node.each_element(&block)
    node = node.next_sibling
  end
end

#empty? ⇒ Boolean

Return true if the BigTree has no stored entries.

Returns:

  • (Boolean) 


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

def empty?
  @entry_counter == 0
end

#get(key) ⇒ Integer or nil

Retrieve the value associated with the given key. If no entry was found, return nil.

Parameters:

  • key (Integer) —

    Unique key

Returns:

  • (Integer or nil) —

    found value or nil



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

def get(key)
  @root.get(key)
end

#has_key?(key) ⇒ Boolean

Check if there is an entry for the given key.

Parameters:

  • key (Integer) —

    Unique key

Returns:

  • (Boolean) —

    True if key is present, false otherwise.



94
95
96
 
# File 'lib/perobs/BigTree.rb', line 94

def has_key?(key)
  @root.has_key?(key)
end

#insert(key, value) ⇒ Object

Insert a new value into the tree using the key as a unique index. If the key already exists the old value will be overwritten.

Parameters:

  • key (Integer) —

    Unique key

  • value (Integer) —

    value



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

def insert(key, value)
  @store.transaction do
    @root.insert(key, value)
  end
end

#length ⇒ Integer

Returns The number of entries stored in the tree.

Returns:

  • (Integer) —

    The number of entries stored in the tree.



128
129
130
 
# File 'lib/perobs/BigTree.rb', line 128

def length
  @entry_counter
end

#node_chain(key) ⇒ Array of BigTreeNode

Return the node chain from the root to the leaf node storing the key/value pair.

Parameters:

  • key (Integer) —

    key to search for

Returns:



87
88
89
 
# File 'lib/perobs/BigTree.rb', line 87

def node_chain(key)
  @root.node_chain(key)
end

#remove(key) ⇒ Integer or nil

Find and remove the value associated with the given key. If no entry was found, return nil, otherwise the found value.

Parameters:

  • key (Integer) —

    Unique key

Returns:

  • (Integer or nil) —

    found value or nil



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

def remove(key)
  removed_value = nil

  @store.transaction do
    removed_value = @root.remove(key)
  end

  removed_value
end

#reverse_each {|key, value| ... } ⇒ Object

Iterate over all entries in the tree in reverse order. Entries are always sorted by the key.

Yields:

  • (key, value) 


151
152
153
154
155
156
157
 
# File 'lib/perobs/BigTree.rb', line 151

def reverse_each(&block)
  node = @last_leaf
  while node
    node.reverse_each_element(&block)
    node = node.prev_sibling
  end
end

#statistics ⇒ Stats

Gather some statistics regarding the tree structure.

Returns:

  • (Stats) —

    Structs with gathered data



173
174
175
176
177
 
# File 'lib/perobs/BigTree.rb', line 173

def statistics
  stats = Stats.new(0, 0, nil, nil)
  @root.statistics(stats)
  stats
end

#to_s ⇒ String

Returns Human reable form of the tree.

Returns:

  • (String) —

    Human reable form of the tree.



161
162
163
 
# File 'lib/perobs/BigTree.rb', line 161

def to_s
  @root.to_s
end