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.



46
47
48
49
50
51
52
53
 
# File 'lib/perobs/BigTree.rb', line 46

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



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/perobs/BigTree.rb', line 162

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

  i = 0
  each do |k, v|
    i += 1
  end

  unless @entry_counter == i
    PEROBS.log.error "BigTree contains #{i} values but entry counter " \
                     "is #{@entry_counter}"
    return false
  end

  true
end

#clear ⇒ Object

Remove all entries from the BigTree.



56
57
58
59
60
 
# File 'lib/perobs/BigTree.rb', line 56

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) 


114
115
116
117
118
119
120
 
# File 'lib/perobs/BigTree.rb', line 114

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

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

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

Yields:

  • (key, value) 


135
136
137
138
139
140
141
142
 
# File 'lib/perobs/BigTree.rb', line 135

def each(&block)
  node = @first_leaf
  while node
    break if node.each_element(&block).nil?

    node = node.next_sibling
  end
end

#empty? ⇒ Boolean

Return true if the BigTree has no stored entries.

Returns:

  • (Boolean) 


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

def empty?
  @entry_counter.zero?
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



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

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.



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

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



66
67
68
69
70
 
# File 'lib/perobs/BigTree.rb', line 66

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.



123
124
125
 
# File 'lib/perobs/BigTree.rb', line 123

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:



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

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



99
100
101
102
103
104
105
106
107
 
# File 'lib/perobs/BigTree.rb', line 99

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) 


147
148
149
150
151
152
153
 
# File 'lib/perobs/BigTree.rb', line 147

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



181
182
183
184
185
 
# File 'lib/perobs/BigTree.rb', line 181

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.



156
157
158
 
# File 'lib/perobs/BigTree.rb', line 156

def to_s
  @root.to_s
end