| 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")
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")
| |||||||||||||||||||||
| 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
}
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
}
| |||||||||||||||||||||
| 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]
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]
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 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
| |||||||||||||||||||||
| 126 | 1 | return Cuckoo::Filter->new(%$params); | |||||||||||||||||||
| 127 | } | ||||||||||||||||||||
| 128 | |||||||||||||||||||||
| 129 | 2 | 1; | |||||||||||||||||||
| 130 | __END__ | ||||||||||||||||||||