| 1 | # -*- Perl -*- | ||||||||||||||||||||||||||||||||||||||||||
| 2 | # | ||||||||||||||||||||||||||||||||||||||||||
| 3 | # Toy deterministic separate chain hash implementation, based on code in | ||||||||||||||||||||||||||||||||||||||||||
| 4 | # "Algorithms (4th Edition)" by Robert Sedgewick and Kevin Wayne. This | ||||||||||||||||||||||||||||||||||||||||||
| 5 | # code is not for any sort of use where performance is critical, or | ||||||||||||||||||||||||||||||||||||||||||
| 6 | # where malicious input may cause "Algorithmic Complexity Attacks" (see | ||||||||||||||||||||||||||||||||||||||||||
| 7 | # perlsec(1)). | ||||||||||||||||||||||||||||||||||||||||||
| 8 | # | ||||||||||||||||||||||||||||||||||||||||||
| 9 | # run perldoc(1) on this file for additional documentation | ||||||||||||||||||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||||||||||||||||||
| 11 | package Algorithm::Toy::HashSC; | ||||||||||||||||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||||||||||||||||
| 13 | 2 | ▶ | use 5.010; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 14 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 15 | 2 | ▶ | use warnings; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 16 | |||||||||||||||||||||||||||||||||||||||||||
| 17 | 2 | ▶ | use Carp qw/croak/; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 18 | 2 | ▶ | use Moo; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 19 | 2 | ▶ | use namespace::clean; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 20 | 2 | ▶ | use Scalar::Util qw/looks_like_number/; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||||||||||||||||
| 22 | 2 | our $VERSION = '0.02'; | |||||||||||||||||||||||||||||||||||||||||
| 23 | |||||||||||||||||||||||||||||||||||||||||||
| 24 | ############################################################################## | ||||||||||||||||||||||||||||||||||||||||||
| 25 | # | ||||||||||||||||||||||||||||||||||||||||||
| 26 | # ATTRIBUTES | ||||||||||||||||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||||||||||||||||
| 28 | # Each list should end up with ~N/M key-value pairs, assuming the input | ||||||||||||||||||||||||||||||||||||||||||
| 29 | # is not malicious, and that the hash function is perfect enough. "M" | ||||||||||||||||||||||||||||||||||||||||||
| 30 | # here is the modulus, and "N" is the number of key-value pairs added. | ||||||||||||||||||||||||||||||||||||||||||
| 31 | # | ||||||||||||||||||||||||||||||||||||||||||
| 32 | # Internally, it's an array of array of arrays, or something like that. | ||||||||||||||||||||||||||||||||||||||||||
| 33 | has _chain => ( | ||||||||||||||||||||||||||||||||||||||||||
| 34 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 35 | 1 | ▶ | default => sub { [] }, | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 36 | 2 | ); | |||||||||||||||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||||||||||||||||
| 38 | has modulus => ( | ||||||||||||||||||||||||||||||||||||||||||
| 39 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 40 | 1 | ▶ | default => sub { 7 }, | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 41 | 5 | ▶ | coerce => sub { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=4 SCAR=13.9
| |||||||||||||||||||||||||||||||||||||||||||
| 42 | 5 | ▶ | die 'modulus must be a positive integer > 1' | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition83%5/6
not defined $_[0] && &looks_like_number($_[0]) or $_[0] < 2
defined $_[0] && &looks_like_number($_[0])
MC/DC66%2/3
not defined $_[0] && &looks_like_number($_[0]) or $_[0] < 2
defined $_[0]
&looks_like_number($_[0])
$_[0] < 2
Truth table75%3/4
not(A && B) or C
A= defined $_[0]B= &looks_like_number($_[0])C= $_[0] < 2
| |||||||||||||||||||||||||||||||||||||||||||
| 43 | if !defined $_[0] | ||||||||||||||||||||||||||||||||||||||||||
| 44 | or !looks_like_number $_[0] | ||||||||||||||||||||||||||||||||||||||||||
| 45 | or $_[0] < 2; | ||||||||||||||||||||||||||||||||||||||||||
| 46 | 3 | return int $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 47 | }, | ||||||||||||||||||||||||||||||||||||||||||
| 48 | 2 | ▶ | trigger => sub { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||||||||||
| 49 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 50 | # clobber extant hash (Moo does not provide old value, so cannot do | ||||||||||||||||||||||||||||||||||||||||||
| 51 | # this only when the modulus changes, oh well) | ||||||||||||||||||||||||||||||||||||||||||
| 52 | 2 | ▶ | $self->_chain( [] ) unless $self->unsafe; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 53 | }, | ||||||||||||||||||||||||||||||||||||||||||
| 54 | 2 | ); | |||||||||||||||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||||||||||||||||
| 56 | # Boolean, disables various sanity checks if set to a true value (in | ||||||||||||||||||||||||||||||||||||||||||
| 57 | # particular whether the hash is cleared when the modulus is changed). | ||||||||||||||||||||||||||||||||||||||||||
| 58 | has unsafe => ( | ||||||||||||||||||||||||||||||||||||||||||
| 59 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 60 | 1 | ▶ | default => sub { 0 }, | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 61 | 3 | ▶ | coerce => sub { $_[0] ? 1 : 0 }, | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 62 | 2 | ); | |||||||||||||||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||||||||||||||||
| 64 | ############################################################################## | ||||||||||||||||||||||||||||||||||||||||||
| 65 | # | ||||||||||||||||||||||||||||||||||||||||||
| 66 | # METHODS | ||||||||||||||||||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||||||||||||||||
| 68 | 2 | ▶ | sub clear_hash { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
clear_hash: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 69 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 70 | 2 | $self->_chain( [] ); | |||||||||||||||||||||||||||||||||||||||||
| 71 | 2 | return $self; | |||||||||||||||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||||||||||||||||
| 73 | |||||||||||||||||||||||||||||||||||||||||||
| 74 | 4 | ▶ | sub get { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
get: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 75 | 4 | my ( $self, $key ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 76 | 4 | ▶ | croak "must provide key" if !defined $key; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 77 | 3 | my $chain = $self->_chain->[ $self->hash($key) ]; | |||||||||||||||||||||||||||||||||||||||||
| 78 | 3 | ▶ | if ( defined $chain ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 79 | 2 | for my $kvpair (@$chain) { | |||||||||||||||||||||||||||||||||||||||||
| 80 | 2 | ▶ | return $kvpair->[1] if $key eq $kvpair->[0]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 81 | } | ||||||||||||||||||||||||||||||||||||||||||
| 82 | } | ||||||||||||||||||||||||||||||||||||||||||
| 83 | 2 | return; | |||||||||||||||||||||||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||||||||||||||||
| 86 | # Derives the index of the chain a particular key will be added to. The | ||||||||||||||||||||||||||||||||||||||||||
| 87 | # hashcode function, if available, should return something that ideally | ||||||||||||||||||||||||||||||||||||||||||
| 88 | # evenly distributes the given keys across the given modulus. | ||||||||||||||||||||||||||||||||||||||||||
| 89 | # | ||||||||||||||||||||||||||||||||||||||||||
| 90 | # Alternative: subclass this module and write yer own hash function. | ||||||||||||||||||||||||||||||||||||||||||
| 91 | 32 | ▶ | sub hash { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
hash: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 92 | 32 | my ( $self, $key ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 93 | 32 | ▶ | croak "must provide key" if !defined $key; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 94 | 31 | my $code = 0; | |||||||||||||||||||||||||||||||||||||||||
| 95 | 31 | ▶ | if ( $key->can('hashcode') ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 96 | 6 | $code = $key->hashcode(); | |||||||||||||||||||||||||||||||||||||||||
| 97 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 98 | # this is pretty terrible... | ||||||||||||||||||||||||||||||||||||||||||
| 99 | 25 | for my $n ( map ord, split //, $key ) { | |||||||||||||||||||||||||||||||||||||||||
| 100 | 49 | $code += $n; | |||||||||||||||||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||||||||||||||||
| 102 | } | ||||||||||||||||||||||||||||||||||||||||||
| 103 | 31 | return abs( $code % $self->modulus ); | |||||||||||||||||||||||||||||||||||||||||
| 104 | } | ||||||||||||||||||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||||||||||||||||
| 106 | 11 | ▶ | sub keys { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
keys: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 107 | 11 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 108 | 11 | my @keys; | |||||||||||||||||||||||||||||||||||||||||
| 109 | 11 | for my $chain ( @{ $self->_chain } ) { | |||||||||||||||||||||||||||||||||||||||||
| 110 | 12 | push @keys, map { $_->[0] } @$chain; | |||||||||||||||||||||||||||||||||||||||||
| 111 | } | ||||||||||||||||||||||||||||||||||||||||||
| 112 | 11 | return @keys; | |||||||||||||||||||||||||||||||||||||||||
| 113 | } | ||||||||||||||||||||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||||||||||||||||||||
| 115 | 3 | ▶ | sub keys_in { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
keys_in: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 116 | 3 | my ( $self, $index ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 117 | 3 | ▶ | croak "must provide index" if !defined $index; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 118 | 2 | $index %= $self->modulus; # this will int() any floating-point nums | |||||||||||||||||||||||||||||||||||||||||
| 119 | 2 | return map { $_->[0] } @{ $self->_chain->[$index] }; | |||||||||||||||||||||||||||||||||||||||||
| 120 | } | ||||||||||||||||||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||||||||||||||||
| 122 | # Keys in the same chain (or bucket) as a given key | ||||||||||||||||||||||||||||||||||||||||||
| 123 | 6 | ▶ | sub keys_with { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
keys_with: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 124 | 6 | my ( $self, $key ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 125 | 6 | ▶ | croak "must provide key" if !defined $key; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 126 | 5 | for my $chain ( @{ $self->_chain } ) { | |||||||||||||||||||||||||||||||||||||||||
| 127 | 5 | for my $kvpair (@$chain) { | |||||||||||||||||||||||||||||||||||||||||
| 128 | 6 | ▶ | return map $_->[0], @$chain if $key eq $kvpair->[0]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 129 | } | ||||||||||||||||||||||||||||||||||||||||||
| 130 | } | ||||||||||||||||||||||||||||||||||||||||||
| 131 | 2 | return; | |||||||||||||||||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||||||||||||||||||||
| 134 | 13 | ▶ | sub put { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
put: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 135 | 13 | my ( $self, $key, $value ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 136 | 13 | ▶ | croak "must provide key" if !defined $key; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 137 | 12 | my $chain = $self->_chain->[ $self->hash($key) ]; | |||||||||||||||||||||||||||||||||||||||||
| 138 | 12 | ▶ | if ( defined $chain ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 139 | 7 | for my $kvpair (@$chain) { | |||||||||||||||||||||||||||||||||||||||||
| 140 | 8 | ▶ | if ( $key eq $kvpair->[0] ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 141 | 1 | $kvpair->[1] = $value; | |||||||||||||||||||||||||||||||||||||||||
| 142 | 1 | return $self; | |||||||||||||||||||||||||||||||||||||||||
| 143 | } | ||||||||||||||||||||||||||||||||||||||||||
| 144 | } | ||||||||||||||||||||||||||||||||||||||||||
| 145 | } | ||||||||||||||||||||||||||||||||||||||||||
| 146 | 11 | push @{ $self->_chain->[ $self->hash($key) ] }, [ $key, $value ]; | |||||||||||||||||||||||||||||||||||||||||
| 147 | 11 | return $self; | |||||||||||||||||||||||||||||||||||||||||
| 148 | } | ||||||||||||||||||||||||||||||||||||||||||
| 149 | |||||||||||||||||||||||||||||||||||||||||||
| 150 | # a.k.a. delete but more indicative of the obtaining-a-value aspect | ||||||||||||||||||||||||||||||||||||||||||
| 151 | 6 | ▶ | sub take { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
take: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 152 | 6 | my ( $self, $key ) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 153 | 6 | ▶ | croak "must provide key" if !defined $key; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 154 | 5 | my $chain = $self->_chain->[ $self->hash($key) ]; | |||||||||||||||||||||||||||||||||||||||||
| 155 | 5 | ▶ | if ( defined $chain ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 156 | 4 | for my $i ( 0 .. $#$chain ) { | |||||||||||||||||||||||||||||||||||||||||
| 157 | 5 | ▶ | if ( $key eq $chain->[$i][0] ) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 158 | 4 | my $kvpair = splice @$chain, $i, 1; | |||||||||||||||||||||||||||||||||||||||||
| 159 | 4 | return $kvpair->[1]; | |||||||||||||||||||||||||||||||||||||||||
| 160 | } | ||||||||||||||||||||||||||||||||||||||||||
| 161 | } | ||||||||||||||||||||||||||||||||||||||||||
| 162 | } | ||||||||||||||||||||||||||||||||||||||||||
| 163 | 1 | return; | |||||||||||||||||||||||||||||||||||||||||
| 164 | } | ||||||||||||||||||||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||||||||||||||||||||
| 166 | 2 | 1; | |||||||||||||||||||||||||||||||||||||||||
| 167 | __END__ | ||||||||||||||||||||||||||||||||||||||||||