CAB/Cache/LRU.pm untested

filter: Statementstmt 0.0% 0 / 78 Branchbran 0.0% 0 / 26 Conditioncond 0.0% 0 / 6 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 0.0% 0 / 15 Podpod 0.0% 0 / 13 totaltotal 0.0% 0 / 142 CC 14 SCAR 27.5
CC
14
Cov
0%
get
30.0
remove
30.0
set
20.0
CRAP 15.6
1 ## -*- Mode: CPerl -*-
2 ##
3 ## File: DTA::CAB::Cache::LRU.pm
4 ## Author: Bryan Jurish <moocow@cpan.org>
5 ## Description: generic least-recently-used cache
6  
7 package DTA::CAB::Cache::LRU;
8 use Carp;
9 use strict;
10  
11 ##==============================================================================
12 ## Globals
13 ##==============================================================================
14  
15 our @ISA = qw();
16  
17 ##==============================================================================
18 ## Constructors etc.
19 ##==============================================================================
20  
21 ## $cache = CLASS_OR_OBJ->new(%args)
22 ## + %args, %$cache:
23 ## {
24 ## ##-- user data
25 ## max_size => $nelts, ##-- maximum number of elements to cache; default=128
26 ## get_cb => \&code, ##-- subroutine called to generate key value as $data=$code->($key) ; default=none
27 ## autohit => $bool, ##-- whether or not to implicitly call hit() on get() and set(); default=1
28 ## ##
29 ## ##-- low-level data
30 ## #size => $nelts, ##-- current cache size (may differ from scalar(@pos2key), scalar(@pos2val) b/c some array items may be undef)
31 ## offset => $pos, ##-- index of least recently used item == next available index for new item
32 ## key2pos => \%key2pos, ##-- $pos=$key2pos{$key}: maps key to item-position
33 ## pos2val => \@values, ##-- $val=$pos2val[$pos]: maps item-position to value (or undef)
34 ## pos2key => \@keys, ##-- $key=$pos2key[$pos]: maps item-position to key (or undef)
35 ## }
36 sub new {
37 my $that = shift;
38 my $cache = bless({
39 max_size => 128,
40 get_cb => undef,
41 autohit => 1,
42  
43 #size => 0,
44 offset => 0,
45 key2pos => {},
46 pos2val => [],
47 pos2key => [],
48 @_,
49 }, ref($that)||$that);
50 return $cache->resize($cache->{max_size});
51 }
52  
53 ## $cache = $cache->clear()
54 ## + clears cache
55 sub clear {
56 my $cache = shift;
57 #$cache->{size} = 0;
58 $cache->{offset} = 0;
59 %{$cache->{key2pos}} = qw();
60 @{$cache->{pos2val}} = qw();
61 @{$cache->{pos2key}} = qw();
62 $cache->{pos2val}[$cache->{max_size}-1]=undef; ##-- implicit auto-grow
63 $cache->{pos2key}[$cache->{max_size}-1]=undef; ##-- implicit auto-grow
64 return $cache;
65 }
66  
67 ## $cache = $cache->resize($max_size)
68 ## + resize the cache
69 ## + implicitly clears the cache
70 sub resize {
71 my ($cache,$max_size) = @_;
72 $cache->{max_size} = $max_size;
73 return $cache->clear();
74 }
75  
76 ##==============================================================================
77 ## Methods: API
78 ##==============================================================================
79  
80 ## $n = $cache->size()
81 ## + number of stored items
82 ## + TODO
83 #sub size {
84 # return $_[0]{size};
85 #}
86  
87 ## $bool = $cache->exists($key)
88 ## + returns true if cache has a stored value for $key
89 sub exists {
90 return CORE::exists($_[0]{key2pos}{$_[1]});
91 }
92  
93 ## $pos = $cache->getpos($key)
94 ## + returns cache position for $key, or undef if $key is not in cache
95 sub getpos {
96 return $_[0]{key2pos}{$_[1]};
97 }
98  
99 ## $offset = $cache->incr()
100 ## + increments offset
101 sub incr {
102 $_[0]{offset} = ($_[0]{offset}+1) % $_[0]{max_size};
103 }
104  
105 ## $val_or_undef = $cache->get($key, %opts)
106 ## + %opts:
107 ## get_cb => \&code, ##-- get callback (locally overrides $cache->{get_cb})
108 ## autohit => $bool, ##-- locally override $cache->{autohit}
109 sub get {
110 my ($cache,$key,%opts) = @_;
111 foreach (qw(get_cb autohit)) {
112 $opts{$_} = $cache->{$_} if (!exists($opts{$_}));
113 }
114  
115 my $pos = $cache->{key2pos}{$key};
116 my ($val);
117 if (defined($pos)) {
118 ##-- cached value
119 $val = $cache->{pos2val}[$pos];
120 $cache->hit($key,$pos) if ($opts{autohit});
121 }
122 elsif (defined($opts{get_cb})) {
123 ##-- user callback
124 $val = $opts{get_cb}->($key);
125 $cache->set($key,$val,%opts);
126 }
127 return $val;
128 }
129  
130 ## $val = $cache->_get($key, %opts)
131 ## + wrapper for $cache->get($key, %opts, autohit=>0)
132 sub _get {
133 return $_[0]->get(@_[1..$#_], autohit=>0);
134 }
135  
136 ## $val = $cache->set($key, $val, %opts)
137 ## + sets value for $key
138 ## + implicitly calls $cache->hit($key) and $cache->clean(%opts)
139 ## + returns index position
140 sub set {
141 my ($cache,$key,$val, %opts) = @_;
142 foreach (qw(autohit autoclean)) {
143 $opts{$_} = $cache->{$_} if (!exists($opts{$_}));
144 }
145 my $pos = $cache->{key2pos}{$key};
146 if (defined($pos)) {
147 ##-- key already cached: just set value
148 $cache->{pos2val}[$pos] = $val;
149 $cache->hit($key,$pos) if ($opts{autohit});
150 } else {
151 ##-- key not cached yet: insert new value at LRU position
152 $pos = $cache->{offset};
153 $cache->remove(undef,$pos);
154 $cache->insert($key,$val,$pos);
155 $cache->incr();
156 }
157  
158 return $val;
159 }
160  
161 ## $pos = $cache->_set($key, $val, %opts)
162 ## + wrapper for $cache->set($key,$val,%opts,autohit=>0)
163 sub _set {
164 return $_[0]->set(@_[1..$#_],autohit=>0);
165 }
166  
167 ## $cache = $cache->insert($key,$val,$pos)
168 ## + insert ($key=>$val) at position $pos
169 ## + low-level method; no offset-modification is done
170 sub insert {
171 my ($cache,$key,$val,$pos) = @_;
172 $cache->{pos2key}[$pos] = $key;
173 $cache->{pos2val}[$pos] = $val;
174 $cache->{key2pos}{$key} = $pos;
175 return $cache;
176 }
177  
178 ## $cache = $cache->remove($key)
179 ## $cache = $cache->remove($key, $pos)
180 ## $cache = $cache->remove(undef, $pos)
181 ## + remove an item from the cache by key and/or position
182 sub remove {
183 my ($cache,$key,$pos) = @_;
184 $pos = $cache->{key2pos}{$key} if (!defined($pos));
185 $key = $cache->{pos2key}[$pos] if (!defined($key));
186 delete($cache->{key2pos}{$key}) if (defined($key));
187 if (defined($pos)) {
188 $cache->{pos2val}[$pos]=undef;
189 $cache->{pos2key}[$pos]=undef;
190 #$cache->{offset} = ($pos+1) % $cache->{max_size} if ($pos==$cache->{offset}); ##-- increment LRU position if required
191 }
192 return $cache;
193 }
194  
195 ## $cache = $cache->hit($key)
196 ## $cache = $cache->hit($key,$oldpos)
197 ## + promotes $key to most recently used
198 sub hit {
199 my ($cache,$key,$oldpos) = @_;
200 $oldpos = $cache->{key2pos}{$key} if (!defined($oldpos));
201 return $cache if (!defined($oldpos) || $oldpos == (($cache->{offset}-1) % $cache->{max_size})); ##-- no update required
202 my $newpos = $cache->{offset};
203 my $val = $cache->{pos2val}[$oldpos];
204 $cache->remove(undef,$newpos);
205 $cache->remove($key, $oldpos);
206 $cache->insert($key, $val, $newpos);
207 $cache->incr();
208 return $cache;
209 }
210  
211  
212 1; ##-- be happy
213  
214 __END__