1 /* Copyright (C) 2004 - 2009  Versant Inc.  http://www.db4o.com */
2 
3 using System;
4 using System.Collections;
5 using Db4objects.Db4o.Foundation;
6 using Db4objects.Db4o.Internal.Caching;
7 
8 namespace Db4objects.Db4o.Internal.Caching
9 {
10 	/// <exclude>
11 	/// Simplified version of the algorithm taken from here:
12 	/// http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2641
13 	/// </exclude>
14 	internal class LRU2QCache : ICache4
15 	{
16 		private readonly CircularBuffer4 _am;
17 
18 		private readonly CircularBuffer4 _a1;
19 
20 		private readonly IDictionary _slots;
21 
22 		private readonly int _maxSize;
23 
24 		private readonly int _a1_threshold;
25 
LRU2QCache(int maxSize)26 		internal LRU2QCache(int maxSize)
27 		{
28 			_maxSize = maxSize;
29 			_a1_threshold = _maxSize / 4;
30 			_am = new CircularBuffer4(_maxSize);
31 			_a1 = new CircularBuffer4(_maxSize);
32 			_slots = new Hashtable(maxSize);
33 		}
34 
Produce(object key, IFunction4 producer, IProcedure4 finalizer )35 		public virtual object Produce(object key, IFunction4 producer, IProcedure4 finalizer
36 			)
37 		{
38 			if (key == null)
39 			{
40 				throw new ArgumentNullException();
41 			}
42 			if (_am.Remove(key))
43 			{
44 				_am.AddFirst(key);
45 				return _slots[key];
46 			}
47 			if (_a1.Remove(key))
48 			{
49 				_am.AddFirst(key);
50 				return _slots[key];
51 			}
52 			if (_slots.Count >= _maxSize)
53 			{
54 				DiscardPage(finalizer);
55 			}
56 			object value = producer.Apply(key);
57 			_slots[key] = value;
58 			_a1.AddFirst(key);
59 			return value;
60 		}
61 
DiscardPage(IProcedure4 finalizer)62 		private void DiscardPage(IProcedure4 finalizer)
63 		{
64 			if (_a1.Size() >= _a1_threshold)
65 			{
66 				DiscardPageFrom(_a1, finalizer);
67 			}
68 			else
69 			{
70 				DiscardPageFrom(_am, finalizer);
71 			}
72 		}
73 
DiscardPageFrom(CircularBuffer4 list, IProcedure4 finalizer)74 		private void DiscardPageFrom(CircularBuffer4 list, IProcedure4 finalizer)
75 		{
76 			Discard(list.RemoveLast(), finalizer);
77 		}
78 
Discard(object key, IProcedure4 finalizer)79 		private void Discard(object key, IProcedure4 finalizer)
80 		{
81 			if (null != finalizer)
82 			{
83 				finalizer.Apply(_slots[key]);
84 			}
85 			Sharpen.Collections.Remove(_slots, key);
86 		}
87 
ToString()88 		public override string ToString()
89 		{
90 			return "LRU2QCache(am=" + ToString(_am) + ", a1=" + ToString(_a1) + ")";
91 		}
92 
ToString(IEnumerable buffer)93 		private string ToString(IEnumerable buffer)
94 		{
95 			return Iterators.ToString(buffer);
96 		}
97 
GetEnumerator()98 		public virtual IEnumerator GetEnumerator()
99 		{
100 			return _slots.Values.GetEnumerator();
101 		}
102 	}
103 }
104