为未知长度的令牌分配足够的内存

Question

由于各种原因,我将不在这里讨论,我在C中编写一个简单的标记化器.下面是一个示例,我在从输入流中读取字符时根据需要以预定的增量调整标记缓冲区的大小.它最终将达到最大令牌的大小,这显然可以容纳更小的令牌.这是一种可接受的方法吗？如果没有,确定为每个令牌分配的正确内存量的最佳方法是什么？

#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的长串上的realloc数量与log N而不是N- 意味着所花费的时间realloc()成比例N log N而不是N2.常数是什么并不重要 - 1.5可能是一个不错的选择(n += n / 2;).

其次,在较长的程序中,您应该检查是否realloc()失败.