NWayTree.pm

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