blob: a241a73e1058e8ee10346359ef9099065921cf11 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
class Cache::LRU
{
has $.limit is rw = 3;
has $.verbose = False;
has %.lookup is rw = ();
has $.head is rw = Any; # Highest
has $.tail is rw = Any; # Lowest
class LRU-elem
{
has $.id;
has $.payload;
has $.higher is rw;
has $.lower is rw;
}
method get-limit
{
return self.limit;
}
method set-limit (Int $new-limit)
{
return if $new-limit < 1;
return if $new-limit == self.limit;
self.limit = $new-limit;
self.shrink while self.lookup.keys.elems > self.limit;
say ": New Cache Capacity: { self.limit }" if self.verbose;
}
method shrink # remove the last item
{
self.lookup{self.tail.id} :delete;
self.tail = self.tail.higher;
self.tail.lower = Any;
}
method !extract ($elem)
{
$elem.higher
?? ( $elem.higher.lower = $elem.lower )
!! ( self.head = $elem.lower );
$elem.lower
?? ( $elem.lower.higher = $elem.higher )
!! ( self.tail = $elem.higher );
$elem.higher = $elem.lower = Any;
return $elem;
}
method delete ($elem)
{
self.lookup{$elem.id}:delete;
return self!extract($elem);
}
method get (Int $id)
{
say ": get $id " if self.verbose;
my $current = self.lookup{$id};
return -1 unless $current;
return $current.payload if $current === self.head;
self!extract($current);
self.head.higher = $current;
$current.lower = self.head;
self.head = $current;
return $current.payload;
}
method set (Int $id, $value)
{
say ": set $id @ $value" if self.verbose;
my $old-head = self.head;
self.head = LRU-elem.new(id => $id, payload => $value);
self.head.lower = $old-head;
$old-head.higher = self.head if $old-head;
if self.lookup{$id}
{
self!extract(self.lookup{$id});
}
else # new
{
self.tail = self.head unless self.tail;
self.shrink if self.lookup.keys == self.limit;
}
self.lookup{$id} = self.head;
}
method dump ($elem = self.head)
{
print $elem.id ~ " -> " ~ $elem.payload;
print " (head)" if $elem === self.head;
print " (tail)" if $elem === self.tail;
say "";
self.dump($elem.lower) if $elem.lower;
}
method dump2 ($elem = self.head)
{
say $elem;
}
}
|
