Class: PEROBS::BTreeNode

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

Overview

The BTreeNode class manages more or less standard BTree nodes. All nodes contain BTree.order number of keys. Leaf node contain BTree.order number of values and no child references. Branch nodes only contain BTree.order + 1 number of child references but no values. The is_leaf flag is used to mark a node as leaf or branch node.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, parent = nil, node_address = nil, is_leaf = true) ⇒ BTreeNode

Create a new BTreeNode object for the given tree with the given parent or recreate the node with the given node_address from the backing store. If node_address is nil a new node will be created. If not, node_address must be an existing address that can be found in the backing store to restore the node.

Parameters:

  • tree (BTree) —

    The tree this node is part of

  • parent (BTreeNode) (defaults to: nil) —

    reference to parent node

  • node_address (Integer) (defaults to: nil) —

    the address of the node to read from the backing store

  • is_leaf (Boolean) (defaults to: true) —

    true if the node should be a leaf node, false if not



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/perobs/BTreeNode.rb', line 56

def initialize(tree, parent = nil, node_address = nil, is_leaf = true)
  @tree = tree
  @parent = nil
  if node_address == 0
    PEROBS.log.fatal "Node address may not be 0"
  end
  @node_address = node_address
  @keys = []
  if (@is_leaf = is_leaf)
    @values = []
  else
    @children = []
  end

  if node_address
    unless node_address.is_a?(Integer)
      PEROBS.log.fatal "node_address is not Integer: #{node_address.class}"
    end

    # This must be an existing node. Try to read it and fill the instance
    # variables.
    unless read_node
      PEROBS.log.fatal "SpaceTree node at address #{node_address} " +
        "does not exist"
    end
  else
    unless parent.nil? || parent.is_a?(BTreeNode) ||
           parent.is_a?(BTreeNodeLink)
      PEROBS.log.fatal "Parent node must be a BTreeNode but is of class " +
        "#{parent.class}"
    end

    # This is a new node. Make sure the data is written to the file.
    @node_address = @tree.nodes.free_address
    self.parent = parent
  end
end

Instance Attribute Details

#children ⇒ Object (readonly)

Returns the value of attribute children.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def children
  @children
end

#dirty ⇒ Object

Returns the value of attribute dirty.



43
44
45
 
# File 'lib/perobs/BTreeNode.rb', line 43

def dirty
  @dirty
end

#is_leaf ⇒ Object (readonly)

Returns the value of attribute is_leaf.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def is_leaf
  @is_leaf
end

#keys ⇒ Object (readonly)

Returns the value of attribute keys.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def keys
  @keys
end

#node_address ⇒ Object (readonly)

Returns the value of attribute node_address.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def node_address
  @node_address
end

#parent ⇒ Object

Returns the value of attribute parent.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def parent
  @parent
end

#values ⇒ Object (readonly)

Returns the value of attribute values.



42
43
44
 
# File 'lib/perobs/BTreeNode.rb', line 42

def values
  @values
end

Class Method Details

.node_bytes(order) ⇒ Object 



94
95
96
97
98
99
100
101
102
 
# File 'lib/perobs/BTreeNode.rb', line 94

def BTreeNode::node_bytes(order)
  1 + # is_leaf
  2 + # actual key count
  2 + # actual value or children count (aka data count)
  8 + # parent address
  8 * order + # keys
  8 * (order + 1) + # values or child addresses
  4 # CRC32 checksum
end

Instance Method Details

#check {|key, value| ... } ⇒ Boolean

Check consistency of the node and all subsequent nodes. In case an error is found, a message is logged and false is returned.

Yields:

  • (key, value)

Returns:

  • (Boolean) —

    true if tree has no errors



430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
 
# File 'lib/perobs/BTreeNode.rb', line 430

def check
  traverse do |node, position, stack|
    if position == 0
      if node.parent && node.keys.size < 1
        node.error "BTreeNode must have at least one entry"
        return false
      end
      if node.keys.size > @tree.order
        node.error "BTreeNode must not have more then #{@tree.order} " +
          "keys, but has #{node.keys.size} keys"
      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}"
          return false
        end
      end

      if node.is_leaf
        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
        end
      else
        unless node.keys.size == node.children.size - 1
          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?(BTreeNodeLink)
            node.error "Child #{i} is of class #{child.class} " +
              "instead of BTreeNodeLink"
            return false
          end
          unless child.parent.is_a?(BTreeNodeLink)
            node.error "Parent reference of child #{i} is of class " +
              "#{child.class} instead of BTreeNodeLink"
            return false
          end
          if child.node_address == node.node_address
            node.error "Child #{i} points to self"
            return false
          end
          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"
            return false
          end
        end
      end
    elsif position <= node.keys.size
      # These checks are done after we have completed the respective child
      # node with index 'position - 1'.
      index = position - 1
      if !node.is_leaf
        unless node.children[index].keys.last < node.keys[index]
          node.error "Child #{node.children[index].node_address} " +
            "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].node_address} " +
            "has too small key #{node.children[position].keys.first}. " +
            "Must be larger than or equal to #{node.keys[index]}."
          return false
        end
      else
        if block_given?
          # If a block was given, call this block with the key and value.
          return false unless yield(node.keys[index], node.values[index])
        end
      end
    end
  end

  true
