Skip to content

Instantly share code, notes, and snippets.

@lucasteles
Last active February 1, 2024 17:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lucasteles/caae0fb6efcd82ba7b1567819a33df3c to your computer and use it in GitHub Desktop.
Save lucasteles/caae0fb6efcd82ba7b1567819a33df3c to your computer and use it in GitHub Desktop.
C# ValueList - non-alloc stack list
using System;
using System.Runtime.CompilerServices;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
ValueList<int> nums = new();
nums.Add(10);
nums.Add(20);
nums.Add(30);
nums.Add(40);
nums.Add(50);
Console.WriteLine(nums);
nums.RemoveAt(0);
Console.WriteLine(nums);
Console.WriteLine(nums[1..^1]);
ValueList<int> nums2 = [20,30,40,50];
Console.WriteLine(nums2);
Console.WriteLine(nums == nums2);
nums2[1] = 99;
Console.WriteLine(nums2);
nums2.Remove(99);
Console.WriteLine(nums2);
nums2.Insert(2, 42);
Console.WriteLine(nums2);
foreach (var n in nums)
Console.Write($"|{n}");
Console.WriteLine();
var plusOne = nums.Select(x => x + 1);
Console.WriteLine(string.Join(';', plusOne));
//
struct ValueList<T> : IList<T>, IEquatable<ValueList<T>> where T : struct, IEquatable<T>
{
public const int MaxSize = 32;
ValueListBuffer buffer;
public int Count { get; private set; } = 0;
public ValueList()
{
if (Unsafe.SizeOf<T>() > 1024)
throw new InvalidOperationException($"{typeof(T).Name} is too big for stack");
}
public readonly bool IsReadOnly => false;
public readonly bool IsFull() => Count >= MaxSize;
public void Add(in T task)
{
if (IsFull()) throw new InvalidOperationException("ValueTaskList is full");
buffer[Count++] = task;
}
void ICollection<T>.Add(T item) => Add(in item);
public void Clear()
{
Span<T> span = buffer;
span.Clear();
Count = 0;
}
public readonly bool Contains(T item) => buffer[..Count].Contains(item);
public readonly void CopyTo(T[] array, int arrayIndex) =>
buffer[..Count].CopyTo(array.AsSpan()[arrayIndex..]);
public readonly int IndexOf(T item)
{
ReadOnlySpan<T> span = buffer;
return span.IndexOf(item);
}
public void RemoveAt(int index)
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException(nameof(index));
Span<T> span = buffer;
span[(index + 1)..Count].CopyTo(span[index..(Count - 1)]);
Count--;
}
public bool Remove(T item)
{
var index = IndexOf(item);
if (index is -1) return false;
RemoveAt(index);
return true;
}
public void Insert(int index, T item)
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException(nameof(index));
if (IsFull()) throw new InvalidOperationException("ValueTaskList is full");
Span<T> span = buffer;
span[index..Count].CopyTo(span[(index + 1)..(Count + 1)]);
span[index] = item;
Count++;
}
public T this[int index]
{
readonly get
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException(nameof(index));
return buffer[index];
}
set
{
if (index < 0 || index >= Count)
throw new ArgumentOutOfRangeException(nameof(index));
buffer[index] = value;
}
}
public readonly ValueList<T> this[Range range]
{
get
{
ValueList<T> result = [];
var values = buffer[..Count][range];
values.CopyTo(result.buffer);
result.Count = values.Length;
return result;
}
}
public static implicit operator ReadOnlySpan<T>(in ValueList<T> list) => list.buffer;
public readonly IEnumerator<T> GetEnumerator()
{
for (var i = 0; i < Count; i++)
yield return buffer[i];
}
readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public readonly bool Equals(ValueList<T> other) => buffer[..Count].SequenceEqual(other.buffer[..other.Count]);
public override readonly bool Equals(object? obj) => obj is ValueList<T> other && Equals(other);
public override readonly int GetHashCode() => base.GetHashCode();
public static bool operator ==(ValueList<T> left, ValueList<T> right) => left.Equals(right);
public static bool operator !=(ValueList<T> left, ValueList<T> right) => !left.Equals(right);
public override readonly string ToString() => ToString(default);
public readonly string ToString(
ReadOnlySpan<char> separator,
ReadOnlySpan<char> prefix = default,
ReadOnlySpan<char> suffix = default
)
{
separator = separator.IsEmpty ? ", " : separator;
prefix = prefix.IsEmpty ? "[" : separator;
suffix = suffix.IsEmpty ? "]" : suffix;
ReadOnlySpan<T> values = buffer[..Count];
StringBuilder builder = new();
builder.Append(prefix);
for (var i = 0; i < values.Length; i++)
{
if (i > 0) builder.Append(separator);
builder.Append(values[i]);
}
builder.Append(suffix);
return builder.ToString();
}
[InlineArray(MaxSize)]
struct ValueListBuffer
{
T element0;
}
}
[10, 20, 30, 40, 50]
[20, 30, 40, 50]
[30, 40]
[20, 30, 40, 50]
True
[20, 99, 40, 50]
[20, 40, 50]
[20, 40, 42, 50]
|20|30|40|50
21;31;41;51
@lucasteles
Copy link
Author

lucasteles commented Feb 1, 2024

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment