3
\$\begingroup\$

I saw a nice generic stack implemented in C, in Stanford's CS107 Programming Paradigms course, so I tried to rewrite it in C#:

public unsafe static class NativeMemory
{
    [DllImport("msvcrt.dll", EntryPoint = "memcpy", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
    public static extern  void* memcpy(void* dest, void* src, UIntPtr count);

    [DllImport("msvcrt.dll", EntryPoint = "malloc", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
    public static extern  void* malloc(UIntPtr count);

    [DllImport("msvcrt.dll", EntryPoint = "realloc", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
    public static extern  void* realloc(void* src, UIntPtr count);

    [DllImport("msvcrt.dll", EntryPoint = "free", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
    public static extern void free(void* src);
}

public unsafe delegate void FreeFunction(void* elemAddr);

public unsafe struct Stack : IDisposable
{
    private readonly int elemSize;
    private readonly FreeFunction freeFunction;
    private int alloclength;
    private void* elems;

    public Stack(int elemSize, FreeFunction freeFunction)
        : this()
    {
        this.elemSize = elemSize;
        this.freeFunction = freeFunction;
        alloclength = 4;
        elems = NativeMemory.malloc((UIntPtr) (elemSize * alloclength));
    }

    public int Count { get; set; }

    public void Push(void* elemAddr)
    {
        if (alloclength == Count)
        {
            Grow();
        }
        NativeMemory.memcpy(((byte*)elems + Count* elemSize), elemAddr, (UIntPtr) elemSize);
        Count++;
    }

    public void Pop(void* elemAddr)
    {
        void* source = ((byte*) elems + (--Count* elemSize));
        NativeMemory.memcpy(elemAddr, source, (UIntPtr)elemSize);
    }

    private void Grow()
    {
        alloclength *= 2;
        elems = NativeMemory.realloc(elems, (UIntPtr) (alloclength* elemSize));
    }

    public void Dispose()
    {
        if (freeFunction != null)
        {
            for (int i = 0; i < Count; i++)
            {
                void* elemAddr = ((byte*) elems + (elemSize * i));
                freeFunction(elemAddr);
            }
        }
        NativeMemory.free(elems);
    }
}

public class Program
{
    private unsafe static void Main(string[] args)
    {
        using (Stack s = new Stack(sizeof (char*), null))
        {
            string[] names = {"rezo", "jack", "andrew"};
            foreach (string n in names)
            {
                fixed (char* ptr = n)
                {
                    char* name = ptr;
                    s.Push(&name);
                }
            }

            while (s.Count > 0)
            {
                char* name;
                s.Pop(&name);
                Console.WriteLine(new string(name));
            }
        }
    }
}

Example of how to store managed objects:

private unsafe static void Main(string[] args)
{
    var names = new[] {"Brad", "Andrew", "Jon","Melissa"};

    using (Stack stack = new Stack(sizeof(GCHandle), (ptr) =>
    {
        GCHandle handle = GCHandle.FromIntPtr(new IntPtr(ptr));
        handle.Free();
    }))
    {
        foreach (var name in names)
        {
            GCHandle handle = GCHandle.Alloc(name);
            stack.Push(&handle);
        }

        while (stack.Count > 0)
        {
            GCHandle objHandle;
            stack.Pop(&objHandle);
            Console.WriteLine((string)objHandle.Target);
        }
    }
}

What do you think about this? Is there a better way to implement a C-style generic stack in C#?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  • UIntPtr is the wrong type to represent a count (it's basically a void *). You want UInt32 or UInt64 depending on your architecture.
  • Count should be private set; callers should not be able to change it directly
  • Why are elemsize and alloclength both signed ints? Shouldn't they be unsigned? Or at least check the incoming elemsize in the constructor?
  • I hope that the documentation explains that the FreeFunction is for freeing individual elements that the Stack owns if it gets destroyed nonempty.
  • What's supposed to happen when they Pop an empty stack? Right now you get undefined behavior.
  • What's supposed to happen if the malloc() or realloc() fails?
\$\endgroup\$
2
  • \$\begingroup\$ Signature of memcpy in pinvoke.net had UIntPtr as the count argument. UIntPtr will be 4 bytes on x86 and 8 bytes on x64. You can check it by printing out UIntPtr.Size on x86 and x64. \$\endgroup\$ Apr 26, 2015 at 6:41
  • \$\begingroup\$ That's an..."interesting" design choice for .NET to include both IntPtr and the (non-compliant) UIntPtr but no MachineWidthInteger. Perhaps a using directive to indicate the type's actual purpose? \$\endgroup\$
    – Snowbody
    Apr 26, 2015 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.