HashSC.pm

filter: Statementstmt 100% 91 / 91 Branchbran 100% 34 / 34 Conditioncond 83.3% 5 / 6 MC/DCmcdc 66.6% 2 / 3 Subroutinesub 100% 21 / 21 Podpod 100% 8 / 8 totaltotal 98.7% 161 / 163 CC 27 SCAR 12.2
CC
27
Cov
99%
get
5.0
keys_with
5.0
put
5.0
CRAP 3.4
« HashSC/ConfigData.pm ↑ Summary
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
BranchTrueFalseTotal
if not defined $_[0] && &looks_like_number($_[0]) or $_[0] < 2 2 3 5
Condition83%5/6
not defined $_[0] && &looks_like_number($_[0]) or $_[0] < 2
l!l&&r!l&&!r
113
defined $_[0] && &looks_like_number($_[0])
!ll&&!rl&&r
014
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
ABCresult
0XX1
10X1
1111
1100
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
BranchTrueFalseTotal
unless $self->unsafe 1 1 2
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
BranchTrueFalseTotal
$_[0] ? : 1 2 3
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
BranchTrueFalseTotal
unless defined $key 1 3 4
77 3 my $chain = $self->_chain->[ $self->hash($key) ];
78 3 ▶ if ( defined $chain ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $chain) 2 1 3
79 2 for my $kvpair (@$chain) {
80 2 ▶ return $kvpair->[1] if $key eq $kvpair->[0];
Branch: 1 branch
BranchTrueFalseTotal
if $key eq $kvpair->[0] 1 1 2
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
BranchTrueFalseTotal
unless defined $key 1 31 32
94 31 my $code = 0;
95 31 ▶ if ( $key->can('hashcode') ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($key->can('hashcode')) { } 6 25 31
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
BranchTrueFalseTotal
unless defined $index 1 2 3
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
BranchTrueFalseTotal
unless defined $key 1 5 6
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
BranchTrueFalseTotal
if $key eq $kvpair->[0] 3 3 6
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
BranchTrueFalseTotal
unless defined $key 1 12 13
137 12 my $chain = $self->_chain->[ $self->hash($key) ];
138 12 ▶ if ( defined $chain ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $chain) 7 5 12
139 7 for my $kvpair (@$chain) {
140 8 ▶ if ( $key eq $kvpair->[0] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($key eq $kvpair->[0]) 1 7 8
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
BranchTrueFalseTotal
unless defined $key 1 5 6
154 5 my $chain = $self->_chain->[ $self->hash($key) ];
155 5 ▶ if ( defined $chain ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $chain) 4 1 5
156 4 for my $i ( 0 .. $#$chain ) {
157 5 ▶ if ( $key eq $chain->[$i][0] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($key eq $chain->[$i][0]) 4 1 5
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__
« HashSC/ConfigData.pm ↑ Summary