Временная память - удобная альтернатива

Многие, наверное, сталкивались с "ограничением" языка Си на работу со строками, когда надо возвратить строку или другие объемные данные, созданные внутри функции. Сейчас вы поймете, почему я взял это слово в кавычки :)

Существует два стандартных и широко известных способа это сделать:

1. Передать функции буфер, куда она запишет свои данные. Проблема в том, буфер может оказаться слишком маленьким, тогда данные не влезут или обрежутся. Либо он может оказаться слишком большим, тогда будет перерасход памяти. Либо, что еще более серьезно, когда буфер окажется мал, а проверка его размера отсутствует, тогда произойдет его переполнение. Как минимум, получим падение, как максимум - будет дыра для хакерских атак.

2. Второй способ: создать буфер в динамической памяти, записать туда данные и возвратить указатель на него. Этот метод тоже имеет недостатки. Во-первых, вы можете просто забыть освободить память, либо алгоритм может содержать ошибки, делающие возможным пропуск кода освобождения памяти. К тому же, будем честны, сам такой код по освобождению ресурсов - снижает читабельности кода. Ну и во-вторых, динамическая память не блещет скоростью и программисты стараются всегда избежать ее выделения там, где требуется оптимизация по скорости. Да и используя ее для частых временных данных, вы рискуете повысить фрагментированность кучи памяти, замедлив ее работу и требование к памяти.

Но все это решается очень простым способом - использование временной памяти.

Смысл идеи в том, что вы выделяете большую секцию, от которой последовательно откусываете маленькие кусочки для временных блоков. Когда секция кончается и следующий размер блока уже не помещается в остаток, вы выделяет новую секцию, запоминая указатель на предыдущую. Все это делается очень, очень быстро, буквально парой машинных инструкций. Освобождение аналогично. Кроме скорости, такой подход позволяет запоминать и восстанавливать состояние временной памяти до заданного блока. Т.е. освободив любой блок, автоматом освободятся все остальные блоки, которые были выделены после него. Таким образом подчистив забытый кем-то "мусор".

Естественно, такая память работает только для блоков, которые создаются в последовательности обратной освобождению.

Далее идет модуль, который реализует заданный функционал. Надеюсь, он окажется вам полезен :)

Примеры

void* top = temp_top(); // Запоминаем текущую вершину
block = temp_alloc (blocksize); // Далее идет куча temp_alloc без temp_free
block = temp_alloc (blocksize);
// Чтобы не перегружать память, можно принудительно освобождать особенно большие блоки
hugeblock = temp_alloc (0x10000);
temp_free (hugeblock);
...
temp_free (top); // Теперь автоматом удаляем все временные блоки, созданные после top

Еще раз: память удаляется очень быстро. Кроме того, не происходит фрагментации стандартной динамической памяти, что неизбежно, если вы смешиваете выделение временных и долгоживущих блоков.

Исходные коды

memtemp.h

#include <stdlib.h>
#include <malloc.h>
#include <wchar.h>
#pragma once
/*
===============
(c) Copyright Vladimir Sapunov, www.fyzor.com
Последовательный менеджер памяти.
Применяется для ускорения выделения и освобождения памяти.
===============
*/
void*  temp_top (void); // Выделяет новый блок в текущей группе
void*  temp_alloc (size_t); // Выделяет новый блок в текущей группе
void  temp_free (void*); // Освобождает все блоки вплоть до указанного
const wchar_t* temp_sprintf (const wchar_t*, ...);
const wchar_t* temp_vsprintf (const wchar_t*, va_list);
const wchar_t* temp_string (const wchar_t*);
const wchar_t* temp_zstring (const wchar_t*, size_t); // Гарантированно возвращает z-строку
void*  temp_block (const void*, size_t); // Выделяет блок и копирует туда данные

memtemp.c

/*
===========
(c) Copyright Vladimir Sapunov, www.fyzor.com
DESCRIPTION: Менеджер последовательных блоков памяти.
REMARKS: Предназначена для скоростного выделения памяти серией по несколько блоков за раз.
Во временной памяти можно размещать блоки, которые выделяются в обратном удалению порядке.
Это дает возможность оптимизировать как выделение, так и освобождение,
применяя простое отрезание блока от текущей секции памяти,
а ддя удаления - возврат к заданной позиции.
Кроме того, при таком откате удаляются все блоки, выделенные после заданного,
что позволяет не заботиться об освобождении блоков вообще,
для этого лишь достаточно периодически делать откаты к наиболее раннему блоку.
===========
*/
#include "memtemp.h"
#define SECTION_SIZE 0x2000 /* Размер стандартной секции под временные блоки */

struct TempSection // Связанный список таких структур образует временную память.
{
 struct TempSection* previous; // Предыдущая секция
 int  capacity; // Остаточная вместимость секции
 BYTE  data []; // Область секции, из которой выдделяются блоки
};
static BYTE*  tmp_dest = NULL; // Начало свободной области в текущей секции
static BYTE*  tmp_end = NULL;  // Конец свободной области в текущей секции
static struct TempSection* tmp_section = NULL; // Текущая секция

