c - 为未知长度的 token 分配足够的内存

Question

出于各种原因，我不会在这里讨论，我正在用 C 编写一个简单的分词器。下面是我破解的一个示例，它在从输入流中读取字符时根据需要以预定的增量调整分词缓冲区的大小。它最终会达到最大代币的大小，显然可以容纳较小的代币。这是一种可以接受的方法吗？如果不是，确定为每个 token 分配的正确内存量的最佳方法是什么？

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define BUFF_CHUNK_SIZE 4

int main() {
    int c, i, n;
    char *buffer;

    i = 0;
    n = BUFF_CHUNK_SIZE;
    buffer = (char *)calloc(n, sizeof(char));

    while ((c = getchar()) != EOF) {
        if (isalnum(c)) {
            buffer[i] = (char)c;
            i++;
            if (i == n) {
                n += BUFF_CHUNK_SIZE;
                buffer = (char *)realloc(buffer, n * sizeof(char));
            }
        }
        else {
            if (i == 0) {
                continue;
            }
            i = 0;
            printf("%s\n", buffer);
            memset(buffer, 0, sizeof(char) * n);
        }
    }
    return 0;
}

Answer 1

这几乎是正确的方法 - 有两个调整。

首先，与其添加一个常量BUFF_CHUNK_SIZE，通常最好将它乘以一个固定的数量。这意味着您在长度为 N 的长字符串上的重新分配数量与 log N 而不是 N 成正比 - 这意味着在 realloc()< 中花费的时间 与 N log N 成正比，而不是 N2。常数是什么并不重要 - 1.5 可能是一个不错的选择 (n += n/2;)。

其次，在较长的程序中，您应该真正检查 realloc() 是否失败。