CnmMemoryCache.cs

Go to the documentation of this file.

/*
 * Copyright (c) Contributors, http://opensimulator.org/
 * See CONTRIBUTORS.TXT for a full list of copyright holders.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the OpenSimulator Project nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace OpenSim.Framework
{
    public class CnmMemoryCache<TKey, TValue> : ICnmCache<TKey, TValue>
    {
        public const int DefaultMaxCount = 4096;

        public const long DefaultMaxSize = 134217728;

        private const int DefaultOperationsBetweenTimeChecks = 40;

        public static readonly TimeSpan DefaultExpirationTime = TimeSpan.FromMinutes(30.0);

        public static readonly TimeSpan MinExpirationTime = TimeSpan.FromSeconds(10.0);

        public readonly IEqualityComparer<TKey> Comparer;

        private TimeSpan m_expirationTime = DefaultExpirationTime;

        private int m_generationBucketCount;

        private int m_generationElementCount;

        private long m_generationMaxSize;

        private int m_maxCount;

        private long m_maxElementSize;

        private long m_maxSize;

        private IGeneration m_newGeneration;

        private IGeneration m_oldGeneration;

        private int m_operationsBetweenTimeChecks = DefaultOperationsBetweenTimeChecks;

        private readonly object m_syncRoot = new object();

        private int m_version;

        public CnmMemoryCache()
            : this(DefaultMaxSize)
        {
        }

        public CnmMemoryCache(long maximalSize)
            : this(maximalSize, DefaultMaxCount)
        {
        }

        public CnmMemoryCache(long maximalSize, int maximalCount)
            : this(maximalSize, maximalCount, DefaultExpirationTime)
        {
        }

        public CnmMemoryCache(long maximalSize, int maximalCount, TimeSpan expirationTime)
            : this(maximalSize, maximalCount, expirationTime, EqualityComparer<TKey>.Default)
        {
        }

        public CnmMemoryCache(long maximalSize,
            int maximalCount,
            TimeSpan expirationTime,
            IEqualityComparer<TKey> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            if (expirationTime < MinExpirationTime)
                expirationTime = MinExpirationTime;
            if (maximalCount < 8)
                maximalCount = 8;
            if (maximalSize < 8)
                maximalSize = 8;
            if (maximalCount > maximalSize)
                maximalCount = (int) maximalSize;

            Comparer = comparer;
            m_expirationTime = expirationTime;
            m_maxSize = maximalSize;
            m_maxCount = maximalCount;

            Initialize();
        }

        protected virtual void AddToNewGeneration(int bucketIndex, TKey key, TValue value, long size)
        {
            // Add to newest generation
            if (!m_newGeneration.Set(bucketIndex, key, value, size))
            {
                // Failed to add new generation
                RecycleGenerations();
                m_newGeneration.Set(bucketIndex, key, value, size);
            }

            m_version++;
        }

        protected virtual int GetBucketIndex(TKey key)
        {
            return (Comparer.GetHashCode(key) & 0x7FFFFFFF) % m_generationBucketCount;
        }

        protected virtual void PurgeGeneration(IGeneration generation)
        {
            generation.Clear();
            m_version++;
        }

        private void CheckExpired()
        {
            // Do this only one in every m_operationsBetweenTimeChecks 
            // Fetching time is using several millisecons - it is better not to do all time.
            m_operationsBetweenTimeChecks--;
            if (m_operationsBetweenTimeChecks <= 0)
                PurgeExpired();
        }

        private void Initialize()
        {
            m_version++;

            m_generationMaxSize = MaxSize / 2;
            MaxElementSize = MaxSize / 8;
            m_generationElementCount = MaxCount / 2;

            // Buckets need to be prime number to get better spread of hash values
            m_generationBucketCount = PrimeNumberHelper.GetPrime(m_generationElementCount);

            m_newGeneration = new HashGeneration(this);
            m_oldGeneration = new HashGeneration(this);
            m_oldGeneration.MakeOld();
        }

        private void RecycleGenerations()
        {
            // Rotate old generation to new generation, new generation to old generation
            IGeneration temp = m_newGeneration;
            m_newGeneration = m_oldGeneration;
            m_newGeneration.Clear();
            m_oldGeneration = temp;
            m_oldGeneration.MakeOld();
        }

        #region Nested type: Enumerator

        private class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private int m_currentEnumerator = -1;

            private readonly IEnumerator<KeyValuePair<TKey, TValue>>[] m_generationEnumerators =
                new IEnumerator<KeyValuePair<TKey, TValue>>[2];

            public Enumerator(CnmMemoryCache<TKey, TValue> cache)
            {
                m_generationEnumerators[ 0 ] = cache.m_newGeneration.GetEnumerator();
                m_generationEnumerators[ 1 ] = cache.m_oldGeneration.GetEnumerator();
            }

            #region IEnumerator<KeyValuePair<TKey,TValue>> Members

            public KeyValuePair<TKey, TValue> Current
            {
                get
                {
                    if (m_currentEnumerator == -1 || m_currentEnumerator >= m_generationEnumerators.Length)
                        throw new InvalidOperationException();

                    return m_generationEnumerators[ m_currentEnumerator ].Current;
                }
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }

            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                if (m_currentEnumerator == -1)
                    m_currentEnumerator = 0;

                while (m_currentEnumerator < m_generationEnumerators.Length)
                {
                    if (m_generationEnumerators[ m_currentEnumerator ].MoveNext())
                        return true;

                    m_currentEnumerator++;
                }

                return false;
            }

            public void Reset()
            {
                foreach (IEnumerator<KeyValuePair<TKey, TValue>> enumerator in m_generationEnumerators)
                {
                    enumerator.Reset();
                }

                m_currentEnumerator = -1;
            }

            #endregion
        }

        #endregion

        #region Nested type: HashGeneration

        private class HashGeneration : IGeneration
        {
            private bool m_accessedSinceLastTimeCheck;

            private readonly int[] m_buckets;

            private readonly CnmMemoryCache<TKey, TValue> m_cache;

            private readonly Element[] m_elements;

            private DateTime m_expirationTime1;

            private int m_firstFreeElement;

            private int m_freeCount;

            private bool m_newGeneration;

            private int m_nextUnusedElement;

            private long m_size;

            public HashGeneration(CnmMemoryCache<TKey, TValue> cache)
            {
                m_cache = cache;
                m_elements = new Element[m_cache.m_generationElementCount];
                m_buckets = new int[m_cache.m_generationBucketCount];
                Clear();
            }

            private int FindElementIndex(int bucketIndex, TKey key, bool moveToFront, out int previousIndex)
            {
                previousIndex = -1;
                int elementIndex = m_buckets[ bucketIndex ];
                while (elementIndex >= 0)
                {
                    if (m_cache.Comparer.Equals(key, m_elements[ elementIndex ].Key))
                    {
                        // Found match
                        if (moveToFront && previousIndex >= 0)
                        {
                            // Move entry to front
                            m_elements[ previousIndex ].Next = m_elements[ elementIndex ].Next;
                            m_elements[ elementIndex ].Next = m_buckets[ bucketIndex ];
                            m_buckets[ bucketIndex ] = elementIndex;
                            previousIndex = 0;
                        }

                        return elementIndex;
                    }

                    previousIndex = elementIndex;
                    elementIndex = m_elements[ elementIndex ].Next;
                }

                return -1;
            }

            private void RemoveElement(int bucketIndex, int entryIndex, int previousIndex)
            {
                if (previousIndex >= 0)
                    m_elements[ previousIndex ].Next = m_elements[ entryIndex ].Next;
                else
                    m_buckets[ bucketIndex ] = m_elements[ entryIndex ].Next;

                Size -= m_elements[ entryIndex ].Size;
                m_elements[ entryIndex ].Value = default(TValue);
                m_elements[ entryIndex ].Key = default(TKey);

                // Add element to free elements list
                m_elements[ entryIndex ].Next = m_firstFreeElement;
                m_firstFreeElement = entryIndex;
                m_freeCount++;
            }

            #region Nested type: Element

            private struct Element
            {
                public TKey Key;

                public int Next;

                public long Size;

                public TValue Value;

                public bool IsFree
                {
                    get { return Size == 0; }
                }
            }

            #endregion

            #region Nested type: Enumerator

            private class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
            {
                private KeyValuePair<TKey, TValue> m_current;

                private int m_currentIndex;

                private readonly HashGeneration m_generation;

                private readonly int m_version;

                public Enumerator(HashGeneration generation)
                {
                    m_generation = generation;
                    m_version = m_generation.m_cache.m_version;
                }

                #region IEnumerator<KeyValuePair<TKey,TValue>> Members

                public KeyValuePair<TKey, TValue> Current
                {
                    get
                    {
                        if (m_currentIndex == 0 || m_currentIndex >= m_generation.Count)
                            throw new InvalidOperationException();

                        return m_current;
                    }
                }

                object IEnumerator.Current
                {
                    get { return Current; }
                }

                public void Dispose()
                {
                }

                public bool MoveNext()
                {
                    if (m_version != m_generation.m_cache.m_version)
                        throw new InvalidOperationException();

                    while (m_currentIndex < m_generation.Count)
                    {
                        if (m_generation.m_elements[ m_currentIndex ].IsFree)
                        {
                            m_currentIndex++;
                            continue;
                        }

                        m_current = new KeyValuePair<TKey, TValue>(m_generation.m_elements[ m_currentIndex ].Key,
                            m_generation.m_elements[ m_currentIndex ].Value);
                        m_currentIndex++;
                        return true;
                    }

                    m_current = new KeyValuePair<TKey, TValue>();
                    return false;
                }

                public void Reset()
                {
                    if (m_version != m_generation.m_cache.m_version)
                        throw new InvalidOperationException();

                    m_currentIndex = 0;
                }

                #endregion
            }

            #endregion

            #region IGeneration Members

            public bool AccessedSinceLastTimeCheck
            {
                get { return m_accessedSinceLastTimeCheck; }

                set { m_accessedSinceLastTimeCheck = value; }
            }

            public int Count
            {
                get { return m_nextUnusedElement - m_freeCount; }
            }

            public DateTime ExpirationTime
            {
                get { return m_expirationTime1; }

                set { m_expirationTime1 = value; }
            }

            public long Size
            {
                get { return m_size; }

                private set { m_size = value; }
            }

            public void Clear()
            {
                for (int i = m_buckets.Length - 1 ; i >= 0 ; i--)
                {
                    m_buckets[ i ] = -1;
                }

                Array.Clear(m_elements, 0, m_elements.Length);
                Size = 0;
                m_firstFreeElement = -1;
                m_freeCount = 0;
                m_nextUnusedElement = 0;
                m_newGeneration = true;
                ExpirationTime = DateTime.MaxValue;
            }

            public bool Contains(int bucketIndex, TKey key)
            {
                int previousIndex;
                if (FindElementIndex(bucketIndex, key, true, out previousIndex) == -1)
                    return false;

                AccessedSinceLastTimeCheck = true;
                return true;
            }

            public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
            {
                return new Enumerator(this);
            }

            public void MakeOld()
            {
                m_newGeneration = false;
            }

            public bool Remove(int bucketIndex, TKey key)
            {
                int previousIndex;
                int entryIndex = FindElementIndex(bucketIndex, key, false, out previousIndex);
                if (entryIndex != -1)
                {
                    RemoveElement(bucketIndex, entryIndex, previousIndex);
                    AccessedSinceLastTimeCheck = true;
                    return true;
                }

                return false;
            }

            public bool Set(int bucketIndex, TKey key, TValue value, long size)
            {
                Debug.Assert(m_newGeneration, "It is possible to insert new elements only to newest generation.");
                Debug.Assert(size > 0, "New element size should be more than 0.");

                int previousIndex;
                int elementIndex = FindElementIndex(bucketIndex, key, true, out previousIndex);
                if (elementIndex == -1)
                {
                    // New key
                    if (Size + size > m_cache.m_generationMaxSize ||
                        (m_nextUnusedElement == m_cache.m_generationElementCount && m_freeCount == 0))
                    {
                        // Generation is full
                        return false;
                    }

                    // Increase size of generation
                    Size += size;

                    // Get first free entry and update free entry list
                    if (m_firstFreeElement != -1)
                    {
                        // There was entry that was removed
                        elementIndex = m_firstFreeElement;
                        m_firstFreeElement = m_elements[ elementIndex ].Next;
                        m_freeCount--;
                    }
                    else
                    {
                        // No entries removed so far - just take a last one
                        elementIndex = m_nextUnusedElement;
                        m_nextUnusedElement++;
                    }

                    Debug.Assert(m_elements[ elementIndex ].IsFree, "Allocated element is not free.");

                    // Move new entry to front
                    m_elements[ elementIndex ].Next = m_buckets[ bucketIndex ];
                    m_buckets[ bucketIndex ] = elementIndex;

                    // Set key and update count
                    m_elements[ elementIndex ].Key = key;
                }
                else
                {
                    // Existing key
                    if (Size - m_elements[ elementIndex ].Size + size > m_cache.m_generationMaxSize)
                    {
                        // Generation is full
                        // Remove existing element, because generation is going to be recycled to 
                        // old generation and element is stored to new generation
                        RemoveElement(bucketIndex, elementIndex, previousIndex);
                        return false;
                    }

                    // Update generation's size
                    Size = Size - m_elements[ elementIndex ].Size + size;
                }

                // Finally set value and size
                m_elements[ elementIndex ].Value = value;
                m_elements[ elementIndex ].Size = size;

                // Success - key was inserterted to generation
                AccessedSinceLastTimeCheck = true;
                return true;
            }

            public bool TryGetValue(int bucketIndex, TKey key, out TValue value, out long size)
            {
                // Find entry index, 
                int previousIndex;
                int elementIndex = FindElementIndex(bucketIndex, key, m_newGeneration, out previousIndex);
                if (elementIndex == -1)
                {
                    value = default(TValue);
                    size = 0;
                    return false;
                }

                value = m_elements[ elementIndex ].Value;
                size = m_elements[ elementIndex ].Size;

                if (!m_newGeneration)
                {
                    // Old generation - remove element, because it is moved to new generation
                    RemoveElement(bucketIndex, elementIndex, previousIndex);
                }

                AccessedSinceLastTimeCheck = true;
                return true;
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }

            #endregion
        }

        #endregion

        #region Nested type: IGeneration

        protected interface IGeneration : IEnumerable<KeyValuePair<TKey, TValue>>
        {
            bool AccessedSinceLastTimeCheck { get; set; }

            int Count { get; }

            DateTime ExpirationTime { get; set; }

            long Size { get; }

            void Clear();

            bool Contains(int bucketIndex, TKey key);

            void MakeOld();

            bool Remove(int bucketIndex, TKey key);

            bool Set(int bucketIndex, TKey key, TValue value, long size);

            bool TryGetValue(int bucketIndex, TKey key, out TValue value, out long size);
        }

        #endregion

        #region ICnmCache<TKey,TValue> Members

        public int Count
        {
            get { return m_newGeneration.Count + m_oldGeneration.Count; }
        }

        public TimeSpan ExpirationTime
        {
            get { return m_expirationTime; }

            set
            {
                if (value < MinExpirationTime)
                    value = MinExpirationTime;

                if (m_expirationTime == value)
                    return;

                m_newGeneration.ExpirationTime = (m_newGeneration.ExpirationTime - m_expirationTime) + value;
                m_oldGeneration.ExpirationTime = (m_oldGeneration.ExpirationTime - m_expirationTime) + value;
                m_expirationTime = value;

                PurgeExpired();
            }
        }

        public bool IsCountLimited
        {
            get { return true; }
        }

        public bool IsSizeLimited
        {
            get { return true; }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public bool IsTimeLimited
        {
            get { return ExpirationTime != TimeSpan.MaxValue; }
        }

        public int MaxCount
        {
            get { return m_maxCount; }

            set
            {
                if (value < 8)
                    value = 8;
                if (m_maxCount == value)
                    return;

                m_maxCount = value;
                Initialize();
            }
        }

        public long MaxElementSize
        {
            get { return m_maxElementSize; }

            private set { m_maxElementSize = value; }
        }

        public long MaxSize
        {
            get { return m_maxSize; }

            set
            {
                if (value < 8)
                    value = 8;
                if (m_maxSize == value)
                    return;

                m_maxSize = value;
                Initialize();
            }
        }

        public long Size
        {
            get { return m_newGeneration.Size + m_oldGeneration.Size; }
        }

        public object SyncRoot
        {
            get { return m_syncRoot; }
        }

        public void Clear()
        {
            m_newGeneration.Clear();
            m_oldGeneration.Clear();
            m_oldGeneration.MakeOld();
            m_version++;
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new Enumerator(this);
        }

        public void PurgeExpired()
        {
            m_operationsBetweenTimeChecks = DefaultOperationsBetweenTimeChecks;

            if (!IsTimeLimited)
                return;

            DateTime now = DateTime.Now;
            if (m_newGeneration.AccessedSinceLastTimeCheck)
            {
                // New generation has been accessed since last check
                // Update it's expiration time.
                m_newGeneration.ExpirationTime = now + ExpirationTime;
                m_newGeneration.AccessedSinceLastTimeCheck = false;
            }
            else if (m_newGeneration.ExpirationTime < now)
            {
                // New generation has been expired.
                // --> also old generation must be expired.
                PurgeGeneration(m_newGeneration);
                PurgeGeneration(m_oldGeneration);
                return;
            }

            if (m_oldGeneration.ExpirationTime < now)
                PurgeGeneration(m_oldGeneration);
        }

        public void Remove(TKey key)
        {
            if (key == null)
                throw new ArgumentNullException("key");

            int bucketIndex = GetBucketIndex(key);
            if (!m_newGeneration.Remove(bucketIndex, key))
            {
                if (!m_oldGeneration.Remove(bucketIndex, key))
                {
                    CheckExpired();
                    return;
                }
            }

            CheckExpired();
            m_version++;
        }

        public void RemoveRange(IEnumerable<TKey> keys)
        {
            if (keys == null)
                throw new ArgumentNullException("keys");

            foreach (TKey key in keys)
            {
                if (key == null)
                    continue;

                int bucketIndex = GetBucketIndex(key);
                if (!m_newGeneration.Remove(bucketIndex, key))
                    m_oldGeneration.Remove(bucketIndex, key);
            }

            CheckExpired();
            m_version++;
        }

        public bool Set(TKey key, TValue value, long size)
        {
            if (key == null)
                throw new ArgumentNullException("key");

            if (size < 0)
                throw new ArgumentOutOfRangeException("size", size, "Value's size can't be less than 0.");

            if (size > MaxElementSize)
            {
                // Entry size is too big to fit cache - ignore it
                Remove(key);
                return false;
            }

            if (size == 0)
                size = 1;

            int bucketIndex = GetBucketIndex(key);
            m_oldGeneration.Remove(bucketIndex, key);
            AddToNewGeneration(bucketIndex, key, value, size);
            CheckExpired();

            return true;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            if (key == null)
                throw new ArgumentNullException("key");

            int bucketIndex = GetBucketIndex(key);
            long size;
            if (m_newGeneration.TryGetValue(bucketIndex, key, out value, out size))
            {
                CheckExpired();
                return true;
            }

            if (m_oldGeneration.TryGetValue(bucketIndex, key, out value, out size))
            {
                // Move element to new generation
                AddToNewGeneration(bucketIndex, key, value, size);
                CheckExpired();
                return true;
            }

            CheckExpired();
            return false;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }
}