You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by di...@apache.org on 2009/12/03 17:00:37 UTC
svn commit: r886834 -
/incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs
Author: digy
Date: Thu Dec 3 16:00:34 2009
New Revision: 886834
URL: http://svn.apache.org/viewvc?rev=886834&view=rev
Log:
LUCENENET-315 SimpleLRUCache Implementation
Modified:
incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs
Modified: incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs
URL: http://svn.apache.org/viewvc/incubator/lucene.net/trunk/C%23/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs?rev=886834&r1=886833&r2=886834&view=diff
==============================================================================
--- incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs (original)
+++ incubator/lucene.net/trunk/C#/src/Lucene.Net/Util/Cache/SimpleLRUCache.cs Thu Dec 3 16:00:34 2009
@@ -20,161 +20,88 @@
namespace Lucene.Net.Util.Cache
{
- public class SimpleLRUCache : SimpleLRUCache_LUCENENET_190_1
+ public class SimpleLRUCache : SimpleMapCache
{
- public SimpleLRUCache(int Capacity)
- : base(Capacity)
- {
- }
- }
-
-
- /// <summary> Simple LRU cache implementation that uses a LinkedHashMap.
- /// This cache is not synchronized, use {@link Cache#SynchronizedCache(Cache)}
- /// if needed.
- ///
- /// Implemented for LUCENENET-190. Good for capacity < 1536
- /// </summary>
- [System.ComponentModel.EditorBrowsable(System.ComponentModel.EditorBrowsableState.Never)]
- public class SimpleLRUCache_LUCENENET_190_1 : Cache
- {
- System.Collections.Generic.Dictionary<object, LRUCacheValueEntry> Data = new Dictionary<object, LRUCacheValueEntry>();
- SortedList<long, object> TimeStamps = new SortedList<long, object>();
+ /// <summary>
+ /// The maximum number of items to cache.
+ /// </summary>
+ private int capacity;
+
+ /// <summary>
+ /// The list to efficiently maintain the LRU state.
+ /// </summary>
+ private LinkedList<ListValueEntry> list;
+
+ /// <summary>
+ /// The dictionary to hash into any location in the list.
+ /// </summary>
+ private Dictionary<object, LinkedListNode<ListValueEntry>> lookup;
+
+ /// <summary>
+ /// The node instance to use/re-use when adding an item to the cache.
+ /// </summary>
+ private LinkedListNode<ListValueEntry> openNode;
- long TimeStamp = 0;
- int Capacity = 1024;
-
- /// <summary> Creates a last-recently-used cache with the specified size. </summary>
- public SimpleLRUCache_LUCENENET_190_1(int Capacity)
+ public SimpleLRUCache(int Capacity)
{
- this.Capacity = Capacity;
+ this.capacity = Capacity;
+ this.list = new LinkedList<ListValueEntry>();
+ this.lookup = new Dictionary<object, LinkedListNode<ListValueEntry>>(Capacity + 1);
+ this.openNode = new LinkedListNode<ListValueEntry>(new ListValueEntry(null, null));
}
public override void Put(object Key, object Value)
{
if (Get(Key) == null)
{
- TimeStamp++;
- Data.Add(Key, new LRUCacheValueEntry(TimeStamp, Value));
- TimeStamps.Add(TimeStamp, Key);
+ this.openNode.Value.ItemKey = Key;
+ this.openNode.Value.ItemValue = Value;
+ this.list.AddFirst(this.openNode);
+ this.lookup.Add(Key, this.openNode);
- if (Data.Count > Capacity)
+ if (this.list.Count > this.capacity)
{
- long key = TimeStamps.Keys[0];
- Data.Remove(TimeStamps[key]);
- TimeStamps.RemoveAt(0);
- }
- }
- }
-
- public override object Get(object Key)
- {
- LRUCacheValueEntry e = null;
- Data.TryGetValue(Key, out e);
- if (e == null) return null;
-
- TimeStamps.Remove(e.TimeStamp);
- e.TimeStamp = ++TimeStamp;
- TimeStamps.Add(e.TimeStamp, Key);
- return e.Value;
-
- }
-
- public override bool ContainsKey(object key)
- {
- return Data.ContainsKey(key);
- }
-
- public override void Close()
- {
- }
-
- class LRUCacheValueEntry
- {
- public long TimeStamp = 0;
- public object Value;
-
- public LRUCacheValueEntry(long TimeStamp, object Value)
- {
- this.TimeStamp = TimeStamp;
- this.Value = Value;
- }
- }
- }
-
-
- /// <summary> Simple LRU cache implementation that uses a LinkedHashMap.
- /// This cache is not synchronized, use {@link Cache#SynchronizedCache(Cache)}
- /// if needed.
- ///
- /// Implemented for LUCENENET-190. Good for capacity > 1536
- /// </summary>
- [System.ComponentModel.EditorBrowsable(System.ComponentModel.EditorBrowsableState.Never)]
- public class SimpleLRUCache_LUCENENET_190_2 : Lucene.Net.Util.Cache.Cache
- {
- System.Collections.Generic.Dictionary<object, LRUCacheValueEntry> Data = new Dictionary<object, LRUCacheValueEntry>();
- System.Collections.Generic.SortedDictionary<long, object> TimeStamps = new SortedDictionary<long, object>();
-
- long TimeStamp = 0;
- int Capacity = 1024;
-
- /// <summary> Creates a last-recently-used cache with the specified size. </summary>
- public SimpleLRUCache_LUCENENET_190_2(int Capacity)
- {
- this.Capacity = Capacity;
- }
-
- public override void Put(object Key, object Value)
- {
- if (Get(Key) == null)
- {
- TimeStamp++;
- Data.Add(Key, new LRUCacheValueEntry(TimeStamp, Value));
- TimeStamps.Add(TimeStamp, Key);
+ // last node is to be removed and saved for the next addition to the cache
+ this.openNode = this.list.Last;
- if (Data.Count > Capacity)
+ // remove from list & dictionary
+ this.list.RemoveLast();
+ this.lookup.Remove(this.openNode.Value.ItemKey);
+ }
+ else
{
- SortedDictionary<long, object>.Enumerator enumTimeStamps = TimeStamps.GetEnumerator();
- enumTimeStamps.MoveNext();
- long key = enumTimeStamps.Current.Key;
- Data.Remove(TimeStamps[key]);
- TimeStamps.Remove(key);
+ // still filling the cache, create a new open node for the next time
+ this.openNode = new LinkedListNode<ListValueEntry>(new ListValueEntry(null, null));
}
-
}
}
public override object Get(object Key)
{
- LRUCacheValueEntry e = null;
- Data.TryGetValue(Key, out e);
- if (e == null) return null;
-
- TimeStamps.Remove(e.TimeStamp);
- e.TimeStamp = ++TimeStamp;
- TimeStamps.Add(e.TimeStamp, Key);
- return e.Value;
- }
-
- class LRUCacheValueEntry
- {
- public long TimeStamp = 0;
- public object Value;
-
- public LRUCacheValueEntry(long TimeStamp, object Value)
+ LinkedListNode<ListValueEntry> node = null;
+ if(!this.lookup.TryGetValue(Key, out node))
{
- this.TimeStamp = TimeStamp;
- this.Value = Value;
+ return null;
}
+ this.list.Remove(node);
+ this.list.AddFirst(node);
+ return node.Value.ItemValue;
}
- public override bool ContainsKey(object key)
+ /// <summary>
+ /// Container to hold the key and value to aid in removal from
+ /// the <see cref="lookup"/> dictionary when an item is removed from cache.
+ /// </summary>
+ class ListValueEntry
{
- return Data.ContainsKey(key);
- }
+ internal object ItemValue;
+ internal object ItemKey;
- public override void Close()
- {
+ internal ListValueEntry(object key, object value)
+ {
+ this.ItemKey = key;
+ this.ItemValue = value;
+ }
}
}