Immutable intrusive 2-3 tree shaped as intrusive array (cache-friendly, values are separated to its own array) and using gen references for the immutability tracking

imtree23.cs

using System;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections.Generic;
using System.Threading;

public enum NodeType : byte { Sentinel, TwoNode, ThreeNode }

public readonly record struct NodeIdx(int Index, int Gen) {
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool IsNil(int limit) => Gen == 0 || Gen > limit;
}

public struct Entry<TKey, TValue>(TKey key, TValue val) {
    public TKey Key = key;
    public TValue Value = val;
}

[StructLayout(LayoutKind.Sequential, Pack = 4)]
public struct Node23 {
    public int H1, H2; 
    public NodeIdx L, M, R; 
    public int D1, D2;
    public NodeType Type; 
}

public class Concurrent23Store<TKey, TValue> {
    internal Node23[] _s; 
    internal Entry<TKey, TValue>[] _d;
    internal int _n = 1, _dv, _g = 1, _rt;

    public Concurrent23Store(int sCap, int dCap) => (_s, _d) = (new Node23[sCap], new Entry<TKey, TValue>[dCap]);

    public Immutable23Tree<TKey, TValue> GetSnapshot() => 
        new(_s, _d, Volatile.Read(ref _rt), Volatile.Read(ref _g), this);

    internal (int r, int g) Put(int root, int limit, TKey key, TValue val) {
        var h = key!.GetHashCode();
        var dIdx = Interlocked.Increment(ref _dv) - 1;
        _d[dIdx] = new(key, val);
        var nextG = Interlocked.Increment(ref _g);
        
        if (root == 0) {
            var rIdx = Interlocked.Increment(ref _n) - 1;
            _s[rIdx] = new() { H1 = h, D1 = dIdx, Type = NodeType.TwoNode };
            Interlocked.CompareExchange(ref _rt, rIdx, 0);
            return (rIdx, nextG);
        }

        // Safe stackalloc via Span
        Span<int> path = stackalloc int[32]; 
        int top = 0, cur = root;
        while (cur != 0) {
            path[top++] = cur;
            ref var n = ref _s[cur];
            if (n.L.IsNil(limit)) break;
            cur = (h < n.H1) ? n.L.Index : (n.Type == NodeType.ThreeNode && h > n.H2 ? n.R.Index : n.M.Index);
        }

        NodeIdx pL = default, pR = default;
        int pH = h, pD = dIdx, split = 1;

        while (top > 0 && split == 1) {
            int src = path[--top], dst = Interlocked.Increment(ref _n) - 1;
            _s[dst] = _s[src]; 
            ref var n = ref _s[dst];
            
            if (n.Type == NodeType.TwoNode) {
                split = 0; n.Type = NodeType.ThreeNode;
                if (pH < n.H1) {
                    (n.H2, n.D2, n.R) = (n.H1, n.D1, n.M);
                    (n.H1, n.D1, n.L, n.M) = (pH, pD, pL, pR);
                } else {
                    (n.H2, n.D2, n.M, n.R) = (pH, pD, pL, pR);
                }
                pR = new(dst, nextG);
            } else {
                int sib = Interlocked.Increment(ref _n) - 1;
                int mH, mD;
                if (pH < n.H1) {
                    (mH, mD) = (n.H1, n.D1);
                    _s[sib] = new() { H1 = n.H2, D1 = n.D2, L = n.M, M = n.R, Type = NodeType.TwoNode };
                    n = new() { H1 = pH, D1 = pD, L = pL, M = pR, Type = NodeType.TwoNode };
                } else if (pH < n.H2) {
                    (mH, mD) = (pH, pD);
                    _s[sib] = new() { H1 = n.H2, D1 = n.D2, L = pR, M = n.R, Type = NodeType.TwoNode };
                    n = new() { H1 = n.H1, D1 = n.D1, L = n.L, M = pL, Type = NodeType.TwoNode };
                } else {
                    (mH, mD) = (n.H2, n.D2);
                    _s[sib] = new() { H1 = pH, D1 = pD, L = n.R, M = pL, Type = NodeType.TwoNode };
                    n = new() { H1 = n.H1, D1 = n.D1, L = n.L, M = n.M, Type = NodeType.TwoNode };
                }
                (pH, pD, pL, pR) = (mH, mD, new(dst, nextG), new(sib, nextG));
            }
        }

        if (split == 1) {
            int nR = Interlocked.Increment(ref _n) - 1;
            _s[nR] = new() { H1 = pH, D1 = pD, L = pL, M = pR, Type = NodeType.TwoNode };
            return (nR, nextG);
        }
        return (pR.Index, nextG);
    }
}

public readonly struct Immutable23Tree<TKey, TValue>(
    Node23[] s, Entry<TKey, TValue>[] d, int root, int gen, Concurrent23Store<TKey, TValue> store) {

	public bool TryFind(TKey key, out TValue val) {
		var h = key!.GetHashCode();
		int cur = root; 
		val = default!;
		var cmp = EqualityComparer<TKey>.Default;

		while (cur != 0) {
			ref readonly var n = ref s[cur];

			// Match on Slot 1
			if (h == n.H1 && cmp.Equals(key, d[n.D1].Key)) {
				val = d[n.D1].Value;
				return true;
			}

			// Match on Slot 2 (if 3-node)
			if (n.Type == NodeType.ThreeNode && h == n.H2 && cmp.Equals(key, d[n.D2].Key)) {
				val = d[n.D2].Value;
				return true;
			}

			// Navigate
			NodeIdx next = (n.Type == NodeType.ThreeNode) 
				? (h < n.H1 ? n.L : (h < n.H2 ? n.M : n.R)) 
				: (h < n.H1 ? n.L : n.M);

			if (next.IsNil(gen)) break;
			cur = next.Index;
		}
		return false;
	}

    public Immutable23Tree<TKey, TValue> Put(TKey key, TValue val) {
        var res = store.Put(root, gen, key, val);
        return new(s, d, res.r, res.g, store);
    }
}

public class Program
{
	public static void Main()
	{
		Console.WriteLine("Hello World");
	}
}