view release on metacpan or  search on metacpan

lib/AC/Yenta/Store/Merkle.pm  view on Meta::CPAN

        %todo = ();

        for my $hd (values %next){
            # update level - 1 with hash
            # put level-1 hash into todo
            my($ns, $nv, $h, $c) = $me->_merkle_update( $hd->{shard}, $level, $hd->{ver}, $hd->{hash}, $hd->{count} );
            $todo{"$ns $nv"} = { ver => $nv, hash => $h, count => $c, shard => $ns } if defined $nv;
        }
        $level --;
    }
}

# non-leaf node:
#  list of (ver => hash+count)
#  of up to 16 next-level-down vers
#  \0 delimited, sorted by ver

# update merkle node
sub _merkle_update {
    my $me    = shift;
    my $shard = shift;
    my $lev   = shift;
    my $ver   = shift;
    my $hash  = shift;
    my $count = shift;

    my $db = $me->{db};

    my $k0 = $me->_mkey($shard, $ver, $lev);
    my $k1 = $me->_mkey($shard, $ver, $lev - 1);

    my(undef, $nextshard, $nextver) = $me->_decode_mkey($k1);

    unless( $lev ){
        # root hash - not used
        debug("updating merkle node root => $hash");
        $me->_mcput( 'root', $hash );
        return;
    }

    # get node
    my $d = $me->_mcget( $k1 );
    my $oldh = sha1_base64($d);
    my %d = split /\0/, $d;

    if($hash){
        # add/update
        debug("updating merkle node $k1 + { $k0 => $hash, $count }");
        $d{$k0} = "$hash $count";
    }else{
        # remove
        debug("updating merkle node $k1 - { $k0 => empty }");
        delete $d{$k0};
    }

    if( keys %d ){

        $d = join("\0", map {"$_\0$d{$_}"} (sort keys %d));
        $me->_mcput( $k1, $d );
        my $newh = sha1_base64($d);
        return if $newh eq $oldh;	# unchanged
        return ($nextshard, $nextver, $newh, scalar keys %d);
    }else{
        $me->_mcdel( $k1 );
        return unless $oldh;		# unchanged
        return ($nextshard, $nextver, undef);
    }
}

# leaf nodes:
#   list of all "ver/key"
#   \0 delimited. sorted by "ver/key"

# add new <key,version> to merkle leaf
sub _merkle_leaf_add {
    my $me    = shift;
    my $shard = shift;
    my $key   = shift;
    my $ver   = shift;

    my $db = $me->{db};
    my $mk = $me->_mkey($shard, $ver, $me->{merkle_height});
    my $vk = $me->_lkey($key, $ver, $shard);

    debug("adding to merkle leaf $mk - $vk");

    # get current data
    my $d = $me->_mcget( $mk );
    my @d = split /\0/, $d;
    # append new item + uniqify
    my %d;
    @d{@d} = ();
    $d{$vk}   = undef;
    $d = join("\0", sort keys %d);
    $me->_mcput( $mk, $d );

    my $hash = sha1_base64($d);
    return ($shard, $ver, $hash, scalar keys %d);
}

# remove <key,version> from merkle leaf
sub _merkle_leaf_del {
    my $me    = shift;
    my $shard = shift;
    my $key   = shift;
    my $ver   = shift;

    my $db = $me->{db};
    my $mk = $me->_mkey($shard, $ver, $me->{merkle_height});
    my $vk = $me->_lkey($key, $ver, $shard);

    debug("removing from merkle leaf $mk - $vk");

    # get current data
    my $d = $me->_mcget( $mk );
    my @d = split /\0/, $d;
    # remove item
    @d = grep { $vk ne $_ } @d;

    if( @d ){
        $d = join("\0", @d);
        $me->_mcput( $mk, $d );

        my $hash = sha1_base64($d);
        return ($shard, $ver, $hash, scalar @d);