OldNileCrocodile Mar 19 2021 at 16:01

Разбиваем строку на подстроки по разделяющим символам своими руками

11 min

27K

Programming*Algorithms*C*

Tutorial

-2

Comments 24

IgorPie Mar 19 2021 at 17:12

Но, это же классика, вроде Кернигана и Ритчи?
Было бы уместно сравнить с ними.

UFO just landed and posted this here

Alex_ME Mar 19 2021 at 17:25

Существует функция strtok_r, которая не использует статическое состояние. Состояние передается через дополнительный аргумент. Уже лучше, чем простой strtok

void *calloc_mem(size_t nelems, size_t elem_size){
  void *buf = calloc(nelems, elem_size);
  if(buf != NULL){
    return buf;
  }
  exit(-1);
}

Не уверен, что exit(-1) из библиотекчной функции — это хорошая идея. Хотя упавшая аллокация довольно редкий случай. Linux по-умолчанию выделяет память лениво, можно выделить больше памяти, чем доступно. Если памяти не хватает, то это произойдет при обращении к очередной невыделенной странице.

OldNileCrocodile Mar 19 2021 at 18:29

Её же нельзя использовать со строковыми константами. (Получите SEGV)
А get_token (и get_token_escaped) можно и со строковыми константами вызывать.
Несомненно, strtok_r лучше strtok, однако, она также, как и разработанная get_token, сохраняет контекст в третьем аргументе saveptr (тот же next).
Плюсом get_token является однородность вызовов. Поясню, не надо переписывать передаваемые аргументы (в коде). Но надо помнить две вещи.
1) про двойной указатель — чтобы всё работало, необходима дополнительная переменная, сохраняющая копию адреса исходной строки.
2) Аргументами get_token являются три вещи:
2.1) Сканируемая строка.
2.2) Массив символов разделителей.
2.3) Указатель на следующую сканируемую строку.

Ну и, кроме того, функция get_token НЕ меняет свой ПЕРВЫЙ аргумент, а strtok_r — меняет (точнее, меняет поведение и зависимость от аргументов после первого вызова). В man-е написано (секция найденные ошибки). Также о дефектах здесь.

-1

Alex_ME Mar 19 2021 at 20:39

Я об этом и не спорю и не утвержал, что все перечисленные проблемы решаются в strtok_r.

DistortNeo Mar 19 2021 at 19:01

А причём тут Linux? Нигде ведь в статье не упоминалась операционная система.

Linux по-умолчанию выделяет память лениво, можно выделить больше памяти, чем доступно.

Даже в случае Linux malloc может вернуть NULL. Например, если попытаться выделить слишком много памяти. Ну или если оверкоммит отключен.

Если памяти не хватает, то это произойдет при обращении к очередной невыделенной странице.

Вот только приложение об этом уже не узнает.

Alex_ME Mar 19 2021 at 20:38

А причём тут Linux?

Прост про его поведение я точно знаю. А вот возможен ли оверкоммит в Windows или нет, я не знаю. Конечно, могут быть и более экзотические ОС. В любом случае, exit(-1) выглядит сомнительно.

Apoheliy Mar 19 2021 at 18:32

По-моему, одно из преимуществ чистого C в том, что строковые/разборные функции не выделяют память. Вообще не выделяют: хочешь чтобы что-то выдали в другую память — вот и дай эту память.
И тогда функции можно отлично применять в коде для запуска на устройствах, где нет (или тебе её не дадут) динамической памяти.
И в драйверах бы очень пригодилась бы функция, которая не лезет в память. Вот совсем не лезет. Потому что выделение памяти это LOCK, и если это вызывать из (например) обработчика прерывания, то всё просто умрёт.

Это всё к тому, что тема нужная, только может сделать её в «C»-стиле?

И ещё, простите за прямой вопрос… Вы точно это писали на чистом C?

Например, конструкция вида:
if(*src_p == '\0')
*next = NULL;
else
*next = src_p;

/* result token */
char *res = alloc_str(tok_size);
memcpy(res, lex_begin, tok_size);
return res;

т.е. когда объявление переменной res идёт не вначале функции, а после кода? Компилятор при этом начинает выводить… э-э-э… боль! (Например, на тот же gcc под Debian).

OldNileCrocodile Mar 19 2021 at 18:43

Я компилировал gcc под Ubuntu. Использовал флаги (-Werror -Wall -pedantic -std=c99).
Да, вы правы, в чистом C переменные в начале функции.
По поводу обработчика прерывания — в начале статьи такой задачи не стояло (не указано в требованиях). Моей задачей было получение новых экземпляров строк (память для них выделялась в куче) из исходной строки посредством разделения её на новые подстроки через символы разделители, плюс экранирование этих разделителей, когда они встречаются в самих лексемах (пример — строковый литерал «ab, cd, ek», где запятая и пробел являются частью одной лексемы (литерала)).

-1

Apoheliy Mar 19 2021 at 19:08

