 Потоковая память
Бывает, нужно создать образ файла в памяти до того, как вы его записали на диск. Приведу несколько примеров, когда это может быть необходимо:
1. Нужно отформатировать какие-то данные в строку, но заранее неизвестен их размер, но известно, что в нем будет большое кол-во операций append/concat, т.е. дописывания в конец строки. В то же время, все должно работать максимально быстро, без лишних передислокаций динамической памяти функцией realloc.
2. Имеется чужой алгоритм, который читает/пишет в файл, пользуясь стандартной библиотекой ввода/вывода, а вам нужно быстро и удобно перехватить его выход или подать на него свои собственные данные без использования диска.
3. Перед записью данных на диск нужно их зашифровать. Или наоборот - перед чтением нужно расшифровать.
Конечно, легче всего для решения задачи создать какой-то модуль, который будет использовать экспоненциальное расширение блока памяти по мере роста размера его содержимого. Т.е. каждый раз, когда верно условие (buffer_size + data_size > buffer_capacity) мы выполняем приращение размера буфера приблизительно по такому алгоритму: buffer_capаcity = min(buffer_size+data_size, buffer_capcity * 0.4 + 256) и далее вызываем buffer=realloc(buffer, buffer_capcity).
Однако этот метод меня всегда смущал тем, что память все равно приходится периодически передислоцировать. На современных процессорах, использующих кэш-память, это будет достаточно накладно, так как каждый раз при очередной передислокации придется выкидывать уже кэшированные блоки и загружать туда новые блоки.
Чтобы избавиться от этого недостатка (не говорю уж про саму функциональность), пришлось написать модуль, приведенный ниже. Он работает также как и диск: все данные делятся на сектора, которые наполняются данными по очереди. Каждый раз, когда объем очередного сектора заканчивается, выделяется новый сектор, который связывается с предыдущим в цепь. Когда и он кончается, то выделяется новый, и так далее. Алгоритм можно еще усовершенствовать, если выделять каждый следующий сектор все большего и большего размера.
Модуль позволят как писать, так и читать данные в формате, сходном с stdio, а также поддерживает функцию аналогичные fseek и ftell. Точное название остальных функций-аналогов из stdio я не сохранил, но их легко изменить, если будет необходимость.
tape.h
#pragma once
// Публичные
struct Tape* Tape_Open (void*, size_t); // Создает ленту, используя новый, либо заданный буфер
void Tape_Close (struct Tape*); // Закрывает ленту
void Tape_Clear (struct Tape*); // Очищает данные
void Tape_Printf (struct Tape*, const char*, ...); // Записывает форматированную подстроку без нуля
void Tape_PutLine (struct Tape*, const char*); // Записывает подстроку без нуля
void Tape_PutString (struct Tape*, const char*); // Записывает строку с нулем на конце
void Tape_PutStringW (struct Tape*, const wchar_t*); // Записывает строку с нулем на конце
void Tape_Putq (struct Tape*, __int64); // Записывает целое 64b
void Tape_Putd (struct Tape*, long); // Записывает целое 32b
void Tape_Putw (struct Tape*, int); // Записывает целое 16b
void Tape_Putb (struct Tape*, int); // Записывает байт
const char* Tape_GetLine (struct Tape*); // Читает во временный буфер подстроку с EOF/EOL на конце
const char* Tape_GetString (struct Tape*); // Читает во временный буфер
// строку с EOF на конце
const wchar_t* Tape_GetStringW (struct Tape*); // Читает во временный буфер
// wchar_t строку с EOF на конце
__int64 Tape_Getq (struct Tape*); // Читает целое 64b
long Tape_Getd (struct Tape*); // Читает целое 32b
int Tape_Getw (struct Tape*); // Читает целое 16b
int Tape_Getb (struct Tape*); // Читает байт
size_t Tape_Read (struct Tape*, void*, size_t); // Читает заданное кол-во байт в бефер
size_t Tape_Write (struct Tape*, const void*, size_t); // Сохраняет заданный буфер
boolean Tape_Eof (struct Tape*); // Проверяет, достигнут ли конец файла
long Tape_Tell (struct Tape*); // Возвращает текущую позицию
int Tape_Seek (struct Tape*, long offset, int origin); // Аналог fseek
void Tape_Align (struct Tape*, size_t); // Выравнивание позиции по
// заданному размеру с заполнением промежутка нулями
const void* xTape_Data (struct Tape*); // Возвращает временный/пользовательский
//буфер с записанными данными
size_t xTape_Size (struct Tape*); // Возвращает размер данных
// Служебные
boolean Tape_Pick (struct Tape*); // Подгружает/выделяет байт для записи
boolean Tape_Fetch (struct Tape*); // Подгружает байт для чтения
void Tape_UpdateTotalInfo (struct Tape*); // При записи, обновляет размер в зависимости
//от последней позиции записи
struct Sector* Tape_MoveLeft (struct Tape*, struct Sector*, long offset); // Ищет сектор
// слева, содержащий смещение
struct Sector* Tape_MoveRight (struct Tape*, struct Sector*, long offset);
tape.c
/*
=============
COPYRIGHT: Sapunov Vladimir
DESCRIPTION: Лента представялет из себя последовательный буфер
для чтения/записи как в файл, оптимизированный на быструю запись.
REMARKS: Данные ленты хранятся в виде связанного списка секторов, что обеспечивает
быструю запись без необходимости постоянно передислоцировать память.
Недостатком является относительно медленный доступ по индексу.
=============
*/
#include "main.h"
#pragma hdrstop
#include "memtape.h"
#define SECTOR_SIZE 1024
struct Tape
{
struct Sector* first; // Первый сектор
struct Sector* last; // Последний сектор
struct Sector* csect; // Текущий сектор
BYTE *curp; // Позиция в текущем секторе
BYTE *wend, *rend; // Предел позиции записи/чтения в текущем секторе
size_t size; // Общий размер
boolean dynamic; // Выделен ли буфер из динамической памяти
};
struct Sector
{
struct Sector *prev, *next; // Связанный список
size_t offset; // Смещение сектора от начала файла
size_t capacity; // Выделенный размер буфера
char data []; // Данные сектора
};
/*
=============
Tape_Open
Создает ленту, используя заданный буфер для заголовка и начальной секции.
Если буфер не задан, то использует динамическую память.
Размер буфера может быть 0, тогда используется стандартный.
=============
*/
struct Tape* Tape_Open (void*buffer, size_t size)
{
struct Tape* dd;
struct Sector* sector;
boolean dynamic;
size_t capacity;
assert (sizeof(struct Tape) + sizeof(struct Sector) < SECTOR_SIZE);
// Проверяем, задан ли буфер и влезет ли в него заголовки и некоторое кол-во байт (16)
if (!buffer || size < sizeof(struct Tape) + sizeof(struct Sector) + 16)
{
dd = mem_alloc (SECTOR_SIZE); // Буфер не задан, либо слишком мал, поэтому выделяем свой
sector = (void*) (dd + 1);
dynamic = true;
capacity = SECTOR_SIZE - (sizeof(struct Tape) + sizeof(struct Sector));
} else {
dd = buffer; // Используем предложенный буфер, так как он достаточно большой
sector = (void*) (dd + 1);
dynamic = false;
capacity = size - (sizeof(struct Tape) + sizeof(struct Sector));
}
// Инициализируем первоначальный сектор.
// Остальный функции требуют как минимум один сеткор в списке.
sector->capacity = capacity;
sector->offset = 0;
sector->prev = NULL;
sector->next = NULL;
// Инициализируем ленту
dd->dynamic = dynamic;
dd->size = 0;
dd->first = sector;
dd->last = sector;
dd->csect = sector;
dd->curp = sector->data;
dd->rend = sector->data;
dd->wend = sector->data + sector->capacity;
return dd;
}
/*
=============
Tape_Close
Закрывает текущую ленту, восстанавливая предыдущую.
=============
*/
void Tape_Close (struct Tape*dd)
{
Tape_Clear (dd);
if (dd->dynamic) mem_free (dd);
}
/*
=============
Tape_Clear
Очищает буферы ленты.
=============
*/
void Tape_Clear (struct Tape*dd)
{
struct Sector *scan, *next;
// Удаляем все сектора, кроме первого
for (scan=dd->first->next; scan; scan=next) {
next = scan->next;
mem_free (scan);
}
// Указываем на первый сектор
dd->csect = dd->last = dd->first;
dd->curp = dd->csect->data;
dd->wend = dd->csect->data + dd->csect->capacity;
dd->rend = dd->csect->data;
dd->size = 0;
}
/*
=============
xTape_Data
Возвращает временный/пользовательский буфер с записанными в ленту данными.
Сама лента НЕ очищается.
=============
*/
const void* xTape_Data (struct Tape*dd)
{
char* buff;
struct Sector* scan;
Tape_UpdateTotalInfo (dd);
// Проверяем оптимальный случай, когда все данные помещаются в первый сектор,
// который размещается в фиксированной памяти, переданной через Tape_Open.
if (!dd->dynamic && dd->size < dd->first->capacity)
return dd->first->data;
// Иначе копируем все во временную память
buff = temp_alloc (dd->size);
for (scan=dd->first; scan; scan=scan->next)
{
size_t chunk = scan->capacity;
if (scan->offset + chunk > dd->size)
chunk = dd->size - scan->offset;
memcpy (buff + scan->offset, scan->data, chunk);
}
return buff;
}
/*
=============
xTape_Size
Возвращает размер записанных данных.
=============
*/
size_t xTape_Size (struct Tape*dd)
{
Tape_UpdateTotalInfo (dd);
return dd->size;
}
/*
=============
Tape_Eof
Проверяет, не достигнут ли предел буфера при чтении.
Если дальнешее чтение не возможно, возвращает true.
=============
*/
boolean Tape_Eof (struct Tape*dd)
{
if (dd->curp == dd->rend && dd->csect == dd->last)
return true;
return false;
}
/*
=============
Tape_Align
Выравнивает позицию по заданному размеру.
Промежуток от предыдущей позиции заполняется нулями.
=============
*/
void Tape_Align (struct Tape*dd, size_t align)
{
int pos = Tape_Tell (dd);
int padding = (pos + align - 1) / align * align - pos;
while (--padding >= 0)
Tape_Putb (dd, 0);
}
/*
=============
Tape_Fetch
Корректирует позицию так, чтобы указывала на действительный буфер.
Должна вызываться после смены позиции, которая могла перевести
позицию на конец текущего сектора.
Возвращает true, если для чтения доступен хотя бы один байт.
=============
*/
boolean Tape_Fetch (struct Tape*dd)
{
if (dd->curp == dd->rend)
{
struct Sector* sect;
if (Tape_Eof(dd)) return false;
Tape_UpdateTotalInfo (dd);
sect = dd->csect->next;
dd->csect = sect;
dd->curp = sect->data;
dd->wend = sect->data + sect->capacity;
dd->rend = sect->data + min (dd->size - sect->offset, sect->capacity);
}
return true;
}
/*
=============
Tape_Pick
Выделяет место под запись минимум одного знака в текущей позици.
Если текущая позиция указывает на EOF, то:
- добавляет новый сектор в конец ленты,
- переводит текущую позицию на начало этого сектора.
Возвращает true, если для записи доступен хотя бы один байт.
=============
*/
boolean Tape_Pick (struct Tape*dd)
{
if (dd->curp == dd->wend)
{
struct Sector* sector;
Tape_UpdateTotalInfo (dd);
if (dd->csect == dd->last)
{
// Создаем новый сектор
sector = mem_alloc (sizeof(struct Sector) + SECTOR_SIZE);
sector->capacity = SECTOR_SIZE;
sector->offset = dd->size;
sector->prev = dd->last;
sector->next = NULL;
// Добавляем сектор к ленте
dd->last->next = sector;
dd->last = sector;
dd->csect = sector;
dd->curp = sector->data;
dd->rend = sector->data;
dd->wend = sector->data + sector->capacity;
} else {
// Переходим на следующий сектор
sector = dd->csect->next;
dd->csect = sector;
dd->curp = sector->data;
dd->wend = sector->data + sector->capacity;
if (sector == dd->last) {
dd->rend = sector->data + (dd->size - sector->offset);
} else {
dd->rend = sector->data + sector->capacity;
}
}
}
return true;
}
/*
=============
Tape_Tell
Возвращает текущую позицию в ленте от начала.
=============
*/
long Tape_Tell (struct Tape*dd)
{
return dd->csect->offset + (dd->curp - dd->csect->data);
}
/*
=============
Tape_Seek
Перемещает текущую позицию.
Параметры функции аналогичны и полностью совместимы с fseek.
Перемещение оптимизировано: всегда выбирается самый короткий путь
к нужному сектору из четырех возможных:
1. с начала вверх,
2. с середины в начало,
3. с середины в конец,
4. с конца вниз.
=============
*/
int Tape_Seek (struct Tape*dd, long offset, int origin)
{
struct Sector* sector;
Tape_UpdateTotalInfo (dd);
switch (origin)
{
case SEEK_CUR: offset = Tape_Tell (dd) + offset; break;
case SEEK_END: offset = dd->size - offset; break;
case SEEK_SET: break;
}
// Удерживаем в пределах ленты
if (offset < 0) offset = 0;
if (offset > dd->size) offset = dd->size;
// Выбираем путь поиска сектора - один из четырех возможных
if (offset < dd->csect->offset) {
if (dd->csect->offset - offset < offset) {
sector = Tape_MoveLeft (dd, dd->csect, offset); // От курсора вниз
} else {
sector = Tape_MoveRight (dd, dd->first, offset); // От начала к курсору
}
} else { // Выше курсора
if (dd->size - offset < offset - dd->csect->offset) {
sector = Tape_MoveLeft (dd, dd->last, offset); // От конца к курсору
} else {
sector = Tape_MoveRight (dd, dd->csect, offset); // От курсора к концу
}
}
// Обновляем ограничители и текущую позицию
dd->csect = sector;
dd->curp = sector->data + (offset - sector->offset);
dd->rend = sector->data + min(sector->capacity, dd->size - sector->offset);
dd->wend = sector->data + sector->capacity;
return offset;
}
// Ищем нужный сектор слева
struct Sector* Tape_MoveLeft (struct Tape*dd, struct Sector*s, long offset)
{
while (s) {
if (offset >= s->offset) return s;
s = s->prev;
}
return dd->first;
}
// Ищем нужный сектор справа
struct Sector* Tape_MoveRight (struct Tape*dd, struct Sector*s, long offset)
{
while (s) {
if (offset < s->offset + s->capacity) return s;
s = s->next;
}
return dd->last;
}
/*
=============
Tape_UpdateTotalInfo
Должна вызываться перед сменой указателя на текущий сектор,
или перед запросом какой-то total-информации.
=============
*/
void Tape_UpdateTotalInfo (struct Tape*dd)
{
if (dd->csect == dd->last) {
dd->size = dd->last->offset + (dd->rend - dd->last->data);
}
}
/*
=============
Tape_Putb
Сохраняет знак в ленту.
По мере надобности расширяет буфер новыми секторами.
=============
*/
void Tape_Putb (struct Tape*dd, int c)
{
if (dd->curp < dd->rend) {
*dd->curp++ = c;
} else if (dd->curp < dd->wend) {
*dd->curp++ = c;
dd->rend = dd->curp;
} else {
Tape_Write (dd, &c, sizeof(char));
}
}
void Tape_Putw (struct Tape*dd, int val)
{
if (dd->curp + sizeof(short) <= dd->rend) {
*((short*)dd->curp)++ = val;
} else if (dd->curp + sizeof(short) <= dd->wend) {
*((short*)dd->curp)++ = val;
dd->rend = dd->curp;
} else {
Tape_Write (dd, &val, sizeof(short));
}
}
void Tape_Putd (struct Tape*dd, long val)
{
if (dd->curp + sizeof(long) <= dd->rend) {
*((long*)dd->curp)++ = val;
} else if (dd->curp + sizeof(long) <= dd->wend) {
*((long*)dd->curp)++ = val;
dd->rend = dd->curp;
} else {
Tape_Write (dd, &val, sizeof(long));
}
}
void Tape_Putq (struct Tape*dd, __int64 val)
{
if (dd->curp + sizeof(__int64) <= dd->rend) {
*((__int64*)dd->curp)++ = val;
} else if (dd->curp + sizeof(__int64) <= dd->wend) {
*((__int64*)dd->curp)++ = val;
dd->rend = dd->curp;
} else {
Tape_Write (dd, &val, sizeof(__int64));
}
}
/*
=============
Tape_Getb
Читает знак из ленты.
Если уже достигнут предел ленты, возвращает -1.
=============
*/
int Tape_Getb (struct Tape*dd)
{
if (dd->curp + sizeof(char) <= dd->rend) {
return *dd->curp++;
} else {
char c;
Tape_Read (dd, &c, sizeof(char));
return c;
}
}
int Tape_Getw (struct Tape*dd)
{
if (dd->curp + sizeof(short) <= dd->rend) {
return *((short*)dd->curp)++;
} else {
short val;
Tape_Read (dd, &val, sizeof(short));
return val;
}
}
long Tape_Getd (struct Tape*dd)
{
if (dd->curp + sizeof(long) <= dd->rend) {
return *((long*)dd->curp)++;
} else {
long val;
Tape_Read (dd, &val, sizeof(long));
return val;
}
}
__int64 Tape_Getq (struct Tape*dd)
{
if (dd->curp + sizeof(__int64) <= dd->rend) {
return *((__int64*)dd->curp)++;
} else {
__int64 val;
Tape_Read (dd, &val, sizeof(__int64));
return val;
}
}
/*
=============
Tape_GetLine
Читает во временный буфер подстроку с EOF/EOL на конце.
=============
*/
const char* Tape_GetLine (struct Tape*dd)
{
char* buff;
int count = 0;
// Находим длину подстроки
while (Tape_Fetch(dd)) {
if (*dd->curp == 0) break;
dd->curp++;
count++;
if (dd->curp[-1] == '\n') break;
}
// Выделяем буфер и читаем туда строку
buff = temp_alloc (count +1);
Tape_Seek (dd, -count, SEEK_CUR);
Tape_Read (dd, buff, count);
buff [count] = 0;
return buff;
}
/*
=============
Tape_GetString
Читает строку с нулем на конце.
Возвращает указатель на строку во временном буфере.
=============
*/
const char* Tape_GetString (struct Tape*dd)
{
char* buff;
int count = 0;
// Находим длину строки
while (Tape_Fetch(dd)) {
if (*dd->curp == 0) break;
dd->curp++;
count++;
}
// Выделяем буфер и читаем туда строку
buff = temp_alloc (count +1);
Tape_Seek (dd, -count, SEEK_CUR);
Tape_Read (dd, buff, count);
buff [count] = 0;
Tape_Getb (dd);
return buff;
}
const wchar_t* Tape_GetStringW (struct Tape*dd)
{
wchar_t* buff;
int count = 0;
int start = Tape_Tell (dd);
// Находим длину строки
while (Tape_Fetch(dd)) {
if (Tape_Getw(dd) == 0) break;
count ++;
}
// Выделяем буфер и читаем туда строку
buff = temp_alloc (count +sizeof(wchar_t));
Tape_Seek (dd, start, SEEK_SET);
Tape_Read (dd, buff, count * sizeof(wchar_t));
buff [count] = 0;
Tape_Getw (dd);
return buff;
}
/*
=============
Tape_Printf
Записывает форматированную подстроку без нуля.
=============
*/
void Tape_Printf (struct Tape*dd, const char*fmt, ...)
{
const char* str;
va_list a;
va_start (a, fmt);
str = temp_vsprintfA (fmt, a);
Tape_Write (dd, str, strlen(str));
va_end (a);
}
/*
=============
Записывает подстроку без нуля.
Используется для записи части текста, без терминатора.
=============
*/
void Tape_PutLine (struct Tape*dd, const char*str)
{
Tape_Write (dd, str, strlen(str));
}
/*
=============
Tape_PutString
Пишет строку с нулем на конце.
=============
*/
void Tape_PutString (struct Tape*dd, const char*str)
{
Tape_Write (dd, str, strlen(str) + 1);
}
void Tape_PutStringW (struct Tape*dd, const wchar_t*str)
{
Tape_Write (dd, str, (wcslen(str) + 1) * sizeof(wchar_t));
}
/*
=============
Tape_Write
Пишет заданное кол-во байтов.
Текущая позиция инкрементируется.
Если текущая позциия указывала на EOF, то фактический размер файла также увеличивается.
=============
*/
size_t Tape_Write (struct Tape*dd, const void*buffer, size_t size)
{
const char* src = buffer;
size_t remains = size;
while (remains && Tape_Pick(dd)) {
size_t chunk = dd->wend - dd->curp;
if (chunk > remains) chunk = remains;
memcpy (dd->curp, src, chunk);
dd->curp += chunk;
src += chunk;
remains -= chunk;
// Обновляем предел чтения в секторе
if (dd->rend < dd->curp)
dd->rend = dd->curp;
}
return size - remains;
}
/*
=============
Tape_Read
Читает заданное кол-во байтов с текущей позиции.
Текущая позиция инкрементируется.
=============
*/
size_t Tape_Read (struct Tape*dd, void *buffer, size_t size)
{
char* dest = buffer;
size_t remains = size;
while (remains && Tape_Fetch(dd)) {
size_t chunk = dd->rend - dd->curp;
if (chunk > remains) chunk = remains;
memcpy (dest, dd->curp, chunk);
dd->curp += chunk;
dest += chunk;
remains -= chunk;
}
return size - remains;
}
Ваше имя:
| Articles & posts |
|---|
| Как работает временная память в мозгу | Резюме на статей о работе гиппокампа мозга, ответственного за хранение временной памяти.
|
|---|
| Потоковая память | Иногда нужно выполнить множество операций конкатенации строки, и сделать это максимально быстро. В статье описывается алгоритм и даются исходники одного из методов решения этой задачи.
|
|---|
| Временная память - удобная альтернатива | Многие, наверное, сталкивались с "ограничением" языка Си на работу со строками, когда надо возвратить строку или другие объемные данные, созданные внутри функции. Сейчас вы поймете, почему я взял это слово в кавычки :)
|
|---|
| Функция создания точки останова на чтение/запись | Эта функция будет полезна при отладке, когда нужно определить, где портятся заданные данные.
|
|---|
| Кремль со спутника | Вид со спутника на несколько известных мест. Карты maps.google.com.
|
|---|
| Представление цвета | Принцип разложения цветов на составляющие для удобного их сравнения. Существующие два олсновных формата представления цвета.
|
|---|
| Сравнение цветов | Соображения по поводу возможного алгоритма сравнения цветов.
|
|---|
| Детектор движения | Общие соображения насчет алгоритма обнаружения движения.
|
|---|
| Сборщик мусора | Альтернатива стандартному алгоритму сборщика мусора, используемому в java.
|
|---|
| 
Main Page
Как работает временная память в мозгу