Введение
Общий алгоритм для пула памяти, который обеспечивает блоки памяти постоянного размера, состоит в использовании свободных (нераспределенных) блоков в качестве «односвязного списка» путем сохранения указателя на следующий свободный блок. После возвращения блока памяти в пул блок добавляется в этот связанный список.
Растет
Вместо того, чтобы возвращать прямые указатели пользователю, библиотека может предоставлять индексы в пул; таким образом, если бы realloc выделяло память в другом месте, индексы, сохраненные в некоторой структуре данных, все еще действительны, поскольку любой метод разрешения мог бы возвращать новый действительный указатель по запросу. Это делает возможным увеличение пула с дополнительным компромиссом при использовании индексов вместо указателей.
Сокращение?
Мне неясно, как можно расширить этот дизайн, чтобы включить сокращение до желаемый размер. Я понимаю, что эта операция будет стоить дорого - либо с точки зрения дизайна, либо с точки зрения производительности. Я вижу два аспекта сжатия: переопределение связанного списка (легко?) И дефрагментация уже выделенных блоков (сложно?). Одно замечание по поводу сокращения: должна быть возможность уменьшить пул, но не так, чтобы любые блоки памяти, уже выданные пользователю, были освобождены.
Перенаправление связанного списка
По существу связанный список будет идти от головы, и любые указатели, которые выше определенного порога, будут пропущены:
threshold: 5
old: 6 -> 3 -> 2 -> 9 -> 4 -> 1 -> 10
new: 3 -> 2 -> 4 -> 1
Это должно быть выполнимо в O(n), где n - это число свободные блоки. Не идеально, но возможно, что операция сжатия будет одноразовой для приложения. Это приведет к тому, что любые новые блоки будут размещены в нижней части пула памяти. Но есть и недостатки: * нам по-прежнему не разрешено на самом деле вызывать realloc, поскольку некоторые из выделенных блоков превышают порог *, нам нужно игнорировать запросы выше порога, чтобы они не возвращались в начало связанного списка
На этом этапе мы должны быть в состоянии идентифицировать блоки, которые превышают пороговое значение в O(n), поскольку они являются точками, которые не были упомянуты в связанном списке. Кроме того, мы знаем, что их меньше, чем свободных пространств ниже порогового значения, в противном случае операция не будет разрешена для выполнения. Какие есть варианты для перемещения этих? Таблица перевода индексов? Возможно, весь дизайн нужно изменить, чтобы приспособиться к усадке?