Unsafe Stack in C#

I was interested to see if it was possible to implement an unsafe stack in C#, so I wrote this:

public unsafe struct Node
{
    public int Value { get; set; }
    public Node* Next { get; set; }
}

public unsafe class Stack
{
    Node* first;

    public int Count { get; private set; }

    public void Push(int value)
    {
        var oldFirst = first;
        first = (Node*)(Marshal.AllocHGlobal(sizeof(Node)));
        first->Value = value;
        first->Next = oldFirst;
        Count++;
    }

    public int Pop()
    {
        if(Count == 0) throw new InvalidOperationException();

        int item = first->Value;
        first = first->Next;
        Count--;
        return item;
    }
}

Test method:

void Main()
{
    Stack stack = new Stack();

    for(int i = 1; i <= 1000;i++)
        stack.Push(i);

    double sum = 0;
    while(stack.Count != 0) sum += stack.Pop();
    Console.WriteLine(sum);
}

Output: 500500

Is there something wrong with this? Is it possible to make it generic?

Your stack seems to be leaking memory. When you want to use native Marshal.AllocHGlobal (which is like malloc in C), you have to free the memory as well in Pop().

public int Pop()
{
    if(Count == 0) throw new InvalidOperationException();

    int item = first->Value;
    Node* node = first;         // take it to local
    first = first->Next;
    Marshal.FreeHGlobal((IntPtr)node);  // dispose/free the memory
    Count--;
    return item;
}

And it should be made IDisposable to do the same for all the nodes in destructor (at least this way, but IDisposable is prefered in such case).

The following is the idea of generic implementation with IDisposable:
(hope I got it right, untested)

public unsafe class Stack: IDisposable {
    protected struct Node {  // implementation detail should not be public
        public Node* next;   // just my preference to have the pointer first
        public IntPtr value; // discussed later
    }
    ~Stack() { // this is destructor (called when garbage collected)
        Dispose(false);
    }
    public void Dispose() { // this is implementation of IDisposable - see keyword using
        Dispose(true);
        GC.SuppressFinalize(this); // prevents calling destructor, we have done the job
    }
    protected virtual void Dispose(bool disposing) {
        while(Count > 0) Pop(); // make sure all unmanaged memory got released
    }

It is not possible to have managed pointers in unmanaged (unsafe/fixed) struct (there would be no way for GC to change such pointers in unmanaged space), but there still is a way to make it generic - links:

SO: Implementing a generic unmanaged array in C#

MSDN: Marshal.PtrToStructure

Unmanaged pointers to managed objects are only valid within fixed contex, where the managed memory is pinned in place, but after leaving the fixed context, the memory can be moved (when there is no reference to object with lower address) or reclaimed (as there is no hint that a reference exist).

Implementing such generic unmanaged Stack would need some Marshal magic, type checking and casting. Simple native types and structures smaller than IntPtr could be casted, bigger structs allocated on unmanaged heap (proper allocation/deallocation needed), some specific objects like strings could be handled as native arrays and converted both ways. Totally generic approach (for any managed class) is not possible and runtime errors (from Marshal) will be the result of it (but not unsafe, this can still be made safe, but not compile-time checked).

This is getting too StackOverflow-ish, too far from CR. I will (propbably) leave it with those ideas and without implementation.

StackExchange Code Review Q#64979, answer score: 8