posts - 19 , comments - 8 , trackbacks - 0

A timeout dictionary in C#

Overview

My use case was a authentication system which stored user details. Fetching this information was expensive, so it was decided to only do this if the record was older than 15 minutes. The following code implements a dictionary were the values "timeout" after a given time period.

The timeout dictionary

The following code implements the dictionary. The constructor takes a date time provider which you can find in a previous post. This allows me to pass in a faster implementation of DateTime, and also allows me to test the code.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using JetBlack.Common.Timers;

namespace JetBlack.Common.Collections
{
    public class TimeoutDictionary<TKey,TValue> : IDictionary<TKey,TValue>
    {
        private readonly IDictionary<TKey, TValue> _valueMap;
        private readonly IDictionary<TKey, DateTime> _timeMap;

        private readonly IDateTimeProvider _dateTimeProvider;
        private readonly TimeSpan _timeout;

        public TimeoutDictionary(IDateTimeProvider dateTimeProvider, TimeSpan timeout)
        {
            _dateTimeProvider = dateTimeProvider;
            _timeout = timeout;
            _valueMap = new Dictionary<TKey, TValue>();
            _timeMap = new Dictionary<TKey, DateTime>();
        }

        private void Reap(DateTime now)
        {
            ISet<TKey> expiredKeys = new HashSet<TKey>();
            foreach (var item in _timeMap)
            {
                if (now - item.Value >= _timeout)
                    expiredKeys.Add(item.Key);
            }
            foreach (var key in expiredKeys)
            {
                _valueMap.Remove(key);
                _timeMap.Remove(key);
            }
        }

        public virtual IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            Reap(_dateTimeProvider.Now);
            return _valueMap.ToList().GetEnumerator();
        }

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

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            Add(item.Key, item.Value);
        }

        public virtual void Add(TKey key, TValue value)
        {
            var now = _dateTimeProvider.Now;
            DateTime time;
            if (!_timeMap.TryGetValue(key, out time))
            {
                _valueMap.Add(key, value);
                _timeMap.Add(key, now);
            }
            else if (now - time >= _timeout)
            {
                _valueMap[key] = value;
                _timeMap[key] = now;
            }
            else
                throw new ArgumentException("An element with the same key already exists", "key");
        }

        public virtual void Clear()
        {
            _valueMap.Clear();
            _timeMap.Clear();
        }

        public virtual bool Contains(KeyValuePair<TKey, TValue> item)
        {
            DateTime time;
            if (!_timeMap.TryGetValue(item.Key, out time))
                return false;

            if (_dateTimeProvider.Now - time < _timeout)
                return Equals(_valueMap[item.Key], item.Value);

            _valueMap.Remove(item.Key);
            _timeMap.Remove(item.Key);

            return false;
        }

        public virtual void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            Reap(_dateTimeProvider.Now);
            foreach (var item in _valueMap)
                array[arrayIndex++] = item;
        }

        public virtual bool Remove(KeyValuePair<TKey, TValue> item)
        {
            DateTime time;
            if (!_timeMap.TryGetValue(item.Key, out time))
                return false;

            var isStale = _dateTimeProvider.Now - time >= _timeout;
            var isEqual = Equals(_valueMap[item.Key], item.Value);
            if (isStale || isEqual)
            {
                _timeMap.Remove(item.Key);
                _valueMap.Remove(item.Key);
            }

            return isEqual && !isStale;
        }

        public virtual bool Remove(TKey key)
        {
            DateTime time;
            if (!_timeMap.TryGetValue(key, out time))
                return false;

            _timeMap.Remove(key);
            _valueMap.Remove(key);

            return _dateTimeProvider.Now - time >= _timeout;
        }

        public virtual int Count
        {
            get
            {
                Reap(_dateTimeProvider.Now);
                return _valueMap.Count;
            }
        }

        public bool IsReadOnly { get { return false; } }

        public virtual bool ContainsKey(TKey key)
        {
            DateTime time;
            if (!_timeMap.TryGetValue(key, out time))
                return false;

            if (_dateTimeProvider.Now - time < _timeout)
                return true;

            _valueMap.Remove(key);
            _timeMap.Remove(key);

            return false;
        }

        public virtual bool TryGetValue(TKey key, out TValue value)
        {
            DateTime time;
            if (_timeMap.TryGetValue(key, out time) && _dateTimeProvider.Now - time < _timeout)
                return _valueMap.TryGetValue(key, out value);

            value = default(TValue);
            return false;
        }

        public virtual TValue this[TKey key]
        {
            get
            {
                DateTime time;
                if (_timeMap.TryGetValue(key, out time))
                {
                    if (_dateTimeProvider.Now - time < _timeout)
                        return _valueMap[key];

                    _valueMap.Remove(key);
                    _timeMap.Remove(key);
                }

                throw new KeyNotFoundException();
            }
            set
            {
                _valueMap[key] = value;
                _timeMap[key] = _dateTimeProvider.Now;
            }
        }

        public virtual ICollection<TKey> Keys
        {
            get
            {
                Reap(_dateTimeProvider.Now);
                return _valueMap.Keys;
            }
        }

        public virtual ICollection<TValue> Values
        {
            get
            {
                Reap(_dateTimeProvider.Now);
                return _valueMap.Values;
            }
        }
    }
}

