Самый экономичный способ чтения и хранения списка строк в C

Вот умеренно эффективный формат, предполагающий, что вы заранее знаете длину всех строк:

|| total size |  string 1 | string 2 | ........ | string N | len(string N) | ... | len(string 2) | len(string 1) ||

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

Вы можете создать свой единственный буфер и хранить их последовательно, расширяя буфер по мере необходимости, используя realloc(). Но тогда вам понадобится второй массив для хранения строковых позиций и, возможно, realloc() его, поэтому я мог бы просто создать динамически распределяемый массив и malloc() каждую строку отдельно.

Найти количество и общую длину всех строк:

int num = 0;
int len = 0;
char* string = GetNextString(input);
while (string)
{
    num += 1;
    len += strlen(string);
    string = GetNextString(input);
}
Rewind(input);

Затем выделите следующие два буфера:

int*  indexes = malloc(num*sizeof(int));
char* strings = malloc((num+len)*sizeof(char));

Наконец заполните эти два буфера:

int index = 0;
for (int i=0; i<num; i++)
{
    indexes[i] = index;
    string = GetNextString(input);
    strcpy(strings+index,string);
    index += strlen(string)+1;
}

После этого вы можете просто использовать strings[indexes[i]] для доступа к i-й строке.

Наиболее эффективным и экономичным способом является двухпроходное решение. В первом проходе вы вычисляете общий размер для всех строк, затем вы выделяете общий блок памяти. Во втором проходе вы читаете все строки, используя большие буферы.

Вы можете создать массив указателей для строк и вычислить разницу между указателями, чтобы получить размеры строк. Таким образом, вы сохраняете нулевой байт как конечный маркер.

Вот полный пример:

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

struct StringMap
{
    char *data;
    char **ptr;
    long cPos;
};


void initStringMap(StringMap *stringMap, long numberOfStrings, long totalCharacters)
{
    stringMap->data = (char*)malloc(sizeof(char)*(totalCharacters+1));
    stringMap->ptr = (char**)malloc(sizeof(char*)*(numberOfStrings+2));
    memset(stringMap->ptr, 0, sizeof(char*)*(numberOfStrings+1));
    stringMap->ptr[0] = stringMap->data;
    stringMap->ptr[1] = stringMap->data;
    stringMap->cPos = 0;
}


void extendString(StringMap *stringMap, char *str, size_t size)
{
    memcpy(stringMap->ptr[stringMap->cPos+1], str, size);
    stringMap->ptr[stringMap->cPos+1] += size;
}


void endString(StringMap *stringMap)
{
    stringMap->cPos++;
    stringMap->ptr[stringMap->cPos+1] = stringMap->ptr[stringMap->cPos];
}


long numberOfStringsInStringMap(StringMap *stringMap)
{
    return stringMap->cPos;
}


size_t stringSizeInStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index+1] - stringMap->ptr[index];
}


char* stringinStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index];
}


void freeStringMap(StringMap *stringMap)
{
    free(stringMap->data);
    free(stringMap->ptr);
}


int main()
{
    // The interesting values
    long numberOfStrings = 0;
    long totalCharacters = 0;

    // Scan the input for required information
    FILE *fd = fopen("/path/to/large/textfile.txt", "r");
    int bufferSize = 4096;
    char *readBuffer = (char*)malloc(sizeof(char)*bufferSize);
    int currentStringLength = 0;
    ssize_t readBytes;
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c != '\n') {
                ++currentStringLength;
            } else {
                ++numberOfStrings;
                totalCharacters += currentStringLength;
                currentStringLength = 0;
            }
        }
    }

    // Display the found results
    printf("Found %ld strings with total of %ld bytes\n", numberOfStrings, totalCharacters);

    // Allocate the memory for the resource
    StringMap stringMap;
    initStringMap(&stringMap, numberOfStrings, totalCharacters);

    // read all strings
    rewind(fd);
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        char *stringStart = readBuffer;
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c == '\n') {
                extendString(&stringMap, stringStart, &readBuffer[i]-stringStart);
                endString(&stringMap);
                stringStart = &readBuffer[i+1];
            }
        }
        if (stringStart < &readBuffer[readBytes]) {
            extendString(&stringMap, stringStart, &readBuffer[readBytes]-stringStart);
        }
    }
    endString(&stringMap);
    fclose(fd);

    // Ok read the list
    numberOfStrings = numberOfStringsInStringMap(&stringMap);
    printf("Number of strings in map: %ld\n", numberOfStrings);
    for (long i = 0; i < numberOfStrings; ++i) {
        size_t stringSize = stringSizeInStringMap(&stringMap, i);
        char *buffer = (char*)malloc(stringSize+1);
        memcpy(buffer, stringinStringMap(&stringMap, i), stringSize);
        buffer[stringSize-1] = '\0';
        printf("string %05ld size=%8ld : %s\n", i, stringSize, buffer);
        free(buffer);
    }

    // free the resource
    freeStringMap(&stringMap);
}

В этом примере читается очень большой текстовый файл, разбивается на строки и создается массив со строкой в ​​каждой строке. Требуется только два вызова malloc. Один для массива указателей и один для блока жала.

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

Первый sizeof(long) bytes хранит количество строк, n. Следующие n long сохраняют смещения в каждой строке от начала string buffer, которое начинается с позиции (n+1)*sizeof(long). Вам не нужно сохранять конечный нуль для каждой строки, но если вы это сделаете, вы можете получить доступ к каждой строке с помощью &str_buffer[offset[i]]. Если вы не сохраните завершающий «\ 0», вам придется скопировать во временный буфер и добавить его самостоятельно.