Class: PEROBS::SpaceTreeNode

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

Overview

The SpaceTree keeps a complete list of all empty spaces in the FlatFile. Spaces are stored with size and address. The Tree is Tenerary Tree. The nodes can link to other nodes with smaller spaces, same spaces and bigger spaces.

Constant Summary collapse

NODE_BYTES =

Each node can hold a reference to the parent, a lower, equal or larger size node and the actual value and the address in the FlatFile. Each of these entries is 8 bytes long.

6 * 8
NODE_BYTES_FORMAT =

The pack/unpack format.

'Q6'

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, node_address, blob_address = 0, size = 0, parent = nil, smaller = nil, equal = nil, larger = nil) ⇒ SpaceTreeNode

Create a new SpaceTreeNode object. If node_address is not nil, the data will be read from the SpaceTree file at the given node_address.



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/perobs/SpaceTreeNode.rb', line 61

def initialize(tree, node_address, blob_address = 0, size = 0,
               parent = nil, smaller = nil, equal = nil, larger = nil)
  @tree = tree
  if node_address <= 0
    PEROBS.log.fatal "Node address (#{node_address}) must be larger than 0"
  end
  @node_address = node_address
  if blob_address < 0
    PEROBS.log.fatal "Blob address (#{node_address}) must be larger than 0"
  end
  @blob_address = blob_address
  @size = size
  @parent = parent
  @smaller = smaller
  @equal = equal
  @larger = larger

  ObjectSpace.define_finalizer(
    self, SpaceTreeNode._finalize(@tree, @node_address))
  @tree.cache.insert_unmodified(self)
end

Instance Attribute Details

#blob_address ⇒ Object

Returns the value of attribute blob_address.



41
42
43
 
# File 'lib/perobs/SpaceTreeNode.rb', line 41

def blob_address
  @blob_address
end

#equal ⇒ Object (readonly)

Returns the value of attribute equal.



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

def equal
  @equal
end

#larger ⇒ Object (readonly)

Returns the value of attribute larger.



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

def larger
  @larger
end

#node_address ⇒ Object (readonly)

Returns the value of attribute node_address.



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

def node_address
  @node_address
end

#parent ⇒ Object

Returns the value of attribute parent.



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

def parent
  @parent
end

#size ⇒ Object

Returns the value of attribute size.



41
42
43
 
# File 'lib/perobs/SpaceTreeNode.rb', line 41

def size
  @size
end

#smaller ⇒ Object (readonly)

Returns the value of attribute smaller.



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

def smaller
  @smaller
end

Class Method Details

._finalize(tree, node_address) ⇒ Object

This method generates the destructor for the objects of this class. It is done this way to prevent the Proc object hanging on to a reference to self which would prevent the object from being collected. This internal method is not intended for users to call.



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

def SpaceTreeNode._finalize(tree, node_address)
  proc { tree.cache._collect(node_address) }
end

.create(tree, blob_address = 0, size = 0, parent = nil) ⇒ Object

Create a new SpaceTreeNode. This method should be used for the creation of new nodes instead of calling the constructor directly.



98
99
100
101
102
103
104
105
 
# File 'lib/perobs/SpaceTreeNode.rb', line 98

def SpaceTreeNode::create(tree, blob_address = 0, size = 0, parent = nil)
  node_address = tree.nodes.free_address

  node = SpaceTreeNode.new(tree, node_address, blob_address, size, parent)
  node.save

  node
end

.load(tree, node_address) ⇒ Object

Restore a node from the backing store at the given address and tree.



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/perobs/SpaceTreeNode.rb', line 110

def SpaceTreeNode::load(tree, node_address)
  unless node_address > 0
    PEROBS.log.fatal "node_address (#{node_address}) must be larger than 0"
  end
  unless (bytes = tree.nodes.retrieve_blob(node_address))
    PEROBS.log.fatal "SpaceTreeNode at address #{node_address} does " +
      "not exist"
  end

  blob_address, size, parent_node_address,
    smaller_node_address, equal_node_address,
    larger_node_address = bytes.unpack(NODE_BYTES_FORMAT)

  parent = parent_node_address != 0 ?
    SpaceTreeNodeLink.new(tree, parent_node_address) : nil
  smaller = smaller_node_address != 0 ?
    SpaceTreeNodeLink.new(tree, smaller_node_address) : nil
  equal = equal_node_address != 0 ?
    SpaceTreeNodeLink.new(tree, equal_node_address) : nil
  larger = larger_node_address != 0 ?
    SpaceTreeNodeLink.new(tree, larger_node_address) : nil

  node = SpaceTreeNode.new(tree, node_address, blob_address, size,
                           parent, smaller, equal, larger)

  node
end

Instance Method Details

#==(node) ⇒ Boolean

Compare this node to another node.



464
465
466
 
# File 'lib/perobs/SpaceTreeNode.rb', line 464

def ==(node)
  node && @node_address == node.node_address
end

#add_space(address, size) ⇒ Object

Add a new node for the given address and size to the tree.



150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
# File 'lib/perobs/SpaceTreeNode.rb', line 150

def add_space(address, size)
  node = self

  loop do
    if node.size == 0
      # This happens only for the root node if the tree is empty.
      node.set_size_and_address(size, address)
      break
    elsif size < node.size
      # The new size is smaller than this node.
      if node.smaller
        # There is already a smaller node, so pass it on.
        node = node.smaller
      else
        # There is no smaller node yet, so we create a new one as a
        # smaller child of the current node.
        node.set_link('@smaller',
                      SpaceTreeNode::create(@tree, address, size, node))
        break
      end
    elsif size > node.size
      # The new size is larger than this node.
      if node.larger
        # There is already a larger node, so pass it on.
        node = node.larger
      else
        # There is no larger node yet, so we create a new one as a larger
        # child of the current node.
        node.set_link('@larger',
                      SpaceTreeNode::create(@tree, address, size, node))
        break
      end
    else
      # Same size as current node. Insert new node as equal child at top of
      # equal list.
      new_node = SpaceTreeNode::create(@tree, address, size, node)
      new_node.set_link('@equal', node.equal)

      node.set_link('@equal', new_node)

      break
    end
  end
end

#check(flat_file) ⇒ false, true

Check this node and all sub nodes for possible structural or logical errors.



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
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
 
# File 'lib/perobs/SpaceTreeNode.rb', line 526

def check(flat_file)
  node_counter = 0
  max_depth = 0

  each do |node, mode, stack|
    max_depth = stack.size if stack.size > max_depth

    case mode
    when :smaller
      if node.smaller
        return false unless node.check_node_link('smaller', stack)
        smaller_node = node.smaller
        if smaller_node.size >= node.size
          PEROBS.log.error "Smaller SpaceTreeNode size " +
            "(#{smaller_node}) is not smaller than #{node}"
          return false
        end
      end
    when :equal
      if node.equal
        return false unless node.check_node_link('equal', stack)
        equal_node = node.equal

        if equal_node.smaller || equal_node.larger
          PEROBS.log.error "Equal node #{equal_node} must not have " +
            "smaller/larger childs"
          return false
        end

        if node.size != equal_node.size
          PEROBS.log.error "Equal SpaceTreeNode size (#{equal_node}) is " +
            "not equal parent node #{node}"
          return false
        end
      end
    when :larger
      if node.larger
        return false unless node.check_node_link('larger', stack)
        larger_node = node.larger
        if larger_node.size <= node.size
          PEROBS.log.error "Larger SpaceTreeNode size " +
            "(#{larger_node}) is not larger than #{node}"
          return false
        end
      end
    when :on_exit
      if flat_file &&
         !flat_file.has_space?(node.blob_address, node.size)
        PEROBS.log.error "SpaceTreeNode has space at offset " +
          "#{node.blob_address} of size #{node.size} that isn't " +
          "available in the FlatFile."
        return false
      end

      node_counter += 1
    end
  end
  PEROBS.log.debug "#{node_counter} SpaceTree nodes checked"
  PEROBS.log.debug "Maximum tree depth is #{max_depth}"

  return true
end

#check_node_link(link, stack) ⇒ Boolean

Check the integrity of the given sub-node link and the parent link pointing back to this node.



