Fz5hSRDD

1TITLE: [Suggestion]Specialized Dictionary<ReadOnlyMemory<TKey>,TValue> with first class ReadOnlySpan<TKey> support
2
3When parsing tokens from a string with `string.Split()` and a Dictionary<string,TValue>, it is causing allocation. The allocation can be avoided by handling the token string as a span and splitting the tokens and using them for dictionary look-ups.
4
5## Proposed API
6A dictionary based on Dictionary<TKey,TValue> but with additional functions for first class ReadOnlySpan<TKey> support.
7```cs
8[DebuggerDisplay("Count = {Count}")]
9public class MemoryDictionary<TKey, TValue> : IDictionary<ReadOnlyMemory<TKey>, TValue>, IDictionary, IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>
10    where TKey : notnull, IEquatable<TKey>
11{
12    private int[]? _buckets;
13    private Entry[]? _entries;
14    private int _count;
15    private int _freeList;
16    private int _freeCount;
17    private int _version;
18    private IMemoryEqualityComparer<TKey>? _comparer;
19    private KeyCollection? _keys;
20    private ValueCollection? _values;
21    private const int StartOfFreeList = -3;
22
23    public MemoryDictionary();
24    public MemoryDictionary(int capacity);
25    public MemoryDictionary(IMemoryEqualityComparer<TKey> comparer);
26    public MemoryDictionary(int capacity, IMemoryEqualityComparer<TKey> comparer);
27    public MemoryDictionary(IDictionary<ReadOnlyMemory<TKey>, TValue> dictionary);
28    public MemoryDictionary(IDictionary<ReadOnlyMemory<TKey>, TValue> dictionary, IMemoryEqualityComparer<TKey> comparer);
29    public MemoryDictionary(IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> collection);
30    public MemoryDictionary(IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> collection, IMemoryEqualityComparer<TKey> comparer);
31
32    public int Count { get; }
33    public KeyCollection Keys { get; }
34    public ValueCollection Values { get; }
35    public IMemoryEqualityComparer<TKey> Comparer { get; }
36
37    public TValue this[ReadOnlyMemory<TKey> key] { get; set; }
38
39    public TValue Get(ReadOnlyMemory<TKey> key);
40    public TValue GetWithSpan(ReadOnlySpan<TKey> key);
41    public bool TryGetValue(ReadOnlyMemory<TKey> key, out TValue value);
42    public bool TryGetValueWithSpan(ReadOnlySpan<TKey> key, [MaybeNullWhen(false)] out TValue value);
43
44    public Enumerator GetEnumerator();
45
46    public void Add(ReadOnlyMemory<TKey> key, TValue value);
47    public bool TryAdd(ReadOnlyMemory<TKey> key, TValue value);
48
49    public bool Remove(ReadOnlyMemory<TKey> key);
50    public bool Remove(ReadOnlyMemory<TKey> key, out TValue value) => RemoveWithSpan(key.Span, out value);
51    public bool RemoveWithSpan(ReadOnlySpan<TKey> key);
52    public bool RemoveWithSpan(ReadOnlySpan<TKey> key, [MaybeNullWhen(false)] out TValue value);
53
54    public void Clear();
55
56    public bool ContainsKey(ReadOnlyMemory<TKey> key);
57    public bool ContainsValue(TValue value);
58
59    private int FindEntry(ReadOnlyMemory<TKey> key);
60    private int FindEntry(ReadOnlySpan<TKey> key);
61
62    private bool TryInsert(ReadOnlyMemory<TKey> key, TValue value, InsertionBehavior behavior);
63
64    private void CopyTo(KeyValuePair<ReadOnlyMemory<TKey>, TValue>[] array, int index);
65    private int Initialize(int capacity);
66
67    public int EnsureCapacity(int capacity);
68    private void Resize();
69    private void Resize(int newSize, bool forceNewHashCodes);
70    public void TrimExcess();
71    public void TrimExcess(int capacity);
72            
73    private static bool IsCompatibleKey(object key);
74
75    ICollection<ReadOnlyMemory<TKey>> IDictionary<ReadOnlyMemory<TKey>, TValue>.Keys { get; }
76    IEnumerable<ReadOnlyMemory<TKey>> IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>.Keys { get; }
77    ICollection IDictionary.Keys { get; }
78
79    ICollection<TValue> IDictionary<ReadOnlyMemory<TKey>, TValue>.Values { get; }
80    IEnumerable<TValue> IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>.Values { get; }
81    ICollection IDictionary.Values { get; }
82
83    object? IDictionary.this[object key] { get; set; }
84
85    IEnumerator IEnumerable.GetEnumerator();
86    IDictionaryEnumerator IDictionary.GetEnumerator();
87
88    void ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Add(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
89    void IDictionary.Add(object key, object? value);
90    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Contains(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
91    bool IDictionary.Contains(object key);
92    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Remove(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
93    void IDictionary.Remove(object key);
94
95    IEnumerator<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.GetEnumerator();
96
97    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.IsReadOnly { get; }
98    bool IDictionary.IsReadOnly { get; }
99
100    bool IDictionary.IsFixedSize { get; }
101
102    void ICollection.CopyTo(Array array, int index);
103    void ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.CopyTo(KeyValuePair<ReadOnlyMemory<TKey>, TValue>[] array, int index);
104    
105    bool ICollection.IsSynchronized { get; }
106    object ICollection.SyncRoot { get; }
107    
108    private enum InsertionBehavior : byte
109    {
110        None = 0,
111        OverwriteExisting = 1,
112        ThrowOnExisting = 2
113    }
114
115    private struct Entry
116    {
117        public int next;
118        public uint hashCode;
119        public ReadOnlyMemory<TKey> key;
120        public TValue value;
121    }
122
123    public struct Enumerator : IEnumerator<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>,
124        IDictionaryEnumerator
125    {
126        private readonly MemoryDictionary<TKey, TValue> _dictionary;
127        private readonly int _version;
128        private int _index;
129        private KeyValuePair<ReadOnlyMemory<TKey>, TValue> _current;
130        private readonly int _getEnumeratorRetType;  // What should Enumerator.Current return?
131
132        internal const int DictEntry = 1;
133        internal const int KeyValuePair = 2;
134
135        internal Enumerator(MemoryDictionary<TKey, TValue> dictionary, int getEnumeratorRetType);
136
137        public bool MoveNext();
138
139        public KeyValuePair<ReadOnlyMemory<TKey>, TValue> Current { get; }
140
141        public void Dispose();
142
143        object? IEnumerator.Current { get; }
144
145        void IEnumerator.Reset();
146
147        DictionaryEntry IDictionaryEnumerator.Entry { get; }
148
149        object IDictionaryEnumerator.Key { get; }
150
151        object? IDictionaryEnumerator.Value { get; }
152    }
153
154    [DebuggerDisplay("Count = {Count}")]
155    public sealed class KeyCollection : ICollection<ReadOnlyMemory<TKey>>, ICollection, IReadOnlyCollection<ReadOnlyMemory<TKey>>
156    {
157        private MemoryDictionary<TKey, TValue> _dictionary;
158
159        public KeyCollection(MemoryDictionary<TKey, TValue> dictionary);
160
161        public Enumerator GetEnumerator();
162
163        public void CopyTo(ReadOnlyMemory<TKey>[] array, int index);
164
165        public int Count { get; }
166
167        bool ICollection<ReadOnlyMemory<TKey>>.IsReadOnly { get; }
168
169        void ICollection<ReadOnlyMemory<TKey>>.Add(ReadOnlyMemory<TKey> item);
170
171        void ICollection<ReadOnlyMemory<TKey>>.Clear();
172
173        bool ICollection<ReadOnlyMemory<TKey>>.Contains(ReadOnlyMemory<TKey> item);
174
175        bool ICollection<ReadOnlyMemory<TKey>>.Remove(ReadOnlyMemory<TKey> item);
176
177        IEnumerator<ReadOnlyMemory<TKey>> IEnumerable<ReadOnlyMemory<TKey>>.GetEnumerator();
178
179        IEnumerator IEnumerable.GetEnumerator();
180
181        void ICollection.CopyTo(Array array, int index);
182
183        bool ICollection.IsSynchronized { get; }
184
185        object ICollection.SyncRoot { get; }
186
187        public struct Enumerator : IEnumerator<ReadOnlyMemory<TKey>>, IEnumerator
188        {
189            private readonly MemoryDictionary<TKey, TValue> _dictionary;
190            private int _index;
191            private readonly int _version;
192            private ReadOnlyMemory<TKey> _currentKey;
193
194            internal Enumerator(MemoryDictionary<TKey, TValue> dictionary);
195
196            public void Dispose();
197
198            public bool MoveNext();
199
200            public ReadOnlyMemory<TKey> Current { get; }
201
202            object? IEnumerator.Current { get; }
203
204            void IEnumerator.Reset();
205        }
206    }
207
208    [DebuggerDisplay("Count = {Count}")]
209    public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue>
210    {
211        private MemoryDictionary<TKey, TValue> _dictionary;
212
213        public ValueCollection(MemoryDictionary<TKey, TValue> dictionary);
214
215        public Enumerator GetEnumerator();
216
217        public void CopyTo(TValue[] array, int index);
218
219        public int Count { get; }
220
221        bool ICollection<TValue>.IsReadOnly { get; }
222
223        void ICollection<TValue>.Add(TValue item);
224
225        bool ICollection<TValue>.Remove(TValue item);
226
227        void ICollection<TValue>.Clear();
228
229        bool ICollection<TValue>.Contains(TValue item);
230
231        IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator();
232
233        IEnumerator IEnumerable.GetEnumerator();
234
235        void ICollection.CopyTo(Array array, int index);
236
237        bool ICollection.IsSynchronized { get; }
238
239        object ICollection.SyncRoot { get; }
240
241        public struct Enumerator : IEnumerator<TValue>, IEnumerator
242        {
243            private readonly MemoryDictionary<TKey, TValue> _dictionary;
244            private int _index;
245            private readonly int _version;
246            private TValue _currentValue;
247
248            internal Enumerator(MemoryDictionary<TKey, TValue> dictionary);
249
250            public void Dispose();
251
252            public bool MoveNext();
253
254            public TValue Current { get; }
255
256            object? IEnumerator.Current { get; }
257
258            void IEnumerator.Reset();
259        }
260    }
261}
262
263```
264
265For equality comparing keys with spans the normal IEqualityComparer<T> has to be extended
266```cs
267public interface IMemoryEqualityComparer<T> : IEqualityComparer<ReadOnlyMemory<T>>
268{
269    bool Equals(ReadOnlyMemory<T> x, ReadOnlySpan<T> y);
270    int GetHashCode(ReadOnlySpan<T> span);
271}
272```
273
274The default MemoryEqualityComparer<T> would look like this
275```cs
276public class MemoryEqualityComparer<T> : IMemoryEqualityComparer<T>
277    where T : IEquatable<T>
278{
279    public static MemoryEqualityComparer<T> Default { get; }
280
281    private MemoryEqualityComparer();
282
283    public bool Equals(ReadOnlyMemory<T> x, ReadOnlyMemory<T> y);
284    public bool Equals(ReadOnlyMemory<T> x, ReadOnlySpan<T> y);
285
286    public int GetHashCode(ReadOnlyMemory<T> memory);
287    public int GetHashCode(ReadOnlySpan<T> span);
288}
289```
290
291## example of usage:
292```cs
293[Flags]
294public enum ScopeField
295{
296    Identity = 1 << 0,
297    IdentityEmail = Identity | (1 << 1),
298    IdentityMemberships = Identity | (1 << 2)
299}
300
301private readonly static Dictionary<ReadOnlyMemory<char>, ScopeField> _mapping = new Dictionary<ReadOnlyMemory<char>, ScopeField>()
302{
303    ["identity".AsMemory()] = ScopeField.Identity,
304    ["identity[email]".AsMemory()] = ScopeField.IdentityEmail,
305    ["identity.memberships".AsMemory()] = ScopeField.IdentityMemberships
306};
307
308public static ScopeField ParseScopeStringWithSpan(string scopeString)
309{
310    ScopeField scopeValue = 0;
311    var scopeSpan = scopeString.AsSpan();
312
313    while (scopeSpan.Length != 0)
314    {
315        int sliceIndex = scopeSpan.IndexOf(' ');
316        if (sliceIndex != -1)
317        {
318            if (sliceIndex == 0)
319            { 
320                scopeSpan = scopeSpan.Slice(1);
321                continue;
322            }
323
324            scopeValue |= _mapping.GetWithSpan(scopeSpan.Slice(0, sliceIndex));
325            scopeSpan = scopeSpan.Slice(sliceIndex + 1);
326        }
327        else
328        {
329            scopeValue |= _mapping.GetWithSpan(scopeSpan);
330            break;
331        }
332    }
333
334    return scopeValue;
335}
336```