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.

Parameters:

  • tree (SpaceTree) —

    Tree that the object should belong to

  • node_address (Integer) —

    Address of the node in the file

  • blob_address (Integer) (defaults to: 0) —

    Address of the free space blob

  • size (Integer) (defaults to: 0) —

    Size of the free space blob

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

    Parent node in the tree

  • smaller (SpaceTreeNode) (defaults to: nil) —

    smaller node in the tree

  • equal (SpaceTreeNode) (defaults to: nil) —

    equal node in the tree

  • larger (SpaceTreeNode) (defaults to: nil) —

    larger node in the tree



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# 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
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

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

Parameters:

  • tree (SpaceTree) —

    The tree the node should belong to

  • blob_address (Integer) (defaults to: 0) —

    Address of the free space blob

  • size (Integer) (defaults to: 0) —

    Size of the free space blob

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

    Parent node in the tree



85
86
87
88
89
90
91
92
 
# File 'lib/perobs/SpaceTreeNode.rb', line 85

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)
  tree.cache.insert(node)

  node
end

.load(tree, node_address, unused = nil) ⇒ Object

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

Parameters:

  • tree (SpaceTree) —

    The tree the node belongs to

  • node_address (Integer) —

    The address in the file.



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/perobs/SpaceTreeNode.rb', line 97

def SpaceTreeNode::load(tree, node_address, unused = nil)
  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)

  tree.cache.insert(node, false)

  node
end

Instance Method Details

#==(node) ⇒ Boolean

Compare this node to another node.

Returns:

  • (Boolean) —

    true if node address is identical, false otherwise



460
461
462
 
# File 'lib/perobs/SpaceTreeNode.rb', line 460

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.

Parameters:

  • address (Integer) —

    address of the free space

  • size (Integer) —

    size of the free space



140
141
142
143
144
145
146
147
148
149
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
 
# File 'lib/perobs/SpaceTreeNode.rb', line 140

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, count) ⇒ false, true

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

Parameters:

  • flat_file (FlatFile) —

    If given, check that the space is also present in the given flat file.

  • count (Integer) —

    The total number of entries in the tree

Returns:

  • (false, true) —

    True if OK, false otherwise



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

def check(flat_file, count)
  node_counter = 0
  max_depth = 0

  @tree.progressmeter.start('Checking space list entries', count) do |pm|
    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

        pm.update(node_counter += 1)
      end
    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.

Parameters:

  • link (String) —

    ‘smaller’, ‘equal’ or ‘larger’

  • stack (Array) —

    List of parent nodes [ address, mode ] touples

Returns:

  • (Boolean) —

    true of OK, false otherwise



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

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 



340
341
342
343
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
 
# File 'lib/perobs/SpaceTreeNode.rb', line 340

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



306
307
308
309
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
 
# File 'lib/perobs/SpaceTreeNode.rb', line 306

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.

Parameters:

  • size (Integer) —

    size of the free space

Returns:

  • (Array or nil) —

    address, size touple or nil



242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
 
# File 'lib/perobs/SpaceTreeNode.rb', line 242

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.

Returns:



420
421
422
423
424
425
426
427
428
429
430
 
# File 'lib/perobs/SpaceTreeNode.rb', line 420

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.

Parameters:

  • size (Integer) —

    size of the free space

Returns:

  • (Array or nil) —

    address, size touple or nil



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/perobs/SpaceTreeNode.rb', line 211

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.

Returns:



406
407
408
409
410
411
412
413
414
415
416
 
# File 'lib/perobs/SpaceTreeNode.rb', line 406

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.

Parameters:

  • address (Integer) —

    address of the free space

  • size (Integer) —

    size of the free space

Returns:

  • (Boolean) —

    True if found, otherwise false



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/perobs/SpaceTreeNode.rb', line 190

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.

Parameters:



382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
 
# File 'lib/perobs/SpaceTreeNode.rb', line 382

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

Save the node into the blob file.



128
129
130
131
132
133
134
135
 
# File 'lib/perobs/SpaceTreeNode.rb', line 128

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 



438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
 
# File 'lib/perobs/SpaceTreeNode.rb', line 438

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(self)
end

#set_size_and_address(size, address) ⇒ Object 



432
433
434
435
436
 
# File 'lib/perobs/SpaceTreeNode.rb', line 432

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

#text_tree_prefix ⇒ String

The indentation and arch routing for the text tree.

Returns:

  • (String) 


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

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.

Returns:

  • (Array) —

    Array with [ address, size ] touples.



467
468
469
470
471
472
473
474
475
476
477
 
# File 'lib/perobs/SpaceTreeNode.rb', line 467

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

Returns:

  • (String) 


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

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.

Returns:

  • (String) 


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

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

#uid ⇒ Integer

Returns The node address since it uniquely identifies the Node.

Returns:

  • (Integer) —

    The node address since it uniquely identifies the Node.



294
295
296
 
# File 'lib/perobs/SpaceTreeNode.rb', line 294

def uid
  @node_address
end

#unlink_node(child_node) ⇒ Object

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

Parameters:



278
279
280
281
282
283
284
285
286
287
288
289
290
 
# File 'lib/perobs/SpaceTreeNode.rb', line 278

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(self)
end