Note: This website is archived. For up-to-date information about D projects and development, please visit wiki.dlang.org.

WikiStart: lrucache.d

File lrucache.d, 4.7 kB (added by CharlesH, 14 years ago)

lrucache.d source file. (tabs == 3 spaces if you need to expand)

Line 
1 // lrucache.d
2 // to test for correctness, compile thus:
3 // dmd -version="testLRUCache" lrucache.d
4 //
5 /**
6   *   Author:  Charles Hixson, charleshixsn@earthlink.net
7   *   Date:    Nov. 8, 2007
8   *   Version: 0.2.b
9   *         (Note:  Version 0.1 was lacking a version number)
10   *   License: MIT license
11   *         (Note:  Some future version will switch to GPL...but this stuff
12   *          *SHOULD* be public domain.)
13   *   Copyright:  Charles Hixson, all rights reserved.  (But see the license.)
14   */
15
16 import   std.conv;
17 import   std.stdio;
18
19 /**
20    *  Key must implement opCmp and be hashable
21    *  Cache's should not be too large, so the size is a ushort.  That's excessive.
22    *  If you want a cache nearly that large, use a database or something.
23    */
24 class LRUCache(Key, Body)
25 {
26 private:
27    typedef  ushort   NodeId;
28    Body[Key]   bodies;
29    NodeId[Key] nodIds;
30    Body        _invalid;
31    ushort      _maxLength;
32    NodeId      maxNode;
33
34 public:
35    this  (ushort maxLength, Body invalid)
36    {  _invalid    =  invalid;
37       _maxLength  =  maxLength;
38    }
39
40
41    const (Body)   opIndex  (Key k)
42    {  if (auto b  =  k  in bodies)
43       {  nodIds[k]   =  ++maxNode;
44          if (maxNode >= _maxLength - 2)   renumber;
45          return   *b;
46       }
47       return   _invalid;
48    }
49
50    const (Body)   opIndexAssign  (Body b, Key k)
51    {  //Node n;
52       if (b == _invalid)   return   _invalid;
53       nodIds[k]   =  ++maxNode;
54       bodies[k]   =  b;
55       if (bodies.length > _maxLength)
56       {  // cache is too large, so remove approx. the 1/4 least recently used
57          ////  N.B.:  Expiration is based on access time.  Creation time is (so far) unused.
58          ulong sum   =  0;
59          NodeId   maxT  =  0;
60          NodeId   minT  =  maxNode;
61          NodeId   meanT;
62          foreach  (nId; nodIds)
63          {  sum   += nId;
64             if (nId < minT)  minT  =  nId;
65             if (nId > maxT)  maxT  =  nId;
66          }
67          meanT =  cast(NodeId)(sum / nodIds.length);
68          NodeId   limit =  cast(NodeId)(minT + (meanT - minT) / 2);
69          foreach  (Key key, NodeId nId; nodIds)
70          {  if (nId <= limit)
71             {  nodIds.remove(key);
72                bodies.remove(key);
73             }
74             else      nodIds[key]  =  cast(NodeId)(nodIds[key] - limit + 1);
75          }
76          maxNode  =  cast(NodeId)(maxNode - limit + 1);
77       }
78       if (maxNode >= _maxLength - 2)   renumber;
79       return   b;
80    }
81
82    int   length() {  return   bodies.length; }
83
84    void  remove   (Key k)
85    {  if (k in bodies)
86       {  nodIds.remove(k);
87          bodies.remove(k);
88       }
89    }
90
91    bool  contains (Key k)
92    {  if (k in nodIds)
93       {  nodIds[k]   =  ++maxNode;
94          return   true;
95       }
96       return   false;
97    }
98
99    ///   for diagnostic purposes only.  Do NOT use this value.
100    ulong   nodeId(Key k)
101    {  if (auto nId   =  k in nodIds)  return   *nId;   return   0; }
102
103    /**
104    *  renumber the nodes.  This is a separate routine to allow different
105    *  algorithms to be easily inserted.  I've picked quick & easy.
106    */
107    private  void  renumber()
108    {  NodeId   nId   =  0;
109       foreach  (Key key, NodeId node; nodIds)   nodIds[key] =  ++nId;
110       maxNode  =   cast(NodeId)((nId > 0) ?  nId - 1  :  0);
111    }
112    version  (testLRUCache)
113    {  void  dump()
114       {  writef("there are %s entries in the cache\n", bodies.length);
115          Key[] keys  =  bodies.keys;
116          for   (int i = 0; i < keys.length;  i++)
117          {  writef ("%2s", keys[i]);
118             writef (": %10s", nodIds[keys[i]]);
119             writef (": %s\n", bodies[keys[i]]);
120          }
121       }
122    }
123 }
124
125
126 version  (testLRUCache)
127 {
128    void  main()
129    {  auto  l  =  new   LRUCache!(int, char)(10, cast(char)0);
130       string   s  =  "This is a rather long string of quasi-random text,";
131       int   i  =  0;
132       foreach  (char c; s)
133       {  writef ("adding %d\n", i);
134          l[i++]   =  c;
135       }
136       l.dump;
137       for   (i = 0;  i < s.length;  i++)
138       {  if (l.contains(i))   writef ("l[%2s] = '%s', id = %s\n", i, l[i], l.nodeId(i));
139          //else                 writef ("l[%2s] = **missing**\n", i);
140       }
141       auto  l2 =  new   LRUCache!(char, int)(10, -17);
142       //string s  =  "This is a rather long string of quasi-random text,";
143       //int i  =  0;
144       i  =  0;
145       foreach  (char c; s)
146       {  writef ("adding %d\n", i);
147          l2[c] =  ++i;
148       }
149       l2.dump;
150       // this next bit shows that accesses change the nodeId
151       // remember that nodeId should not be used for any purpose outside of the class...
152       // it's highly unstable.
153       for   (i = 0;  i < s.length;  i++)
154       {  if (l2.contains(s[i]))
155                   writef ("l2[%2s] = '%s', id = %s\n", s[i], l2[s[i]], l2.nodeId(s[i]));
156          //else
157          //       writef ("l2[%2s] = **missing**\n", s[i]);
158       }
159    }
160 }