Abnormal programming
March 2011 12

Превращаем C# в C++: ручное управление памятью

В этой статье я хочу показать, как можно оформить ручное управление памятью в C# и сделать затем с его помощью простой однонаправленный список.

Для затравки забежим немного вперёд и покажем, как в итоге будет создаваться экземплят такого списка:
new CustomLinkedList<double, ListBasedAllocator<CustomLinkedListNode<double, int>>, int>()


Сразу условимся, что мы не будем использовать unsafe контекст. Это снижает портируемость и нивелирует всё удовольствие, что можно получить при разработке заявленного списка.

Свои указатели


К счастью (!), .NET не поддерживает указатели в том виде, в котором их поддерживает C++. Всё, что доступно при разработке управляемого кода — это
  • Инстансы ссылочных типов. Все они хранятся в куче и обслуживаются сборщиком мусора. Поскольку мы пишем своё управление памяти, о них можно забыть сразу.
  • Завёрнутые в коробку инстансы типов-значений. В принципе, они мало отличаются от инстансов ссылочных типов и нам не подходят по тем же причинам.
  • Управляемые указатели. Могут указывать как в кучу, так и на стек. Насколько я знаю, они могут храниться только в локальных переменных и/или передаваться в другие функции при вызове. Поэтому они нам тоже не подойдут.

Решим мы эту проблему просто: не будем её решать вообще на данном этапе, а отложим до лучших времён. Пока же договоримся везде использовать параметр типа Pointer.

Модификация структур, содержащихся в контейнерах


В этой статье я буду рассматривать аллокаторы для структур данных фиксированного размера. Опишем интерфейс такого аллокатора:
  1. /// <summary>
  2. /// Обобщённый интерфейс для аллокаторов объектов определённого типа.
  3. /// </summary>
  4. /// <typeparam name="T">Тип объектов, с которыми работает аллокатор</typeparam>
  5. /// <typeparam name="TPointer">Тип указателя, используемый для доступа к памяти</typeparam>
  6. public interface ICustomTypeAllocator<T, TPointer>
  7. {
  8.     /// <summary>
  9.     /// Выделяет область памяти для одного объекта и возвращает указатель на эту область
  10.     /// </summary>
  11.     TPointer Allocate();
  12.     /// <summary>
  13.     /// Освобождает память, по адресу pointer.
  14.     /// Если установлен флаг checkErrors, аллокатор по возможности производит проверку того,
  15.     /// что данный указатель действительно указывает на ранее выделенный блок памяти,
  16.     /// и, если это не так, генерирует исключение.
  17.     /// </summary>
  18.     /// <param name="pointer">Указатель на область памяти, подлежащую освобождению</param>
  19.     /// <param name="checkErrors"></param>
  20.     void Free(TPointer pointer, bool checkErrors = false);
  21.     /// <summary>
  22.     /// Позволяет осуществлять доступ к объекту по адресу pointer.
  23.     /// </summary>
  24.     /// <param name="pointer">Адрес области памяти, в которой находится объект.</param>
  25.     T this[TPointer pointer] { get; set; }
  26.  
  27.     /// <summary>
  28.     /// Возвращает указатель, который всегда является невалидным
  29.     /// </summary>
  30.     TPointer InvalidPointer { get; }
  31.     /// <summary>
  32.     /// Проверяет, является ли заданный указатель валидным.
  33.     /// </summary>
  34.     /// <param name="pointer">Указатель для проверки</param>
  35.     bool IsPointerValid(TPointer pointer);
  36. }
* This source code was highlighted with Source Code Highlighter.

Когда мы попытаемся использовать этот интерфейс (а может и раньше), мы наткнёмся на следующую проблему:
var pointer = allocator.Allocate();
allocator[pointer].Value = 0;

Если в качестве типа T мы указали тип-значение (а именно это и есть наша первичная цель), то указанный код не скомпилируется. Причина тому проста: результатом операции allocator[pointer] будет копия структуры, содержащейся по указанному адресу, а не сама структура. Я знаю два выхода из проблемы:
  1. Сохранить результат allocator[pointer] во временную переменную, произвести нужные операции над стурктурой и записать её обратно.
  2. Добавить в интерфейс аллокатора функцию, которая будет заданным образом модифицировать значение по заданному адресу.
Пойдём по второму пути. Для этого объявим тип-делегат, принимающий один параметр по ссылке и возвращающий void: public delegate void Modifier<T>(ref T value); и добавим функцию-модификатор в наш интерфейс:
  1. /// <summary>
  2. /// Изменяет объект по заданному адресу pointer, вызывая функцию modifier
  3. /// </summary>
  4. /// <param name="pointer">Указатель на изменяемый объект</param>
  5. /// <param name="modifier">Функция, которая изменит значение объекта</param>
  6. void Set(TPointer pointer, Modifier<T> modifier);

По умолчанию нам негде хранить указатели


Я буду рассматривать реализацию аллокатора на основе списка свободных узлов. С C++ всё просто: какой бы тип пользователь не хотел хранить в управляемой нами памяти, мы можем представить элемент в виде объединения (union) пользовательской структуры и структуры, имеющей ровно один элемент — указатель на следующий свободный элемент в списке. .NET вне unsafe контекста не поддерживает объединения. Поэтому нужно, чтобы пользователь нашего аллокатора явно предоставил нам место для хранения указателя. Для этого мы объявим интерфейс ILinkedListNode c единственным членом Pointer Node{ get; set; }, и потребуем, чтобы тип элемента, с которым работает аллокатор, был унаследован от этого интерфейса.
public class ListBasedAllocator<T>: ICustomTypeAllocator<T, int> where T: ILinkedListNode<int>

Реализация аллокатора и списка


Полагаю каждый уважающий себя программист должен уметь реализовать аллокатор, основанный на списке свободных узлов и уж тем более — однонаправленный список. Всё это описано, например, в книге Кормена.
Исходный код полной реализации (на C#) и тестового примера (на F#) можно скачать или посмотреть здесь.

В заключение


Наверное, объём кода реализации списка и аллокатора можно было бы сократить за счёт вывода типов, переписав его на F#.

Пока не стоит использовать подобную магию в продакшене. :)

P.S. То ли ещё будет!
+6
8k 24
Comments 40
Top of the day