File Coverage

blib/lib/Cuckoo/Filter.pm

Criterion	Covered	Total	%
statement	54	69	78.2
branch	6	10	60.0
condition	3	6	50.0
subroutine	9	10	90.0
pod	5	5	100.0
total	77	100	77.0

package Cuckoo::Filter;

use warnings;
use strict;

our $VERSION = "0.0.2";

use Digest;

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

sub _hash {
    my ($self, $item) = @_;

    # djb hash
    my $h = 5381;
    for (my $i = 0; $i < length $item; $i++) {
        my $prefix = $i > 0 ? "x${i} " : '';
        my $t = unpack("${prefix}C1", $item);
        $h = (($h << 5) + $h) + $t;
    }

    return $h;
}

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

1;
__END__