// Copyright (c) Microsoft. All Rights Reserved. Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
#nullable enable
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;
namespace Microsoft.CodeAnalysis.Collections
{
///
/// A MultiDictionary that allows only adding, and preserves the order of values added to the
/// dictionary. Thread-safe for reading, but not for adding.
///
///
/// Always uses the default comparer.
///
internal sealed class OrderPreservingMultiDictionary :
IEnumerable.ValueSet>>
{
#region Pooling
private readonly ObjectPool>? _pool;
private OrderPreservingMultiDictionary(ObjectPool> pool)
{
_pool = pool;
}
public void Free()
{
if (_dictionary != null)
{
// Allow our ValueSets to return their underlying ArrayBuilders to the pool.
foreach (var kvp in _dictionary)
{
kvp.Value.Free();
}
_dictionary.Free();
_dictionary = null;
}
_pool?.Free(this);
}
// global pool
private static readonly ObjectPool> s_poolInstance = CreatePool();
// if someone needs to create a pool;
public static ObjectPool> CreatePool()
{
var pool = new ObjectPool>(
pool => new OrderPreservingMultiDictionary(pool),
16); // Size is a guess.
return pool;
}
public static OrderPreservingMultiDictionary GetInstance()
{
var instance = s_poolInstance.Allocate();
Debug.Assert(instance.IsEmpty);
return instance;
}
#endregion Pooling
// An empty dictionary we keep around to simplify certain operations (like "Keys")
// when we don't have an underlying dictionary of our own.
private static readonly Dictionary s_emptyDictionary = new Dictionary();
// The underlying dictionary we store our data in. null if we are empty.
private PooledDictionary? _dictionary;
public OrderPreservingMultiDictionary()
{
}
private void EnsureDictionary()
{
_dictionary ??= PooledDictionary.GetInstance();
}
public bool IsEmpty => _dictionary == null;
///
/// Add a value to the dictionary.
///
public void Add(K k, V v)
{
if (_dictionary is object && _dictionary.TryGetValue(k, out var valueSet))
{
Debug.Assert(valueSet.Count >= 1);
// Have to re-store the ValueSet in case we upgraded the existing ValueSet from
// holding a single item to holding multiple items.
_dictionary[k] = valueSet.WithAddedItem(v);
}
else
{
this.EnsureDictionary();
_dictionary![k] = new ValueSet(v);
}
}
public Dictionary.Enumerator GetEnumerator()
{
return _dictionary is null ? s_emptyDictionary.GetEnumerator() : _dictionary.GetEnumerator();
}
IEnumerator> IEnumerable>.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
///
/// Get all values associated with K, in the order they were added.
/// Returns empty read-only array if no values were present.
///
public ImmutableArray this[K k]
{
get
{
if (_dictionary is object && _dictionary.TryGetValue(k, out var valueSet))
{
Debug.Assert(valueSet.Count >= 1);
return valueSet.Items;
}
return ImmutableArray.Empty;
}
}
public bool Contains(K key, V value)
{
return _dictionary is object &&
_dictionary.TryGetValue(key, out var valueSet) &&
valueSet.Contains(value);
}
///
/// Get a collection of all the keys.
///
public Dictionary.KeyCollection Keys
{
get { return _dictionary is null ? s_emptyDictionary.Keys : _dictionary.Keys; }
}
public struct ValueSet : IEnumerable
{
///
/// Each value is either a single V or an .
/// Never null.
///
private readonly object _value;
internal ValueSet([DisallowNull] V value)
{
_value = value!;
}
internal ValueSet(ArrayBuilder values)
{
_value = values;
}
internal void Free()
{
var arrayBuilder = _value as ArrayBuilder;
arrayBuilder?.Free();
}
[NotNull]
internal V this[int index]
{
get
{
Debug.Assert(this.Count >= 1);
var arrayBuilder = _value as ArrayBuilder;
if (arrayBuilder == null)
{
if (index == 0)
{
return (V)_value;
}
else
{
throw new IndexOutOfRangeException();
}
}
else
{
return arrayBuilder[index];
}
}
}
internal bool Contains(V item)
{
Debug.Assert(this.Count >= 1);
var arrayBuilder = _value as ArrayBuilder;
return arrayBuilder == null
? EqualityComparer.Default.Equals(item, (V)_value)
: arrayBuilder.Contains(item);
}
internal ImmutableArray Items
{
get
{
Debug.Assert(this.Count >= 1);
var arrayBuilder = _value as ArrayBuilder;
if (arrayBuilder == null)
{
// promote singleton to set
Debug.Assert(_value is V, "Item must be a a V");
return ImmutableArray.Create((V)_value);
}
else
{
return arrayBuilder.ToImmutable();
}
}
}
internal int Count => (_value as ArrayBuilder)?.Count ?? 1;
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public Enumerator GetEnumerator()
{
return new Enumerator(this);
}
internal ValueSet WithAddedItem(V item)
{
Debug.Assert(this.Count >= 1);
var arrayBuilder = _value as ArrayBuilder;
if (arrayBuilder == null)
{
// Promote from singleton V to ArrayBuilder.
Debug.Assert(_value is V, "_value must be a V");
// By default we allocate array builders with a size of two. That's to store
// the single item already in _value, and to store the item we're adding.
// In general, we presume that the amount of values per key will be low, so this
// means we have very little overhead when there are multiple keys per value.
arrayBuilder = ArrayBuilder.GetInstance(capacity: 2);
arrayBuilder.Add((V)_value);
arrayBuilder.Add(item);
}
else
{
arrayBuilder.Add(item);
}
return new ValueSet(arrayBuilder);
}
public struct Enumerator : IEnumerator
{
private readonly ValueSet _valueSet;
private readonly int _count;
private int _index;
public Enumerator(ValueSet valueSet)
{
_valueSet = valueSet;
_count = _valueSet.Count;
Debug.Assert(_count >= 1);
_index = -1;
}
[NotNull]
public V Current => _valueSet[_index];
object IEnumerator.Current => Current;
public bool MoveNext()
{
_index++;
return _index < _count;
}
public void Reset()
{
_index = -1;
}
public void Dispose()
{
}
}
}
}
}