end

#copy_elements(src_idx, dest_node, dst_idx = 0, count = nil) ⇒ Object 



291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
# File 'lib/perobs/BTreeNode.rb', line 291

def copy_elements(src_idx, dest_node, dst_idx = 0, count = nil)
  unless count
    count = @tree.order - src_idx
  end
  if dst_idx + count > @tree.order
    PEROBS.log.fatal "Destination too small for copy operation"
  end
  if dest_node.is_leaf != @is_leaf
    PEROBS.log.fatal "Source #{@is_leaf} and destination " +
      "#{dest_node.is_leaf} node must be of same kind"
  end

  dest_node.keys[dst_idx, count] = @keys[src_idx, count]
  dest_node.dirty = true
  if @is_leaf
    # For leaves we copy the keys and corresponding values.
    dest_node.values[dst_idx, count] = @values[src_idx, count]
  else
    # For branch nodes we copy all but the first specified key (that
    # one moved up to the parent) and all the children to the right of the
    # moved-up key.
    (count + 1).times do |i|
      dest_node.set_child(dst_idx + i, @children[src_idx + i])
    end
  end
end

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

Iterate over all the key/value pairs in this node and all sub-nodes.

Yields:

  • (key, value) 


383
384
385
386
387
388
389
 
# File 'lib/perobs/BTreeNode.rb', line 383

def each
  traverse do |node, position, stack|
    if node.is_leaf && position < node.keys.size
      yield(node.keys[position], node.values[position])
    end
  end
end

#error(msg) ⇒ Object 



595
596
597
598
 
# File 'lib/perobs/BTreeNode.rb', line 595

def error(msg)
  PEROBS.log.error "Error in BTreeNode @#{@node_address}: #{msg}\n" +
    @tree.to_s
end

#get(key) ⇒ Integer or nil

Return the value that matches the given key or return nil if they key is unknown.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer or nil) —

    value that matches the key



135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/perobs/BTreeNode.rb', line 135

def get(key)
  node = self

  while node do
    # 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.
      return node.keys[i] == key ? node.values[i] : nil
    end

    # 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}"
end

#insert(key, value) ⇒ Object

Insert or replace the given value by using the key as unique address.

Parameters:

  • key (Integer) —

    Unique key to retrieve the value

  • value (Integer) —

    value to insert



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/perobs/BTreeNode.rb', line 107

def insert(key, value)
  node = self

  # Traverse the tree to find the right node to add or replace the value.
  while node do
    # All nodes that we find on the way that are full will be split into
    # two half-full nodes.
    if node.keys.size >= @tree.order
      node = node.split_node
    end

    # Once we have reached a leaf node we can insert or replace the value.
    if node.is_leaf
      node.insert_element(key, value)
      return
    else
      # Descend into the right child node to add the value to.
      node = node.children[node.search_key_index(key)]
    end
  end

  PEROBS.log.fatal 'Could not find proper node to add to'
end

#insert_element(key, value_or_child) ⇒ Object

Insert the given value or child into the current node using the key as index.

Parameters:

  • key (Integer) —

    key to address the value or child

  • value_or_child (Integer or BTreeNode) —

    value or BTreeNode reference



227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/perobs/BTreeNode.rb', line 227

def insert_element(key, value_or_child)
  if @keys.size >= @tree.order
    PEROBS.log.fatal "Cannot insert into a full BTreeNode"
  end

  mark_as_modified
  i = search_key_index(key)
  if @keys[i] == key
    # Overwrite existing entries
    @keys[i] = key
    if is_leaf
      @values[i] = value_or_child
    else
      @children[i + 1] = BTreeNodeLink.new(@tree, value_or_child)
    end
  else
    # Create a new entry
    @keys.insert(i, key)
    if is_leaf
      @values.insert(i, value_or_child)
    else
      @children.insert(i + 1, BTreeNodeLink.new(@tree, value_or_child))
    end
  end
