lib/perobs/BigTreeNode.rb in perobs-4.5.0 vs lib/perobs/BigTreeNode.rb in perobs-4.6.0
- old
+ new
@@ -1,7 +1,7 @@
-# encoding: UTF-8
-#
+# frozen_string_literal: true
+
# = BigTreeNode.rb -- Persistent Ruby Object Store
#
# Copyright (c) 2016, 2017 by Chris Schlaeger <chris@taskjuggler.org>
#
# MIT License
@@ -23,26 +23,24 @@
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-require 'perobs/Object'
-require 'perobs/Array'
+require_relative 'Object'
+require_relative 'Array'
module PEROBS
-
# The BigTreeNode class provides the BTree nodes for the BigTree objects.
# A node can either be a branch node or a leaf node. Branch nodes don't
# store values, only references to child nodes. Leaf nodes don't have child
# nodes but store the actual values. All nodes store a list of keys that are
# used to naviate the tree and find the values. A key is either directly
# associated with a value or determines the lower key boundary for the
# following child node.
class BigTreeNode < PEROBS::Object
-
attr_persist :tree, :parent, :keys, :values, :children,
- :prev_sibling, :next_sibling
+ :prev_sibling, :next_sibling
# Internal constructor. Use Store.new(BigTreeNode, ...) instead.
# @param p [Handle]
# @param tree [BigTree] The tree this node should belong to
# @param is_leaf [Boolean] True if a leaf node should be created, false
@@ -92,37 +90,33 @@
# @param value [Integer] value to insert
def insert(key, value)
node = myself
# Traverse the tree to find the right node to add or replace the value.
- while node do
+ while node
# All nodes that we find on the way that are full will be split into
# two half-full nodes.
- if node.keys.size >= @tree.node_size
- node = node.split_node
- end
+ node = node.split_node if node.keys.size >= @tree.node_size
# Once we have reached a leaf node we can insert or replace the value.
- if node.is_leaf?
- return node.insert_element(key, value)
- else
- # Descend into the right child node to add the value to.
- node = node.children[node.search_key_index(key)]
- end
+ return node.insert_element(key, value) if node.is_leaf?
+
+ # Descend into the right child node to add the value to.
+ node = node.children[node.search_key_index(key)]
end
- PEROBS.log.fatal "Could not find proper node to insert into"
+ PEROBS.log.fatal 'Could not find proper node to insert into'
end
# Return the value that matches the given key or return nil if they key is
# unknown.
# @param key [Integer] key to search for
# @return [Integer or nil] value that matches the key
def get(key)
node = self
- while node do
+ while node
# Find index of the entry that best fits the key.
i = node.search_key_index(key)
if node.is_leaf?
# This is a leaf node. Check if there is an exact match for the
# given key and return the corresponding value or nil.
@@ -131,23 +125,23 @@
# Descend into the right child node to continue the search.
node = node.children[i]
end
- PEROBS.log.fatal "Could not find proper node to get from while " +
- "looking for key #{key}"
+ PEROBS.log.fatal 'Could not find proper node to get from while ' \
+ "looking for key #{key}"
end
# Return the node chain from the root to the leaf node storing the
# key/value pair.
# @param key [Integer] key to search for
# @return [Array of BigTreeNode] node list (may be empty)
def node_chain(key)
node = myself
- list = [ node ]
+ list = [node]
- while node do
+ while node
# Find index of the entry that best fits the key.
i = node.search_key_index(key)
if node.is_leaf?
# This is a leaf node. Check if there is an exact match for the
# given key and return the corresponding value or nil.
@@ -167,11 +161,11 @@
# @param key [Integer] key to search for
# @return [Boolean] True if key was found, false otherwise
def has_key?(key)
node = self
- while node do
+ while node
# Find index of the entry that best fits the key.
i = node.search_key_index(key)
if node.is_leaf?
# This is a leaf node. Check if there is an exact match for the
# given key and return the corresponding value or nil.
@@ -180,33 +174,31 @@
# Descend into the right child node to continue the search.
node = node.children[i]
end
- PEROBS.log.fatal "Could not find proper node to get from while " +
- "looking for key #{key}"
+ PEROBS.log.fatal 'Could not find proper node to get from while ' \
+ "looking for key #{key}"
end
# Return the value that matches the given key and remove the value from
# the tree. Return nil if the key is unknown.
# @param key [Integer] key to search for
# @return [Object] value that matches the key
def remove(key)
node = self
- while node do
+ while node
# Find index of the entry that best fits the key.
i = node.search_key_index(key)
if node.is_leaf?
# This is a leaf node. Check if there is an exact match for the
# given key and return the corresponding value or nil.
- if node.keys[i] == key
- @tree.entry_counter -= 1
- return node.remove_element(i)
- else
- return nil
- end
+ return nil if node.keys[i] != key
+
+ @tree.entry_counter -= 1
+ return node.remove_element(i)
end
# Descend into the right child node to continue the search.
node = node.children[i]
end
@@ -215,14 +207,13 @@
end
# Iterate over all the key/value pairs in this node and all sub-nodes.
# @yield [key, value]
def each
- traverse do |node, position, stack|
- if node.is_leaf? && position < node.keys.size
+ traverse do |node, position, _|
+ node.is_leaf? && position < node.keys.size &&
yield(node.keys[position], node.values[position])
- end
end
end
# Iterate over all the key/value pairs of the node.
# @yield [key, value]
@@ -250,11 +241,11 @@
# @return [Boolean] true if tree has no errors
def check
branch_depth = nil
traverse do |node, position, stack|
- if position == 0
+ if position.zero?
if node.parent
# After a split the nodes will only have half the maximum keys.
# For branch nodes one of the split nodes will have even 1 key
# less as this will become the branch key in a parent node.
if node.keys.size < min_keys - (node.is_leaf? ? 0 : 1)
@@ -262,84 +253,84 @@
return false
end
end
if node.keys.size > @tree.node_size
- node.error "BigTree node must not have more then " +
- "#{@tree.node_size} keys, but has #{node.keys.size} keys"
+ node.error 'BigTree node must not have more then ' \
+ "#{@tree.node_size} keys, but has #{node.keys.size} keys"
return false
end
last_key = nil
node.keys.each do |key|
if last_key && key < last_key
- node.error "Keys are not increasing monotoneously: " +
- "#{node.keys.inspect}"
+ node.error 'Keys are not increasing monotoneously: ' \
+ "#{node.keys.inspect}"
return false
end
last_key = key
end
if node.is_leaf?
if branch_depth
unless branch_depth == stack.size
- node.error "All leaf nodes must have same distance from root"
+ node.error 'All leaf nodes must have same distance from root'
return false
end
else
branch_depth = stack.size
end
if node.prev_sibling.nil?
if @tree.first_leaf != node
- node.error "Leaf node #{node._id} has no previous sibling " +
- "but is not the first leaf of the tree"
+ node.error "Leaf node #{node._id} has no previous sibling " \
+ 'but is not the first leaf of the tree'
return false
end
elsif node.prev_sibling.next_sibling != node
- node.error "next_sibling of previous sibling does not point to " +
- "this node"
+ node.error 'next_sibling of previous sibling does not point to ' \
+ 'this node'
return false
end
if node.next_sibling.nil?
if @tree.last_leaf != node
- node.error "Leaf node #{node._id} has no next sibling " +
- "but is not the last leaf of the tree"
+ node.error "Leaf node #{node._id} has no next sibling " \
+ 'but is not the last leaf of the tree'
return false
end
elsif node.next_sibling.prev_sibling != node
- node.error "previous_sibling of next sibling does not point to " +
- "this node"
+ node.error 'previous_sibling of next sibling does not point to ' \
+ 'this node'
return false
end
unless node.keys.size == node.values.size
- node.error "Key count (#{node.keys.size}) and value " +
- "count (#{node.values.size}) don't match"
- return false
+ node.error "Key count (#{node.keys.size}) and value " \
+ "count (#{node.values.size}) don't match"
+ return false
end
if node.children
- node.error "children must be nil for a leaf node"
+ node.error 'children must be nil for a leaf node'
return false
end
else
if node.values
- node.error "values must be nil for a branch node"
+ node.error 'values must be nil for a branch node'
return false
end
unless node.children.size == node.keys.size + 1
- node.error "Key count (#{node.keys.size}) must be one " +
- "less than children count (#{node.children.size})"
- return false
+ node.error "Key count (#{node.keys.size}) must be one " \
+ "less than children count (#{node.children.size})"
+ return false
end
node.children.each_with_index do |child, i|
unless child.is_a?(BigTreeNode)
- node.error "Child #{i} is of class #{child.class} " +
- "instead of BigTreeNode"
+ node.error "Child #{i} is of class #{child.class} " \
+ 'instead of BigTreeNode'
return false
end
unless child.parent.is_a?(BigTreeNode)
- node.error "Parent reference of child #{i} is of class " +
- "#{child.class} instead of BigTreeNode"
+ node.error "Parent reference of child #{i} is of class " \
+ "#{child.class} instead of BigTreeNode"
return false
end
if child == node
node.error "Child #{i} point to self"
return false
@@ -347,29 +338,26 @@
if stack.include?(child)
node.error "Child #{i} points to ancester node"
return false
end
unless child.parent == node
- node.error "Child #{i} does not have parent pointing " +
- "to this node"
+ node.error "Child #{i} does not have parent pointing " \
+ 'to this node'
return false
end
- if i > 0
- unless node.children[i - 1].next_sibling == child
- node.error "next_sibling of node " +
- "#{node.children[i - 1]._id} " +
- "must point to node #{child._id}"
- return false
- end
+ if i.positive? && node.children[i - 1].next_sibling != child
+ node.error 'next_sibling of node ' \
+ "#{node.children[i - 1]._id} " \
+ "must point to node #{child._id}"
+ return false
end
- if i < node.children.length - 1
- unless child == node.children[i + 1].prev_sibling
- node.error "prev_sibling of node " +
- "#{node.children[i + 1]._id} " +
- "must point to node #{child._id}"
- return false
- end
+ if i < node.children.length - 1 &&
+ child != node.children[i + 1].prev_sibling
+ node.error 'prev_sibling of node ' \
+ "#{node.children[i + 1]._id} " \
+ "must point to node #{child._id}"
+ return false
end
end
end
elsif position <= node.keys.size
# These checks are done after we have completed the respective child
@@ -380,19 +368,19 @@
# If a block was given, call this block with the key and value.
return false unless yield(node.keys[index], node.values[index])
end
else
unless node.children[index].keys.last < node.keys[index]
- node.error "Child #{node.children[index]._id} " +
- "has too large key #{node.children[index].keys.last}. " +
- "Must be smaller than #{node.keys[index]}."
+ node.error "Child #{node.children[index]._id} " \
+ "has too large key #{node.children[index].keys.last}. " \
+ "Must be smaller than #{node.keys[index]}."
return false
end
unless node.children[position].keys.first >= node.keys[index]
- node.error "Child #{node.children[position]._id} " +
- "has too small key #{node.children[position].keys.first}. " +
- "Must be larger than or equal to #{node.keys[index]}."
+ node.error "Child #{node.children[position]._id} " \
+ "has too small key #{node.children[position].keys.first}. " \
+ "Must be larger than or equal to #{node.keys[index]}."
return false
end
end
end
end
@@ -402,31 +390,29 @@
# @return [String] Human reable form of the sub-tree.
def to_s
str = ''
- traverse do |node, position, stack|
- if position == 0
+ traverse do |node, position, _|
+ if position.zero?
begin
- str += "#{node.parent ? node.parent.tree_prefix + ' +' : 'o'}" +
- "#{node.tree_branch_mark}-" +
- "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
+ str += "#{node.parent ? node.parent.tree_prefix + ' +' : 'o'}" \
+ "#{node.tree_branch_mark}-" \
+ "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
rescue => e
str += "@@@@@@@@@@: #{e.message}\n"
end
else
begin
if node.is_leaf?
if node.keys[position - 1]
- str += "#{node.tree_prefix} |" +
- "[#{node.keys[position - 1]}, " +
+ str += "#{node.tree_prefix} |" \
+ "[#{node.keys[position - 1]}, " \
"#{node.values[position - 1]}]\n"
end
- else
- if node.keys[position - 1]
- str += "#{node.tree_prefix} #{node.keys[position - 1]}\n"
- end
+ elsif node.keys[position - 1]
+ str += "#{node.tree_prefix} #{node.keys[position - 1]}\n"
end
rescue => e
str += "@@@@@@@@@@: #{e.message}\n"
end
end
@@ -516,14 +502,13 @@
# @param index [Integer] The index of the entry to be removed
# @return [Object] The removed value
def remove_element(index)
# Delete the key at the specified index.
unless (key = @keys.delete_at(index))
- PEROBS.log.fatal "Could not remove element #{index} from BigTreeNode " +
- "@#{@_id}"
+ PEROBS.log.fatal "Could not remove element #{index} from BigTreeNode @#{@_id}"
end
- update_branch_key(key) if index == 0
+ update_branch_key(key) if index.zero?
# Delete the corresponding value.
removed_value = @values.delete_at(index)
if @keys.length < min_keys
if @prev_sibling && @prev_sibling.parent == @parent
@@ -531,11 +516,11 @@
@prev_sibling.merge_with_leaf_node(myself)
elsif @next_sibling && @next_sibling.parent == @parent
borrow_from_next_sibling(@next_sibling) ||
merge_with_leaf_node(@next_sibling)
elsif @parent
- PEROBS.log.fatal "Cannot not find adjecent leaf siblings"
+ PEROBS.log.fatal 'Cannot not find adjecent leaf siblings'
end
end
# The merge has potentially invalidated this node. After this method has
# been called this copy of the node should no longer be used.
@@ -547,11 +532,11 @@
def remove_child(node)
unless (index = search_node_index(node))
PEROBS.log.fatal "Cannot remove child #{node._id} from node #{@_id}"
end
- if index == 0
+ if index.zero?
# Removing the first child is a bit more complicated as the
# corresponding branch key is in a parent node.
key = @keys.shift
update_branch_key(key)
else
@@ -590,22 +575,22 @@
end
end
def merge_with_leaf_node(node)
if @keys.length + node.keys.length > @tree.node_size
- PEROBS.log.fatal "Leaf nodes are too big to merge"
+ PEROBS.log.fatal 'Leaf nodes are too big to merge'
end
self.keys += node.keys
self.values += node.values
node.parent.remove_child(node)
end
def merge_with_branch_node(node)
if @keys.length + 1 + node.keys.length > @tree.node_size
- PEROBS.log.fatal "Branch nodes are too big to merge"
+ PEROBS.log.fatal 'Branch nodes are too big to merge'
end
index = @parent.search_node_index(node) - 1
self.keys << @parent.keys[index]
self.keys += node.keys
@@ -668,13 +653,13 @@
# nodes.
# @yield [node, position, stack]
def traverse
# We use a non-recursive implementation to traverse the tree. This stack
# keeps track of all the known still to be checked nodes.
- stack = [ [ self, 0 ] ]
+ stack = [[self, 0]]
- while !stack.empty?
+ until stack.empty?
node, position = stack.pop
# Call the payload method. The position marks where we are in the node
# with respect to the traversal. 0 means we've just entered the node
# for the first time and are about to descent to the first child.
@@ -682,37 +667,33 @@
# 2nd child is being processed. If we have N children, the last
# position is N after we have processed the last child and are about
# to return to the parent node.
yield(node, position, stack)
- if position <= node.keys.size
- # Push the next position for this node onto the stack.
- stack.push([ node, position + 1 ])
+ next unless position <= node.keys.size
- if !node.is_leaf? && node.children[position]
- # If we have a child node for this position, push the linked node
- # and the starting position onto the stack.
- stack.push([ node.children[position], 0 ])
- end
+ # Push the next position for this node onto the stack.
+ stack.push([node, position + 1])
+
+ if !node.is_leaf? && node.children[position]
+ # If we have a child node for this position, push the linked node
+ # and the starting position onto the stack.
+ stack.push([node.children[position], 0])
end
end
end
# Gather some statistics about the node and all sub nodes.
# @param stats [Stats] Data structure that stores the gathered data
def statistics(stats)
traverse do |node, position, stack|
- if position == 0
+ if position.zero?
if node.is_leaf?
stats.leaf_nodes += 1
depth = stack.size + 1
- if stats.min_depth.nil? || stats.min_depth < depth
- stats.min_depth = depth
- end
- if stats.max_depth.nil? || stats.max_depth > depth
- stats.max_depth = depth
- end
+ stats.min_depth = depth if stats.min_depth.nil? || stats.min_depth < depth
+ stats.max_depth = depth if stats.max_depth.nil? || stats.max_depth > depth
else
stats.branch_nodes += 1
end
end
end
@@ -741,10 +722,11 @@
end
# Branch node decoration for the inspection method.
def tree_branch_mark
return '' unless @parent
+
'-'
end
# Text for the node line for the inspection method.
def tree_summary
@@ -864,10 +846,7 @@
node = node.parent
end
# The smallest element has no branch key.
end
-
end
-
end
-