Изучить принципы работы аллокаторов памяти, реализовать несколько типов аллокаторов, а также создать структуры данных, использующие эти аллокаторы для управления памятью.
IAllocatorСоздать файл allocator.h, который станет единым стандартом для всего проекта. Структура должна содержать указатели на функции, где первым аргументом всегда идет указатель на саму структуру (self).
ArrayList) вызывать методы аллокатора, не зная, как он устроен внутри. Контекст конкретной реализации (буфер, дерево блоков и т.д.) хранится в поле void* ctx.typedef struct IAllocator {
void* (*alloc)(struct IAllocator* self, size_t size);
void (*free)(struct IAllocator* self, void* ptr);
void* (*realloc)(struct IAllocator* self, void* ptr, size_t new_size);
void (*reset)(struct IAllocator* self);
void* ctx;
} IAllocator;
Написать набор функций-заглушек, которые ничего не делают или возвращают NULL.
free). Чтобы не проверять каждый раз if (allocator->free != NULL), в структуру записывается указатель на «безопасную» пустую функцию.void stub_free(IAllocator* self, void* ptr) {
// Ничего не делаем, чтобы не упасть при вызове
(void)self; (void)ptr;
}
void* stub_realloc(IAllocator* self, void* ptr, size_t size) {
(void)self; (void)ptr; (void)size;
return NULL; // Сигнализируем, что реаллокация невозможна
}
free, realloc и reset, которые не приводят к аварийному завершению программы.Создать реализацию IAllocator, которая внутри использует стандартные malloc и free из <stdlib.h>.
void* sys_alloc_impl(IAllocator* self, size_t size) {
return malloc(size);
}
// ... и так далее для всех функций
IAllocator create_sys_alloc()), которая возвращает готовую структуру. Успешное выделение и освобождение памяти через этот интерфейс.Создать короткие псевдонимы для вызова функций.
a->alloc(a, size) неудобно и легко ошибиться. Лучше обернуть это в простые функции или макросы.static inline void* i_alloc(IAllocator* a, size_t sz) {
return a->alloc(a, sz);
}
ArrayList) становится чище и читабельнее.Реализация максимально быстрого аллокатора, который выделяет память простым смещением указателя.
ctx):typedef struct {
void* buffer; // Начало выделенной области
size_t size; // Общий размер
size_t offset; // Текущая позиция для следующей аллокации
} LinearCtx;
alloc (сдвигает offset), reset (offset = 0), free (пустая заглушка).malloc. При переполнении буфера возвращает NULL.Реализация аллокатора для объектов одинакового размера (например, только для узлов списка).
ctx):typedef struct Node { struct Node* next; } Node;
typedef struct {
void* buffer;
size_t block_size;
Node* free_list; // Указатель на первый свободный блок
} PoolCtx;
alloc (забирает узел из free_list), free (кладет узел обратно), realloc (заглушка/NULL).Реализация алгоритма, работающего со степенями двойки для минимизации внешней фрагментации.
alloc (поиск/деление блоков), free (освобождение/слияние), realloc (полная реализация).Реализация массива, который автоматически расширяется при заполнении.
IAllocator. При добавлении элемента, если size == capacity, массив должен вызвать realloc (или alloc + memcpy, если realloc вернул NULL).typedef struct {
IAllocator* alloc;
void** data;
size_t size;
size_t capacity;
} ArrayList;
Реализация структуры FIFO (First-In, First-Out) на основе узлов.
Node), содержащий данные и указатель на следующий элемент. Память под каждый Node запрашивается у аллокатора.pop) вызывается free для узла.void queue_push(Queue* q, void* val) {
Node* n = q->alloc->alloc(q->alloc, sizeof(Node));
n->data = val;
// ... вставка в хвост
}
Реализация ассоциативного массива (ключ-значение) с разрешением коллизий (метод цепочек).
alloc и free. Лучше всего тестировать в связке с Buddy-аллокатором.insert(table, key, value), get(table, key), remove(table, key).Это критический аспект при написании своего аллокатора. Процессоры требуют, чтобы данные определенных типов (например, double или указатели) находились по адресам, кратным 8 байтам.
alloc должны возвращать указатель, выровненный по границе 8 байт.offset или размера блока используйте формулу: (size + 7) & ~7. Это округлит любое число вверх до ближайшего кратного восьми.Не пытайтесь сразу запустить HashTable на Buddy-аллокаторе. Двигайтесь итеративно:
malloc (через ваш интерфейс). Если падает здесь — проблема в логике структуры, а не в памяти.Используйте gdb
Аллокатор — это фундамент. Если он ломается, падает всё здание.
assert внутри alloc. Если память закончилась, функция должна просто вернуть NULL.NULL.Даже если ваша программа не падает, в ней могут быть утечки или порча памяти.
valgrind --leak-check=full или компилируйте с флагами -fsanitize=address -fno-omit-frame-pointer. Это покажет ошибки, которые «не видны» при обычном запуске.