lib/Zero/NWayTree.pm

filter: Statementstmt 7.0% 58 / 825 Branchbran 8.3% 2 / 24 Conditioncond 0.0% 0 / 5 MC/DCmcdc 0.0% 0 / 3 Subroutinesub 8.3% 12 / 143 Podpod 0.0% 0 / 11 totaltotal 7.1% 72 / 1011 CC 19 SCAR 18.4
CC
19
Cov
7%
printNode
56.0
FindComparison
30.0
printTree
30.0
CRAP 6.3
« lib/Zero/Emulator.pm ↑ Summary blib/lib/Zero/NWayTree.pm »
1 #!/usr/bin/perl -I/home/phil/perl/cpan/ZeroEmulator/lib/ -Ilib
2 #-------------------------------------------------------------------------------
3 # Zero assembler language implemention of a generic N-Way tree.
4 # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2023
5 #-------------------------------------------------------------------------------
6 # Key compression in each node by eliminating any common prefix present in each key in each node especially useful if we were to add attributes like userid, process, string position, rwx etc to front of each key. Data does does not need this additional information.
7 1 ▶use v5.30;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 package Zero::NWayTree;
9 1 our $VERSION = 20230511; # Version
10 1 ▶use warnings FATAL => qw(all);
Subroutine BEGIN: called CC=1 SCAR=0.0
11 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 1 ▶use Carp qw(cluck confess);
Subroutine BEGIN: called CC=1 SCAR=0.0
13 1 ▶use Data::Dump qw(dump);
Subroutine BEGIN: called CC=1 SCAR=0.0
14 1 ▶use Data::Table::Text qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
15 1 ▶use Zero::Emulator qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
16 1 ▶eval "use Test::More tests=>29" unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
17  
18 1 makeDieConfess;
19  
20 0 ▶my sub MaxIterations{99}; # The maximum number of levels in a tree
Subroutine MaxIterations: not called CC=1 SCAR=6.9
21  
22 my $Tree = sub # The structure of an n-way tree
23 1 ▶ {my $t = Zero::Emulator::AreaStructure("Structure");
Subroutine __ANON__: called CC=1 SCAR=0.0
24 1 $t->name(q(keys)); # Number of keys in tree
25 1 $t->name(q(nodes)); # Number of nodes in tree
26 1 $t->name(q(NumberOfKeysPerNode)); # The maximum number of keys in a node of this tree
27 1 $t->name(q(root)); # Root node
28 1 $t
29 1 }->();
30  
31 my $Node = sub # The structure of an n-way tree node
32 1 ▶ {my $n = Zero::Emulator::AreaStructure("Node_Structure");
Subroutine __ANON__: called CC=1 SCAR=0.0
33 1 $n->name(q(length)); # The current number of keys in the node
34 1 $n->name(q(id)); # A number identifying this node within this tree
35 1 $n->name(q(up)); # Parent node unless at the root node
36 1 $n->name(q(tree)); # The definition of the containing tree
37 1 $n->name(q(keys)); # Keys associated with this node
38 1 $n->name(q(data)); # Data associated with each key associated with this node
39 1 $n->name(q(down)); # Next layer of nodes down from this node
40 1 $n
41 1 }->();
42  
43 my $FindResult = sub # The structure of a find result
44 1 ▶ {my $f = Zero::Emulator::AreaStructure("FindResult");
Subroutine __ANON__: called CC=1 SCAR=0.0
45 1 $f->name(q(node)); # Node found
46 1 $f->name(q(cmp)); # Result of the last comparison
47 1 $f->name(q(key)); # Key searched for
48 1 $f->name(q(index)); # Index in the node of located element
49 1 $f
50 1 }->();
51  
52 0 ▶my sub FindComparison_lower {0} # Comparison result
Subroutine FindComparison_lower: not called CC=1 SCAR=6.9
53 0 ▶my sub FindComparison_equal {1}
Subroutine FindComparison_equal: not called CC=1 SCAR=6.9
54 0 ▶my sub FindComparison_higher {2}
Subroutine FindComparison_higher: not called CC=1 SCAR=6.9
55 0 ▶my sub FindComparison_notFound{3}
Subroutine FindComparison_notFound: not called CC=1 SCAR=6.9
56  
57 #D1 Constructor # Create a new tree.
58  
59 sub New($) # Create a variable referring to a new tree descriptor.
60 0 ▶ {my ($n) = @_; # Maximum number of keys per node in this tree
Subroutine New: not called CC=3 SCAR=24.8
Pod undocumented
61  
62 0 ▶ $n > 2 && $n % 2 or confess "Number of key/data elements per node must be > 2 and odd";
Branch: 1 branch
BranchTrueFalseTotal
$n > 2 and $n % 2 or confess("Number of key/data elements per node must be > 2 and odd") 0 0 0
Condition0%0/3
$n > 2 and $n % 2
!ll&&!rl&&r
000
MC/DC0%0/2
$n > 2 and $n % 2
$n > 2 $n % 2
Truth table0%0/3
A and B
A= $n > 2B= $n % 2
ABresult
0X0
100
111
63  
64 0 my $t = Array "Tree"; # Allocate tree descriptor
65 0 Mov [$t, $Tree->address(q(NumberOfKeysPerNode)), 'Tree'], $n; # Save maximum number of keys per node
66 0 Mov [$t, $Tree->address(q(root)), 'Tree'], 0; # Clear root
67 0 Mov [$t, $Tree->address(q(keys)), 'Tree'], 0; # Clear keys
68 0 Mov [$t, $Tree->address(q(nodes)), 'Tree'], 0; # Clear nodes
69 0 $t
70 }
71  
72 my sub Tree_getField($$) # Get a field from a tree descriptor
73 0 ▶ {my ($tree, $field) = @_; # Tree, field name
Subroutine Tree_getField: not called CC=1 SCAR=6.9
74 0 Mov [$tree, $Tree->address($field), 'Tree'] # Get attribute from tree descriptor
75 }
76  
77 my sub maximumNumberOfKeys($) # Get the maximum number of keys per node for a tree
78 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine maximumNumberOfKeys: not called CC=1 SCAR=6.9
79 0 Tree_getField($tree, q(NumberOfKeysPerNode)); # Get attribute from tree descriptor
80 };
81  
82 my sub root($) # Get the root node of a tree
83 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine root: not called CC=1 SCAR=6.9
84 0 Tree_getField($tree, q(root)); # Get attribute from tree descriptor
85 };
86  
87 my sub setRoot($$) # Set the root node of a tree
88 0 ▶ {my ($tree, $root) = @_; # Tree, root
Subroutine setRoot: not called CC=1 SCAR=6.9
89 0 Mov [$tree, $Tree->address(q(root)), 'Tree'], $root; # Set root attribute
90 };
91  
92 sub Keys($) # Get the number of keys in the tree..
93 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine Keys: not called CC=1 SCAR=6.9
Pod undocumented
94 0 Tree_getField($tree, q(keys)); # Keys
95 };
96  
97 my sub incKeys($) # Increment the number of keys in a tree
98 0 ▶ {my ($tree) = @_; # Tree
Subroutine incKeys: not called CC=1 SCAR=6.9
99 0 Inc [$tree, $Tree->address(q(keys)), 'Tree']; # Number of keys
100 };
101  
102 my sub nodes($) # Get the number of nodes in the tree
103 0 ▶ {my ($tree) = @_; # Tree to examine
Subroutine nodes: not called CC=1 SCAR=6.9
104 0 Tree_getField($tree, q(nodes)); # Nodes
105 };
106  
107 my sub incNodes($) # Increment the number of nodes n a tree
108 0 ▶ {my ($tree) = @_; # Tree
Subroutine incNodes: not called CC=1 SCAR=6.9
109 0 Inc [$tree, $Tree->address(q(nodes)), 'Tree']; # Number of nodes
110 };
111  
112 my sub Node_getField($$) # Get a field from a node descriptor
113 0 ▶ {my ($node, $field) = @_; # Node, field name
Subroutine Node_getField: not called CC=1 SCAR=6.9
114 0 Mov [$node, $Node->address($field), 'Node']; # Get attribute from node descriptor
115 }
116  
117 my sub Node_length($) # Get number of keys in a node
118 0 ▶ {my ($node) = @_; # Node
Subroutine Node_length: not called CC=1 SCAR=6.9
119 0 Node_getField($node, q(length)); # Get length
120 }
121  
122 my sub Node_setLength($$) # Set the length of a node
123 0 ▶ {my ($node, $length) = @_; # Node, length
Subroutine Node_setLength: not called CC=1 SCAR=6.9
124 0 Mov [$node, $Node->address(q(length)), 'Node'], $length; # Set length attribute
125 }
126  
127 my sub Node_incLength($) # Increment the length of a node
128 0 ▶ {my ($node) = @_; # Node
Subroutine Node_incLength: not called CC=1 SCAR=6.9
129 0 Inc [$node, $Node->address(q(length)), 'Node']; # Increment length attribute
130 }
131  
132 my sub Node_id($) # Get id of a node
133 0 ▶ {my ($node) = @_; # Node
Subroutine Node_id: not called CC=1 SCAR=6.9
134 0 Node_getField($node, q(id)); # Get id
135 }
136  
137 my sub Node_up($) # Get parent node from this node
138 0 ▶ {my ($node) = @_; # Node
Subroutine Node_up: not called CC=1 SCAR=6.9
139 0 Node_getField($node, q(up)); # Get up
140 }
141  
142 my sub Node_setUp($$) # Set the parent of a node
143 0 ▶ {my ($node, $parent) = @_; # Node, parent node, area containing parent node reference
Subroutine Node_setUp: not called CC=1 SCAR=6.9
144 0 Mov [$node, $Node->address(q(up)), 'Node'], $parent; # Set parent
145 }
146  
147 my sub Node_tree($) # Get tree containing a node
148 0 ▶ {my ($node) = @_; # Node
Subroutine Node_tree: not called CC=1 SCAR=6.9
149 0 Node_getField($node, q(tree)); # Get tree
150 }
151  
152 my sub Node_getIndex($$$) # Get the indexed field from a node
153 0 ▶ {my ($node, $index, $field) = @_; # Node, index of field, field name
Subroutine Node_getIndex: not called CC=1 SCAR=6.9
154 0 my $F = Mov [$node, $Node->address($field), 'Node']; # Fields
155 0 Mov [$F, \$index, ucfirst $field]; # Field
156 }
157  
158 my sub Node_setIndex($$$$) # Set an indexed field to a specified value
159 0 ▶ {my ($node, $index, $field, $value) = @_; # Node, index, field name, value
Subroutine Node_setIndex: not called CC=1 SCAR=6.9
160 0 my $F = Mov [$node, $Node->address($field), 'Node']; # Fields
161 0 Mov [$F, \$index, ucfirst $field], $value; # Set field to value
162 }
163  
164 my sub Node_keys($$) # Get the indexed key from a node
165 0 ▶ {my ($node, $index) = @_; # Node, index of key
Subroutine Node_keys: not called CC=1 SCAR=6.9
166 0 Node_getIndex($node, $index, q(keys)); # Keys
167 }
168  
169 my sub Node_data($$) # Get the indexed data from a node
170 0 ▶ {my ($node, $index) = @_; # Node, index of data
Subroutine Node_data: not called CC=1 SCAR=6.9
171 0 Node_getIndex($node, $index, q(data)); # Data
172 }
173  
174 my sub Node_down($$) # Get the indexed child node from a node
175 0 ▶ {my ($node, $index) = @_; # Node, index of child
Subroutine Node_down: not called CC=1 SCAR=6.9
176 0 Node_getIndex($node, $index, q(down)); # Child
177 }
178  
179 my sub Node_isLeaf($) # Put 1 in a temporary variable if a node is a leaf else 0
180 0 ▶ {my ($node) = @_; # Node
Subroutine Node_isLeaf: not called CC=1 SCAR=6.9
181 0 Not [$node, $Node->address('down'), 'Node']; # Whether the down field is present or not . 0 is never a user allocated memory area
182 }
183  
184 my sub Node_setKeys($$$) # Set a key by index
185 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setKeys: not called CC=1 SCAR=6.9
186 0 Node_setIndex($node, $index, q(keys), $value) # Set indexed key
187 }
188  
189 my sub Node_setData($$$) # Set a data field by index
190 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setData: not called CC=1 SCAR=6.9
191 0 Node_setIndex($node, $index, q(data), $value) # Set indexed key
192 }
193  
194 my sub Node_setDown($$$) # Set a child by index
195 0 ▶ {my ($node, $index, $value) = @_; # Node, index, value
Subroutine Node_setDown: not called CC=1 SCAR=6.9
196 0 Node_setIndex($node, $index, q(down), $value) # Set indexed key
197 }
198  
199 my sub Node_new($%) # Create a variable referring to a new node descriptor
200 0 ▶ {my ($tree, %options) = @_; # Tree node is being created in, options
Subroutine Node_new: not called CC=2 SCAR=17.9
201 0 my $n = Array "Node"; # Allocate node
202 0 my $k = Array "Keys"; # Allocate keys
203 0 my $d = Array "Data"; # Allocate data
204  
205 0 ▶ Node_setLength $n, $options{length} // 0; # Length
Condition0%0/2
$options{"length"} // 0
l!l
00
MC/DC0%0/1
$options{"length"} // 0
$options{"length"}
Truth table0%0/2
A
A= $options{"length"}
Aresult
11
00
206  
207 0 Node_setUp $n, 0; # Parent
208  
209 0 Mov [$n, $Node->address(q(keys)), 'Node'], $k; # Keys area
210 0 Mov [$n, $Node->address(q(data)), 'Node'], $d; # Data area
211 0 Mov [$n, $Node->address(q(down)), 'Node'], 0; # Down area
212 0 Mov [$n, $Node->address(q(tree)), 'Node'], $tree; # Containing tree
213 0 incNodes($tree);
214 0 Mov [$n, $Node->address(q(id)), 'Node'], # Assign an id to this node within the tree
215 [$tree, $Tree->address(q(nodes)), 'Tree'];
216 0 my $N = maximumNumberOfKeys($tree); # Get the maximum number of keys per node for a tree
217 0 $n # Return reference to new node
218 }
219  
220 my sub Node_allocDown($%) # Upgrade a leaf node to an internal node
221 0 ▶ {my ($node, %options) = @_; # Node to upgrade, options
Subroutine Node_allocDown: not called CC=1 SCAR=6.9
222 0 my $d = Array "Down"; # Allocate down
223 0 Mov [$node, $Node->address(q(down)), 'Node'], $d; # Down area
224 }
225  
226 my sub FindResult_getField($$) # Get a field from a find result
227 0 ▶ {my ($findResult, $field) = @_; # Find result, name of field
Subroutine FindResult_getField: not called CC=1 SCAR=6.9
228 0 Mov [$findResult, $FindResult->address($field), q(FindResult)]; # Fields
229 }
230  
231 sub FindResult_key($) # Get key from find result..
232 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_key: not called CC=1 SCAR=6.9
Pod undocumented
233 0 FindResult_getField($f, q(key)) # Key
234 }
235  
236 sub FindResult_cmp($) # Get comparison from find result..
237 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_cmp: not called CC=1 SCAR=6.9
Pod undocumented
238 0 FindResult_getField($f, q(cmp)) # Comparison
239 }
240  
241 my sub FindResult_index($) # Get index from find result
242 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_index: not called CC=1 SCAR=6.9
243 0 FindResult_getField($f, q(index)) # Index
244 }
245  
246 my sub FindResult_node($) # Get node from find result
247 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_node: not called CC=1 SCAR=6.9
248 0 FindResult_getField($f, q(node)) # Node
249 }
250  
251 sub FindResult_data($) # Get data field from find results..
252 0 ▶ {my ($f) = @_; # Find result
Subroutine FindResult_data: not called CC=1 SCAR=6.9
Pod undocumented
253  
254 0 my $n = FindResult_node ($f);
255 0 my $i = FindResult_index($f);
256 0 my $d = Node_data($n, $i);
257 0 $d
258 }
259  
260 my sub FindComparison($$) # Convert a symbolic name for a find result comparison to an integer
261 0 ▶ {my ($f, $cmp) = @_; # Find result, comparison result name
Subroutine FindComparison: not called CC=5 SCAR=34.0
262 0 ▶ return 0 if $cmp eq q(lower);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "lower" 0 0 0
263 0 ▶ return 1 if $cmp eq q(equal);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "equal" 0 0 0
264 0 ▶ return 2 if $cmp eq q(higher);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "higher" 0 0 0
265 0 ▶ return 3 if $cmp eq q(notFound);
Branch: 1 branch
BranchTrueFalseTotal
if $cmp eq "notFound" 0 0 0
266 }
267  
268 my sub Node_open($$$$$) # Open a gap in an interior node
269 0 ▶ {my ($node, $offset, $length, $K, $D) = @_; # Node
Subroutine Node_open: not called CC=1 SCAR=6.9
270  
271 0 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
272 0 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
273 0 my $n = Mov [$node, \$Node->offset(qw(down)), 'Node'];
274  
275 0 ShiftUp [$k, \$offset, 'Keys'], $K;
276 0 ShiftUp [$d, \$offset, 'Data'], $D;
277 0 my $o1 = Add $offset, 1;
278 0 ShiftUp [$n, \$o1, 'Down'], 0;
279 0 Node_incLength $node;
280 }
281  
282 my sub Node_openLeaf($$$$$) # Open a gap in a leaf node
283 0 ▶ {my ($node, $offset, $length, $K, $D) = @_; # Node
Subroutine Node_openLeaf: not called CC=1 SCAR=6.9
284  
285 0 my $k = Mov [$node, \$Node->offset(qw(keys)), 'Node'];
286 0 my $d = Mov [$node, \$Node->offset(qw(data)), 'Node'];
287  
288 0 ShiftUp [$k, \$offset, 'Keys'], $K;
289 0 ShiftUp [$d, \$offset, 'Data'], $D;
290 0 Node_incLength $node;
291 }
292  
293 my sub Node_copy($$$$$) # Copy part of one interior node into another node.
294 0 ▶ {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
Subroutine Node_copy: not called CC=1 SCAR=6.9
295  
296 For # Each key, data, down
297 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
298 0 my $S = Add $so, $i;
299 0 my $T = Add $to, $i;
300  
301 0 my $k = Node_keys ($s, $S);
302 0 my $d = Node_data ($s, $S);
303 0 my $n = Node_down ($s, $S);
304 0 Node_setKeys($t, $T, $k);
305 0 Node_setData($t, $T, $d);
306 0 Node_setDown($t, $T, $n);
307 0 } $length;
308  
309 0 my $S = Add $so, $length;
310 0 my $T = Add $to, $length;
311  
312 0 my $n = Node_down($s, $S);
313 0 Node_setDown($t, $T, $n);
314 }
315  
316 my sub Node_copy_leaf($$$$$) # Copy part of one leaf node into another node.
317 0 ▶ {my ($t, $s, $to, $so, $length) = @_; # Target node, source node, target offset, source offset, length
Subroutine Node_copy_leaf: not called CC=1 SCAR=6.9
318  
319 For # Each key, data, down
320 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
321 0 my $S = Add $so, $i;
322 0 my $T = Add $to, $i;
323  
324 0 my $k = Node_keys ($s, $S);
325 0 my $d = Node_data ($s, $S);
326 0 Node_setKeys($t, $T, $k);
327 0 Node_setData($t, $T, $d);
328 0 } $length;
329 }
330  
331 my sub Node_free($) # Free a node
332 0 ▶ {my ($node) = @_; # Node to free
Subroutine Node_free: not called CC=1 SCAR=6.9
333 IfFalse Node_isLeaf($node),
334 Then
335 0 ▶ {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
Subroutine __ANON__: not called CC=1 SCAR=6.9
336 0 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
337 0 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
338 0 Free $K, "Keys";
339 0 Free $D, "Data";
340 0 Free $N, "Down";
341 0 };
342 0 Free $node, "Node";
343 }
344  
345 my sub FindResult_new($$$$) # New find result on stack
346 0 ▶ {my ($node, $key, $cmp, $index) = @_; # Node,search key, comparison result, index
Subroutine FindResult_new: not called CC=1 SCAR=6.9
347 0 my $f = Array "FindResult"; # Find result
348  
349 0 Mov [$f, $FindResult->address(q(node)) , 'FindResult'], $node;
350 0 Mov [$f, $FindResult->address(q(key)) , 'FindResult'], $key;
351 0 Mov [$f, $FindResult->address(q(cmp)) , 'FindResult'], $cmp;
352 0 Mov [$f, $FindResult->address(q(index)), 'FindResult'], $index;
353 0 $f
354 }
355  
356 my sub ReUp($) # Reconnect the children to their new parent.
357 0 ▶ {my ($node) = @_; # Parameters
Subroutine ReUp: not called CC=1 SCAR=6.9
358 0 my $l = Node_length($node);
359 0 my $L = Add $l, 1;
360  
361 For
362 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
363 0 my $d = Node_down ($node, $i);
364 0 Node_setUp($d, $node);
365 0 } $L;
366 }
367  
368 my sub Node_indexInParent # Get the index of a node in its parent.
369 0 ▶ {my ($node) = @_; # Node
Subroutine Node_indexInParent: not called CC=1 SCAR=6.9
370 0 my $p = Node_up($node);
371 0 AssertNe($p, 0); # Number of children as opposed to the number of keys
372 0 my $l = Node_length($p);
373 0 AssertNe($l, 0); # Number of children as opposed to the number of keys
374 0 my $L = Add $l, 1;
375 0 my $r = Var; # Index of child
376  
377 Block
378 0 ▶ {my ($Start, $Good, $Bad, $End) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
379 For # Loop through each child looking for the one specified
380 0 ▶ {my ($i, $check, $next, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
381 IfEq Node_down($p, $i), $node,
382 Then
383 0 ▶ {Mov $r, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
384 0 Jmp $End;
385 0 };
386 0 } $L;
387 0 Assert; # Something has gone seriously wrong if we cannot find the node within its parent
388 0 };
389 0 $r
390 }
391  
392 my sub Node_SplitIfFull($) # Split a node if it is full. Return true if the node was split else false
393 0 ▶ {my ($node) = @_; # Node to split
Subroutine Node_SplitIfFull: not called CC=1 SCAR=6.9
394 0 my $nl = Node_length($node);
395 0 my $t = Node_tree($node); # Associated tree
396 0 my $m = maximumNumberOfKeys($t);
397 0 my $split = Var;
398  
399 Block # Various splitting scenarios
400 0 ▶ {my ($start, $good, $bad, $end) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
401 0 Jlt $bad, $nl, $m; # Must be a full node
402  
403 0 my $N = maximumNumberOfKeys($t); # Split points
404 0 my $n = Mov $N; # Copy
405 0 ShiftRight $n, 1; # Index of key that will be placed in parent
406  
407 0 my $L = Add $n, 1;
408 0 my $R = Subtract $N, $L;
409  
410 0 my $l = Node_new($t, length=>$n); # New child nodes
411 0 my $r = Node_new($t, length=>$R);
412  
413 IfFalse Node_isLeaf($node), # Not a leaf
414 Then
415 0 ▶ {Node_allocDown $l; # Add down area on left
Subroutine __ANON__: not called CC=1 SCAR=6.9
416 0 Node_allocDown $r; # Add down area on right
417 0 Node_copy($l, $node, 0, 0, $n); # New left node
418 0 Node_copy($r, $node, 0, $L, $R); # New right node
419 0 ReUp($l);
420 0 ReUp($r);
421 },
422 Else
423 0 ▶ {Node_allocDown $node; # Add down area
Subroutine __ANON__: not called CC=1 SCAR=6.9
424 0 Node_copy_leaf($l, $node, 0, 0, $n); # New left leaf
425 0 Node_copy_leaf($r, $node, 0, $L, $R); # New right leaf
426 0 };
427  
428 0 my $p = Node_up($node); # Existing parent node
429 IfTrue $p,
430 Then # Not a root node
431 0 ▶ {my $pl = Node_length($p);
Subroutine __ANON__: not called CC=1 SCAR=6.9
432 0 Node_setUp($l, $p); # Connect children to parent
433 0 Node_setUp($r, $p);
434  
435 IfEq Node_down($p, 0), $node,
436 Then # Splitting the first child - move everything up
437 0 ▶ {my $nk = Node_keys($node, $n);
Subroutine __ANON__: not called CC=1 SCAR=6.9
438 0 my $nd = Node_data($node, $n);
439 0 Node_open ($p, 0, $pl, $nk, $nd);
440 0 Node_setDown($p, 0, $l);
441 0 Node_setDown($p, 1, $r);
442 0 Node_free($node);
443 0 Jmp $good;
444 0 };
445  
446 IfEq Node_down($p, $pl), $node, # Splitting the last child - just add it on the end
447 Then
448 0 ▶ {my $pk = Node_keys($node, $n);
Subroutine __ANON__: not called CC=1 SCAR=6.9
449 0 my $pd = Node_data($node, $n);
450 0 Node_setKeys ($p, $pl, $pk);
451 0 Node_setDown ($p, $pl, $l);
452 0 my $nd = Node_data($node, $n);
453 0 Node_setData ($p, $pl, $nd);
454 0 my $pl1 = Add $pl, 1;
455 0 Node_setLength($p, $pl1);
456 0 Node_setDown ($p, $pl1, $r);
457 0 Node_free ($node);
458 0 Jmp $good;
459 0 };
460  
461 For # Splitting a middle child:
462 0 ▶ {my ($i) = @_; # Child index
Subroutine __ANON__: not called CC=1 SCAR=6.9
463 IfEq Node_down($p, $i), $node, # Find the node that points from the parent to the current node
464 Then
465 0 ▶ {my $pli = Subtract $pl, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
466 0 my $pk = Node_keys($node, $n);
467 0 my $pd = Node_data($node, $n);
468 0 Node_open ($p, $i, $pli, $pk, $pd);
469 0 Node_setDown ($p, $i, $l);
470 0 my $i1 = Add $i, 1;
471 0 Node_setDown ($p, $i1, $r);
472 0 Node_free ($node);
473 0 Jmp $good;
474 0 };
475 0 } [1, $pl];
476 0 Assert; # Could not find the child in the parent
477 0 };
478  
479 0 Node_setUp($l, $node); # Root node with single key after split
480 0 Node_setUp($r, $node); # Connect children to parent
481  
482 0 my $pk = Node_keys($node, $n); # Single key
483 0 my $pd = Node_data($node, $n); # Data associated with single key
484 0 Node_setKeys ($node, 0, $pk);
485 0 Node_setData ($node, 0, $pd);
486 0 Node_setDown ($node, 0, $l);
487 0 Node_setDown ($node, 1, $r);
488 0 Node_setLength($node, 1);
489  
490 0 if (1) # Resize split node
491 0 {my $K = Mov [$node, $Node->address(q(keys)), 'Node'];
492 0 my $D = Mov [$node, $Node->address(q(data)), 'Node'];
493 0 my $N = Mov [$node, $Node->address(q(down)), 'Node'];
494 0 Resize $K, 1;
495 0 Resize $D, 1;
496 0 Resize $N, 2;
497 }
498  
499 0 Jmp $good;
500 }
501 Good # Node was split
502 0 ▶ {Mov $split, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
503 },
504 Bad # Node was to small to split
505 0 ▶ {Mov $split, 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
506 0 };
507 0 $split
508 }
509  
510 #D1 Find # Find a key in a tree.
511  
512 my sub FindAndSplit($$) # Find a key in a tree splitting full nodes along the path to the key.
513 0 ▶ {my ($tree, $key) = @_; # Parameters (NWayTree(Tree) * const tree, # Tree to search
Subroutine FindAndSplit: not called CC=1 SCAR=6.9
514 0 my $node = root($tree);
515  
516 0 Node_SplitIfFull($node); # Split the root node if necessary
517 0 my $F = Var;
518  
519 Block # Exit this block when we have located the key
520 0 ▶ {my ($Start, $Good, $Bad, $Found) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
521  
522 For # Step down through the tree
523 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
524 0 my $nl = Node_length($node); # Length of node
525 0 my $last = Subtract $nl, 1; # Greater than largest key in node. Data often gets inserted in ascending order so we do this check first rather than last.
526 IfGt $key, Node_keys($node, $last), # Key greater than greatest key
527 Then
528 {IfTrue Node_isLeaf($node), # Leaf
529 Then
530 0 ▶ {Mov $F, FindResult_new($node, $key, FindComparison_higher, $last);
Subroutine __ANON__: not called CC=1 SCAR=6.9
531 0 Jmp $Found;
532 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
533 0 my $last1 = Add $last, 1;
534 0 my $n = Node_down($node, $last1); # We will be heading down through the last node so split it in advance if necessary
535 IfFalse Node_SplitIfFull($n), # No split needed
536 Then
537 0 ▶ {Mov $node, $n;
Subroutine __ANON__: not called CC=1 SCAR=6.9
538 0 };
539 0 Jmp $next;
540 0 };
541  
542 For # Search the keys in this node as greater than least key and less than largest key
543 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
544 0 my $k = Node_keys($node, $i); # Current key
545  
546 IfLt $key, $k, # Greater than current key
547 Then
548 {IfTrue Node_isLeaf($node),
549 Then
550 0 ▶ {Mov $F, FindResult_new($node, $key, FindComparison_lower, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
551 0 Jmp $Found;
552 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
553  
554 0 my $n = Node_down($node, $i);
555 IfFalse Node_SplitIfFull($n), # Split the node we have stepped to if necessary - if we do we will have to restart the descent from one level up because the key might have moved to the other node.
556 Then
557 0 ▶ {Mov $node, $n;
Subroutine __ANON__: not called CC=1 SCAR=6.9
558 0 };
559 0 Jmp $end;
560 0 };
561  
562 IfEq $key, $k, # Found key
563 Then
564 0 ▶ {Mov $F, FindResult_new($node, $key, FindComparison_equal, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
565 0 Jmp $Found;
566 0 };
567 0 } $nl;
568 0 } MaxIterations;
569 0 Assert; # Failed to descend through the tree to the key.
570 0 };
571 0 $F # Results of find
572 }
573  
574 sub Find($$) # Find a key in a tree returning its associated data or undef if the key does not exist..
575 0 ▶ {my ($tree, $key) = @_; # Tree to search, key to find
Subroutine Find: not called CC=1 SCAR=6.9
Pod undocumented
576  
577 my $p = Procedure 'NWayTree_Find', sub
578 0 ▶ {my ($p) = @_; # Procedure description
Subroutine __ANON__: not called CC=1 SCAR=6.9
579 0 my $tree = ParamsGet 0;
580 0 my $key = ParamsGet 1;
581  
582 0 my $node = root($tree); # Current node we are searching
583  
584 IfFalse $node, # Empty tree
585 Then
586 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindComparison_notFound, -1);
Subroutine __ANON__: not called CC=1 SCAR=6.9
587 0 Return;
588 0 };
589  
590 For # Step down through tree
591 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
592 0 my $nl = Node_length($node);
593 0 my $nl1 = Subtract $nl, 1;
594  
595 IfGt $key, Node_keys($node, $nl1), # Bigger than every key
596 Then
597 {IfTrue Node_isLeaf($node), # Leaf
598 Then
599 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindComparison_higher, $nl);
Subroutine __ANON__: not called CC=1 SCAR=6.9
600 0 Return;
601 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
602 0 Mov $node, Node_down($node, $nl);
603 0 Jmp $next;
604 0 };
605  
606 For # Search the keys in this node as less than largest key
607 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
608 0 my $k = Node_keys($node, $i); # Key from tree
609 IfEq $key, $k, # Found key
610 Then
611 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindComparison_equal, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
612 0 Return;
613 0 };
614 IfLt $key, $k, # Lower than current key
615 Then
616 {IfTrue Node_isLeaf($node), # Leaf
617 Then
618 0 ▶ {ReturnPut 0, FindResult_new($node, $key, FindComparison_lower, $i);
Subroutine __ANON__: not called CC=1 SCAR=6.9
619 0 Return;
620 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
621 0 Mov $node, Node_down($node, $i);
622 0 Jmp $end;
623 0 };
624 0 } $nl;
625 0 } MaxIterations;
626 0 Assert;
627 0 };
628  
629 0 ParamsPut 0, $tree; # Set parameters and call insert procedure
630 0 ParamsPut 1, $key;
631 0 Call $p;
632 0 ReturnGet 0;
633 }
634  
635 #D1 Insert # Create a new entry ina tree connecting a key to data.
636  
637 sub Insert($$$%) # Insert a key and its associated data into a tree.
638 0 ▶ {my ($tree, $key, $data, %options) = @_; # Tree, key, data
Subroutine Insert: not called CC=1 SCAR=6.9
Pod undocumented
639  
640 my $p = Procedure 'NWayTree_Insert', sub
641 0 ▶ {my ($p) = @_; # Procedure description
Subroutine __ANON__: not called CC=1 SCAR=6.9
642  
643 Block
644 0 ▶ {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
645  
646 0 my $tree = ParamsGet 0;
647 0 my $key = ParamsGet 1;
648 0 my $data = ParamsGet 2;
649 0 my $n = root($tree); # Root node of tree
650  
651 IfFalse $n, # Empty tree
652 Then
653 0 ▶ {my $n = Node_new($tree, length=>1);
Subroutine __ANON__: not called CC=1 SCAR=6.9
654 0 Node_setKeys ($n, 0, $key);
655 0 Node_setData ($n, 0, $data);
656 0 incKeys($tree);
657 0 setRoot($tree, $n);
658 0 Jmp $Finish;
659 0 };
660  
661 0 my $nl = Node_length($n); # Current length of node
662 IfLt $nl, maximumNumberOfKeys($tree), # Node has room for another key
663 Then
664 {IfFalse Node_up($n), # Root node
665 Then
666 {IfTrue Node_isLeaf($n),
667 Then
668 {For # Each key
669 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
670 0 my $k = Node_keys($n, $i); # Key to check
671 IfEq $key, $k, # Key already present
672 Then
673 0 ▶ {Node_setData($n, $i, $data);
Subroutine __ANON__: not called CC=1 SCAR=6.9
674 0 Jmp $Finish;
675 0 };
676 IfLt $key, $k, # We have reached the insertion point
677 Then
678 0 ▶ {my $nli = Subtract $nl, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
679 0 Node_openLeaf($n, $i, $nli, $key, $data);
680 0 incKeys($tree);
681 0 Jmp $Finish;
682 0 };
683 0 ▶ } $nl;
Subroutine __ANON__: not called CC=1 SCAR=6.9
684 0 Node_setKeys($n, $nl, $key); # Insert the key at the end of the block because it is greater than all the other keys in the block
685 0 Node_setData($n, $nl, $data);
686 0 my $nl1 = Add $nl, 1;
687 0 Node_setLength($n, $nl1);
688 0 incKeys($tree);
689 0 Jmp $Finish;
690 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
691 0 ▶ };
Subroutine __ANON__: not called CC=1 SCAR=6.9
692 0 };
693 # Insert node
694 0 my $r = FindAndSplit($tree, $key); # Check for existing key
695 0 my $N = FindResult_node($r);
696 0 my $c = FindResult_cmp($r);
697 0 my $i = FindResult_index($r);
698 0 Free $r, "FindResult";
699  
700 IfEq $c, FindComparison_equal, # Found an equal key whose data we can update
701 Then
702 0 ▶ {Node_setData($N, $i, $data);
Subroutine __ANON__: not called CC=1 SCAR=6.9
703 0 Jmp $Finish;
704 0 };
705  
706 0 my $Nl = Node_length($N);
707 0 my $Nl1 = Add $Nl, 1;
708 IfEq $c, FindComparison_higher, # Found a key that is greater than the one being inserted
709 Then
710 0 ▶ {my $i1 = Add $i, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
711 0 my $l = Subtract $Nl, $i1;
712 0 Node_openLeaf($N, $i1, $l, $key, $data);
713 },
714 Else
715 0 ▶ {my $l = Subtract $Nl, $i;
Subroutine __ANON__: not called CC=1 SCAR=6.9
716 0 Node_openLeaf($N, $i, $l, $key, $data);
717 0 };
718  
719 0 incKeys($tree);
720 0 Node_SplitIfFull($N); # Split if the leaf is full to force keys up the tree
721 0 };
722 0 Return;
723 0 };
724  
725 0 ParamsPut 0, $tree; # Set parameters and call insert procedure. As the tree parameter does not change very often the user has the option of setting it themselves out side of a loop.
726 0 ParamsPut 1, $key;
727 0 ParamsPut 2, $data;
728 0 Call $p;
729 }
730  
731 #D1 Iteration # Iterate over the keys and their associated data held in a tree.
732  
733 my sub GoAllTheWayLeft($) # Go as left as possible from the current node
734 0 ▶ {my ($node) = @_; # Node
Subroutine GoAllTheWayLeft: not called CC=1 SCAR=6.9
735 0 my $f = Var;
736  
737 IfFalse $node, # Empty tree
738 Then
739 0 ▶ {Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0);
Subroutine __ANON__: not called CC=1 SCAR=6.9
740 },
741 Else
742 {For # Step down through tree
743 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
744 IfTrue Node_isLeaf($node), # Reached leaf
745 Then
746 0 ▶ {Jmp $end;
Subroutine __ANON__: not called CC=1 SCAR=6.9
747 0 };
748 0 Mov $node, Node_down($node, 0);
749 0 ▶ } MaxIterations;
Subroutine __ANON__: not called CC=1 SCAR=6.9
750 0 Mov $f, FindResult_new($node, Node_keys($node, 0), FindComparison_equal, 0);# Leaf - place us on the first key
751 0 };
752 0 $f
753 }
754  
755 my sub GoUpAndAround($) # Go up until it is possible to go right or we can go no further
756 0 ▶ {my ($find) = @_; # Find
Subroutine GoUpAndAround: not called CC=1 SCAR=6.9
757 0 my $f = Var;
758 Block
759 0 ▶ {my ($Start, $Good, $Bad, $Finish) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
760 0 my $node = FindResult_node($find);
761  
762 IfTrue Node_isLeaf($node), # Leaf
763 Then
764 0 ▶ {my $I = FindResult_index($find);
Subroutine __ANON__: not called CC=1 SCAR=6.9
765 0 my $L = Node_length($node);
766 0 my $L1 = Subtract $L, 1;
767 IfLt $I, $L1, # More keys in leaf
768 Then
769 0 ▶ {my $i = Add $I, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
770 0 Mov $f, FindResult_new($node, Node_keys($node, $i),
771 FindComparison_equal, $i);
772 0 Jmp $Finish;
773 0 };
774  
775 0 my $parent = Node_up($node); # Parent
776 IfTrue $parent,
777 Then
778 {For # Not the only node in the tree
779 0 ▶ {my ($j, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
780 0 my $i = Node_indexInParent($node); # Index in parent
781  
782 IfEq $i, Node_length($parent), # Last key - continue up
783 Then
784 0 ▶ {Mov $node, $parent;
Subroutine __ANON__: not called CC=1 SCAR=6.9
785 0 my $Parent = Node_up($parent); # Parent
786 0 Mov $parent, $Parent;
787 IfFalse $parent,
788 Then
789 0 ▶ {Jmp $end;
Subroutine __ANON__: not called CC=1 SCAR=6.9
790 0 };
791 },
792 Else
793 0 ▶ {Mov $f, FindResult_new($parent, Node_keys($parent, $i), # Not the last key
Subroutine __ANON__: not called CC=1 SCAR=6.9
794 FindComparison_equal, $i);
795 0 Jmp $Finish;
796 0 };
797 0 ▶ } MaxIterations;
Subroutine __ANON__: not called CC=1 SCAR=6.9
798 0 };
799 0 Mov $f, FindResult_new($node, 0, FindComparison_notFound, 0); # Last key of root
800 0 Jmp $Finish;
801 0 };
802  
803 0 my $i = FindResult_index($find); # Not a leaf so on an interior key so we can go right then all the way left
804 0 my $I = Add $i, 1;
805 0 my $d = Node_down($node, $I);
806 0 Mov $f, GoAllTheWayLeft($d);
807 0 };
808 0 $f
809 }
810  
811 my sub IterStart($) # Start an iterator
812 0 ▶ {my ($tree) = @_; # Tree to iterate
Subroutine IterStart: not called CC=1 SCAR=6.9
813 0 my $n = root($tree);
814 0 GoAllTheWayLeft($n);
815 }
816  
817 my sub IterCheck($) # True if we can continue to iterate
818 0 ▶ {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
Subroutine IterCheck: not called CC=1 SCAR=6.9
819 0 my $r = Var;
820 IfEq FindResult_cmp($F), FindComparison_notFound,
821 Then
822 0 ▶ {Mov $r, 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
823 },
824 Else
825 0 ▶ {Mov $r, 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
826 0 };
827 0 $r
828 }
829  
830 my sub IterNext($) # Next element of an iteration
831 0 ▶ {my ($F) = @_; # Parameters (NWayTree(FindResult) const find) # Find result of last iteration
Subroutine IterNext: not called CC=1 SCAR=6.9
832 0 GoUpAndAround($F);
833 }
834  
835 sub Iterate(&$) # Iterate over a tree.
836 0 ▶ {my ($block, $tree) = @_; # Block of code to execute for each key in tree, tree
Subroutine Iterate: not called CC=1 SCAR=6.9
Pod undocumented
837 0 my $f = IterStart($tree);
838  
839 For
840 0 ▶ {my ($i, $check, $next, $end) = @_; # Parameters
Subroutine __ANON__: not called CC=1 SCAR=6.9
841  
842 IfFalse IterCheck($f),
843 Then
844 0 ▶ {Jmp $end;
Subroutine __ANON__: not called CC=1 SCAR=6.9
845 0 };
846  
847 0 &$block($f);
848  
849 0 my $F = Mov $f;
850 0 Mov $f, IterNext($f);
851 0 Free $F, "FindResult";
852 0 } 1e99;
853 }
854  
855 #D1 Print # Print trees horizontally.
856  
857 my sub printNode($$$$$) # Print the keys or data in a node in memory
858 0 ▶ {my ($memory, $node, $indent, $out, $keyNotData) = @_;
Subroutine printNode: not called CC=7 SCAR=40.3
859 0 ▶ ref($node) =~ m(Node) or confess "Not a node: ".dump($node);
Branch: 1 branch
BranchTrueFalseTotal
ref($node) =~ /Node/u or confess('Not a node: ' . Zero::NWayTree::dump($node)) 0 0 0
860 0 my $k = $$node[$Node->offset(q(keys))];
861 0 my $d = $$node[$Node->offset(q(data))];
862 0 my $n = $$node[$Node->offset(q(down))];
863  
864 0 ▶ if ($n) # Interior node
Branch: 1 branch
BranchTrueFalseTotal
if ($n) { } 0 0 0
865 0 {my $K = $$memory{$k};
866 0 my $D = $$memory{$d};
867 0 my $N = $$memory{$n};
868 0 my $l = $$node[$Node->offset(q(length))];
869  
870 0 for my $i(0..$l-1)
871 0 {my $c = $$memory{$$N[$i]}; # Child node
872 0 my $p = $$memory{$$c[$Node->offset(q(up))]};
873  
874 0 __SUB__->($memory, $c, $indent+1, $out, $keyNotData);
875 0 ▶ push @$out, [$indent, $keyNotData ? $$K[$i] : $$D[$i]];
Branch: 1 branch
BranchTrueFalseTotal
$keyNotData ? : 0 0 0
876 }
877  
878 0 __SUB__->($memory, $$memory{$$N[$l]}, $indent+1, $out, $keyNotData);
879 }
880  
881 else # Leaf node
882 0 {my $K = $$memory{$k};
883 0 my $D = $$memory{$d};
884 0 my $l = $$node[$Node->offset(q(length))];
885  
886 0 for my $i(0..$l-1)
887 0 {my $k = $$K[$i];
888 0 my $d = $$D[$i];
889 0 ▶ push @$out, [$indent, $keyNotData ? $k : $d];
Branch: 1 branch
BranchTrueFalseTotal
$keyNotData ? : 0 0 0
890 }
891 }
892 0 $out
893 }
894  
895 my sub printTree($$) # Print a tree
896 0 ▶ {my ($m, $keyNotData) = @_; # Memory, key or data
Subroutine printTree: not called CC=5 SCAR=34.0
897 0 my $t = $$m{1};
898 0 my $r = $$m{$$t[$Tree->offset(q(root))]};
899 0 my $o = printNode($m, $r, 0, [], $keyNotData);
900  
901 0 my $C = $#$o; # Number of columns
902 0 my $R = max(map {$$o[$_][0]} keys @$o); # Number of rows
903  
904 0 my $W = 3; # Field width for each key
905 0 my @o; # Output area
906 0 for my $r(0..$R)
907 0 {for my $c(0..$C)
908 0 {$o[$r][$c] = ' ' x $W;
909 }
910 }
911  
912 0 for my $p(keys @$o) # Write tree horizontally
913 0 ▶ {next unless defined(my $v = $$o[$p][1]);
Branch: 1 branch
BranchTrueFalseTotal
unless defined(my $v = $o->[$p][1]) 0 0 0
914 0 my $r = $$o[$p][0];
915 0 my $c = $p;
916  
917 0 $o[$r][$c] = sprintf("%${W}d", $v);
918 }
919  
920 0 join "\n", (map { (join "", $o[$_]->@*) =~ s(\s+\Z) ()r;} keys @o), ''; # As a single string after removing trailing spaces on each line
921 }
922  
923 sub printTreeKeys($) # Print the keys held in a tree.
924 0 ▶ {my ($m) = @_; # Memory
Subroutine printTreeKeys: not called CC=1 SCAR=6.9
Pod undocumented
925 0 printTree($m, 1);
926 }
927  
928 sub printTreeData($) # Print the data held in a tree.
929 0 ▶ {my ($m) = @_; # Memory
Subroutine printTreeData: not called CC=1 SCAR=6.9
Pod undocumented
930 0 printTree($m, 0);
931 }
932  
933 #D1 Utilities # Utility functions.
934  
935 sub randomArray($) # Create a random array.
936 0 ▶ {my ($N) = @_; # Size of array
Subroutine randomArray: not called CC=2 SCAR=17.9
Pod undocumented
937  
938 0 my @r = 1..$N;
939 0 srand(1);
940  
941 0 for my $i(keys @r) # Disarrange the array
942 0 {my $s = int rand @r;
943 0 my $t = int rand @r;
944 0 ($r[$t], $r[$s]) = ($r[$s], $r[$t]);
945 }
946 @r
947 0 }
948  
949 1 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
950 1 ▶use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS);
Subroutine BEGIN: called CC=1 SCAR=0.0
951  
952 1 @ISA = qw(Exporter);
953 1 @EXPORT = qw();
954 1 @EXPORT_OK = qw(Find FindResult_cmp FindResult_data FindResult_key Insert Iterate New printTreeKeys printTreeData randomArray);
955 #say STDERR '@EXPORT_OK = qw(', (join ' ', sort @EXPORT_OK), ');'; exit;
956 1 %EXPORT_TAGS = (all=>[@EXPORT, @EXPORT_OK]);
957  
958 1 ▶return 1 if caller;
Branch: 1 branch
BranchTrueFalseTotal
if caller 1 0 1
959  
960 #D0 Tests
961  
962 0 Test::More->builder->output("/dev/null"); # Reduce number of confirmation messages during testing
963  
964 0 eval {goto latest};
965  
966 sub is_deeply;
967 sub ok($;$);
968 sub done_testing;
969  
970 #latest:;
971 0 if (1)
972 0 {Start 1;
973 0 Out New(3);
974 0 my $e = Execute(suppressOutput=>1);
975 0 is_deeply $e->out, [1];
976 0 is_deeply $e->memory, { 1 => bless([0, 0, 3, 0], "Tree") };
977 }
978  
979 #latest:;
980 0 if (1)
981 0 {Start 1;
982 0 my $t = New(3);
983 0 my $r = root($t);
984  
985 0 setRoot($t, 1);
986 0 my $R = root($t);
987  
988 0 my $n = maximumNumberOfKeys($t);
989  
990 0 incKeys($t) for 1..3;
991 0 Out [$t, $Tree->address(q(keys)), 'Tree'];
992  
993 0 incNodes($t) for 1..5;
994 0 Out nodes($t);
995  
996 0 my $e = Execute(suppressOutput=>1);
997 0 is_deeply $e->out, [3, 5];
998 0 is_deeply $e->memory, { 1 => bless([3, 5, 3, 1], "Tree") };
999 }
1000  
1001 #latest:;
1002 0 if (1) #TNode_open
1003 0 {Start 1;
1004 0 my $t = New(7); # Create tree
1005 0 my $n = Node_new($t); # Create node
1006 0 my $e = Execute(suppressOutput=>1);
1007 0 is_deeply $e->memory, {
1008 1 => bless([0, 1, 7, 0], "Tree"),
1009 2 => bless([0, 1, 0, 1, 3, 4, 0], "Node"),
1010 3 => bless([], "Keys"),
1011 4 => bless([], "Data")};
1012 }
1013  
1014 #latest:;
1015 0 if (1) #TNode_open
1016 0 {Start 1;
1017 0 my $N = 7;
1018 0 my $t = New($N); # Create tree
1019 0 my $n = Node_new($t); # Create node
1020  
1021 0 Node_allocDown $n;
1022  
1023 0 for my $i(0..$N-1)
1024 0 {Node_setKeys($n, $i, 1+$i);
1025 0 Node_setData($n, $i, 11+$i);
1026 0 Node_setDown($n, $i, 21+$i);
1027 }
1028  
1029 0 Node_setDown($n, $N, 28);
1030  
1031 0 Node_open($n, 2, 4, 3, 13);
1032 0 my $e = Execute(suppressOutput=>1);
1033  
1034 0 is_deeply $e->memory, {
1035 1 => bless([0, 1, 7, 0], "Tree"),
1036 2 => bless([1, 1, 0, 1, 3, 4, 5], "Node"),
1037 3 => bless([1, 2, 3, 3 .. 7], "Keys"),
1038 4 => bless([11, 12, 13, 13 .. 17], "Data"),
1039 5 => bless([21, 22, 23, 0, 24 .. 28], "Down")};
1040 }
1041  
1042 #latest:;
1043 0 if (1) #TNode_copy
1044 0 {Start 1;
1045 0 my $t = New(7); # Create tree
1046 0 my $p = Node_new($t); Node_allocDown($p); # Create a node
1047 0 my $q = Node_new($t); Node_allocDown($q); # Create a node
1048  
1049 0 for my $i(0..6)
1050 0 {Node_setKeys($p, $i, 11+$i);
1051 0 Node_setData($p, $i, 21+$i);
1052 0 Node_setDown($p, $i, 31+$i);
1053 0 Node_setKeys($q, $i, 41+$i);
1054 0 Node_setData($q, $i, 51+$i);
1055 0 Node_setDown($q, $i, 61+$i);
1056 }
1057  
1058 0 Node_setDown($p, 7, 97);
1059 0 Node_setDown($q, 7, 99);
1060  
1061 0 Node_copy( $q, $p, 1, 3, 2);
1062  
1063 0 my $e = Execute(suppressOutput=>1);
1064  
1065 0 is_deeply $e->memory, {
1066 1 => bless([0, 2, 7, 0], "Tree"),
1067 2 => bless([0, 1, 0, 1, 3, 4, 5], "Node"),
1068 3 => bless([11 .. 17], "Keys"),
1069 4 => bless([21 .. 27], "Data"),
1070 5 => bless([31 .. 37, 97], "Down"),
1071 6 => bless([0, 2, 0, 1, 7, 8, 9], "Node"),
1072 7 => bless([41, 14, 15, 44 .. 47], "Keys"),
1073 8 => bless([51, 24, 25, 54 .. 57], "Data"),
1074 9 => bless([61, 34, 35, 36, 65, 66, 67, 99], "Down")}
1075 }
1076  
1077 #latest:;
1078 0 if (1) #TFindResult_new #TFindResult_cmp
1079 0 {Start 1;
1080 0 my $f = FindResult_new(1, 2, 3, 4);
1081 0 my $n = FindResult_node($f);
1082 0 my $k = FindResult_key($f);
1083 0 my $c = FindResult_cmp($f);
1084 0 my $i = FindResult_index($f);
1085 0 Out $_ for $n, $c, $k, $i;
1086 0 my $e = Execute(suppressOutput=>1);
1087 0 is_deeply $e->out, [1, 3, 2, 4];
1088 0 is_deeply $e->memory, {1=>[1, 3, 2, 4]};
1089 }
1090  
1091 #latest:;
1092 0 if (1) #TInsert
1093 0 {Start 1;
1094 0 my $t = New(3); # Create tree
1095 0 my $f = Find($t, 1);
1096 0 my $c = FindResult_cmp($f);
1097 0 AssertEq($c, FindComparison_notFound);
1098 0 my $e = Execute(suppressOutput=>1);
1099 0 is_deeply $e->out, [];
1100 }
1101  
1102 #latest:;
1103 0 if (1) #TInsert
1104 0 {Start 1;
1105 0 my $t = New(3);
1106 0 Insert($t, 1, 11);
1107 0 my $e = Execute(suppressOutput=>1);
1108  
1109 0 is_deeply $e->memory, {
1110 1 => bless([1, 1, 3, 2], "Tree"),
1111 2 => bless([1, 1, 0, 1, 3, 4, 0], "Node"),
1112 3 => bless([1], "Keys"),
1113 4 => bless([11], "Data")};
1114 }
1115  
1116 #latest:;
1117 0 if (1) #TInsert
1118 0 {Start 1;
1119 0 my $t = New(3);
1120 0 Insert($t, 1, 11);
1121 0 Insert($t, 2, 22);
1122 0 my $e = Execute(suppressOutput=>1);
1123  
1124 0 is_deeply $e->memory, {
1125 1 => bless([2, 1, 3, 2], "Tree"),
1126 2 => bless([2, 1, 0, 1, 3, 4, 0], "Node"),
1127 3 => bless([1, 2], "Keys"),
1128 4 => bless([11, 22], "Data")};
1129 }
1130  
1131 #latest:;
1132 0 if (1) #TInsert
1133 0 {Start 1;
1134 0 my $t = New(3);
1135 0 Insert($t, $_, "$_$_") for 1..3;
1136 0 my $e = Execute(suppressOutput=>1);
1137  
1138 0 is_deeply $e->memory, {
1139 1 => bless([3, 1, 3, 2], "Tree"),
1140 2 => bless([3, 1, 0, 1, 3, 4, 0], "Node"),
1141 3 => bless([1, 2, 3], "Keys"),
1142 4 => bless([11, 22, 33], "Data")}
1143 }
1144  
1145 #latest:;
1146 0 if (1) #TInsert
1147 0 {Start 1;
1148 0 my $t = New(3);
1149 0 Insert($t, $_, "$_$_") for 1..4;
1150 0 my $e = Execute(suppressOutput=>1);
1151  
1152 0 is_deeply $e->memory, {
1153 1 => bless([4, 3, 3, 2], "Tree"),
1154 2 => bless([1, 1, 0, 1, 3, 4, 11], "Node"),
1155 3 => bless([2], "Keys"),
1156 4 => bless([22], "Data"),
1157 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1158 6 => bless([1], "Keys"),
1159 7 => bless([11], "Data"),
1160 8 => bless([2, 3, 2, 1, 9, 10, 0], "Node"),
1161 9 => bless([3, 4], "Keys"),
1162 10 => bless([33, 44], "Data"),
1163 11 => bless([5, 8], "Down"),
1164 };
1165 }
1166  
1167 #latest:;
1168 0 if (1) #TInsert
1169 0 {Start 1;
1170 0 my $t = New(3);
1171 0 Insert($t, $_, "$_$_") for 1..5;
1172  
1173 0 my $e = Execute(suppressOutput=>1);
1174  
1175 0 is_deeply $e->memory, {
1176 1 => bless([5, 5, 3, 2], "Tree"),
1177 2 => bless([2, 1, 0, 1, 3, 4, 11], "Node"),
1178 3 => bless([2, 4], "Keys"),
1179 4 => bless([22, 44], "Data"),
1180 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1181 6 => bless([1], "Keys"),
1182 7 => bless([11], "Data"),
1183 11 => bless([5, 14, 17], "Down"),
1184 14 => bless([1, 4, 2, 1, 15, 16, 0], "Node"),
1185 15 => bless([3], "Keys"),
1186 16 => bless([33], "Data"),
1187 17 => bless([1, 5, 2, 1, 18, 19, 0], "Node"),
1188 18 => bless([5], "Keys"),
1189 19 => bless([55], "Data")}
1190 }
1191  
1192 #latest:;
1193 0 if (1) #TInsert
1194 0 {Start 1;
1195 0 my $t = New(3);
1196 0 Insert($t, $_, "$_$_") for 1..6;
1197 0 my $e = Execute(suppressOutput=>1);
1198  
1199 0 is_deeply $e->memory, {
1200 1 => bless([6, 5, 3, 2], "Tree"),
1201 2 => bless([2, 1, 0, 1, 3, 4, 11], "Node"),
1202 3 => bless([2, 4], "Keys"),
1203 4 => bless([22, 44], "Data"),
1204 5 => bless([1, 2, 2, 1, 6, 7, 0], "Node"),
1205 6 => bless([1], "Keys"),
1206 7 => bless([11], "Data"),
1207 11 => bless([5, 14, 17], "Down"),
1208 14 => bless([1, 4, 2, 1, 15, 16, 0], "Node"),
1209 15 => bless([3], "Keys"),
1210 16 => bless([33], "Data"),
1211 17 => bless([2, 5, 2, 1, 18, 19, 0], "Node"),
1212 18 => bless([5, 6], "Keys"),
1213 19 => bless([55, 66], "Data")};
1214 }
1215  
1216 #latest:;
1217 0 if (1) #TNew #TInsert
1218 0 {my $W = 3; my $N = 66; my @r = randomArray $N;
1219  
1220 0 Start 1;
1221 0 my $t = New($W);
1222  
1223 0 for my $i(1..$N)
1224 0 {Insert($t, $r[$i-1], $r[$i-1]);
1225 }
1226  
1227 0 my $e = Execute(suppressOutput=>1);
1228 0 is_deeply printTreeKeys($e->memory), <<END;
1229 30
1230 13 44 55
1231 7 20 25 37 50 61
1232 2 4 9 11 15 17 23 27 33 35 39 41 47 52 58 63 65
1233 1 3 5 6 8 10 12 14 16 18 19 21 22 24 26 28 29 31 32 34 36 38 40 42 43 45 46 48 49 51 53 54 56 57 59 60 62 64 66
1234 END
1235 }
1236  
1237 #latest:;
1238 0 if (1) # Print tree - random - 5
1239 0 {my $W = 5; my $N = 66; my @r = randomArray $N;
1240  
1241 0 Start 1;
1242 0 my $t = New($W);
1243  
1244 0 for my $i(1..$N)
1245 0 {Insert($t, $r[$i-1], $r[$i-1]);
1246 }
1247  
1248 0 my $e = Execute(suppressOutput=>1);
1249 0 is_deeply printTreeKeys($e->memory), <<END;
1250 23 39 51
1251 4 7 12 17 20 27 30 33 36 43 47 55 58 62
1252 1 2 3 5 6 8 9 10 11 13 14 15 16 18 19 21 22 24 25 26 28 29 31 32 34 35 37 38 40 41 42 44 45 46 48 49 50 52 53 54 56 57 59 60 61 63 64 65 66
1253 END
1254 }
1255  
1256 #latest:;
1257 0 if (1) # Print tree keys
1258 0 {my $W = 3; my $N = 65;
1259  
1260 0 Start 1;
1261 0 my $t = New($W);
1262  
1263 0 for my $i(1..$N)
1264 0 {Insert($t, $i, $i);
1265 }
1266  
1267 0 my $e = Execute(suppressOutput=>1);
1268 0 is_deeply printTreeKeys($e->memory), <<END;
1269 16 32
1270 8 24 40 48 56
1271 4 12 20 28 36 44 52 60
1272 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 64
1273 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1274 END
1275 }
1276  
1277 #latest:;
1278 0 if (1) # Print tree keys - reverse
1279 0 {my $W = 3; my $N = 65;
1280  
1281 0 Start 1;
1282 0 my $t = New($W);
1283  
1284 0 for my $i(reverse 1..$N)
1285 0 {Insert($t, $i, $i);
1286 }
1287  
1288 0 my $e = Execute(suppressOutput=>1);
1289 0 is_deeply printTreeKeys($e->memory), <<END;
1290 34 50
1291 10 18 26 42 58
1292 6 14 22 30 38 46 54 62
1293 2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
1294 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1295 END
1296 }
1297  
1298 #latest:;
1299 0 if (1) # Print tree data
1300 0 {my $W = 3; my $N = 65;
1301  
1302 0 Start 1;
1303 0 my $t = New($W);
1304  
1305 0 for my $i(1..$N)
1306 0 {Insert($t, $i, $i);
1307 }
1308  
1309 0 my $e = Execute(suppressOutput=>1);
1310 0 is_deeply printTreeKeys($e->memory), <<END;
1311 16 32
1312 8 24 40 48 56
1313 4 12 20 28 36 44 52 60
1314 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 64
1315 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1316 END
1317 }
1318  
1319 #latest:;
1320 0 if (1) # Print tree data - reverse
1321 0 {my $W = 3; my $N = 65;
1322  
1323 0 Start 1;
1324 0 my $t = New($W);
1325  
1326 0 for my $i(reverse 1..$N)
1327 0 {Insert($t, $i, $i);
1328 }
1329  
1330 0 my $e = Execute(suppressOutput=>1);
1331 0 is_deeply printTreeData($e->memory), <<END;
1332 34 50
1333 10 18 26 42 58
1334 6 14 22 30 38 46 54 62
1335 2 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
1336 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65
1337 END
1338 }
1339  
1340 #latest:;
1341 0 if (1) # Compare trees of keys and data
1342 0 {my $W = 3; my $N = 165; my @r = randomArray $N;
1343  
1344 0 Start 1;
1345 0 my $t = New($W);
1346  
1347 0 for my $i(0..$N-1)
1348 0 {Insert($t, $r[$i], $r[$i]);
1349 }
1350  
1351 0 my $e = Execute(suppressOutput=>1);
1352 0 is_deeply printTreeKeys($e->memory),
1353 printTreeData($e->memory);
1354 }
1355  
1356 #latest:;
1357 0 if (1) #TprintTreeKeys #TprintTreeData
1358 0 {my $W = 7; my $N = 165; my @r = randomArray $N;
1359  
1360 0 Start 1;
1361 0 my $t = New($W);
1362  
1363 0 for my $i(0..$N-1)
1364 0 {Insert($t, $r[$i], $r[$i]);
1365 }
1366  
1367 0 my $e = Execute(suppressOutput=>1);
1368 0 is_deeply printTreeKeys($e->memory),
1369 printTreeData($e->memory);
1370 }
1371  
1372 #latest:;
1373 0 if (1) # Compare trees of keys and data
1374 0 {my $W = 3; my $N = 75; my @r = randomArray $N;
1375  
1376 0 Start 1;
1377 0 my $t = New($W);
1378  
1379 0 for my $i(0..$N-1)
1380 0 {Insert($t, $r[$i], $r[$i]);
1381 }
1382  
1383 Iterate # Iterate tree
1384 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1385 0 my $k = FindResult_key($find);
1386 0 Out $k;
1387 0 } $t;
1388  
1389 0 my $e = Execute(suppressOutput=>1);
1390 0 is_deeply $e->out, [1..$N];
1391 }
1392  
1393 #latest:;
1394 0 if (1) #TrandomArray
1395 0 {my $W = 3; my $N = 76; my @r = randomArray $N;
1396  
1397 0 Start 1;
1398 0 my $t = New($W);
1399  
1400 0 for my $i(0..$N-1)
1401 0 {Insert($t, $r[$i], $r[$i]);
1402 }
1403  
1404 Iterate # Iterate tree
1405 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1406 0 my $k = FindResult_key($find);
1407 0 Out $k;
1408 0 } $t;
1409  
1410 0 my $e = Execute(suppressOutput=>1);
1411 0 is_deeply $e->out, [1..$N];
1412 }
1413  
1414 #latest:;
1415 0 if (1) #TIterate #TKeys #TFindResult_key #TFindResult_data #TFind
1416 0 {my $W = 3; my $N = 107; my @r = randomArray $N;
1417  
1418 0 Start 1;
1419 0 my $t = New($W); # Create tree at expected location in memory
1420  
1421 0 my $a = Array "aaa";
1422 0 for my $I(1..$N) # Load array
1423 0 {my $i = $I-1;
1424 0 Mov [$a, $i, "aaa"], $r[$i];
1425 }
1426  
1427 ForArray # Create tree
1428 0 ▶ {my ($i, $k) = @_;
Subroutine __ANON__: not called CC=1 SCAR=6.9
1429 0 my $n = Keys($t);
1430 0 AssertEq $n, $i; # Check tree size
1431 0 my $K = Add $k, $k;
1432 0 Tally 1;
1433 0 Insert($t, $k, $K); # Insert a new node
1434 0 Tally 0;
1435 0 } $a, q(aaa);
1436  
1437 Iterate # Iterate tree
1438 0 ▶ {my ($find) = @_; # Find result
Subroutine __ANON__: not called CC=1 SCAR=6.9
1439 0 my $k = FindResult_key($find);
1440 0 Out $k;
1441 0 my $f = Find($t, $k); # Find
1442 0 my $d = FindResult_data($f);
1443 0 my $K = Add $k, $k;
1444 0 AssertEq $K, $d; # Check result
1445 0 } $t;
1446  
1447 0 my $e = Execute(suppressOutput=>1);
1448  
1449 0 is_deeply $e->out, [1..$N]; # Expected sequence
1450  
1451 0 is_deeply $e->tallyCount, 26177; # Insertion instruction counts
1452 0 is_deeply $e->tallyCounts->{1}, {
1453 add => 860,
1454 array => 607,
1455 call => 107,
1456 free => 360,
1457 inc => 1044,
1458 jEq => 631,
1459 jGe => 1667,
1460 jLe => 461,
1461 jLt => 565,
1462 jmp => 1436,
1463 jNe => 1095,
1464 mov => 12328,
1465 not => 695,
1466 paramsGet => 321,
1467 paramsPut => 321,
1468 resize => 12,
1469 return => 107,
1470 shiftRight => 68,
1471 shiftUp => 300,
1472 subtract => 641,
1473 tracePoint => 2551,
1474 };
1475 }
1476  
1477 0 done_testing;
1478  
1479 # (\A.{80})\s+(#.*\Z) \1\2
« lib/Zero/Emulator.pm ↑ Summary blib/lib/Zero/NWayTree.pm »