4
\$\begingroup\$

As a follow-up on my earlier question, here is the new implementation. The major change is now that the base class just deals in ICacheValue values which are implemented by the derived classes and generated through implementation of a factory method.

Unfortunately requires some casting in the derived classes but I don't think there is a way around it in C#.

Looking for general review, best practices, design improvements, hidden bugs etc.

Cache base class

It's now abstract and requires the implementation of the CreateCacheValue factory method. It only deals with the basic read/write access of items. All public methods are protected by a lock which call internal unlocked methods which are all virtual so they can get overwritten by the derived cache implementations.

public abstract class Cache<TKey, TValue>
{
    protected interface ICacheValue
    {
        TValue Value { get; set; }
    }

    protected readonly Dictionary<TKey, ICacheValue> _ValueCache = new Dictionary<TKey, ICacheValue>();
    protected object SyncRoot = new object();

    protected abstract ICacheValue CreateCacheValue(TValue value);
    protected abstract void UpdateElementAccess(TKey key, ICacheValue cacheValue);
    protected abstract void CacheValueInvalidated(ICacheValue cacheValue);

    public virtual int Count
    {
        get { return _ValueCache.Count; }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        ICacheValue v;
        value = default(TValue);

        lock (SyncRoot)
        {
            v = GetCacheValueUnlocked(key);
            if (v != null)
            {
                value = v.Value;
                UpdateElementAccess(key, v);
                return true;
            }
        }

        return false;
    }

    protected virtual ICacheValue GetCacheValueUnlocked(TKey key)
    {
        ICacheValue v;
        return _ValueCache.TryGetValue(key, out v) ? v : null;
    }

    public void SetValue(TKey key, TValue value)
    {
        lock (SyncRoot)
        {
            SetValueUnlocked(key, value);
        }
    }

    protected virtual ICacheValue SetValueUnlocked(TKey key, TValue value)
    {
        ICacheValue cacheValue = GetCacheValueUnlocked(key);
        if (cacheValue == null)
        {
            cacheValue = CreateCacheValue(value);
            _ValueCache[key] = cacheValue;
        }
        else
        {
            cacheValue.Value = value;
        }
        UpdateElementAccess(key, cacheValue);
        return cacheValue;
    }

    public void Invalidate(TKey key)
    {
        lock (SyncRoot)
        {
            InvalidateUnlocked(key);
        }
    }

    protected virtual void InvalidateUnlocked(TKey key)
    {
        var value = GetCacheValueUnlocked(key);
        if (value != null)
        {
            _ValueCache.Remove(key);
            CacheValueInvalidated(value);
        }
    }

    public virtual void Flush()
    {
        lock (SyncRoot)
        {
            FlushUnlocked();
        }
    }

    protected virtual void FlushUnlocked()
    {
        _ValueCache.Clear();
    }

    public List<TKey> GetKeys()
    {
        lock (SyncRoot)
        {
            return new List<TKey>(_ValueCache.Keys);
        }
    }
}

Size limited cache

Implements an LRU strategy. Items are invalidated on each cache access (read and write) if required.

public class SizeLimitedCache<TKey, TValue> : Cache<TKey, TValue>
{
    protected sealed class CacheValue : ICacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

        public LinkedListNode<KeyValuePair<TKey, CacheValue>> IndexRef { get; set; }
        public TValue Value { get; set; }
    }

    private readonly LinkedList<KeyValuePair<TKey, CacheValue>> _IndexList = new LinkedList<KeyValuePair<TKey, CacheValue>>();

    public int MaxSize { get; set; }

    public SizeLimitedCache(int maxSize)
    {
        MaxSize = maxSize;
    }

    protected override void UpdateElementAccess(TKey key, ICacheValue cacheValue)
    {
        var value = (CacheValue)cacheValue;
        // put element at front of the index list
        // remove first if already present in list, create new otherwise
        var idxRef = value.IndexRef;
        if (idxRef != null)
        {
            _IndexList.Remove(idxRef);
        }
        else
        {
            idxRef = new LinkedListNode<KeyValuePair<TKey, CacheValue>>(new KeyValuePair<TKey, CacheValue>(key, value));
            value.IndexRef = idxRef;
        }
        _IndexList.AddFirst(idxRef);

        // remove all entries from end of list until max size is satisfied
        while (_IndexList.Count > MaxSize)
        {
            InvalidateUnlocked(_IndexList.Last.Value.Key);
        }
    }

    protected sealed override ICacheValue CreateCacheValue(TValue value)
    {
        return new CacheValue(value);
    }

    protected override void CacheValueInvalidated(ICacheValue cacheValue)
    {
        _IndexList.Remove(((CacheValue)cacheValue).IndexRef);
    }

    protected override void FlushUnlocked()
    {
        base.FlushUnlocked();
        _IndexList.Clear();
    }
}