594
595
596
597
598
599
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
628
629
630
 
# File 'lib/perobs/SpaceTreeNode.rb', line 594

def check_node_link(link, stack)
  if (node = instance_variable_get('@' + link))
    # Node links must only be of class SpaceTreeNodeLink
    unless node.nil? || node.is_a?(SpaceTreeNodeLink)
      PEROBS.log.error "Node link #{link} of node #{to_s} " +
        "is of class #{node.class}"
      return false
    end

    # Link must not point back to self.
    if node == self
      PEROBS.log.error "#{link} address of node " +
        "#{node.to_s} points to self #{to_s}"
      return false
    end

    # Link must not point to any of the parent nodes.
    if stack.include?(node)
      PEROBS.log.error "#{link} address of node #{to_s} " +
        "points to parent node #{node}"

        return false
    end

    # Parent link of node must point back to self.
    if node.parent != self
      PEROBS.log.error "@#{link} node #{node.to_s} does not have parent " +
        "link pointing " +
        "to parent node #{to_s}. Pointing at " +
        "#{node.parent.nil? ? 'nil' : node.parent.to_s} instead."

      return false
    end
  end

  true
end

#delete_node ⇒ Object 



344
345
346
347
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
380
381
 
# File 'lib/perobs/SpaceTreeNode.rb', line 344

def delete_node
  if @equal
    # Replace the current node with the next @equal node.
    @equal.set_link('@smaller', @smaller) if @smaller
    @equal.set_link('@larger', @larger) if @larger
    relink_parent(@equal)
  elsif @smaller && @larger.nil?
    # We have no @larger node, so we can just replace the current node
    # with the @smaller node.
    relink_parent(@smaller)
  elsif @larger && @smaller.nil?
    # We have no @smaller node, wo we can just replace the current node
    # with the @larger node.
    relink_parent(@larger)
  elsif @smaller && @larger
    # Find the largest node in the smaller sub-node. This node will
    # replace the current node.
    node = @smaller.find_largest_node
    if node != @smaller
      # If the found node is not the direct @smaller node, attach the
      # smaller sub-node of the found node to the parent of the found
      # node.
      node.relink_parent(node.smaller)
      # The @smaller sub node of the current node is attached to the
      # @smaller link of the found node.
      node.set_link('@smaller', @smaller)
    end
    # Attach the @larger sub-node of the current node to the @larger link
    # of the found node.
    node.set_link('@larger', @larger)
    # Point the link in the parent of the current node to the found node.
    relink_parent(node)
  else
    # The node is a leaf node.
    relink_parent(nil)
  end
  @tree.delete_node(@node_address) if @parent
end

#each ⇒ Object

Depth-first iterator for all nodes. The iterator yields the given block at 5 points for any found node. The mode variable indicates the point. :on_enter Coming from the parent we’ve entered the node for the first

time

:smaller We are about to follow the link to the smaller sub-node :equal We are about to follow the link to the equal sub-node :larger We are about to follow the link to the larger sub-node :on_exit We have completed this node



310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
 
# File 'lib/perobs/SpaceTreeNode.rb', line 310

def each
  # 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, :on_enter ] ]

  while !stack.empty?
    node, mode = stack.pop

    # Empty trees only have a dummy node that has no parent, and a size
    # and address of 0.
    break if node.size == 0 && node.blob_address == 0 && node.parent.nil?

    case mode
    when :on_enter
      yield(node, mode, stack)
      stack.push([ node, :smaller ])
    when :smaller
      yield(node, mode, stack) if node.smaller
      stack.push([ node, :equal ])
      stack.push([ node.smaller, :on_enter]) if node.smaller
    when :equal
      yield(node, mode, stack) if node.equal
      stack.push([ node, :larger ])
      stack.push([ node.equal, :on_enter]) if node.equal
    when :larger
      yield(node, mode, stack) if node.larger
      stack.push([ node, :on_exit])
      stack.push([ node.larger, :on_enter]) if node.larger
    when :on_exit
      yield(node, mode, stack)
    end
  end
end

#find_equal_or_larger_space(size) ⇒ Array or nil

Return an address/size touple that matches the requested size or is larger than the requested size plus the overhead for another blob. Return nil if nothing was found.



