C# ThreadSafeSortedDictionary Implementation with limited methods

Question

I have made an attempt at creating a ThreadSafeSortedDictionary, and I am working with .NET 4.0.

I have had a look at Thread safe SortedDictionary but not confident about the thread safety aspect.

Anyone think this can work, or NOT for a reason I cannot see associated with:

1. Thread safety - it needs to be thread safe
2. Performance/Efficiency - I am not majorly concerned about this (unless there is a huge problem with performance)

My code:

public class ThreadSafeSortedDict<TKey, TValue>
{
    private readonly SortedDictionary<TKey, TValue> _dict;
    private readonly ReaderWriterLockSlim _dictReaderWriterLockSlim;
    private readonly ReaderWriterLockSlim _readonlyDictionaryLock;

    public Dictionary<TKey, TValue> ReadOnly { get; set; }

    public ThreadSafeSortedDict(IComparer<TKey> comparer)
    {
        _dict = new SortedDictionary<TKey, TValue>(comparer);
        _dictReaderWriterLockSlim = new ReaderWriterLockSlim();
        _readonlyDictionaryLock = new ReaderWriterLockSlim();
    }

    public void Add(TKey key, TValue value)
    {
        _dictReaderWriterLockSlim.EnterWriteLock();
        try
        {
            _dict.Add(key,value);
        }
        finally
        {
            _dictReaderWriterLockSlim.ExitWriteLock();
        }

        SetReadOnlyDictionary();
    }

    public void AddRange(IEnumerable<KeyValuePair<TKey,TValue>> keyValues)
    {
        if (keyValues == null) return;
        _dictReaderWriterLockSlim.EnterWriteLock();
        try
        {
            foreach (var keyValue in keyValues)
            {
                Add(keyValue.Key, keyValue.Value);
            }
        }
        finally
        {
            _dictReaderWriterLockSlim.ExitWriteLock();
        }

        SetReadOnlyDictionary();
    }

    public void Remove(TKey key)
    {
        _dictReaderWriterLockSlim.EnterWriteLock();
        try
        {
            _dict.Remove(key);
        }
        finally
        {
            _dictReaderWriterLockSlim.ExitWriteLock();
        }

        SetReadOnlyDictionary();
    }

    public void Replace(IEnumerable<KeyValuePair<TKey, TValue>> newKeyValues)
    {
        if (newKeyValues == null) return;

        _dictReaderWriterLockSlim.EnterWriteLock();

        try
        {
            _dict.Clear();
            AddRange(newKeyValues);
        }
        finally
        {
            _dictReaderWriterLockSlim.ExitWriteLock();
        }
    }

    private void SetReadOnlyDictionary()
    {
        _readonlyDictionaryLock.EnterWriteLock();
        try
        {
            ReadOnly = GetSortedKeyValues().ToDictionary(x => x.Key, x => x.Value);
        }
        finally
        {
            _readonlyDictionaryLock.ExitWriteLock();
        }
    }

    private List<KeyValuePair<TKey, TValue>> GetSortedKeyValues()
    {
        _dictReaderWriterLockSlim.EnterReadLock();
        try
        {
            return _dict.ToList();
        }
        finally
        {
            _dictReaderWriterLockSlim.ExitReadLock();
        }
    }
}

Answer 1

I don't see any obvious thread-safety issues with your code. To me, the bigger issues are matters of correctness:

1. A minor problem is that your ReadOnly property has a public setter. This means any code outside the class can set the property at any time, without any synchronization. Your class design should reflect the intended usage. Presumably you don't want any other code to change the property value, so the setter should be private.
2. A major problem is that while the class name is ThreadSafeSortedDict<TKey, TValue>, there's no publicly accessible view of the data that is sorted. When you set the ReadOnly property, you create a new unsorted dictionary from the original data. Even though you enumerate the source dictionary in order, which is sorted, there are no guarantees that the data in the new dictionary will remain in the order in which it was added. The dictionary class is, by design, an unordered collection.

If you really want to maintain the data in a SortedDictionary<TKey, TValue> object, and present a sorted view of it, you need to use some type of ordered collection as your ReadOnly property type. This could be another SortedDictionary<TKey, TValue>, but since the intent is for the collection to be read-only, IMHO it makes more sense to make the type IReadOnlyDictionary<TKey, TValue>, returning a ReadOnlyDictionary<TKey, TValue> object. And rather than creating a new object every time the sorted dictionary is modified, you can initialize it lazily and invalidate it when the sorted dictionary is modified.

For example:

public class ThreadSafeSortedDict<TKey, TValue>
{
    private readonly SortedDictionary<TKey, TValue> _dict;
    private IReadOnlyDictionary<TKey, TValue> _readOnly;
    private readonly object _lock = new object();

    public IReadOnlyDictionary<TKey, TValue> ReadOnly
    {
        get
        {
            lock (_lock)
            {
                if (_readOnly == null)
                {
                  // NOTE: SortedList is faster when populating from already-sorted data
                    _readOnly = new ReadOnlyDictionary(new SortedList(_dict));
                }
            }

            return _readOnly;
        }
    }

    public ThreadSafeSortedDict(IComparer<TKey> comparer)
    {
        _dict = new SortedDictionary<TKey, TValue>(comparer);
    }

    public void Add(TKey key, TValue value)
    {
        lock (_lock)
        {
            _dict.Add(key,value);
            _readOnly = null;
        }
    }

