Cache.cs

    class Cache<TKey, TValue> where TKey : IComparable<TKey>
    {
        private readonly object _lock = new object();
        private IBinarySearchTree<TKey, TValue> _tree = AVLTree<TKey, TValue>.Empty;

        public TValue GetOrAdd(TKey key, [NotNull] Func<TKey, TValue> valueFactory)
        {
            if (valueFactory == null) throw new ArgumentNullException("valueFactory");
            
            do { 
                var oldTree = _tree;
                var node = oldTree.Search(key);
                if (!node.IsEmpty)
                  return node.Value;
                
                // Need to add the value.  Tree is immutable so the add can happen 
                // without any kind of locking.  
                var value = valueFactory(key);
                var newTree = oldTree.Add(key, value);
                if (oldTree == Interlocked.CompareExchange(ref _tree, newTree, oldTree)) {
                    // My write to _tree was successful.  It now holds the value stored
                    // in newTree.  
                    return value;
                }
                
                // The CompareExchange call failed.  That means another thread 
                // has updated the _tree value.  Need to redo my search again because 
                // that Add may have been for the same value 
                
            } while (true);
                
        }

        public void Clear()
        {
            _tree = AVLTree<TKey, TValue>.Empty;
        }
    }