Самый быстрый алгоритм для разбиения строки на C?

Question

Я пишу парсер ввода CLI, и я хочу знать, что является самым быстрым алгоритмом для разбиения строки на токены.

Правила:

• Пространство означает конец маркера.
• Любой символ может быть экранирован с помощью обратного слэша, что означает, что я воспринимаю его как без какого-либо специального значения. (В настоящее время используется только для выхода в пространство)

Вот код, я в настоящее время с помощью:

#define POINTER_ARRAY_STEP 10 
#define STRING_STEP 255 

char **parse_line(char *line) 
{ 
    char **array; 
    size_t array_len; 
    size_t array_index; 
    size_t token_len; 
    size_t token_index; 

    array_len = POINTER_ARRAY_STEP; 
    array = malloc((array_len + 1) * sizeof(char*)); /* +1 to leave space for NULL */ 
    array_index = 0; 

    token_len = STRING_STEP; 
    array[array_index] = malloc(token_len + 1); 
    token_index = 0; 

    for (; *line; ++line) { 
     if (array_index == array_len) { 
      array_len += POINTER_ARRAY_STEP; 
      array = realloc(array, (array_len + 1) * sizeof(char*)); 
     } 
     if (token_index == token_len) { 
      token_len += STRING_STEP; 
      array[array_index] = realloc(array[array_index], token_len + 1); 
     } 
     if (*line == '\\') { 
      array[array_index][token_index++] = *++line; 
      continue; 
     } 
     if (*line == ' ') { 
      array[array_index][token_index] = 0; 
      array[++array_index] = malloc(token_len + 1); 
      token_index = 0; 
      continue; 
     } 
     array[array_index][token_index++] = *line; 
    } 
    /* Null terminate the last array element */ 
    array[array_index][token_index] = 0; 

    /* Null terminate the array */ 
    array[array_index + 1] = NULL; 
    return array; 
} 

Answer 1

Ваш метод является небезопасным и неэффективным: не проверять ошибки распределения памяти, и вы называете realloc() слишком много раз.

Вот другой подход:

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

Память позже может быть освобождена путем вызова free() как в массиве указателей, так и в его первом элементе.

Вот код:

#include <stdlib.h> 

char **parse_line(const char *line) { 
    size_t len, i, j, k, items = 1, escapes = 0; 
    char **array; 
    char *buf; 

    for (len = 0; line[len]; len++) { 
     if (line[len] == '\\') { 
      escapes++; 
      if (line[++len] == '\0') 
       break; 
     } else 
     if (line[len] == ' ') { 
      items++; 
     } 
    } 
    if (len == escapes) { 
     /* special case empty line */ 
     array = malloc(sizeof(*array)); 
     if (array != NULL) { 
      array[0] = NULL; 
     } 
     return array; 
    } 
    array = malloc((items + 1) * sizeof(*array)); 
    buf = malloc(len + 1 - escapes); 

    if (array == NULL || buf == NULL) { 
     free(array); 
     free(buf); 
     return NULL; 
    } 
    items[0] = buf; 
    k = 1; 
    for (i = j = 0; i < len; i++) { 
     if (line[i] == '\\') { 
      if (++i == len) 
       break; 
      buf[j++] = line[i]; 
     } else 
     if (line[i] == ' ') { 
      buf[j++] = '\0'; 
      items[k++] = buf + j; 
     } else { 
      buf[j++] = line[i]; 
     } 
    } 
    buf[j] = '\0'; 
    items[k] = NULL; 
    return items; 
} 

Answer 2

Отдается быстрый алгоритм

сделать только два прохода. Один раз, чтобы найти количество токенов и длину необходимого буфера.

2-й раз, чтобы разбить дублируемую линию.

Массив токенов указывает на одну выделенную память, поэтому, когда это делается, tokens[0] должен быть свободен, а также tokens.

Как OP запросил более быстрый алгоритм , ниже $ псевдокод $/code.

char **parse_line(const char *line) { 
    size_t token_count = 1; 
    const char *p = line; 
    $Let `p` each element in `line`$ 
    $if `*p` is a separator, increment `token_count` 
    $else `*p` is an escape not followed by a \0$ 
     $advance `p`$ 
    } 
    } 

    $ `p`, at the end of the string, so allocate enough for a $ 
    $ duplicate +1 based on the difference of `p` and the start. $ 
    $ Check allocation success         $ 
    $ Copy into `char *line_buffer`        $ 

    // The token count is known, get enough pointers + 1 and check 
    char **tokens = malloc(sizeof *tokens * (token_count + 1)); 

    // More complex code could perform only 1 allocation for `tokens` and `line_buffer` 

    $ Let `q` be first element in line_buffer 
    $ Let `d` be the same (destination pointer) 
    $ set begin_token flag $ 
    size_t token_index = 0; 
    for (;;) { 
    $ if begin_token flag set $ { 
     $ clear begin_token $ 
     tokens[token_index] = q; 
     d = q; 
    } 
    $ if `*q` separator (space or \0) $ { 
     *d = '\0'; 
     token_index++; 
     $ if *q at end of string $ break; 
     $ set begin_token flag $ 
    $else { 
     if `*q` is an escape not followed by a \0$ 
     $advance q$ 
     } 
     $copy *q to *d, advance both pointers. 
    } 
    } 
    $set last tokens[] to NULL$ 
    return tokens; 
}