The thread safe implementation

The following code adds thread safety.

using System;
using System.Collections.Generic;
using JetBlack.Common.Timers;

namespace JetBlack.Common.Collections
{
    public class ConcurrentTimeoutDictionary<TKey,TValue> : TimeoutDictionary<TKey,TValue>
    {
        public ConcurrentTimeoutDictionary(IDateTimeProvider dateTimeProvider, TimeSpan timeout)
            : base(dateTimeProvider, timeout)
        {
        }

        public override void Add(TKey key, TValue value)
        {
            lock (this)
            {
                base.Add(key, value);
            }
        }

        public override void Clear()
        {
            lock (this)
            {
                base.Clear();
            }
        }

        public override bool Contains(KeyValuePair<TKey, TValue> item)
        {
            lock (this)
            {
                return base.Contains(item);
            }
        }

        public override bool ContainsKey(TKey key)
        {
            lock (this)
            {
                return base.ContainsKey(key);
            }
        }

        public override void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            lock (this)
            {
                base.CopyTo(array, arrayIndex);
            }
        }

        public override int Count
        {
            get
            {
                lock (this)
                {
                    return base.Count;
                }
            }
        }

        public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            lock (this)
            {
                return base.GetEnumerator();
            }
        }

        public override ICollection<TKey> Keys
        {
            get
            {
                lock (this)
                {
                    return base.Keys;
                }
            }
        }

        public override bool Remove(KeyValuePair<TKey, TValue> item)
        {
            lock (this)
            {
                return base.Remove(item);
            }
        }

        public override bool Remove(TKey key)
        {
            lock (this)
            {
                return base.Remove(key);
            }
        }

        public override bool TryGetValue(TKey key, out TValue value)
        {
            lock (this)
            {
                return base.TryGetValue(key, out value);
            }
        }

        public override ICollection<TValue> Values
        {
            get
            {
                lock (this)
                {
                    return base.Values;
                }
            }
        }

        public override TValue this[TKey key]
        {
            get
            {
                lock (this)
                {
                    return base[key];
                }
            }
            set
            {
                lock (this)
                {
                    base[key] = value;
                }
            }
        }
    }
}

Testing

Finally we can test the time dependent code!

using System;
using JetBlack.Common.Collections;
using JetBlack.Common.Timers.Testing;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JetBlack.Common.UnitTest.Collections
{
    [TestClass]
    public class TimeoutDictionaryUnitTest
    {
        [TestMethod]
        public void TestContainsKey()
        {
            var dateTimeProvider = new DiscreteDateTimeProvider(DateTime.Today, TimeSpan.FromMilliseconds(200));
            var timeoutDictionary = new TimeoutDictionary<string, int>(dateTimeProvider, TimeSpan.FromMilliseconds(500));

            timeoutDictionary.Add("one", 1);
            Assert.IsTrue(timeoutDictionary.ContainsKey("one"));
            Assert.IsTrue(timeoutDictionary.ContainsKey("one"));
            Assert.IsFalse(timeoutDictionary.ContainsKey("one"));
        }
    }
}

Print | posted on Friday, December 19, 2014 9:17 AM | Filed Under [ C# TimeoutDictionary ]

Feedback

Gravatar

# re: A timeout dictionary in C#

Why not use memory cache?
12/15/2016 8:56 AM | Sean
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: