blib/lib/Cuckoo/Filter.pm

filter: Statementstmt 81.9% 68 / 83 Branchbran 41.6% 5 / 12 Conditioncond 55.5% 5 / 9 MC/DCmcdc 16.6% 1 / 6 Subroutinesub 92.3% 12 / 13 Podpod 100% 7 / 7 totaltotal 75.3% 98 / 130 CC 13 SCAR 15.1
CC
13
Cov
75%
insert
12.6
new
3.1
delete
3.0
CRAP 4.5
↑ Summary
1 package Cuckoo::Filter;
2  
3 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 2 ▶use Storable qw(nfreeze thaw);
Subroutine BEGIN: called CC=1 SCAR=0.0
6 2 our $VERSION = "0.0.4";
7  
8 2 ▶use Digest;
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10 2 our @serialize_keys = qw(bucket_size max_retry fingerprint_size buckets);
11  
12 2 ▶sub new {
Subroutine new: called CC=3 SCAR=11.2
Pod documented
13 2 my ($class, %params) = @_;
14 2 my $self = {
15 bucket_size => 2 ** 18,
16 max_retry => 500,
17 fingerprint_size => 3,
18 %params,
19 };
20 2 ▶ $self->{digest} //= Digest->new("SHA-1");
Condition33%1/3
$self->{"digest"} //= "Digest"->new("SHA-1")
l!l&&r!l&&!r
020
MC/DC0%0/2
$self->{"digest"} //= "Digest"->new("SHA-1")
$self->{"digest"} "Digest"->new("SHA-1")
Truth table33%1/3
A //= B
A= $self->{"digest"}B= "Digest"->new("SHA-1")
ABresult
1X1
011
000
21 # init fixed array
22 2 ▶ $self->{buckets} //= do {
Condition66%2/3
$self->{"buckets"} //= do { my(@buckets) = (); $#buckets = $self->{"bucket_size"}; $self->{"item_count"} = 0; \@buckets }
l!l&&r!l&&!r
110
MC/DC0%0/2
$self->{"buckets"} //= do { my(@buckets) = (); $#buckets = $self->{"bucket_size"}; $self->{"item_count"} = 0; \@buckets }
$self->{"buckets"} do { my(@buckets) = (); $#buckets = $self->{"bucket_size"}; $self->{"item_count"} = 0; \@buckets }
Truth table66%2/3
A //= B
A= $self->{"buckets"}B= do { my(@buckets) = (); $#buckets = $self->{"bucket_size"}; $self->{"item_count"} = 0; \@buckets }
ABresult
1X1
011
000
23 1 my @buckets = ();
24 1 $#buckets = $self->{bucket_size};
25 1 $self->{item_count} = 0;
26 \@buckets
27 1 };
28  
29 2 return bless $self, $class;
30 }
31  
32 13 ▶sub _fingerprint {
Subroutine _fingerprint: called CC=1 SCAR=0.0
33 13 my ($self, $item) = @_;
34 13 my $digest = do {
35 13 my $d= $self->{digest};
36 13 $d->add($item);
37 13 $d->digest;
38 };
39  
40 13 return substr($digest, 0, $self->{fingerprint_size}-1);
41 }
42  
43 # djb hash
44 26 ▶sub _hash {
Subroutine _hash: called CC=2 SCAR=6.9
45 26 my $str = shift;
46 26 my @bytes = unpack 'C*', $str;
47 26 my $h = 5381;
48 26 for my $i (@bytes) {
49 39 $h = (($h << 5) + $h) + $i;
50 }
51 26 $h;
52 }
53  
54 9 ▶sub lookup {
Subroutine lookup: called CC=2 SCAR=7.0
Pod documented
55 9 my ($self, $item) = @_;
56 9 my $fp = $self->_fingerprint($item);
57 9 my $idx1 = _hash($item) % $self->{bucket_size};
58 9 my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
59  
60 9 ▶ return defined $self->{buckets}[$idx1] || $self->{buckets}[$idx2];
Condition66%2/3
defined $self->{'buckets'}[$idx1] || $self->{'buckets'}[$idx2]
l!l&&r!l&&!r
306
MC/DC50%1/2
defined $self->{'buckets'}[$idx1] || $self->{'buckets'}[$idx2]
defined $self->{'buckets'}[$idx1] $self->{'buckets'}[$idx2]
Truth table66%2/3
A || B
A= defined $self->{'buckets'}[$idx1]B= $self->{'buckets'}[$idx2]
ABresult
1X1
011
000
61 }
62  
63 4 ▶sub insert {
Subroutine insert: called CC=6 SCAR=25.3
Pod documented
64 4 my ($self, $item) = @_;
65 4 ▶ return 0 if $self->lookup($item);
Branch: 1 branch
BranchTrueFalseTotal
if $self->lookup($item) 1 3 4
66 3 my $fp = $self->_fingerprint($item);
67 3 my $idx1 = _hash($item) % $self->{bucket_size};
68 3 my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
69 3 for my $index ($idx1, $idx2) {
70 3 ▶ if (! defined $self->{buckets}[$index]) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $self->{"buckets"}[$index]) 3 0 3
71 3 $self->{buckets}[$index] = $item;
72 3 $self->{item_count}++;
73 3 return 1;
74 }
75 }
76  
77 0 my $index = +($idx1, $idx2)[int(rand(2))];
78 0 ▶ for (my $i = 0; $i < $self->{max_retry}; $i++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $self->{"max_retry"}) 0 0 0
79 0 $fp = do {
80 0 my $f = $self->{buckets}[$index];
81 0 $self->{buckets}[$index] = $fp;
82 0 $f;
83 };
84 0 $index = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
85  
86 0 ▶ if (! defined $self->{buckets}[$index]) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $self->{"buckets"}[$index]) 0 0 0
87 0 $self->{buckets}[$index] = $fp;
88 0 $self->{item_count}++;
89 0 return 1;
90 }
91 }
92  
93 0 return 0;
94 }
95  
96 1 ▶sub delete {
Subroutine delete: called CC=3 SCAR=11.1
Pod documented
97 1 my ($self, $item) = @_;
98 1 my $fp = $self->_fingerprint($item);
99 1 my $idx1 = _hash($item) % $self->{bucket_size};
100 1 my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
101 1 for my $index ($idx1, $idx2) {
102 1 ▶ if (defined $self->{buckets}[$index]) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $self->{"buckets"}[$index]) 1 0 1
103 1 delete $self->{buckets}[$index];
104 1 $self->{item_count}--;
105 1 return 1;
106 }
107 }
108 0 return 0;
109 }
110  
111 0 ▶sub count {
Subroutine count: not called CC=1 SCAR=6.9
Pod documented
112 0 my $self = shift;
113 0 return $self->{item_count};
114 }
115  
116 1 ▶sub serialize {
Subroutine serialize: called CC=1 SCAR=0.0
Pod documented
117 1 my $self = shift;
118 1 my %params = map { $_ => $self->{$_} } @serialize_keys;
119 1 return nfreeze \%params;
120 }
121  
122 1 ▶sub deserialize {
Subroutine deserialize: called CC=2 SCAR=7.0
Pod documented
123 1 my ($serialized, $digest) = @_;
124 1 my $params = thaw($serialized);
125 1 ▶ $params->{digest} = $digest if $digest;
Branch: 1 branch
BranchTrueFalseTotal
if $digest 0 1 1
126 1 return Cuckoo::Filter->new(%$params);
127 }
128  
129 2 1;
130 __END__
↑ Summary