voxelman.container.cache source code

1 /**
2 Copyright: Copyright (c) 2016 Andrey Penechko.
3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6 module voxelman.container.cache;
7 
8 // entries are sorted based on last access time.
9 // successfull gets bring entries to the front of list,
10 // thus preventing them from being replaces on put
11 // LRU (least recently used) are dropped when cache is filled.
12 struct Cache(Key, Value, uint maxEntries)
13 {
14 	enum lastEntryIndex = maxEntries - 1;
15 
16 	// returns null if key is not found.
17 	// gives entry max priority
18 	Value* get(Key key)
19 	{
20 		static bool searchPred(Entry a, Key b)
21 		{
22 			return a.key == b;
23 		}
24 		import std.algorithm : countUntil;
25 		ptrdiff_t entry = countUntil!searchPred(entries[0..numUsed], key);
26 
27 		if (entry == -1)
28 			return null;
29 		else
30 		{
31 			bringEntryToFront(entry);
32 			return &values[entries[0].valueIndex];
33 		}
34 	}
35 
36 	private void bringEntryToFront(size_t index)
37 	{
38 		Entry temp = entries[index];
39 		for(ptrdiff_t i = index-1; i>=0; --i)
40 		{
41 			entries[i+1] = entries[i];
42 		}
43 		entries[0] = temp;
44 	}
45 
46 	void put(Key key, Value val)
47 	{
48 		Value* valPtr = put(key);
49 		*valPtr = val;
50 	}
51 
52 	Value* put(Key key)
53 	{
54 		if (numUsed == maxEntries)
55 		{
56 			auto index = entries[lastEntryIndex].valueIndex;
57 			entries[lastEntryIndex] = Entry(key, index);
58 			bringEntryToFront(lastEntryIndex);
59 			return &values[index];
60 		}
61 		else
62 		{
63 			entries[numUsed] = Entry(key, numUsed);
64 			auto res = &values[numUsed];
65 			bringEntryToFront(numUsed);
66 			++numUsed;
67 			return res;
68 		}
69 	}
70 
71 	void toString()(scope void delegate(const(char)[]) sink) const
72 	{
73 		import std.format : formattedWrite;
74 		sink.formattedWrite("Cache!(%s, %s, %s)(", Key, Value, maxEntries);
75 		foreach(i; 0..numUsed)
76 		{
77 			auto e = entries[i];
78 			sink.formattedWrite("%s:%s, ", e.key, values[e.valueIndex]);
79 		}
80 		sink.formattedWrite(")");
81 	}
82 
83 	static struct Entry
84 	{
85 		Key key;
86 		size_t valueIndex;
87 	}
88 
89 	Entry[maxEntries] entries;
90 	Value[maxEntries] values;
91 	size_t numUsed;
92 }
93 
94 unittest
95 {
96 	Cache!(int, string, 3) cache;
97 
98 	//cache.writeln;
99 	cache.put(1, "1");
100 	//cache.writeln;
101 	cache.put(2, "2");
102 	//cache.writeln;
103 	cache.put(3, "3");
104 	//cache.writeln;
105 	cache.put(4, "4");
106 	//cache.writeln;
107 	assert(cache.get(1) is null);
108 
109 	assert(*cache.get(4) == "4");
110 	//cache.writeln;
111 
112 	assert(cache.get(5) is null);
113 
114 	cache.put(5, "5");
115 	//cache.writeln;
116 	assert(cache.get(2) is null);
117 
118 	cache.get(3);
119 	//cache.writeln;
120 	assert(cache.entries[0].key == 3);
121 }