252
253
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
 
# File 'lib/perobs/SpaceTreeNode.rb', line 252

def find_equal_or_larger_space(size)
  node = self

  loop do
    if node.size < size
      if node.larger
        # The current space is not yet large enough. If we have a larger sub
        # node check that one next.
        node = node.larger
      else
        break
      end
    elsif node.size == size ||
          node.size >= size * 2 + FlatFileBlobHeader::LENGTH
      # We've found a space that is either a perfect match or is large
      # enough to hold at least one more record. Remove it from the list and
      # return it.
      actual_size = node.size
      address = node.blob_address
      node.delete_node
      return [ address, actual_size ]
    elsif node.smaller
      # The current space is larger than size but not large enough for an
      # additional record. So check if we have a perfect match in the
      # smaller brach if available.
      node = node.smaller
    else
      break
    end
  end

  return nil
end

#find_largest_node ⇒ SpaceTreeNode

Find the node with the largest size in this sub-tree.



424
425
426
427
428
429
430
431
432
433
434
 
# File 'lib/perobs/SpaceTreeNode.rb', line 424

def find_largest_node
  node = self
  loop do
    if node.larger
      node = node.larger
    else
      # We've found a 'leaf' node.
      return node
    end
  end
end

#find_matching_space(size) ⇒ Array or nil

Return an address/size touple that matches exactly the requested size. Return nil if nothing was found.



221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
 
# File 'lib/perobs/SpaceTreeNode.rb', line 221

def find_matching_space(size)
  node = self

  loop do
    if node.size < size
      if node.larger
        # The current space is not yet large enough. If we have a larger sub
        # node check that one next.
        node = node.larger
      else
        break
      end
    elsif node.size == size
      # We've found a space that is an exact match. Remove it from the
      # list and return it.
      address = node.blob_address
      node.delete_node
      return [ address, size ]
    else
      break
    end
  end

  return nil
end

#find_smallest_node ⇒ SpaceTreeNode

Find the node with the smallest size in this sub-tree.



410
411
412
413
414
415
416
417
418
419
420
 
# File 'lib/perobs/SpaceTreeNode.rb', line 410

def find_smallest_node
  node = self
  loop do
    if node.smaller
      node = node.smaller
    else
      # We've found a 'leaf' node.
      return node
    end
  end
end

#has_space?(address, size) ⇒ Boolean

Check if this node or any sub-node has an entry for the given address and size.



200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/perobs/SpaceTreeNode.rb', line 200

def has_space?(address, size)
  node = self
  loop do
    if node.blob_address == address
      return size == node.size
    elsif size < node.size && node.smaller
      node = node.smaller
    elsif size > node.size && node.larger
      node = node.larger
    elsif size == node.size && node.equal
      node = node.equal
    else
      return false
    end
  end
end

#relink_parent(node) ⇒ Object

Replace the link in the parent node of the current node that points to the current node with the given node.



386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
 
# File 'lib/perobs/SpaceTreeNode.rb', line 386

def relink_parent(node)
  if @parent
    if @parent.smaller == self
      @parent.set_link('@smaller', node)
    elsif @parent.equal == self
      @parent.set_link('@equal', node)
    elsif @parent.larger == self
      @parent.set_link('@larger', node)
    else
      PEROBS.log.fatal "Cannot relink unknown child node with address " +
        "#{node.node_address} from #{parent.to_s}"
    end
  else
    if node
      @tree.set_root(node)
      node.parent = nil
    else
      set_size_and_address(0, 0)
    end
  end
end

#save ⇒ Object 



138
139
140
141
142
143
144
145
 
# File 'lib/perobs/SpaceTreeNode.rb', line 138

def save
  bytes = [ @blob_address, @size,
            @parent ? @parent.node_address : 0,
            @smaller ? @smaller.node_address : 0,
            @equal ? @equal.node_address : 0,
            @larger ? @larger.node_address : 0].pack(NODE_BYTES_FORMAT)
  @tree.nodes.store_blob(@node_address, bytes)
end

#set_link(name, node_or_address) ⇒ Object 



442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
 
# File 'lib/perobs/SpaceTreeNode.rb', line 442

def set_link(name, node_or_address)
  if node_or_address
    # Set the link to the given SpaceTreeNode or node address.
    instance_variable_set(name,
                          node = node_or_address.is_a?(SpaceTreeNodeLink) ?
                          node_or_address :
                          SpaceTreeNodeLink.new(@tree, node_or_address))
    # Link the node back to this node via the parent variable.
    node.parent = self
  else
    # Clear the node link.
    instance_variable_set(name, nil)
  end
  @tree.cache.insert_modified(self)
end

#set_size_and_address(size, address) ⇒ Object 



436
437
438
439
440
 
# File 'lib/perobs/SpaceTreeNode.rb', line 436

def set_size_and_address(size, address)
  @size = size
  @blob_address = address
  @tree.cache.insert_modified(self)
end

#text_tree_prefix ⇒ String

The indentation and arch routing for the text tree.



659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
 
# File 'lib/perobs/SpaceTreeNode.rb', line 659

def text_tree_prefix
  if (node = @parent)
    str = '+'
  else
    # Prefix start for root node line
    str = 'o'
  end

  while node
    last_child = false
    if node.parent
      if node.parent.smaller == node
        last_child = node.parent.equal.nil? && node.parent.larger.nil?
      elsif node.parent.equal == node
        last_child = node.parent.larger.nil?
      elsif node.parent.larger == node
        last_child = true
      end
    else
      # Padding for the root node
      str = '  ' + str
      break
    end

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

  str
end

#to_a ⇒ Array

Collects address and size touples of all nodes in the tree with a depth-first strategy and stores them in an Array.



471
472
473
474
475
476
477
478
479
480
481
 
# File 'lib/perobs/SpaceTreeNode.rb', line 471

def to_a
  ary = []

  each do |node, mode, stack|
    if mode == :on_enter
      ary << [ node.blob_address, node.size ]
    end
  end

  ary
end

#to_s ⇒ String

Textual version of the node data. It has the form node_address:[blob_address, size] ^parent_node_address <smaller_node_address >larger_node_address



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
518
519
 
# File 'lib/perobs/SpaceTreeNode.rb', line 487

def to_s
  s = "#{@node_address}:[#{@blob_address}, #{@size}]"
  if @parent
    begin
      s += " ^#{@parent.node_address}"
    rescue
      s += ' ^@'
    end
  end
  if @smaller
    begin
      s += " <#{@smaller.node_address}"
    rescue
      s += ' <@'
    end
  end
  if @equal
    begin
      s += " =#{@equal.node_address}"
    rescue
      s += ' =@'
    end
  end
  if @larger
    begin
      s += " >#{@larger.node_address}"
    rescue
      s += ' >@'
    end
  end

  s
end

#to_tree_s ⇒ String

Convert the node and all child nodes into a tree like text form.



634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
 
# File 'lib/perobs/SpaceTreeNode.rb', line 634

def to_tree_s
  str = ''

  each do |node, mode, stack|
    if mode == :on_enter
      begin
        branch_mark = node.parent.nil? ? '' :
          node.parent.smaller == node ? '<' :
          node.parent.equal == node ? '=' :
          node.parent.larger == node ? '>' : '@'

        str += "#{node.text_tree_prefix}#{branch_mark}-" +
          "#{node.smaller || node.equal || node.larger ? 'v-' : '--'}" +
          "#{node.to_s}\n"
      rescue
        str += "#{node.text_tree_prefix}- @@@@@@@@@@\n"
      end
    end
  end

  str
end

#unlink_node(child_node) ⇒ Object

Remove a smaller/equal/larger link from the current node.



288
289
290
291
292
293
294
295
296
297
298
299
300
 
# File 'lib/perobs/SpaceTreeNode.rb', line 288

def unlink_node(child_node)
  if @smaller == child_node
    @smaller = nil
  elsif @equal == child_node
    @equal = nil
  elsif @larger == child_node
    @larger = nil
  else
    PEROBS.log.fatal "Cannot unlink unknown child node with address " +
      "#{child_node.node_address} from #{to_s}"
  end
  @tree.cache.insert_modified(self)
end