end

#is_top? ⇒ Boolean

Returns:

  • (Boolean) 


519
520
521
 
# File 'lib/perobs/BTreeNode.rb', line 519

def is_top?
  @parent.nil? || @parent.parent.nil? || @parent.parent.parent.nil?
end

#mark_as_modified ⇒ Object 



629
630
631
632
 
# File 'lib/perobs/BTreeNode.rb', line 629

def mark_as_modified
  @tree.mark_node_as_modified(self)
  @dirty = true
end

#merge_node(upper_sibling, parent_index) ⇒ Object 



209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/perobs/BTreeNode.rb', line 209

def merge_node(upper_sibling, parent_index)
  if upper_sibling == self
    PEROBS.log.fatal "Cannot merge node @#{@node_address} with self"
  end
  unless upper_sibling.is_leaf
    insert_element(@parent.keys[parent_index], upper_sibling.children[0])
  end
  upper_sibling.copy_elements(0, self, @keys.size, upper_sibling.keys.size)
  @tree.delete_node(upper_sibling.node_address)

  @parent.remove_element(parent_index)
end

#remove(key) ⇒ Integer or nil

Return the value that matches the given key and remove the value from the tree. Return nil if the key is unknown.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer or nil) —

    value that matches the key



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/perobs/BTreeNode.rb', line 159

def remove(key)
  node = self

  while node do
    # 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
        return node.remove_element(i)
      else
        return nil
      end
    end

    # Descend into the right child node to continue the search.
    node = node.children[i]
  end

  PEROBS.log.fatal 'Could not find proper node to remove from'
end

#remove_element(index) ⇒ Object

Remove the element at the given index.



254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
 
# File 'lib/perobs/BTreeNode.rb', line 254

def remove_element(index)
  # We need this key to find the link in the parent node.
  first_key = @keys[0]
  removed_value = nil

  mark_as_modified
  # Delete the key at the specified index.
  unless @keys.delete_at(index)
    PEROBS.log.fatal "Could not remove element #{index} from BTreeNode " +
      "@#{@node_address}"
  end
  if @is_leaf
    # For leaf nodes, also delete the corresponding value.
    removed_value = @values.delete_at(index)
  else
    # The corresponding child has can be found at 1 index higher.
    @children.delete_at(index + 1)
  end

  # Find the lower and upper siblings and the index of the key for this
  # node in the parent node.
  lower_sibling, upper_sibling, parent_index =
    find_closest_siblings(first_key)

  if lower_sibling &&
     lower_sibling.keys.size + @keys.size < @tree.order
    lower_sibling.merge_node(self, parent_index - 1)
  elsif upper_sibling &&
        @keys.size + upper_sibling.keys.size < @tree.order
    merge_node(upper_sibling, parent_index)
  end

  # The merge has potentially invalidated this node. After this method has
  # been called this copy of the node should no longer be used.
  removed_value
end

#search_key_index(key) ⇒ Integer

Search the keys of the node that fits the given key. The result is either the index of an exact match or the index of the position where the given key would have to be inserted.

Parameters:

  • key (Integer) —

    key to search for

Returns:

  • (Integer) —

    Index of the matching key or the insert position.



348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
 
# File 'lib/perobs/BTreeNode.rb', line 348

def search_key_index(key)
  # Handle special case for empty keys list.
  return 0 if @keys.empty?

  # Keys are unique and always sorted. Use a binary search to find the
  # index that fits the given key.
  li = pi = 0
  ui = @keys.size - 1
  while li <= ui
    # The pivot element is always in the middle between the lower and upper
    # index.
    pi = li + (ui - li) / 2

    if key < @keys[pi]
      # The pivot element is smaller than the key. Set the upper index to
      # the pivot index.
      ui = pi - 1
    elsif key > @keys[pi]
      # The pivot element is larger than the key. Set the lower index to
      # the pivot index.
      li = pi + 1
    else
      # We've found an exact match. For leaf nodes return the found index.
      # For branch nodes we have to add one to the index since the larger
      # child is the right one.
      return @is_leaf ? pi : pi + 1
    end
  end
  # No exact match was found. For the insert operaton we need to return
  # the index of the first key that is larger than the given key.
  @keys[pi] < key ? pi + 1 : pi
end

#set_child(index, child) ⇒ Object 



323
324
325
326
327
328
329
330
331
 
# File 'lib/perobs/BTreeNode.rb', line 323

def set_child(index, child)
  if child
    @children[index] = BTreeNodeLink.new(@tree, child)
    @children[index].parent = self
  else
    @children[index] = nil
  end
  mark_as_modified
