Выделение достаточного количества памяти для токенов неизвестной длины

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 обычно лучше умножить на фиксированную величину. Это означает, что количество ваших reallocs на длинной строке длиной N становится пропорциональным log N, а не N - это означает, что время, проведенное в realloc(), пропорционально N log N, а не N2. Неважно, что это за константа - 1.5 может быть хорошим выбором (n += n / 2;).

Во-вторых, в более длинной программе вы должны действительно проверить, не работает ли realloc().

Answer 2

realloc был прав, но вы должны использовать символ в качестве разделителя токенов?!

#define BUFF_CHUNK_SIZE 4
#define TOKSEP ";"

char *getOneToken(char *s,size_t n)
{
  int c;
  char *p=s;
  while( p-s < n-1 && !feof(stdin) && ((c=getchar())=='\n'?c=getchar():1) )
    if( isalnum(c) )
      *p++=c;
  *p=0;
  return s;
}

main() 
{
  char *buffer=calloc(1,1),
        tok[BUFF_CHUNK_SIZE+1];

  while( *getOneToken(tok,sizeof tok) )
  {
    buffer=realloc(buffer,strlen(buffer)+strlen(tok)+2);
    if( *buffer ) strcat(buffer,TOKSEP);
    strcat(buffer,tok);
  }

  puts(buffer);
  free(buffer);
  return 0;
}