File: Shared\MS\Internal\SizeLimitedCache.cs
Project: wpf\src\PresentationCore.csproj (PresentationCore)
using System;
using System.Collections.Generic;
 
using MS.Internal.PresentationCore;
 
namespace MS.Internal
{
    /// <summary>
    ///     Implementation of a cache with a limited size (a limited number of items
    ///     can be stored in the cache). When adding to a full cache, the element
    ///     that was last accessed is removed. Also, the cache supports permanent items
    ///     which are not subject to removal or change.
    /// </summary>
    /// <remarks>
    ///     The cache is stored in a hash table. The hash table maps
    ///     keys to nodes in a linked list. Each node contains the required
    ///     info (key, resource, permanence flag). The linked list is what
    ///     maintains the order in which items should be removed. The beginning
    ///     (_begin.Next) is the first to be removed and the end (_end.Previous)
    ///     is the last to be removed. Every time a node is accessed or
    ///     changed, it gets moved to the end of the list. Also, permanent items,
    ///     though in the hash table, are NOT in the linked list.
    /// </remarks>
    [FriendAccessAllowed]
    internal class SizeLimitedCache<K, V>
    {
        //*****************************************************
        // Constructors
        // ****************************************************
 
        /// <summary>
        ///     Constructs a ResourceCache instance
        /// </summary>
        /// <param name="maximumItems">
        ///     The maximum number of nonpermanent resources the cache can store.
        /// </param>
        public SizeLimitedCache(int maximumItems)
        {
            if (maximumItems <= 0)
            {
                throw new ArgumentOutOfRangeException("maximumItems");
            }
 
            _maximumItems = maximumItems;
            _permanentCount = 0;
 
            // set up an empty list.
            // the _begin and _end nodes are empty nodes marking the begin and
            // end of the list.
            _begin = new Node(default(K), default(V), false);
            _end = new Node(default(K), default(V), false);
           _begin.Next = _end;
            _end.Previous = _begin;
            _nodeLookup = new Dictionary<K, Node>();
        }
 
        //*****************************************************
        // Public Properties
        // ****************************************************
 
        /// <summary>
        ///     Returns the maximum number of nonpermanent resources the cache can store.
        /// </summary>
        public int MaximumItems
        {
            get
            {
                return _maximumItems;
            }
        }
 
        //*****************************************************
        // Public Methods
        // ****************************************************
 
        /// <summary>
        ///     Add an item to the cache. If the cache is full, the last item 
        ///     to have been accessed is removed. Permanent objects are not 
        ///     included in the count to determine if the cache is full.
        /// </summary>
        /// <param name="key">
        ///     The key of the object to add.
        /// </param>
        /// <param name="resource">
        ///     The object to be stored in the cache.
        /// </param>
        /// <param name="isPermanent">
        ///     bool indicating if the object to be cached will always be left
        ///     in the cache upon adding to a full cache.
        /// </param>
        public void Add(K key, V resource, bool isPermanent)
        {
 
            if ( (object)key == null)
            {
                throw new ArgumentNullException("key");
            }
            if ( (object)resource == null)
            {
                throw new ArgumentNullException("resource");
            }
 
            // note: [] throws, thus we should check if its in the dictionary first.
            if (!_nodeLookup.ContainsKey(key))
            {
                Node node = new Node(key, resource, isPermanent);
                if (!isPermanent)
                {
                    if (IsFull())
                    {
                        RemoveOldest();
                    }
                    InsertAtEnd(node);
                }
                else
                {
                    _permanentCount++;
                }
                _nodeLookup[key] = node;
            }
            else
            {
                Node node = _nodeLookup[key];
                if (!node.IsPermanent)
                {
                    RemoveFromList(node);
                }
 
                if (!node.IsPermanent && isPermanent)
                {
                    _permanentCount++;
                }
                else if (node.IsPermanent && !isPermanent)
                {
                    _permanentCount--;
                    if (IsFull())
                    {
                        RemoveOldest();
                    }
                }
 
                node.IsPermanent = isPermanent;
                node.Resource = resource;
                if (!isPermanent)
                {
                    InsertAtEnd(node);
                }
            }
        }
 
        /// <summary>
        ///     Remove an item from the cache.
        /// </summary>
        /// <param name="key">
        ///     The key of the object to remove.
        /// </param>
        public void Remove(K key)
        {
            if ( (object)key == null)
            {
                throw new ArgumentNullException("key");
            }
 
            // note: [] throws, thus we should check if its in the dictionary first.
            if (!_nodeLookup.ContainsKey(key))
            {
                return;
            }
            Node node = _nodeLookup[key];
 
            _nodeLookup.Remove(key);
            if (!node.IsPermanent)
            {
                RemoveFromList(node);
            }
            else
            {
                _permanentCount--;
            }
        }
 
        /// <summary>
        ///     Retrieve an item from the cache.
        /// </summary>
        /// <param name="key">
        ///     The key of the object to get.
        /// </param>
        /// <returns>
        ///     The object stored in the cache based on the key. If the key is not
        ///     contained in the class, V.default is returned (Use the Contains method
        ///     if V is a value type)
        /// </returns>
        public V Get(K key)
        {
            if ( (object)key == null)
            {
                throw new ArgumentNullException("key");
            }
 
            // note: [] throws, thus we should check if its in the dictionary first.
            if (!_nodeLookup.ContainsKey(key))
            {
                return default(V);
            }
            Node node = _nodeLookup[key];
 
            if (!node.IsPermanent)
            {
                RemoveFromList(node);
                InsertAtEnd(node);
            }
 
            return node.Resource;
        }
 
        //*****************************************************
        // Private Methods
        // ****************************************************
 
        /// <summary>
        ///     Remove the oldest nonpermanent item in the cache.
        /// </summary>
        private void RemoveOldest()
        {
            Node node = _begin.Next;
            _nodeLookup.Remove(node.Key);
            RemoveFromList(node);
        }
 
        /// <summary>
        ///     Inserts a node at the end of the linked list
        /// </summary>
        /// <param name="node">
        ///     The node to insert
        /// </param>
        private void InsertAtEnd(Node node)
        {
            node.Next = _end;
            node.Previous = _end.Previous;
            node.Previous.Next = node;
            _end.Previous = node;
        }
 
        /// <summary>
        ///     Removes an item from the linked list
        /// </summary>
        /// <param name="node">
        ///     The node to remove
        /// </param>
        private void RemoveFromList(Node node)
        {
            node.Previous.Next = node.Next;
            node.Next.Previous = node.Previous;
        }
 
        /// <summary>
        ///     Check if the cache is full. Do not include permanent items
        ///     in the count.
        /// </summary>
        /// <returns>
        ///     true if the cache is full. false if not.
        /// </returns>
        private bool IsFull()
        {
            return (_nodeLookup.Count - _permanentCount >= _maximumItems);
        }
 
        /// <summary>
        ///     Doubly linked list node class. Has 3 values: key, resource, permanence flag
        /// </summary>
        private class Node
        {
            public Node(K key, V resource, bool isPermanent)
            {
                Key = key;
                Resource = resource;
                IsPermanent = isPermanent;
            }
 
            public K Key
            {
                get { return _key; }
                set { _key = value; }
            }
 
            public V Resource
            {
                get { return _resource; }
                set { _resource = value; }
            }
 
            public bool IsPermanent
            {
                get { return _isPermanent; }
                set { _isPermanent = value; }
            }
 
            public Node Next
            {
                get { return _next; }
                set { _next = value; }
            }
 
            public Node Previous
            {
                get { return _previous; }
                set { _previous = value; }
            }
 
            private V _resource;
            private K _key;
            private bool _isPermanent;
            private Node _next;
            private Node _previous;
        }
 
        //*****************************************************
        // Private Fields
        // ****************************************************
 
        // the maximum nonpermanent items allowed
        private int _maximumItems;
 
        // need to keep a separate counter for permanent items
        private int _permanentCount;
 
        // the _begin and _end nodes are empty nodes marking the begin and
        // end of the list.
        private Node _begin;
        private Node _end;
 
        // the hashtable mapping keys to nodes
        private Dictionary<K, Node> _nodeLookup;
    }
}