    public void AddRange(IEnumerable<KeyValuePair<TKey,TValue>> keyValues)
    {
        if (keyValues == null) return;
        lock (_lock)
        {
            foreach (var keyValue in keyValues)
            {
                Add(keyValue.Key, keyValue.Value);
            }
            _readOnly = null;
        }
    }

    public void Remove(TKey key)
    {
        lock (_lock)
        {
            _dict.Remove(key);
            _readOnly = null;
        }
    }

    public void Replace(IEnumerable<KeyValuePair<TKey, TValue>> newKeyValues)
    {
        if (newKeyValues == null) return;

        lock (_lock)
        {
            _dict.Clear();
            AddRange(newKeyValues);
            _readOnly = null;
        }
    }
}

Using lock instead of the reader-writer lock should not affect performance significantly, if at all, and makes the code a lot more obviously thread-safe. It seems to me that the above should be sufficient. Still, if it's not, some improvements you could make include:

1. Going ahead and using the reader-writer lock. You'll need to acquire the reader lock in the ReadOnly property, and upgrade it to a writer lock if you need to set the _readOnly field (i.e. if it's set to null). This could improve performance if you have a very large amount of contention on the ReadOnly property.
2. Not bothering with the custom type, and using ConcurrentDictionary<TKey, TValue> instead, just copying its contents and sorting them after the fact when you need a sorted view of the dictionary. Whether this is useful in your case I can't say, as there's not enough context in the question. If you will still need to implement some type of synchronization to avoid trying to retrieve the sorted view when some other thread is trying to modify the collection, then you'll probably want some kind of wrapper type anyway.
3. Having your type implement IReadOnlyDictionary<TKey, TValue> rather than having a ReadOnly property. Then you can pass your object as a read-only dictionary object where needed, but code that needs to actually modify the dictionary can still do so via the original type.

Given what information is available in the question at the moment, I'd say option #3 is probably best. It would require the most work, but seems to me to provide the cleanest, most efficient API. You would avoid having to have the ReadOnly property and you would avoid having to make a copy of the collection. The class itself would serve as the read-only copy, and it would automatically be kept up-to-date with respect to the underlying dictionary collection, because the implementation of IReadOnlyDictionary<TKey, TValue> would just defer to the underlying dictionary (with synchronization, of course).

Answer 2

First of all, thanks to @Peter Duniho for the information and answer. I first attempted using reader writer locks, but had quite a bit of trouble and took the advise to use locks for simplicity. My solution is modifying Peters answer, because I did not want to lock everytime the ReadOnly dictionary was accessed.

And my ultimate goals for this class are:

1. At any point in time, I would like to access the ReadOnly collection (and stop users to write to it).

2. If something in the underlying dictionary gets added/removed, I do not want this to affect other's who are already using/reading/iterating the ReadOnly they have access to.

Here is the solution:

public class ThreadSafeSortedDictionary<TKey, TValue>
{
    private readonly SortedDictionary<TKey, TValue> _dict;
    private readonly object _sync;

    public ReadOnlyDictionary<TKey, TValue> ReadOnly { get; private set; }

    public IEnumerable<TValue> Values
    {
        get { return ReadOnly.Values; }
    }

    public IEnumerable<TKey> Keys
    {
        get { return ReadOnly.Keys; }
    }

    public int Count
    {
        get { return ReadOnly.Count; }
    }

    public ThreadSafeSortedDictionary(IComparer<TKey> comparer)
    {
        _dict = new SortedDictionary<TKey, TValue>(comparer);
        _sync = new object();
    }

    public void Add(TKey key, TValue value)
    {
        lock (_sync)
        {
            _dict.Add(key, value);
            SetReadOnlyDictionary();
        }
    }

    public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> keyValues)
    {
        if (keyValues == null) return;
        InternalAddRange(keyValues);
    }

    public void Remove(TKey key)
    {
        lock (_sync)
        {
            _dict.Remove(key);
            SetReadOnlyDictionary();
        }
    }

    public void Replace(IEnumerable<KeyValuePair<TKey, TValue>> newKeyValues)
    {
        //Throw exception, because otherwise we'll end up clearing the dictionary
        if (newKeyValues == null) throw new ArgumentNullException("newKeyValues");
        InternalAddRange(newKeyValues, true);
    }

    private void InternalAddRange(IEnumerable<KeyValuePair<TKey, TValue>> keyValues, bool clearBeforeAdding = false)
    {
        lock (_sync)
        {
            if (clearBeforeAdding) _dict.Clear();
            foreach (var kvp in keyValues)
            {
                _dict.Add(kvp.Key, kvp.Value);
            }
            SetReadOnlyDictionary();
        }
    }

    private void SetReadOnlyDictionary()
    {
        lock (_sync)
        {
            ReadOnly = new DictionaryReadOnly<TKey, TValue>(new SortedList<TKey, TValue>(_dict, _dict.Comparer));
        }
    }
}

And I used the ReadOnlyDictionary from the answer of Is there a read-only generic dictionary available in .NET?

I used SortedList vs SortedDictionary for the ReadOnly property, because I am creating them quite a few times (during add/remove/replace), and because 1. SortedList perform better in memory 2. are quicker in lookup, and as I am only using them for Read Only purposes, only lookup will be needed.