Я пытаюсь разбить строку char32_t
на токены, разделенные разделителем. Я не использую какую-либо функцию strtok или другую стандартную библиотечную функцию, потому что указано, что входная строка и разделитель будут многобайтовой строкой Unicode.
Вот функция, которую я написал:
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <uchar.h>
#include <wchar.h>
char32_t **sp(char32_t *str, char32_t delim, int *len) {
*len = 1;
char32_t *s = str;
while (*s != U'\0') {
if (*s == delim) {
(*len)++;
}
s++;
}
char32_t **tokens = (char32_t **)malloc((*len) * sizeof(char32_t *));
if (tokens == NULL) {
exit(111);
}
char32_t * p = str;
int i = 0;
while (*p != U'\0') {
int tok_len = 0;
while (p[tok_len] != U'\0' && p[tok_len] != delim) {
tok_len++;
}
tokens[i] = (char32_t *)malloc(sizeof(char32_t) * (tok_len + 1));
if (tokens[i] == NULL) {
exit(112);
}
memcpy(tokens[i], p, tok_len * sizeof(char32_t));
tokens[i][tok_len] = U'\0';
p += tok_len + 1;
i++;
}
return tokens;
}
А вот и код драйвера
int main() {
char32_t *str = U"Hello,World,mango,hey,";
char32_t delim = U',';
int len = 0;
char32_t ** tokens = sp(str, delim, &len);
wprintf(L"len -> %d\n", len);
for (int i = 0; i < len; i++) {
if (tokens[i]) {
wprintf(L"[%d] %ls\n" , i , tokens[i]);
}
free(tokens[i]);
}
free(tokens);
}
Вот результат:
len -> 5
[0] Hello
[1] World
[2] mango
[3] hey
[4] (null)
Но когда я проверяю программу с помощью valgrind, она показывает несколько ошибок памяти.
valgrind -s --leak-check=full --track-origins=yes ./x3
==7703== Memcheck, a memory error detector
==7703== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==7703== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info
==7703== Command: ./x3
==7703==
tok -> 5
tok -> 5
tok -> 5
tok -> 3
len -> 5
[0] Hello
[1] World
[2] mango
[3] hey
==7703== Conditional jump or move depends on uninitialised value(s)
==7703== at 0x48FDAF8: __wprintf_buffer (vfprintf-process-arg.c:396)
==7703== by 0x48FF421: __vfwprintf_internal (vfprintf-internal.c:1459)
==7703== by 0x490CFAE: wprintf (wprintf.c:32)
==7703== by 0x1093C9: main (main.c:51)
==7703== Uninitialised value was created by a heap allocation
==7703== at 0x4841888: malloc (vg_replace_malloc.c:393)
==7703== by 0x1091FC: sp (main.c:17)
==7703== by 0x109384: main (main.c:47)
==7703==
[4] (null)
==7703== Conditional jump or move depends on uninitialised value(s)
==7703== at 0x4844225: free (vg_replace_malloc.c:884)
==7703== by 0x1093DA: main (main.c:52)
==7703== Uninitialised value was created by a heap allocation
==7703== at 0x4841888: malloc (vg_replace_malloc.c:393)
==7703== by 0x1091FC: sp (main.c:17)
==7703== by 0x109384: main (main.c:47)
==7703==
==7703==
==7703== HEAP SUMMARY:
==7703== in use at exit: 0 bytes in 0 blocks
==7703== total heap usage: 7 allocs, 7 frees, 5,248 bytes allocated
==7703==
==7703== All heap blocks were freed -- no leaks are possible
==7703==
==7703== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
==7703==
==7703== 1 errors in context 1 of 2:
==7703== Conditional jump or move depends on uninitialised value(s)
==7703== at 0x4844225: free (vg_replace_malloc.c:884)
==7703== by 0x1093DA: main (main.c:52)
==7703== Uninitialised value was created by a heap allocation
==7703== at 0x4841888: malloc (vg_replace_malloc.c:393)
==7703== by 0x1091FC: sp (main.c:17)
==7703== by 0x109384: main (main.c:47)
==7703==
==7703==
==7703== 1 errors in context 2 of 2:
==7703== Conditional jump or move depends on uninitialised value(s)
==7703== at 0x48FDAF8: __wprintf_buffer (vfprintf-process-arg.c:396)
==7703== by 0x48FF421: __vfwprintf_internal (vfprintf-internal.c:1459)
==7703== by 0x490CFAE: wprintf (wprintf.c:32)
==7703== by 0x1093C9: main (main.c:51)
==7703== Uninitialised value was created by a heap allocation
==7703== at 0x4841888: malloc (vg_replace_malloc.c:393)
==7703== by 0x1091FC: sp (main.c:17)
==7703== by 0x109384: main (main.c:47)
==7703==
==7703== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
Я не могу понять, в чем проблема. любая помощь будет оценена
Я также пробовал со строками Unicode, та же ошибка возникает.
valgrind
выдает эти ошибки, потому что ваша программа обращается к неинициализированной памяти в последней итерации этого for
цикла в main()
функции (т. е. при доступе к tokens[4]
, когда значение len
равно 5
):
for (int i = 0; i < len; i++) {
if (tokens[i]) {
wprintf(L"[%d] %ls\n" , i , tokens[i]);
}
free(tokens[i]);
}
malloc
функция выделяет память и оставляет ее неинициализированной. Здесь, в функции sp()
, когда ваша программа выделяет память, она не инициализируется:
char32_t **tokens = (char32_t **)malloc((*len) * sizeof(char32_t *));
Цикл while
функции sp()
выделяет и копирует некоторое значение в выделенную память для всех членов массива tokens
, кроме последнего члена, и оставляет его неинициализированным. В main()
ваша программа обращается к этому неинициализированному элементу и, следовательно, valgrind
сообщает об ошибке.
Чтобы решить проблему, в функции sp()
после выделения памяти в tokens
-
Либо сделайте последний указатель членом массива токенов NULL
:
// this is the bare minimum change required to fix the problem
tokens [*len - 1] = NULL;
Или сделайте все указатели NULL
for (int i = 0; i < *len; ++i) {
tokens[i] = NULL;
}
Или используйте calloc
, чтобы выделить память для tokens
, что обеспечит инициализацию всех выделенных указателей в NULL
:
char32_t **tokens = calloc((*len), sizeof(char32_t *));
С любым из вышеупомянутых решений valgrind
вывод:
# valgrind -s --leak-check=full --track-origins=yes ./a.out
==9761== Memcheck, a memory error detector
==9761== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9761== Using Valgrind-3.17.0 and LibVEX; rerun with -h for copyright info
==9761== Command: ./a.out
==9761==
len -> 5
[0] Hello
[1] World
[2] mango
[3] hey
==9761==
==9761== HEAP SUMMARY:
==9761== in use at exit: 0 bytes in 0 blocks
==9761== total heap usage: 7 allocs, 7 frees, 5,248 bytes allocated
==9761==
==9761== All heap blocks were freed -- no leaks are possible
==9761==
==9761== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Обнаружил еще одну проблему в вашем коде: когда входная строка не имеет символа-разделителя в качестве последнего символа, ваша программа в конечном итоге получает доступ к входной строке за пределами ее длины, что приводит к неопределенному поведению. Посмотрите на этот оператор цикла while
функции sp()
:
p += tok_len + 1;
Предположим, что входная строка - U"Hello,World,mango,hey"
[обратите внимание, что последний символ строки не является разделителем ,
]. Условие вложенного цикла while приведет к false
, когда p[tok_len]
равно U'\0'
при повторении входной строки, а приведенный ниже оператор p += tok_len + 1;
сделает указатель p
указывающим на память сразу за входной строкой. Условие внешнего цикла while
пытается разыменовать p
, что приведет к неопределенному поведению.
Замените этот оператор цикла while
функции sp()
:
p += tok_len + 1;
с этим
p += tok_len;
p += (*p != '\0') ? 1 : 0;
Сначала указатель p
будет указывать на один символ после конца текущих токенов во входной строке, и если этот символ не является нулевым завершающим символом, то к указателю 1
будет добавлено только p
, иначе нет.
Тело цикла while
может быть реализовано гораздо лучше, а также может быть оборудовано для обработки таких сценариев, как, например, забота о пробелах, когда слова во входной строке имеют пробелы между ними, входная строка только с разделителями и т. д. Я оставляю вам возможность улучшить реализацию и позаботиться о других сценариях.
Обновлено:
Это ваше требование - если последний символ входной строки является разделителем, то последний член массива tokens
должен указывать на пустую строку, а не на NULL
.
Вам не нужно обрабатывать это как особый сценарий после цикла, как вы показали в комментарии. Вы можете обработать это в теле цикла, который обрабатывает входную строку и извлекает из нее токены, например:
char32_t **sp(const char32_t *str, const char32_t delim, int *len) {
*len = 1;
for (int i = 0; str[i] != U'\0'; ++i) {
if (str[i] == delim) (*len)++;
}
char32_t **tokens = malloc ((*len) * sizeof (char32_t *));
if (tokens == NULL) {
exit(111);
}
int start = 0, end = 0, i = 0;
do {
if ((str[end] == delim) || (str[end] == U'\0')) {
tokens[i] = malloc (sizeof (char32_t) * (end - start + 1));
if (tokens[i] == NULL) {
exit(112);
}
memcpy (tokens[i], &str[start], sizeof (char32_t) * (end - start));
tokens[i][end - start] = U'\0';
start = end + 1; i++;
}
} while (str[end++] != U'\0');
return tokens;
}
Несколько тестовых случаев:
Строка ввода:
char32_t *str = U"Hello,World,mango,hey,";
Выход:
# ./a.out
len -> 5
[0] Hello
[1] World
[2] mango
[3] hey
[4]
Строка ввода:
char32_t *str = U"Hello,World,mango,hey";
Выход:
# ./a.out
len -> 4
[0] Hello
[1] World
[2] mango
[3] hey
Строка ввода:
char32_t *str = U",,, , u";
Выход:
# ./a.out
len -> 5
[0]
[1]
[2]
[3]
[4] u
Строка ввода:
char32_t *str = U" ";
Выход:
# ./a.out
len -> 1
[0]
Если вы хотите, чтобы последний токен был пустой строкой, а не NULL
, когда последний символ входной строки является разделителем, то в этом случае выделите пробел символа 1
и назначьте его ссылку на последний член указателя массива tokens
и напишите null завершающий символ к нему. Это потребует от вас изменения способа разбора входной строки (в основном, тела цикла while
).
Я добавил этот блок if (tokens[*len-1] == NULL) { tokens[i] = malloc(1 * sizeof(char32_t)); tokens[i][0] = U'\0'; }
перед возвратом токенов в функцию sp()
, похоже, это решает проблему
@polu_ Не нужно заботиться об этом как об особом сценарии. Я разместил код, который заботится об этом сценарии при обработке входной строки. Проверь это.
Это действительно решило проблему, однако я заметил, что если последний символ является разделителем, последний токен каким-то образом равен нулю, а не просто является пустой строкой, например, здесь
"a,,b,c,d,"
, последний токен этой строки равен нулю[0] a [1] [2] b [3] c [4] d [5] (null)