Last update November 13, 2007

Lru Cache

Difference (last change) (no other diffs, normal page display)

Changed: 4,171c4,6

==Warnings & Limitations:==
nodeId is kept as a ushort. Even though it's periodically reduced when the cache is flushed, this doesn't reset it. A routine is needed to renumber the cache nodes, but I haven't thought of a quick way to do this. For many uses this would mean that a cache could only be used for a short period of time. (Perhaps after the cache is flushed I should just arbitrarily renumber the entries from 1-n? Or whenever the maxT value gets within maxSize+1 of ushort.max? At this point I haven't decided on what the best solution is. (The nodeId could also be made a ulong, which would postpone the problem for quite awhile, though it wouldn't solve it in principle.)

This code is released under the MIT license. If you want something else, ask.

[[code][linenumber=1][linenumberformat=%03d ]
// lrucache.d
// to test for correctness, compile thus:
// dmd -version="testLRUCache" lrucache.d
//
/**
* Author: Charles Hixson, charleshixsn@earthlink.net
* Date: Nov. 8, 2007
* Version: 0.2.b
* (Note: Version 0.1 was lacking a version number)
* License: MIT license
* (Note: Some future version will switch to GPL...but this stuff
* *SHOULD* be public domain.)
* Copyright: Charles Hixson, all rights reserved. (But see the license.)
*/

import std.conv;
import std.stdio;

/**
* Key must implement opCmp and be hashable
* Cache's should not be too large, so the size is a ushort. That's excessive.
* If you want a cache nearly that large, use a database or something.
*/
class LRUCache(Key, Body)
{
private:
typedef ushort NodeId?;
Body[Key] bodies;
NodeId?[Key] nodIds;
Body _invalid;
ushort _maxLength;
NodeId? maxNode;

public:
this (ushort maxLength, Body invalid)
{ _invalid = invalid;
_maxLength = maxLength;
}

const (Body) opIndex (Key k)
{ if (auto b = k in bodies)
{ nodIds[k] = ++maxNode;
if (maxNode >= _maxLength - 2) renumber;
return *b;
}
return _invalid;
}

const (Body) opIndexAssign (Body b, Key k)
{ //Node? n;
if (b == _invalid) return _invalid;
nodIds[k] = ++maxNode;
bodies[k] = b;
if (bodies.length > _maxLength)
{ // cache is too large, so remove approx. the 1/4 least recently used
//// N.B.: Expiration is based on access time. Creation time is (so far) unused.
ulong sum = 0;
NodeId? maxT = 0;
NodeId? minT = maxNode;
NodeId? meanT;
foreach (nId; nodIds)
{ sum += nId;
if (nId < minT) minT = nId;
if (nId > maxT) maxT = nId;
}
meanT = cast(NodeId?)(sum / nodIds.length);
NodeId? limit = cast(NodeId?)(minT + (meanT - minT) / 2);
foreach (Key key, NodeId? nId; nodIds)
{ if (nId <= limit)
{ nodIds.remove(key);
bodies.remove(key);
}
else nodIds[key] = cast(NodeId?)(nodIds[key] - limit + 1);
}
maxNode = cast(NodeId?)(maxNode - limit + 1);
}
if (maxNode >= _maxLength - 2) renumber;
return b;
}

int length() { return bodies.length; }

void remove (Key k)
{ if (k in bodies)
{ nodIds.remove(k);
bodies.remove(k);
}
}

bool contains (Key k)
{ if (k in nodIds)
{ nodIds[k] = ++maxNode;
return true;
}
return false;
}

/// for diagnostic purposes only. Do NOT use this value.
ulong nodeId(Key k)
{ if (auto nId = k in nodIds) return *nId; return 0; }

/**
* renumber the nodes. This is a separate routine to allow different
* algorithms to be easily inserted. I've picked quick & easy.
*/
private void renumber()
{ NodeId? nId = 0;
foreach (Key key, NodeId? node; nodIds) nodIds[key] = ++nId;
maxNode = cast(NodeId?)((nId > 0) ? nId - 1 : 0);
}
version (testLRUCache)
{ void dump()
{ writef("there are %s entries in the cache\n", bodies.length);
Key[] keys = bodies.keys;
for (int i = 0; i < keys.length; i++)
{ writef ("%2s", keys[i]);
writef (": %10s", nodIds[keys[i]]);
writef (": %s\n", bodies[keys[i]]);
}
}
}
}

version (testLRUCache)
{
void main()
{ auto l = new LRUCache!(int, char)(10, cast(char)0);
string s = "This is a rather long string of quasi-random text,";
int i = 0;
foreach (char c; s)
{ writef ("adding %d\n", i);
l[i++] = c;
}
l.dump;
for (i = 0; i < s.length; i++)
{ if (l.contains(i)) writef ("l[%2s] = '%s', id = %s\n", i, l[i], l.nodeId(i));
//else writef ("l[%2s] = **missing**\n", i);
}
auto l2 = new LRUCache!(char, int)(10, -17);
//string s = "This is a rather long string of quasi-random text,";
//int i = 0;
i = 0;
foreach (char c; s)
{ writef ("adding %d\n", i);
l2[c] = ++i;
}
l2.dump;
// this next bit shows that accesses change the nodeId
// remember that nodeId should not be used for any purpose outside of the class...
// it's highly unstable.
for (i = 0; i < s.length; i++)
{ if (l2.contains(s[i]))
writef ("l2[%2s] = '%s', id = %s\n", s[i], l2[s[i]], l2.nodeId(s[i]));
//else
// writef ("l2[%2s] = **missing**\n", s[i]);
}
}
}

]

The code for this project is now located in the

scrapple project:
*

project page
*

source

LRUCache

This is a "Least Recently Used Cache", that has a maximum size, and when the size is exceeded, it deletes the least recently used entries.

The code for this project is now located in the scrapple project: