lib/perobs/BTreeNode.rb in perobs-4.2.0 vs lib/perobs/BTreeNode.rb in perobs-4.3.0

@@ -57,26 +57,26 @@
     #        backing store
     # @param is_leaf [Boolean] true if the node should be a leaf node, false
     #        if not
     def initialize(tree, node_address = nil, parent = nil, is_leaf = true,
                    prev_sibling = nil, next_sibling = nil,
-                   keys = [], values = [], children = [])
+                   keys = nil, values = nil, children = nil)
       @tree = tree
       if node_address == 0
         PEROBS.log.fatal "Node address may not be 0"
       end
       @node_address = node_address
       @parent = link(parent)
       @prev_sibling = link(prev_sibling)
       @next_sibling = link(next_sibling)
-      @keys = keys
+      @keys = keys || []
       if (@is_leaf = is_leaf)
-        @values = values
-        @children = []
+        @values = values || []
+        @children = nil
       else
-        @children = children
-        @values = []
+        @children = children || []
+        @values = nil
       end
     end
 
     # Create a new SpaceTreeNode. This method should be used for the creation
     # of new nodes instead of calling the constructor directly.
@@ -583,15 +583,15 @@
 
       child
     end
 
     def trim(idx)
-      @keys = @keys[0..idx - 1]
+      @keys.slice!(idx, @keys.length - idx)
       if @is_leaf
-        @values = @values[0..idx - 1]
+        @values.slice!(idx, @values.length - idx)
       else
-        @children = @children[0..idx]
+        @children.slice!(idx + 1, @children.length - idx - 1)
       end
       @tree.node_cache.insert(self)
     end
 
     # Search the keys of the node that fits the given key. The result is
@@ -652,17 +652,22 @@
     # Check consistency of the node and all subsequent nodes. In case an error
     # is found, a message is logged and false is returned.
     # @yield [key, value]
     # @return [nil or Hash] nil in case of errors or a hash with some
     #         statistical information about the tree
-    def check
+    def check(&block)
       stats = Stats.new(nil, 0, 0, 0)
 
       traverse do |node, position, stack|
         if position == 0
           stats.nodes_count += 1
           if node.parent
+            unless node.parent.is_a?(BTreeNodeLink)
+              node.error "parent is a #{node.parent.class} instead of a " +
+                "BTreeNodeLink"
+              return nil
+            end
             # 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)
               node.error "BTreeNode #{node.node_address} has too few keys"
@@ -693,10 +698,20 @@
                 return nil
               end
             else
               stats.branch_depth = node.tree_level
             end
+            if node.prev_sibling && !node.prev_sibling.is_a?(BTreeNodeLink)
+              node.error "prev_sibling is a #{node.prev_sibling.class} " +
+                "instead of a BTreeNodeLink"
+              return nil
+            end
+            if node.next_sibling && !node.next_sibling.is_a?(BTreeNodeLink)
+              node.error "next_sibling is a #{node.next_sibling.class} " +
+                "instead of a BTreeNodeLink"
+              return nil
+            end
             if node.prev_sibling.nil? && @tree.first_leaf != node
               node.error "Leaf node #{node.node_address} has no previous " +
                 "sibling but is not the first leaf of the tree"
               return nil
             end
@@ -706,28 +721,28 @@
               return nil
             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 nil
+              return nil
             end
-            unless node.children.empty?
+            unless node.children.nil?
               node.error "@children must be nil for a leaf node"
               return nil
             end
 
             stats.leave_nodes += 1
             stats.leaves += node.keys.length
           else
-            unless node.values.empty?
+            unless node.values.nil?
               node.error "@values must be nil for a branch node"
               return nil
             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 nil
+              return nil
             end
             node.children.each_with_index do |child, i|
               unless child.is_a?(BTreeNodeLink)
                 node.error "Child #{i} is of class #{child.class} " +
                   "instead of BTreeNodeLink"
@@ -787,10 +802,12 @@
               return nil
             end
           else
             if block_given?
               # If a block was given, call this block with the key and value.
-              return nil unless yield(node.keys[index], node.values[index])
+              unless yield(node.keys[index], node.values[index])
+                return nil
+              end
             end
           end
         end
       end