end

#split_node ⇒ BTreeNodeLink

Split the current node into two nodes. The upper half of the elements will be moved into a newly created node. This node will retain the lower half.

Returns:



186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
# File 'lib/perobs/BTreeNode.rb', line 186

def split_node
  unless @parent
    # The node is the root node. We need to create a parent node first.
    self.parent = @tree.new_node(nil, nil, false)
    @parent.set_child(0, self)
    @tree.set_root(@parent)
  end

  # Create the new sibling that will take the 2nd half of the
  # node content.
  sibling = @tree.new_node(@parent, nil, @is_leaf)
  # Determine the index of the middle element that gets moved to the
  # parent. The order must be an uneven number, so adding 1 will get us
  # the middle element.
  mid = @tree.order / 2 + 1
  # Insert the middle element key into the parent node
  @parent.insert_element(@keys[mid], sibling)
  copy_elements(mid + (@is_leaf ? 0 : 1), sibling)
  trim(mid)

  @parent
end

#to_s ⇒ Object 



523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
 
# File 'lib/perobs/BTreeNode.rb', line 523

def to_s
  str = ''

  traverse do |node, position, stack|
    if position == 0
      begin
        str += "#{node.parent ? node.parent.tree_prefix + '  +' : 'o'}" +
          "#{node.tree_branch_mark}-" +
          "#{node.keys.first.nil? ? '--' : 'v-'}#{node.tree_summary}\n"
      rescue
        str += "@@@@@@@@@@\n"
      end
    else
      begin
        if node.is_leaf
          if 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
        end
      rescue
        str += "@@@@@@@@@@\n"
      end
    end
  end

  str
end

#traverse {|node, position, stack| ... } ⇒ Object

This is a generic tree iterator. It yields before it descends into the child node and after (which is identical to before the next child descend). It yields the node, the position and the stack of parent nodes.

Yields:

  • (node, position, stack) 


396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
 
# File 'lib/perobs/BTreeNode.rb', line 396

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 ] ]

  while !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.
    # Position 1 is after the 1st child has been processed and before the
    # 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 <= @tree.order
      # 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
end

#tree_branch_mark ⇒ Object 



577
578
579
580
 
# File 'lib/perobs/BTreeNode.rb', line 577

def tree_branch_mark
  return '' unless @parent
  '-'
end

#tree_prefix ⇒ Object 



557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
 
# File 'lib/perobs/BTreeNode.rb', line 557

def tree_prefix
  node = self
  str = ''

  while node
    is_last_child = false
    if node.parent
      is_last_child = node.parent.children.last == node
    else
      # Don't add lines for the top-level.
      break
    end

    str = (is_last_child ? '   ' : '  |') + str
    node = node.parent
  end

  str
end

#tree_summary ⇒ Object 



582
583
584
585
586
587
588
589
590
591
592
593
 
# File 'lib/perobs/BTreeNode.rb', line 582

def tree_summary
  s = " @#{@node_address}"
  if @parent
    begin
      s += " ^#{@parent.node_address}"
    rescue
      s += ' ^@'
    end
  end

  s
end

#trim(idx) ⇒ Object 



333
334
335
336
337
338
339
340
341
 
# File 'lib/perobs/BTreeNode.rb', line 333

def trim(idx)
  mark_as_modified
  @keys = @keys[0..idx - 1]
  if @is_leaf
    @values = @values[0..idx - 1]
  else
    @children = @children[0..idx]
  end
end

#write_node ⇒ Object 



600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
 
# File 'lib/perobs/BTreeNode.rb', line 600

def write_node
  return unless @dirty

  ary = [
    @is_leaf ? 1 : 0,
    @keys.size,
    @is_leaf ? @values.size : @children.size,
    @parent ? @parent.node_address : 0
  ] + @keys + ::Array.new(@tree.order - @keys.size, 0)

  if @is_leaf
    ary += @values + ::Array.new(@tree.order + 1 - @values.size, 0)
  else
    if @children.size != @keys.size + 1
      PEROBS.log.fatal "write_node: Children count #{@children.size} " +
        "is not #{@keys.size + 1}"
    end
    @children.each do |child|
      PEROBS.log.fatal "write_node: Child must not be nil" unless child
    end
    ary += @children.map{ |c| c.node_address } +
      ::Array.new(@tree.order + 1 - @children.size, 0)
  end
  bytes = ary.pack(node_bytes_format)
  bytes += [ Zlib::crc32(bytes) ].pack('L')
  @tree.nodes.store_blob(@node_address, bytes)
  @dirty = false
end