:), простите за некоторую назойливость, :)

У Вас нет требований, поиск по статье даже такого слова не находит.

Проблемы с памятью могут быть не только в драйверах. Например, программы на чипы пишутся (в том числе) на чистом C — там даже операционной системы нет и за памятью никто не следит. Однако можно на этапе компиляции такой программы сказать: вот есть строка длиной х байт и эту строку будем использовать для получения результатов. Т.е. вывод результата не в новую строку из кучи, а во внешнюю подготовленную строку. Как Вам такой вариант?

Alex_ME Mar 19 2021 at 20:45

Если не идет речь об отсутствии аллокаций и выделении памяти, то я ~разбалованынй более высокоуровневыми ЯП~ предпочел бы нечто такое удобства ради:

#python
slices = str.split(' ')

struct slices
{
    char* slices;
    size_t count;
};

int slices_split(const char* string, const char* delimiter, struct slices* slices );
void slices_free(struct slices* slices);

-1

Alex_ME Mar 19 2021 at 20:41

Разве объявление переменной в середине функций не разрешено, начиная с C99? Боль начинает выводить, только если с помощью goto объявление перепрыгнуть. И то, тогда просто не соберется.

OldNileCrocodile Mar 20 2021 at 10:19

Я компилировал с флагом -std=c99. Он разрешает такие вещи (компилятор gcc не ругался).
Также добавил дисклеймер насчёт этого в начале Введения.

Tzimie Mar 20 2021 at 11:58

На турбо С в начале 90х уже можно было писать

Apoheliy Mar 19 2021 at 18:50

Небольшое пожелание:
Если ваш код опирается на внешние / пользовательские функции выделения памяти, то очень желательно использовать также и внешние / пользовательские функции освобождения памяти. Тогда (например) программист сможет подцепись свой менеджер памяти.

Так сказать это будет хорошим стилем.

Kotofay Mar 19 2021 at 19:40

И 1984 году люди занимались разбором строки и продолжается это и до сих пор.

/*
HEADER:         CUGXXX;
TITLE:          Generalized, finite-state parser;
DATE:           3-20-86;
DESCRIPTION:    Powerful parser allowing extraction of single tokens from
                character strings.  User can specify delimiters/escape
                character.
KEYWORDS:       Generalized finite-state parser, Parser;
FILENAME:       PARSER.C;
WARNINGS:       None;
AUTHORS:        Lloyd Zusman;
COMPILER:       DeSmet C;
REFERENCES:     US-DISK 1308;
ENDREF
*/

#include <ctype.h>
#pragma hdrstop

/* states */

#define IN_WHITE 0
#define IN_TOKEN 1
#define IN_QUOTE 2
#define IN_OZONE 3

static int _p_state;	   /* current state	 */
static unsigned _p_flag;  /* option flag	 */
static char _p_curquote;  /* current quote char */
static int _p_tokpos;	   /* current token pos  */

/* routine to find character in string ... used only by "parser" */

static int sindex(char ch, char *string){
  char *cp;
  for(cp=string;*cp;++cp)
    if(ch==*cp)
      return (int)(cp-string);	/* return postion of character */
  return -1;			/* eol ... no match found */
}

/* routine to store a character in a string ... used only by "parser" */

static void chstore(char *string, int max, int ch){
  char c;
  if((_p_tokpos >= 0)&&(_p_tokpos < max-1))
  {
    if(_p_state==IN_QUOTE)
      c=ch;
    else
      switch(_p_flag&3)
      {
	case 1: 	    /* convert to upper */
	  c=toupper(ch);
	  break;

	case 2: 	    /* convert to lower */
	  c=tolower(ch);
	  break;

	default:	    /* use as is */
	  c=ch;
	  break;
      }
    string[_p_tokpos++]=c;
  }
  return;
}

/* here it is! */

