| 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__ |