c - C 中分割字符串最快的算法？

Question

我正在编写一个 CLI 输入解析器，我想知道将字符串拆分为标记的最快算法是什么。

规则:

• 空格表示 token 结束。
• 任何字符都可以用反斜杠转义，这意味着我按原样使用它，没有任何特殊含义。 (目前仅用于转义空格)

这是我当前使用的代码:

#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;
}