Skip to content

Instantly share code, notes, and snippets.

@kkolyan

kkolyan/LightHashSet.cs

Last active December 19, 2021 15:58
Show Gist options
  • Save kkolyan/76ba34bd5ffb15184b8ed0cba01b56c3 to your computer and use it in GitHub Desktop.
Save kkolyan/76ba34bd5ffb15184b8ed0cba01b56c3 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
LightHashSet.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using NUnit.Framework;
public class LightHashSet<T> : IEnumerable<T>
{
private struct Node
{
public int nextNodeId;
public T value;
public override string ToString()
{
return $"{nameof(nextNodeId)}: {nextNodeId}, {nameof(value)}: {value}";
}
}
private Node[] _nodes;
private int _nodeCount;
private readonly int[] _table;
private int _modCount;
private static readonly EqualityComparer<T> _comparer = EqualityComparer<T>.Default;
public LightHashSet(int tableSize, int initialNodePoolSize)
{
_table = new int[tableSize];
_nodes = new Node[initialNodePoolSize];
_nodeCount = 0;
}
public void Clear()
{
_nodeCount = 0;
Array.Clear(_table, 0, _table.Length);
Array.Clear(_nodes, 0, _nodeCount);
_modCount++;
}
public bool Add(in T value)
{
int bucket = Bucket(value);
int nodeId = _table[bucket];
while (nodeId > 0)
{
ref Node node = ref _nodes[nodeId - 1];
if (_comparer.Equals(node.value, value))
{
return false;
}
nodeId = node.nextNodeId;
}
if (_nodes.Length <= _nodeCount)
{
Array.Resize(ref _nodes, _nodes.Length * 2);
}
int newNodeId = _nodeCount + 1;
ref Node newNode = ref _nodes[newNodeId - 1];
newNode.value = value;
newNode.nextNodeId = _table[bucket];
_nodeCount++;
_table[bucket] = newNodeId;
_modCount++;
return true;
}
public bool Contains(in T value)
{
int bucket = Bucket(value);
int nodeId = _table[bucket];
while (nodeId > 0)
{
ref Node node = ref _nodes[nodeId - 1];
if (_comparer.Equals(node.value, value))
{
return true;
}
nodeId = node.nextNodeId;
}
return false;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private int Bucket(in T value)
{
return Math.Abs(_comparer.GetHashCode(value)) % _table.Length;
}
public Enumerator GetEnumerator()
{
Enumerator it = default;
it.set = this;
it.modCount = _modCount;
it.Reset();
return it;
}
public struct Enumerator : IEnumerator<T>
{
internal LightHashSet<T> set;
private int _idx;
internal int modCount;
public bool MoveNext()
{
if (modCount != set._modCount)
{
throw new Exception("set was modified during its iteration");
}
_idx++;
return _idx < set._nodeCount;
}
public void Reset()
{
_idx = -1;
}
object IEnumerator.Current => Current;
public T Current => set._nodes[_idx].value;
public void Dispose() { }
}
IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
public class LightHashSetTest
{
[Test]
public void ContainsAdded()
{
LightHashSet<string> set = new LightHashSet<string>(16, 16);
set.Add("A");
Assert.True(set.Contains("A"));
}
[Test]
public void NotContainsNotAdded()
{
LightHashSet<string> set = new LightHashSet<string>(16, 16);
set.Add("A");
Assert.False(set.Contains("B"));
}
[Test]
public void ContainsBothWithCollision()
{
LightHashSet<string> set = new LightHashSet<string>(1, 16);
set.Add("A");
set.Add("B");
Assert.True(set.Contains("A"));
Assert.True(set.Contains("B"));
}
[Test]
public void ReportsOnAdd()
{
LightHashSet<string> set = new LightHashSet<string>(16, 16);
Assert.True(set.Add("A"));
Assert.False(set.Add("A"));
}
[Test]
public void ClearWorks()
{
LightHashSet<string> set = new LightHashSet<string>(16, 16);
set.Add("A");
set.Clear();
Assert.False(set.Contains("A"));
}
[Test]
public void Linq()
{
LightHashSet<string> set = new LightHashSet<string>(16, 16);
set.Add("A");
set.Add("B");
string s = string.Join(", ", set.OrderBy(it => it));
Assert.AreEqual("A, B", s);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment