blib/lib/Silicon/Chip/Btree.pm

filter: Statementstmt 88.2% 15 / 17 Branchbran n/a Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 6 / 6 Podpod n/a totaltotal 91.3% 21 / 23 CC 1 SCAR 0.5
CC
1
Cov
88%
BEGIN
1.3
BEGIN
1.0
BEGIN
1.0
CRAP 1.0
↑ Summary
1 #!/usr/bin/perl -I/home/phil/perl/cpan/SvgSimple/lib/ -I/home/phil/perl/cpan/SiliconChip/lib/
2 #-------------------------------------------------------------------------------
3 # Implement a B-Tree as a silicon chip.
4 # Philip R Brenan at appaapps dot com, Appa Apps Ltd Inc., 2023
5 #-------------------------------------------------------------------------------
6 1 ▶use v5.34;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 package Silicon::Chip::Btree;
8 our $VERSION = 20231112; # Version
9 1 ▶use warnings FATAL => qw(all);
Subroutine BEGIN: called CC=1 SCAR=0.0
10 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 1 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 1 ▶use Data::Dump qw(dump);
Subroutine BEGIN: called CC=1 SCAR=0.0
13 0 ▶use Data::Table::Text qw(:all);
Subroutine BEGIN: called CC=1 SCAR=2.6
14 use Silicon::Chip qw(:all);
15  
16 makeDieConfess;
17  
18 #D1 B-Tree Node # A node in a B-Tree containing keys, data and links to other nodes. Nodes only produce output when their preset id is present on their enable bus. This makes it possible for one node to select another node for further processing of the key being sought.
19  
20 sub newBtreeNodeCompare($$$$$$$$$$$%) # Create a new B-Tree node. The node is activated only when its preset id appears on its enable bus otherwise it produces zeroes regardless of its inputs.
21 {my ($chip, $id, $output, $enable, $find, $keys, $data, $next, $top, $N, $B, %options) = @_; # Chip, numeric id of this node, output name, enable bus, key to find, keys to search, data corresponding to keys, next links, top next link, maximum number of keys in a node, size of key in bits, options
22 @_ >= 11 or confess "Eleven or more parameters";
23  
24 my @B = ($N, $B);
25 my $O = $output;
26 my $C = $chip;
27  
28 my sub aa($) {my ($n) = @_; "$O.$n"} # Create an internal gate name for this node
29  
30 my sub id () {aa "id"} #i Id for this node
31 my sub en () {aa "enabled"} #i Enable code
32 my sub pe () {aa "maskEqual"} #i Point mask showing key equal to search key
33 my sub mm () {aa "maskMore"} #i Monotone mask showing keys more than the search key
34 my sub dfo() {aa "dataFound"} #O The data corresponding to the key found or zero if not found
35 my sub df () {aa "dataFound1"}
36 my sub df2() {aa "dataFound2"}
37 my sub fo() {aa "found"} #O Whether a matching key was found
38 my sub f () {aa "found1"}
39 my sub f2() {aa "found2"}
40 my sub mf () {aa "moreFound"} #i The next link for the first key greater than the search key is such a key is present int the node
41 my sub nm () {aa "noMore"} #i No key in the node is greater than the search key
42 my sub nfo() {aa "nextLink"} #O The next link for the found key if any
43 my sub nf () {aa "nextLink1"}
44 my sub nf2() {aa "nextLink2"}
45 my sub pm () {aa "pointMore"} #i Point mask showing the first key in the node greater than the search key
46  
47 $N > 2 or confess <<"END";
48 The number of keys the node can hold must be greater than 2, not $N
49 END
50  
51 $N % 2 or confess <<"END";
52 The number of keys the node can hold must be odd, not even: $N
53 END
54 $C->bits(id, $B, $id); # Save id of node
55 $C->compareEq(en, id, $enable, %options); # Check whether this node is enabled
56  
57 for my $i(1..$N)
58 {$C->compareEq(n(pe, $i), n($keys, $i), $find, %options); # Compare equal point mask
59 $C->compareGt(n(mm, $i), n($keys, $i), $find, %options); # Compare more monotone mask
60 }
61 $C->setSizeBits($_, $N) for pe, mm;
62  
63 $C->chooseWordUnderMask (df2, $data, pe, %options); # Choose data under equals mask
64 $C->orBits (f2, pe, %options); # Show whether key was found
65  
66 $C->norBits (nm, mm, %options); # True if the more monotone mask is all zero indicating that all of the keys in the node are less than or equal to the search key
67 $C->monotoneMaskToPointMask(pm, mm, %options); # Convert monotone more mask to point mask
68 $C->chooseWordUnderMask (mf, $next, pm, %options); # Choose next link using point mask from the more monotone mask created
69 $C->chooseFromTwoWords (nf2, mf, $top, nm, %options); # Show whether key was found
70  
71 $C->enableWord (df, df2, en, %options); # Enable data found
72 $C->outputBits (dfo, df, %options); # Enable data found output
73  
74 $C->and (f, [f2, en]); # Enable found flag
75 $C->output (fo, f, %options); # Enable found flag output
76  
77 $C->enableWord (nf, nf2, en, %options); # Enable next link
78 $C->outputBits (nfo, nf, %options); # Enable next link output
79 $C
80 }
81  
82 my $BtreeNodeIds = 0; # Create unique ids for nodes
83  
84 sub newBtreeNode($$$$%) # Create a new B-Tree node. The node is activated only when its preset id appears on its enable bus otherwise it produces zeroes regardless of its inputs.
85 {my ($chip, $output, $N, $B, %options) = @_; # Chip, name prefix for node, maximum number of keys in a node, size of key in bits, options
86 @_ >= 4 or confess "Four or more parameters";
87 my $c = $chip;
88 my @b = qw(enable find top);
89 my @w = qw(keys data next);
90 my @B = qw(found);
91 my @W = qw(dataFound nextLink);
92  
93 my $id = ++$BtreeNodeIds; # Node number used to identify the node
94 my sub n($)
95 {my ($name) = @_; # Options
96 "$output.$id.$name"
97 }
98  
99 $c->inputBits (n($_), $B) for @b; # Input bits
100 $c->inputWords(n($_), $N, $B) for @w; # Input words
101  
102 &newBtreeNodeCompare($c, $id, # B-Tree node
103 "$output.$id", (map {n($_)} qw(enable find keys data next top)), $N, $B);
104  
105 genHash("Silicon::Chip::Btree::Node", # Node in B-Tree
106 (map {($_=>n($_))} @b, @w, @B, @W),
107 chip => $chip,
108 id => $id,
109 )
110 }
111  
112 =pod
113  
114 =encoding utf-8
115  
116 =for html <p><a href="https://github.com/philiprbrenan/SiliconChipBtree"><img src="https://github.com/philiprbrenan/SiliconChipBtree/workflows/Test/badge.svg"></a>
117  
118 =head1 Name
119  
120 Silicon::Chip::Btree - Implement a B-Tree as a silicon chip.
121  
122 =head1 Synopsis
123  
124 =head1 Description
125  
126 Implement a B-Tree as a silicon chip.
127  
128  
129 Version 20231112.
130  
131  
132 The following sections describe the methods in each functional area of this
133 module. For an alphabetic listing of all methods by name see L<Index|/Index>.
134  
135  
136  
137 =head1 B-Tree Node
138  
139 A node in a B-Tree containing keys, data and links to other nodes. Nodes only produce output when their preset id is present on their enable bus. This makes it possible for one node to select another node for further processing of the key being sought.
140  
141 =head2 newBtreeNodeCompareย ($chip, $id, $output, $enable, $find, $keys, $data, $next, $top, $N, $B, %options)
142  
143 Create a new B-Tree node. The node is activated only when its preset id appears on its enable bus otherwise it produces zeroes regardless of its inputs.
144  
145 Parameter Description
146 1 $chip Chip
147 2 $id Numeric id of this node
148 3 $output Output name
149 4 $enable Enable bus
150 5 $find Key to find
151 6 $keys Keys to search
152 7 $data Data corresponding to keys
153 8 $next Next links
154 9 $top Top next link
155 10 $N Maximum number of keys in a node
156 11 $B Size of key in bits
157 12 %options Options
158  
159 B<Example:>
160  
161  
162 if (1)
163 {my $B = 3; my $N = 3; my $id = 5;
164
165 my $c = Silicon::Chip::newChip;
166
167 $c->inputBits ("enable", $B); # Enable - the node only operates if this value matches its preset id
168 $c->inputBits ("find", $B); # Key to search for
169 $c->inputWords("keys", $N, $B); # Keys to search
170 $c->inputWords("data", $N, $B); # Data associated with each key
171 $c->inputWords("next", $N, $B); # Next node associated with each key
172 $c->inputBits ("top", $B); # Top next node
173
174
175 &newBtreeNodeCompare($c, $id, qw(out enable find keys data next top),$N,$B);# B-Tree node # ๐—˜๐˜…๐—ฎ๐—บ๐—ฝ๐—น๐—ฒ
176  
177
178 my sub test($) # Find keys in a node
179 {my ($f) = @_;
180
181 my %e = $c->setBits ("enable", $id);
182 my %f = $c->setBits ("find", $f);
183 my %t = $c->setBits ("top", $N+1);
184 my %k = $c->setWords("keys", 1..$N);
185 my %d = $c->setWords("data", 1..$N);
186 my %n = $c->setWords("next", 1..$N);
187 my $i = {%e, %f, %k, %d, %n, %t};
188 my $s = $c->simulate($i, $f == 2 ? (svg=>q(svg/btreeNode)) : ());
189
190 is_deeply($s->steps, 11);
191 is_deeply($s->value("out.found"), $f >= 1 && $f <= $N ? 1 : 0);
192 is_deeply($s->bint ("out.dataFound"), $f <= $N ? $f : 0);
193 is_deeply($s->bint ("out.nextLink"), $f <= $N ? $f+1 : $N+1);
194 }
195 test($_) for 0..$N+1;
196
197 my sub test2($) # Find and not find keys in a node
198 {my ($f) = @_;
199
200 my %e = setBits ($c, "enable", $id);
201 my %f = setBits ($c, "find", $f);
202 my %t = setBits ($c, "top", 2*$N+1);
203 my %k = setWords($c, "keys", map {2*$_} 1..$N);
204 my %d = setWords($c, "data", 1..$N);
205 my %n = setWords($c, "next", map {2*$_-1} 1..$N);
206 my $i = {%e, %f, %k, %d, %n, %t};
207 my $s = $c->simulate($i);
208
209 is_deeply($s->steps, 11);
210 is_deeply($s->value('out.found'), $f == 0 || $f % 2 ? 0 : 1);
211 is_deeply($s->bint ("out.dataFound"), $f % 2 ? 0 : $f / 2);
212 is_deeply($s->bint ("out.nextLink"), $f + ($f % 2 ? 0 : 1)) if $f <= 2*$N ;
213 }
214 test2($_) for 0..2*$N+1;
215
216 my sub test3($) # Not enabled so only ever outputs 0
217 {my ($f) = @_;
218
219 my %e = setBits ($c, "enable", 0); # Disable
220 my %f = setBits ($c, "find", $f);
221 my %t = setBits ($c, "top", 2*$N+1);
222 my %k = setWords($c, "keys", map {2*$_} 1..$N);
223 my %d = setWords($c, "data", 1..$N);
224 my %n = setWords($c, "next", map {2*$_-1} 1..$N);
225 my $i = {%e, %f, %k, %d, %n, %t};
226 my $s = $c->simulate($i);
227
228 is_deeply($s->steps, 11);
229 is_deeply($s->value("out.found"), 0);
230 is_deeply($s->bint ("out.dataFound"), 0);
231 is_deeply($s->bint ("out.nextLink"), 0);
232 }
233 test3($_) for 0..2*$N+1;
234 }
235
236  
237 =for html <img src="https://raw.githubusercontent.com/philiprbrenan/SiliconChipBtree/main/lib/Silicon/Chip/svg/btreeNode.svg">
238
239  
240 =head2 newBtreeNode($chip, $output, $N, $B, %options)
241  
242 Create a new B-Tree node. The node is activated only when its preset id appears on its enable bus otherwise it produces zeroes regardless of its inputs.
243  
244 Parameter Description
245 1 $chip Chip
246 2 $output Name prefix for node
247 3 $N Maximum number of keys in a node
248 4 $B Size of key in bits
249 5 %options Options
250  
251 B<Example:>
252  
253  
254 if (1)
255 {my $B = 3; my $N = 3;
256
257 my $c = Silicon::Chip::newChip;
258
259 my @n = map {newBtreeNode($c, "n", $N, $B)} 1..3; # B-Tree node # ๐—˜๐˜…๐—ฎ๐—บ๐—ฝ๐—น๐—ฒ
260  
261
262 my %e = map {setBits ($c, $_->enable, 1) } @n;
263 my %f = map {setBits ($c, $_->find, 2) } @n;
264 my %t = map {setBits ($c, $_->top, 2*$N+1) } @n;
265 my %k = map {setWords($c, $_->keys, map {2*$_} 1..$N)} @n;
266 my %d = map {setWords($c, $_->data, 1..$N)} @n;
267 my %n = map {setWords($c, $_->next, map {2*$_-1} 1..$N)} @n;
268 my $i = {%e, %f, %k, %d, %n, %t};
269
270 my $s = $c->simulate($i, svg=>q(svg/btreeNode));
271 is_deeply($s->value($n[0]->found), 1);
272 is_deeply($s->bint ($n[0]->dataFound), 1);
273 is_deeply($s->bint ($n[0]->nextLink), 3);
274 }
275
276  
277  
278 =head1 Index
279  
280  
281 1 L<newBtreeNode|/newBtreeNode> - Create a new B-Tree node.
282  
283 2 L<newBtreeNodeCompare|/newBtreeNodeCompare> - Create a new B-Tree node.
284  
285 =head1 Installation
286  
287 This module is written in 100% Pure Perl and, thus, it is easy to read,
288 comprehend, use, modify and install via B<cpan>:
289  
290 sudo cpan install Silicon::Chip::Btree
291  
292 =head1 Author
293  
294 L<philiprbrenan@gmail.com|mailto:philiprbrenan@gmail.com>
295  
296 L<http://www.appaapps.com|http://www.appaapps.com>
297  
298 =head1 Copyright
299  
300 Copyright (c) 2016-2023 Philip R Brenan.
301  
302 This module is free software. It may be used, redistributed and/or modified
303 under the same terms as Perl itself.
304  
305 =cut
306  
307  
308  
309 #D0 Tests # Tests and examples
310 goto finish if caller; # Skip testing if we are being called as a module
311 clearFolder(q(svg), 99); # Clear the output svg folder
312 eval "use Test::More qw(no_plan);";
313 eval "Test::More->builder->output('/dev/null');" if -e q(/home/phil/);
314 eval {goto latest};
315  
316 #svg https://raw.githubusercontent.com/philiprbrenan/SiliconChipBtree/main/lib/Silicon/Chip/
317  
318 #latest:;
319 if (1) #TnewBtreeNodeCompare
320 {my $B = 3; my $N = 3; my $id = 5;
321  
322 my $c = Silicon::Chip::newChip;
323  
324 $c->inputBits ("enable", $B); # Enable - the node only operates if this value matches its preset id
325 $c->inputBits ("find", $B); # Key to search for
326 $c->inputWords("keys", $N, $B); # Keys to search
327 $c->inputWords("data", $N, $B); # Data associated with each key
328 $c->inputWords("next", $N, $B); # Next node associated with each key
329 $c->inputBits ("top", $B); # Top next node
330  
331 &newBtreeNodeCompare($c, $id, qw(out enable find keys data next top),$N,$B);# B-Tree node
332  
333 my sub test($) # Find keys in a node
334 {my ($f) = @_;
335  
336 my %e = $c->setBits ("enable", $id);
337 my %f = $c->setBits ("find", $f);
338 my %t = $c->setBits ("top", $N+1);
339 my %k = $c->setWords("keys", 1..$N);
340 my %d = $c->setWords("data", 1..$N);
341 my %n = $c->setWords("next", 1..$N);
342 my $i = {%e, %f, %k, %d, %n, %t};
343 my $s = $c->simulate($i, $f == 2 ? (svg=>q(svg/btreeNode)) : ());
344  
345 is_deeply($s->steps, 11);
346 is_deeply($s->value("out.found"), $f >= 1 && $f <= $N ? 1 : 0);
347 is_deeply($s->bint ("out.dataFound"), $f <= $N ? $f : 0);
348 is_deeply($s->bint ("out.nextLink"), $f <= $N ? $f+1 : $N+1);
349 }
350 test($_) for 0..$N+1;
351  
352 my sub test2($) # Find and not find keys in a node
353 {my ($f) = @_;
354  
355 my %e = setBits ($c, "enable", $id);
356 my %f = setBits ($c, "find", $f);
357 my %t = setBits ($c, "top", 2*$N+1);
358 my %k = setWords($c, "keys", map {2*$_} 1..$N);
359 my %d = setWords($c, "data", 1..$N);
360 my %n = setWords($c, "next", map {2*$_-1} 1..$N);
361 my $i = {%e, %f, %k, %d, %n, %t};
362 my $s = $c->simulate($i);
363  
364 is_deeply($s->steps, 11);
365 is_deeply($s->value('out.found'), $f == 0 || $f % 2 ? 0 : 1);
366 is_deeply($s->bint ("out.dataFound"), $f % 2 ? 0 : $f / 2);
367 is_deeply($s->bint ("out.nextLink"), $f + ($f % 2 ? 0 : 1)) if $f <= 2*$N ;
368 }
369 test2($_) for 0..2*$N+1;
370  
371 my sub test3($) # Not enabled so only ever outputs 0
372 {my ($f) = @_;
373  
374 my %e = setBits ($c, "enable", 0); # Disable
375 my %f = setBits ($c, "find", $f);
376 my %t = setBits ($c, "top", 2*$N+1);
377 my %k = setWords($c, "keys", map {2*$_} 1..$N);
378 my %d = setWords($c, "data", 1..$N);
379 my %n = setWords($c, "next", map {2*$_-1} 1..$N);
380 my $i = {%e, %f, %k, %d, %n, %t};
381 my $s = $c->simulate($i);
382  
383 is_deeply($s->steps, 11);
384 is_deeply($s->value("out.found"), 0);
385 is_deeply($s->bint ("out.dataFound"), 0);
386 is_deeply($s->bint ("out.nextLink"), 0);
387 }
388 test3($_) for 0..2*$N+1;
389 }
390  
391 #latest:;
392 if (1) #TnewBtreeNode
393 {my $B = 3; my $N = 3;
394  
395 my $c = Silicon::Chip::newChip;
396 my @n = map {newBtreeNode($c, "n", $N, $B)} 1..3; # B-Tree node
397  
398 my %e = map {setBits ($c, $_->enable, 1) } @n;
399 my %f = map {setBits ($c, $_->find, 2) } @n;
400 my %t = map {setBits ($c, $_->top, 2*$N+1) } @n;
401 my %k = map {setWords($c, $_->keys, map {2*$_} 1..$N)} @n;
402 my %d = map {setWords($c, $_->data, 1..$N)} @n;
403 my %n = map {setWords($c, $_->next, map {2*$_-1} 1..$N)} @n;
404 my $i = {%e, %f, %k, %d, %n, %t};
405  
406 my $s = $c->simulate($i, svg=>q(svg/btreeNode));
407 is_deeply($s->value($n[0]->found), 1);
408 is_deeply($s->bint ($n[0]->dataFound), 1);
409 is_deeply($s->bint ($n[0]->nextLink), 3);
410 }
411  
412 done_testing();
413 finish: 1;
↑ Summary