int parser(unsigned inflag, char* token, unsigned tokmax, char* line, char* white, char* brkchar, char* quote, char eschar, char* brkused, int* next, char* quoted){
  int qp;
  char c,nc;

  *brkused=0;		/* initialize to null */
  *quoted=0;		/* assume not quoted  */

  if(!line[*next])	/* if we're at end of line, indicate such */
    return 1;

  _p_state=IN_WHITE;	   /* initialize state */
  _p_curquote=0;	   /* initialize previous quote char */
  _p_flag=inflag;	   /* set option flag */

  for(_p_tokpos=0; c = line[*next] ;++(*next))	/* main loop */
  {
    if((qp=sindex(c,brkchar))>=0)  /* break */
    {
      switch(_p_state)
      {
	case IN_WHITE:		/* these are the same here ...	*/
	case IN_TOKEN:		/* ... just get out		*/
	case IN_OZONE:		/* ditto			*/
	  ++(*next);
	  *brkused=brkchar[qp];
	  goto byebye;

	case IN_QUOTE:		 /* just keep going */
	  chstore(token,tokmax,c);
	  break;
      }
    }
    else if((qp=sindex(c,quote))>=0)  /* quote */
    {
      switch(_p_state)
      {
	case IN_WHITE:	 /* these are identical, */
	  _p_state=IN_QUOTE;	    /* change states   */
	  _p_curquote=quote[qp];	 /* save quote char */
	  *quoted=1;	/* set to true as long as something is in quotes */
	  break;

	case IN_QUOTE:
	  if(quote[qp]==_p_curquote)	/* same as the beginning quote? */
	  {
	    _p_state=IN_OZONE;
	    _p_curquote=0;
	  }
	  else
	    chstore(token,tokmax,c);	/* treat as regular char */
	  break;

	case IN_TOKEN:
	case IN_OZONE:
	  *brkused=c;			/* uses quote as break char */
	  goto byebye;
      }
    }
    else if((qp=sindex(c,white))>=0)	   /* white */
    {
      switch(_p_state)
      {
	case IN_WHITE:
	case IN_OZONE:
	  break;		/* keep going */

	case IN_TOKEN:
	  _p_state=IN_OZONE;
	  break;

	case IN_QUOTE:
	  chstore(token,tokmax,c);     /* it's valid here */
	  break;
      }
    }
    else if(c == eschar)			/* escape */
    {
      nc=line[(*next)+1];
      if(nc==0) 		/* end of line */
      {
	*brkused=0;
	chstore(token,tokmax,c);
	++(*next);
	goto byebye;
      }
      switch(_p_state)
      {
	case IN_WHITE:
	  --(*next);
	  _p_state=IN_TOKEN;
	  break;

	case IN_TOKEN:
	case IN_QUOTE:
	  ++(*next);
	  chstore(token,tokmax,nc);
	  break;

	case IN_OZONE:
	  goto byebye;
      }
    }
    else	/* anything else is just a real character */
    {
      switch(_p_state)
      {
	case IN_WHITE:
	  _p_state=IN_TOKEN;	    /* switch states */

	case IN_TOKEN:		 /* these 2 are     */
	case IN_QUOTE:		 /*  identical here */
	  chstore(token,tokmax,c);
	  break;

	case IN_OZONE:
	  goto byebye;
      }
    }
  }		/* end of main loop */

byebye:
  token[_p_tokpos]=0;	/* make sure token ends with EOS */

  return 0;

}

Продолжение кода, с пространным и подробнейшим обяснением создателя и с примером исполнения online: cpp.sh/96ieg

OldNileCrocodile Apr 27 2021 at 13:22

Хорошо. А что если у нас массив строк, каждую из которых надо разбить на токены? Например, нам надо построить из массива строк [«12 24 32», «26 27», «10 11 44»] построить такую строчку «10 11 12 24 26 27 32 44». (Т.е. фактически получить упорядоченное объединение списков чисел, где список представлен строкой из чисел).

Kotofay Apr 27 2021 at 19:12

Статические переменные упаковываете в структуру и передаёте эту структуру в парсер.
Т.о. состояние парсера сохраняется для каждой строки отдельно, вспомните как сделано для сишного FILE.

MaxMxMz Mar 19 2021 at 22:12

PVS_Studio здесь не будет плакать?
size_t contains_symbol(char *src, char symbol){
size_t pos = 1;
if(symbols == NULL)
return -1;
while(*symbols != '\0'){
if(*symbols++ == symbol)

OldNileCrocodile Mar 20 2021 at 12:03

Уже поправил

WinPooh73 Mar 21 2021 at 06:51

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

Это требование кажется не вполне универсальным. Предположим, мы разбираем строку, считанную из .csv-файла, в котором несколько первых или последних полей имеют значение пустой строки. При отбрасывании разделителей эти поля будут потеряны.

OldNileCrocodile May 3 2021 at 16:37

Конечно, они будут пустыми. Но это можно исправить, ведь мы знаем, что каждое поле разделено ровно одной запятой. (поправьте, если это не так). Написанная функция пока рассматривает разделители как единый непрерывный разделитель (т.е. если 4 пробела — это не значит, что у нас 4 поля, это лишь значит, что у нас один разделитель). И её следует переписать для учёта вашего указанного случая.

Ryppka Mar 22 2021 at 08:21

Придирки.
Не уверен, что в size_t contains_symbol(char *symbols, char symbol) имеет смысл говорить о возврате -1 — она превратиться в максимальное беззнаковое целое. Компилятор, увидев проверку возвращенного значения на отрицательность, будет обескуражен. Может, лучше для положения в массиве использовать ptrdiff_t?
Ну и объявлять аргумент char в C не слишком осмысленно, хотя и можно.

OldNileCrocodile Mar 22 2021 at 13:05

Поправил return в contains_symbol с учётом size_t. Да, ptrdiff_t можно использовать, с учётом наличия отрицательных адресов (т.к. ptrdiff_t, в отличие от size_t, является знаковым целочисленным типом).