/*
===========
temp_alloc
Выделяет новый временный блок.
Всегда пытается выделить блок в текущей секции (это самый быстрый вариант).
Но если блок там не помещается, то выделяет новую секцию,
при этом, идет обращения к динамической памяти.
Возвращает указатель на новый блок, который можно также использовать
для отката назад и удаления всех блоков, созданных после этого.
===========
*/
void* temp_alloc (size_t size)
{
  // Расширяем объем памяти по мере необходимости
 if (tmp_dest + size > tmp_end)
 {
  DWORD capacity = max (size, SECTION_SIZE);
  struct TempSection* fresh = malloc (sizeof(struct TempSection) + capacity);
  if (!fresh) return NULL;
  DEBUG_PRINT (("temp_alloc: alloc section of size %u\n", capacity));
  fresh->previous = tmp_section;
  fresh->capacity = capacity;
  tmp_section = fresh;
  tmp_dest = fresh->data + size;
  tmp_end = fresh->data + capacity;
  return fresh->data;
 } else {
  DEBUG_PRINT (("temp_alloc: fast alloc size %u\n", size));
  tmp_dest += size;
  return tmp_dest - size;
 }
}
/*
===========
temp_free
Освобождает все блоки, выделенные после заданного, включая его самомго.
Должна вызываться для отката состояния памяти назад.
===========
*/
void temp_free (void*mem)
{
 struct TempSection* scan, *prev;
  // Удаляем все влоть до узла владельца блока.
 for (scan = tmp_section; scan; scan = prev)
 {
  if ((BYTE*)mem >= scan->data && (BYTE*)mem <= scan->data + scan->capacity)
   break;
  prev = scan->previous;
  free (scan);
 }
 if (scan) {
  tmp_section = scan;
  tmp_dest = mem;
  tmp_end = scan->data + scan->capacity;
 } else {
  tmp_section = NULL;
  tmp_dest = NULL;
  tmp_end = NULL;
 }
}
/*
===========
temp_top
Возвращает последнюю позицию во временной памяти.
Используется для отката назад и освобождения всех блоков,
выделенных после этой позиции.
===========
*/
void* temp_top (void)
{
 return tmp_dest;
}
/*
===========
temp_block
Выделяет воременный блок и инициализирует его заданными байтами.
Полезна для облегчения создания копий.
===========
*/
void* temp_block (const void*from, size_t size)
{
 void* t = temp_alloc (size);
 memcpy (t, from, size);
 return t;
}
/*
===========
temp_vsprintf
Форматирует строку во временный буфер и возвращает его указатель.
Поддерживает любую длину строк и вставок.
===========
*/
const wchar_t* temp_vsprintf (const wchar_t*fmt, va_list a)
{
 int  length;
 wchar_t  buf [256];
 wchar_t* temp;
 length = vswprintf (buf, LEN(buf), fmt, a);
 if (length < 0)
 {
  size_t  capacity = 0;
  wchar_t* str = NULL;
  while (length < 0) {
   capacity = capacity * 2 + 1024;
   str = realloc (str, capacity * sizeof(wchar_t));
   if (!str) return NULL;
   length = vswprintf (str, capacity, fmt, a);
  }
  temp = temp_block (str, (length + 1) * sizeof(wchar_t));
  free (str);
 } else {
  temp = temp_block (buf, (length + 1) * sizeof(wchar_t));
 }
 return temp;
}
const wchar_t* temp_sprintf (const wchar_t*fmt, ...)
{
 const wchar_t* temp;
 va_list a;
 va_start (a, fmt);
 temp = temp_vsprintf (fmt, a);
 va_end (a);
 return temp;
}
/*
===========
temp_string
Копирует строку во временный буфер и возврщает его указатель.
Аналогична strdup.
===========
*/
const wchar_t* temp_string (const wchar_t*s)
{
 size_t size = (wcslen(s) + 1) * sizeof(wchar_t);
 void* t = temp_alloc (size);
 memcpy (t, s, size);
 return t;
}
/*
===========
temp_zstring
Гарантированно возвращает строку с нулем на конце.
Если в строке нет нуля, копирует ее во временный буфер и дополняет нулем.
===========
*/
const wchar_t* temp_zstring (const wchar_t*s, size_t size)
{
 wchar_t* temp;
 if (s[0] == 0) return L"";
 if (s[size-1] == 0) return s;
 temp = temp_alloc ((size + 1) * sizeof(wchar_t));
 memcpy (temp, s, size * sizeof(wchar_t));
 temp [size] = 0;
 return temp;
}

Bug fix 6.09.2010

// Старая строка:
 if ((BYTE*)mem >= scan->data && (BYTE*)mem < scan->data + scan->capacity)
// Новая строка:
 if ((BYTE*)mem >= scan->data && (BYTE*)mem <= scan->data + scan->capacity)

Ваше имя:

Articles & posts
Как работает временная память в мозгу	Резюме на статей о работе гиппокампа мозга, ответственного за хранение временной памяти.
Потоковая память	Иногда нужно выполнить множество операций конкатенации строки, и сделать это максимально быстро. В статье описывается алгоритм и даются исходники одного из методов решения этой задачи.
Временная память - удобная альтернатива	Многие, наверное, сталкивались с "ограничением" языка Си на работу со строками, когда надо возвратить строку или другие объемные данные, созданные внутри функции. Сейчас вы поймете, почему я взял это слово в кавычки :)
Функция создания точки останова на чтение/запись	Эта функция будет полезна при отладке, когда нужно определить, где портятся заданные данные.
Кремль со спутника	Вид со спутника на несколько известных мест. Карты maps.google.com.
Представление цвета	Принцип разложения цветов на составляющие для удобного их сравнения. Существующие два олсновных формата представления цвета.
Сравнение цветов	Соображения по поводу возможного алгоритма сравнения цветов.
Детектор движения	Общие соображения насчет алгоритма обнаружения движения.
Сборщик мусора	Альтернатива стандартному алгоритму сборщика мусора, используемому в java.