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