Time limited cache

Regularly expires items from the cache. I'm not totally happy with this implementation because technically it makes all operations O(n) due to the expiry timer locking the cache when expiring items. Should probably be based on a similar idea as the size limited cache by checking from the end of the list for expired items (just time based rather than size based).

public class TimeLimitedCache<TKey, TValue> : Cache<TKey, TValue>, IDisposable
{
    protected sealed class CacheValue : ICacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
            LastAccess = DateTime.Now;
        }

        public TValue Value { get; set; }
        public DateTime LastAccess { get; set; }
    }

    private DateTime _LastCacheAccess = DateTime.MinValue;

    public TimeSpan MaxEntryAge { get; set; }

    private TimeSpan _ExpiryInterval;
    public TimeSpan ExpiryInterval
    {
        get { return _ExpiryInterval; }
        set
        {
            _ExpiryInterval = value;
            DisposeTimer();
            _ExpiryTimer = new Timer(o => Expire(), null, value, value);
        }
    }

    private const int DefaultExpiryIntervalSec = 600;
    private System.Threading.Timer _ExpiryTimer;
    private int _ExpiryIsRunning = 0;

    public TimeLimitedCache(TimeSpan maxEntryAge)
        : this(maxEntryAge, TimeSpan.FromSeconds(DefaultExpiryIntervalSec))
    {
    }

    public TimeLimitedCache(TimeSpan maxEntryAge, TimeSpan expiryInterval)
    {
        MaxEntryAge = maxEntryAge;
        ExpiryInterval = expiryInterval;
    }

    private void Expire()
    {
        if (Interlocked.CompareExchange(ref _ExpiryIsRunning, 1, 0) == 1)
        {
            // expiry is still running
            return;
        }
        // paranoia
        try 
        {
            lock (SyncRoot)
            {
                var maxAge = MaxEntryAge;
                var toExpire = _ValueCache.Where(x => ((CacheValue)x.Value).LastAccess + maxAge < _LastCacheAccess).Select(x => x.Key).ToList();
                toExpire.ForEach(InvalidateUnlocked);
            }
        }
        finally
        {
            _ExpiryIsRunning = 0;
        }
    }

    protected override void UpdateElementAccess(TKey key, ICacheValue cacheValue)
    {
        _LastCacheAccess = DateTime.Now;
        ((CacheValue)cacheValue).LastAccess = DateTime.Now;
    }

    protected sealed override ICacheValue CreateCacheValue(TValue value)
    {
        return new CacheValue(value);
    }

    protected override void CacheValueInvalidated(ICacheValue cacheValue)
    {
    }

    private void DisposeTimer()
    {
        if (_ExpiryTimer != null)
        {
            _ExpiryTimer.Change(TimeSpan.FromMilliseconds(-1), TimeSpan.Zero);
            _ExpiryTimer.Dispose();
            _ExpiryTimer = null;
        }
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (disposing)
        {
            DisposeTimer();
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

Unfortunately requires some casting in the derived classes but I don't think there is a way around it in C#.

There is a way around that.

Define a 3rd template parameter to specify the type of cache value; use a where constraint on the 3rd parameter; and change the interface from protected to public (so that you can use it in the definition of the public Cache class):

public abstract class Cache<TKey, TValue, TCacheValue>
    where TCacheValue : class, Cache<TKey, TValue, TCacheValue>.ICacheValue
{
    public interface ICacheValue
    {
        TValue Value { get; set; }
    }

Use the specific TCacheValue type instead of ICacheValue throughout the implementation of the Cache class:

    protected readonly Dictionary<TKey, TCacheValue> _ValueCache = new Dictionary<TKey, TCacheValue>();
    protected object SyncRoot = new object();

    protected abstract TCacheValue CreateCacheValue(TValue value);
    protected abstract void UpdateElementAccess(TKey key, TCacheValue cacheValue);
    protected abstract void CacheValueInvalidated(TCacheValue cacheValue);

    public virtual int Count
    {
        get { return _ValueCache.Count; }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        TCacheValue v;
        value = default(TValue);

        lock (SyncRoot)
        {
            v = GetCacheValueUnlocked(key);
            if (v != null)
            {
                value = v.Value;
                UpdateElementAccess(key, v);
                return true;
            }
        }

        return false;
    }

    protected virtual TCacheValue GetCacheValueUnlocked(TKey key)
    {
        TCacheValue v;
        return _ValueCache.TryGetValue(key, out v) ? v : null;
    }

    public void SetValue(TKey key, TValue value)
    {
        lock (SyncRoot)
        {
            SetValueUnlocked(key, value);
        }
    }

    protected virtual TCacheValue SetValueUnlocked(TKey key, TValue value)
    {
        TCacheValue cacheValue = GetCacheValueUnlocked(key);
        if (cacheValue == null)
        {
            cacheValue = CreateCacheValue(value);
            _ValueCache[key] = cacheValue;
        }
        else
        {
            cacheValue.Value = value;
        }
        UpdateElementAccess(key, cacheValue);
        return cacheValue;
    }

    public void Invalidate(TKey key)
    {
        lock (SyncRoot)
        {
            InvalidateUnlocked(key);
        }
    }

    protected virtual void InvalidateUnlocked(TKey key)
    {
        var value = GetCacheValueUnlocked(key);
        if (value != null)
        {
            _ValueCache.Remove(key);
            CacheValueInvalidated(value);
        }
    }

    public virtual void Flush()
    {
        lock (SyncRoot)
        {
            FlushUnlocked();
        }
    }

    protected virtual void FlushUnlocked()
    {
        _ValueCache.Clear();
    }

    public List<TKey> GetKeys()
    {
        lock (SyncRoot)
        {
            return new List<TKey>(_ValueCache.Keys);
        }
    }
}

Now you can specify a subclass as follows, without using down-casts in the implementation, specifying Cache in the methods' signatures instead of ICache:

public class SizeLimitedCache<TKey, TValue> : Cache<TKey, TValue, SizeLimitedCache<TKey, TValue>.CacheValue>
{
    public sealed class CacheValue : ICacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

        public LinkedListNode<KeyValuePair<TKey, CacheValue>> IndexRef { get; set; }
        public TValue Value { get; set; }
    }

    private readonly LinkedList<KeyValuePair<TKey, CacheValue>> _IndexList = new LinkedList<KeyValuePair<TKey, CacheValue>>();

    public int MaxSize { get; set; }

    public SizeLimitedCache(int maxSize)
    {
        MaxSize = maxSize;
    }

    protected override void UpdateElementAccess(TKey key, CacheValue cacheValue)
    {
        var value = cacheValue;
        // put element at front of the index list
        // remove first if already present in list, create new otherwise
        var idxRef = value.IndexRef;
        if (idxRef != null)
        {
            _IndexList.Remove(idxRef);
        }
        else
        {
            idxRef = new LinkedListNode<KeyValuePair<TKey, CacheValue>>(new KeyValuePair<TKey, CacheValue>(key, value));
            value.IndexRef = idxRef;
        }
        _IndexList.AddFirst(idxRef);

        // remove all entries from end of list until max size is satisfied
        while (_IndexList.Count > MaxSize)
        {
            InvalidateUnlocked(_IndexList.Last.Value.Key);
        }
    }

    protected sealed override CacheValue CreateCacheValue(TValue value)
    {
        return new CacheValue(value);
    }

    protected override void CacheValueInvalidated(CacheValue cacheValue)
    {
        _IndexList.Remove(cacheValue.IndexRef);
    }

    protected override void FlushUnlocked()
    {
        base.FlushUnlocked();
        _IndexList.Clear();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Hmm, yes I was focused on keeping as much internal as possible. I guess making some implementation detail public might be an acceptable trade-off \$\endgroup\$ – ChrisWue Feb 21 '14 at 7:10
2
\$\begingroup\$

I'm missing XML Documentation on these classes.


public abstract class Cache<TKey, TValue>

You could short the type parameters with K for key and T for type. That's at least the "default" usage in Java, I'm not sure if that rule can be applied to C# (especially now that I see that this style is used in the framework itself, but something nice to keep in mind), too.


You're inconsistent with your naming, sometimes you call TValue v orvalue, on the other hand you also call ICacheValue v, value or valueCache. You should always use value for TValue and valueCache for IValueCache.


protected abstract ICacheValue CreateCacheValue(TValue value);
protected abstract void UpdateElementAccess(TKey key, ICacheValue cacheValue);
protected abstract void CacheValueInvalidated(ICacheValue cacheValue);

Due to the missing documentation, these names seem sub-optimal. For exampling, does CreateCacheValue also put the value into the cache? If yes, it should maybe be called Put or Store. What does UpdateElementAccess? Does it update some sort of access control within the cache for the given value? Should it only be called Update? CacheValueInvalidated should most likely be called InvalidateCacheValue or Invalidate or Remove.

Note that all this confusion could be cleared by documentation.

\$\endgroup\$
  • 1
    \$\begingroup\$ CacheValueInvalidated is the correct name, but UpdateElementAccess should probably be ElementAccessed. These are are called when that action happens so the derived class can perform additional housekeeping. I guess some documentation can't hurt :P \$\endgroup\$ – ChrisWue Feb 21 '14 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.