|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Diagnostics;
namespace System.Collections.Specialized
{
/// <summary>
/// Implements <see cref="IDictionary"/> using a singly linked list.
/// Recommended for collections that typically include fewer than 10 items.
/// </summary>
[Serializable]
[System.Runtime.CompilerServices.TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public class ListDictionary : IDictionary
{
private DictionaryNode? head; // Do not rename (binary serialization)
private int version; // Do not rename (binary serialization)
private int count; // Do not rename (binary serialization)
private readonly IComparer? comparer; // Do not rename (binary serialization)
public ListDictionary()
{
}
public ListDictionary(IComparer? comparer)
{
this.comparer = comparer;
}
public object? this[object key]
{
get
{
ArgumentNullException.ThrowIfNull(key);
DictionaryNode? node = head;
if (comparer == null)
{
while (node != null)
{
object oldKey = node.key;
if (oldKey.Equals(key))
{
return node.value;
}
node = node.next;
}
}
else
{
while (node != null)
{
object oldKey = node.key;
if (comparer.Compare(oldKey, key) == 0)
{
return node.value;
}
node = node.next;
}
}
return null;
}
set
{
ArgumentNullException.ThrowIfNull(key);
version++;
DictionaryNode? last = null;
DictionaryNode? node;
for (node = head; node != null; node = node.next)
{
object oldKey = node.key;
if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0)
{
break;
}
last = node;
}
if (node != null)
{
// Found it
node.value = value;
return;
}
// Not found, so add a new one
DictionaryNode newNode = new DictionaryNode();
newNode.key = key;
newNode.value = value;
if (last != null)
{
last.next = newNode;
}
else
{
head = newNode;
}
count++;
}
}
public int Count
{
get
{
return count;
}
}
public ICollection Keys
{
get
{
return new NodeKeyValueCollection(this, true);
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public bool IsFixedSize
{
get
{
return false;
}
}
public bool IsSynchronized
{
get
{
return false;
}
}
public object SyncRoot => this;
public ICollection Values
{
get
{
return new NodeKeyValueCollection(this, false);
}
}
public void Add(object key, object? value)
{
ArgumentNullException.ThrowIfNull(key);
version++;
DictionaryNode? last = null;
for (DictionaryNode? node = head; node != null; node = node.next)
{
object oldKey = node.key;
if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0)
{
throw new ArgumentException(SR.Format(SR.Argument_AddingDuplicate, key));
}
last = node;
}
// Not found, so add a new one
DictionaryNode newNode = new DictionaryNode();
newNode.key = key;
newNode.value = value;
if (last != null)
{
last.next = newNode;
}
else
{
head = newNode;
}
count++;
}
public void Clear()
{
count = 0;
head = null;
version++;
}
public bool Contains(object key)
{
ArgumentNullException.ThrowIfNull(key);
for (DictionaryNode? node = head; node != null; node = node.next)
{
object oldKey = node.key;
if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0)
{
return true;
}
}
return false;
}
public void CopyTo(Array array, int index)
{
ArgumentNullException.ThrowIfNull(array);
ArgumentOutOfRangeException.ThrowIfNegative(index);
if (array.Length - index < count)
throw new ArgumentException(SR.Arg_InsufficientSpace);
for (DictionaryNode? node = head; node != null; node = node.next)
{
array.SetValue(new DictionaryEntry(node.key, node.value), index);
index++;
}
}
public IDictionaryEnumerator GetEnumerator()
{
return new NodeEnumerator(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new NodeEnumerator(this);
}
public void Remove(object key)
{
ArgumentNullException.ThrowIfNull(key);
version++;
DictionaryNode? last = null;
DictionaryNode? node;
for (node = head; node != null; node = node.next)
{
object oldKey = node.key;
if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0)
{
break;
}
last = node;
}
if (node == null)
{
return;
}
if (node == head)
{
head = node.next;
}
else
{
Debug.Assert(last != null);
last.next = node.next;
}
count--;
}
private sealed class NodeEnumerator : IDictionaryEnumerator
{
private readonly ListDictionary _list;
private DictionaryNode? _current;
private readonly int _version;
private bool _start;
public NodeEnumerator(ListDictionary list)
{
_list = list;
_version = list.version;
_start = true;
_current = null;
}
public object Current
{
get
{
return Entry;
}
}
public DictionaryEntry Entry
{
get
{
if (_current == null)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumOpCantHappen);
}
return new DictionaryEntry(_current.key, _current.value);
}
}
public object Key
{
get
{
if (_current == null)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumOpCantHappen);
}
return _current.key;
}
}
public object? Value
{
get
{
if (_current == null)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumOpCantHappen);
}
return _current.value;
}
}
public bool MoveNext()
{
if (_version != _list.version)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
}
if (_start)
{
_current = _list.head;
_start = false;
}
else if (_current != null)
{
_current = _current.next;
}
return (_current != null);
}
public void Reset()
{
if (_version != _list.version)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
}
_start = true;
_current = null;
}
}
private sealed class NodeKeyValueCollection : ICollection
{
private readonly ListDictionary _list;
private readonly bool _isKeys;
public NodeKeyValueCollection(ListDictionary list, bool isKeys)
{
_list = list;
_isKeys = isKeys;
}
void ICollection.CopyTo(Array array, int index)
{
ArgumentNullException.ThrowIfNull(array);
ArgumentOutOfRangeException.ThrowIfNegative(index);
for (DictionaryNode? node = _list.head; node != null; node = node.next)
{
array.SetValue(_isKeys ? node.key : node.value, index);
index++;
}
}
int ICollection.Count
{
get
{
int count = 0;
for (DictionaryNode? node = _list.head; node != null; node = node.next)
{
count++;
}
return count;
}
}
bool ICollection.IsSynchronized
{
get
{
return false;
}
}
object ICollection.SyncRoot
{
get
{
return _list.SyncRoot;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return new NodeKeyValueEnumerator(_list, _isKeys);
}
private sealed class NodeKeyValueEnumerator : IEnumerator
{
private readonly ListDictionary _list;
private DictionaryNode? _current;
private readonly int _version;
private readonly bool _isKeys;
private bool _start;
public NodeKeyValueEnumerator(ListDictionary list, bool isKeys)
{
_list = list;
_isKeys = isKeys;
_version = list.version;
_start = true;
_current = null;
}
public object? Current
{
get
{
if (_current == null)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumOpCantHappen);
}
return _isKeys ? _current.key : _current.value;
}
}
public bool MoveNext()
{
if (_version != _list.version)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
}
if (_start)
{
_current = _list.head;
_start = false;
}
else if (_current != null)
{
_current = _current.next;
}
return (_current != null);
}
public void Reset()
{
if (_version != _list.version)
{
throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
}
_start = true;
_current = null;
}
}
}
[Serializable]
[System.Runtime.CompilerServices.TypeForwardedFrom("System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public class DictionaryNode
{
public object key = null!; // Do not rename (binary serialization)
public object? value; // Do not rename (binary serialization)
public DictionaryNode? next; // Do not rename (binary serialization)
}
}
}
|