Turn C # into C ++: manual memory management

In this article I want to show how you can arrange manual memory management in C # and then make a simple one-way list with it.

For the seed we’ll go ahead a bit and show how in the end an instance of such a list will be created:

new CustomLinkedList< double , ListBasedAllocator<CustomLinkedListNode< double , int >>, int >()

Immediately agree that we will not use unsafe context. This reduces portability and eliminates all the pleasure that can be obtained by developing the list.

Your pointers

Fortunately (!), .NET does not support pointers as C ++ supports them. All that is available when developing managed code is

• Reference instances They are all heaped and maintained by the garbage collector. As we write our memory management, you can forget about them right away.
• The boxed value type instances. In principle, they do not differ much from instances of reference types and are not suitable for the same reasons.
• Managed Pointers They can point both to the heap and to the stack. As far as I know, they can only be stored in local variables and / or passed to other functions when called. Therefore, they also will not suit us.

We will solve this problem simply: we will not solve it at all at this stage, but we will postpone it until better times. In the meantime, we agree to use the Pointer type parameter everywhere.
')

Modification of structures contained in containers

In this article I will consider allocators for fixed-size data structures. We describe the interface of such an allocator:

1. /// <summary>
2. /// Generalized interface for allocators of objects of a certain type.
3. /// </ summary>
4. /// <typeparam name = "T"> Type of objects with which the allocator works </ typeparam>
5. /// <typeparam name = "TPointer"> Pointer type used for memory access </ typeparam>
6. public interface ICustomTypeAllocator <T, TPointer>
7. {
8. /// <summary>
9. /// Allocates memory for one object and returns a pointer to that area.
10. /// </ summary>
11. TPointer Allocate ();
12. /// <summary>
13. /// Releases memory at pointer.
14. /// If the checkErrors flag is set, the allocator will, if possible, check that
15. /// that this pointer really points to a previously allocated block of memory,
16. /// and, if not, throws an exception.
17. /// </ summary>
18. /// <param name = "pointer"> A pointer to the area of ​​memory to be freed </ param>
19. /// <param name = "checkErrors"> </ param>
20. void Free (TPointer pointer, bool checkErrors = false );
21. /// <summary>
22. /// Allows access to the object at the pointer address.
23. /// </ summary>
24. /// <param name = "pointer"> Address of the memory area in which the object is located. </ param>
25. T this [TPointer pointer] { get ; set ; }
27. /// <summary>
28. /// Returns a pointer that is always invalid.
29. /// </ summary>
30. TPointer InvalidPointer { get ; }
31. /// <summary>
32. /// Checks whether the specified pointer is valid.
33. /// </ summary>
34. /// <param name = "pointer"> Pointer to check </ param>
35. bool IsPointerValid (TPointer pointer);
36. }

* This source code was highlighted with Source Code Highlighter .

When we try to use this interface (and maybe even earlier), we will come across the following problem:

var pointer = allocator.Allocate();
allocator[pointer].Value = 0;

If we specified type-value as type T (namely this is our primary goal), then the specified code will not compile. The reason for this is simple: the result of the allocator [pointer] operation is a copy of the structure contained at the specified address, and not the structure itself. I know two ways out of the problem:

1. Save the result of the allocator [pointer] to a temporary variable, perform the necessary operations on the structure and write it back.
2. Add a function to the interface of the allocator that will modify the value at the specified address in the specified manner.

Let's go on the second path. To do this, we declare a delegate type that takes one parameter by reference and returns void: public delegate void Modifier<T>( ref T value ); and add a modifier function to our interface:

1. /// <summary>
2. /// Modifies the object at the specified address pointer, calling the function modifier
3. /// </ summary>
4. /// <param name = "pointer"> A pointer to a variable object </ param>
5. /// <param name = "modifier"> A function that changes the value of an object </ param>
6. void Set (TPointer pointer, Modifier <T> modifier);

By default, we have nowhere to store pointers.

I will consider the implementation of the allocator based on the list of free nodes. With C ++, everything is simple: whatever type the user wants to store in the memory we manage, we can represent an element as a union of a user structure and a structure that has exactly one element — a pointer to the next free element in the list. .NET outside unsafe context does not support joins. Therefore, it is necessary that the user of our allocator explicitly provide us with a place to store the pointer. To do this, we will declare the ILinkedListNode interface with a single member Pointer Node {get; set; }, and require that the type of the element with which the allocator works is inherited from this interface.

public class ListBasedAllocator<T>: ICustomTypeAllocator<T, int > where T: ILinkedListNode< int >

Implementation of the allocator and list

I suppose every self-respecting programmer should be able to implement an allocator based on the list of free nodes and even more so - a unidirectional list. All this is described, for example, in the book of Cormen.
The source code of the full implementation (in C #) and the test case (in F #) can be downloaded or viewed here .

Finally

Probably, the volume of the code for the implementation of the list and the allocator could be reduced by typing types, rewriting it in F #.

Do not use similar magic in production yet. :)

PS What else will be!