File Coverage

blib/lib/Cuckoo/Filter.pm

Criterion	Covered	Total	%
statement	65	80	81.2
branch	5	10	50.0
condition	5	9	55.5
subroutine	12	13	92.3
pod	7	7	100.0
total	94	119	78.9

package Cuckoo::Filter;

use warnings;
use strict;
use Storable qw(nfreeze thaw);
our $VERSION = "0.0.4";

use Digest;

our @serialize_keys = qw(bucket_size max_retry fingerprint_size buckets);

sub new {
    my ($class, %params) = @_;
    my $self = {
        bucket_size => 2 ** 18,
        max_retry => 500,
        fingerprint_size => 3,
        %params,
    };
    $self->{digest} //= Digest->new("SHA-1");
    # init fixed array
    $self->{buckets} //= do {
        my @buckets = ();
        $#buckets = $self->{bucket_size};
        $self->{item_count} = 0;
        \@buckets
    };

    return bless $self, $class;
}

sub _fingerprint {
    my ($self, $item) = @_;
    my $digest = do {
        my $d= $self->{digest};
        $d->add($item);
        $d->digest;
    };

    return substr($digest, 0, $self->{fingerprint_size}-1);
}

# djb hash
sub _hash {
    my $str = shift;
    my @bytes = unpack 'C*', $str;
    my $h = 5381;
    for my $i (@bytes) {
        $h = (($h << 5) + $h) + $i;
    }
    $h;
}

sub lookup {
    my ($self, $item) = @_;
    my $fp = $self->_fingerprint($item);
    my $idx1 = _hash($item) % $self->{bucket_size};
    my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};

    return defined $self->{buckets}[$idx1] || $self->{buckets}[$idx2];
}

sub insert {
    my ($self, $item) = @_;
    return 0 if $self->lookup($item);
    my $fp = $self->_fingerprint($item);
    my $idx1 = _hash($item) % $self->{bucket_size};
    my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
    for my $index ($idx1, $idx2) {
        if (! defined $self->{buckets}[$index]) {
            $self->{buckets}[$index] = $item;
            $self->{item_count}++;
            return 1;
        }
    }

    my $index = +($idx1, $idx2)[int(rand(2))];
    for (my $i = 0; $i < $self->{max_retry}; $i++) {
        $fp = do {
            my $f = $self->{buckets}[$index];
            $self->{buckets}[$index] = $fp;
            $f;
        };
        $index = ($idx1 ^ _hash($fp)) % $self->{bucket_size};

        if (! defined $self->{buckets}[$index]) {
            $self->{buckets}[$index] = $fp;
            $self->{item_count}++;
            return 1;
        }
    }

    return 0;
}

sub delete {
    my ($self, $item) = @_;
    my $fp = $self->_fingerprint($item);
    my $idx1 = _hash($item) % $self->{bucket_size};
    my $idx2 = ($idx1 ^ _hash($fp)) % $self->{bucket_size};
    for my $index ($idx1, $idx2) {
        if (defined $self->{buckets}[$index]) {
            delete $self->{buckets}[$index];
            $self->{item_count}--;
            return 1;
        }
    }
    return 0;
}

sub count {
    my $self = shift;
    return $self->{item_count};
}

sub serialize {
    my $self = shift;
    my %params = map { $_ => $self->{$_} } @serialize_keys;
    return nfreeze \%params;
}

sub deserialize {
    my ($serialized, $digest) = @_;
    my $params = thaw($serialized);
    $params->{digest} = $digest if $digest;
    return Cuckoo::Filter->new(%$params);
}

1;
__END__