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

Введение

Приветствую вас, дорогие читатели. В данной статье описана разработка функции разделения строк. Возможно, эта функция может стать для вас хорошей альтернативой, вместо функции strtok из стандартной библиотеки языка Си.

Вообще говоря, сама задача разбиения строк на подстроки, каждая из которых отделена в исходной строке определённым символом, является довольно распространённой. Очень часто необходимо извлечь из строки слова, разделённые пробелами. Конечно, в стандартной библиотеке языка Си уже есть функция strtok (заголовочный файл <string.h>), но она имеет свои побочные эффекты, перечисленные ниже.

1. Функция модифицирует исходную строку, разбивая её на лексемы. Она возвращает указатель на саму лексему, или NULL, в случае, когда нет больше лексем. Подробнее о ней можно прочитать здесь.

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

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

4. Она не учитывает экранирование символов разделителей.

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

1. Не менять оригинальную строку, в которой ищутся лексемы.

2. Для каждой найденной лексемы создавать новую строку.

3. Сохранять свою текущую позицию, а именно - указатель на подстроку, которая ещё не разбиралась.

4. Иметь однородную последовательность вызовов.

5. Иметь возможность экранировать символы разделители, при сложных лексемах.

Основные шаги при разделении строк.

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

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

Наконец, для выделения памяти необходимо будет написать функцию, учитывающая исключительную ситуацию при работе с памятью (ошибки вида SEGV), а также макрос, позволяющий кратко писать вызов такой функции.

Разработка функции.

Приступим к разработке. Для начала определим заголовочный файл "str_utils.h", содержащий все прототипы необходимых функций. Реализации функций положим в файл "str_utils.c".

Начнём с функции нахождения символов в строке. Библиотечная функция strchr могла бы решить эту задачу. Но проблема в том, что она не допускает в качестве аргумента строки, в которой надо искать символ, значения NULL. При попытке компилировать с флагами -Wall -Werror, файл с таким аргументом не скомпилируется. Хотя, такую ситуацию можно было бы обработать, вернув NULL. Поэтому был определён свой вариант данной функции с именем contains_symbol. Её прототип выглядит следующим образом:

size_t contains_symbol(char *src, char symbol);

Её реализация определена следующим образом (файл "str_utils.c"):

size_t contains_symbol(char *src, char symbol){
  size_t pos = 1;
  if(symbols == NULL)
    return -1;
  while(*symbols != '\0'){
    if(*symbols++ == symbol)
      return pos;
    pos++;
  }
  return 0;
}

Данная функция возвращает позицию символа в строке, увеличенную на единицу. Она не учитывает нулевой символ. Если символ не был найден, функция вернёт 0, либо -1, если ей передали NULL. Её удобно использовать в цикле while, при проверке текущего символа строки на его наличие в другой строке.

Для инкапсуляции работы с памятью был определён отдельный заголовочный файл "mem.h", содержащий следующие прототипы:

void *alloc_mem(size_t nbytes);
void *calloc_mem(size_t nelems, size_t elem_size);

#define alloc_str(x) ((char *) alloc_mem(x + 1))

Соответствующие функции реализованы в отдельном файле "mem.c":

#include <string.h>
#include <stdlib.h>
void *alloc_mem(size_t nbytes){
  char *buf = (char *)malloc(nbytes);
  if(buf != NULL){
    memset(buf, '\0', nbytes);
    return buf;
  }
  exit(-1);
}

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

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

Функция обрезки разделителей строки trim_separators выглядит следующим образом:

/* trims symbols from separators at src string */
/* returns new trimmed string */
char *trim_separators(char *src, char *separators);

char *trim_separators(char *src, char *separators){
  if(src == NULL || separators == NULL)
    return NULL;
  char *sp = src;
  while(contains_symbol(separators, *sp)) sp++;
  
  /* if it contains only symbols from separators => NULL */
  if(sp - s == strlen(s)) return NULL;
  
  char *sp2 = s + strlen(s) - 1; /* last char at src */
  while(contains_symbol(separators, *sp2)) sp2--;
  
  /* if it contains only symbols from separators => NULL */
  if(sp2 < s) return NULL;
  
  size_t sz = 0;
  if(sp2 - sp == 0 && *sp == '\0') return NULL; /* zero byte is not a character */
  else if(sp2 - sp == 0){
    sz = 1;
  }
  else{
    sz = (sp2 - sp) + 1;
  }
  char *res = alloc_mem(sz);
  memcpy(res, sp, sz);/* copy all chars except last zero byte */
  return res;
}

В начале мы проверяем на NULL аргументы функции. Если они нулевые, то возвращаем NULL.

Далее, через указатель sp, проходим строку слева направо, пока мы встречаем символы из строки separators. Если мы прошли всю строку, значит она целиком и полностью состоит из сепараторов, следовательно надо удалить все символы, или же просто вернуть NULL.

char *sp = src;
while(contains_symbol(separators, *sp)) sp++;
  
/* if it contains only symbols from separators => NULL */
if(sp - s == strlen(s)) return NULL;

Аналогично, далее через указатель sp2, проходим строку справа налево, проверяя, находится ли текущий символ в массиве separators. Если это не так, то мы прерываем цикл, а указатели будут содержать ссылку на первые символы, не являющимися разделителями. Если мы опять прошли всю строку, значит снова придётся удалять всю строку, следовательно, возвращаем NULL.

char *sp2 = s + strlen(s) - 1; /* last char at src */
while(contains_symbol(separators, *sp2)) sp2--;
  
/* if it contains only symbols from separators => NULL */
if(sp2 < s) return NULL;

Наконец, вычисляем длину строки. Если указатели ссылаются на одно и то же место, то в строке был лишь один символ, не являющийся разделителем, а потому размер результата будет равным 1 байту (один лишний байт для нулевого символа учтён в макросе alloc_str). Если же этот единственный символ является нулевым (маркером конца), то возвращаем NULL. Иначе берём разницу между адресами указателями, прибавляем к ней единицу, и получаем длину новой строки. Затем мы просто выделяем память для новой строки и копируем в неё строку, начинающуюся с указателя sp.

Теперь, объединим работу выше написанных функции, в единую функцию get_token().

Код функции get_token дан ниже:

char *get_token(char *src, char *delims, char **next){
  if(src == NULL || delims == NULL)
    return NULL;
  char *delims_p = delims;
  /* the end of lexem (points to symbol that follows right after lexem */
  char *src_p = trim_separators(src, delims);
  /* the begining of the lexem */
  char *lex_begin = src_p;
  if(src_p == NULL){
    *next = NULL;
    return NULL;
  }
  
  /* flag that indicates reaching of delimeter */
  int flag = 0;
  while(*src_p != '\0'){
    flag = 0;
    while(*delims_p != '\0'){
      if(*delims_p == *src_p){
        flag = 1;
        break;
      }
      delims_p++;
    }
    if(flag == 1)
      break;
    delims_p = delims;
    src_p++;
  }
  
  /* now src_p points to the symbol right after lexem */
  /* compute lexem size and reset pointers (from trimmed to the original src) */
  char *offset;
  size_t tok_size;
  offset = (src + strspn(src, delims));
  tok_size = (src_p - lex_begin);
  free(lex_begin);
  lex_begin = offset;
  src_p = offset + tok_size;
  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;
}

В ней используется функция обрезки trim_separators(). Функция обрезки возвращает новую строку, и далее сканирование ведётся по ней. В цикле лишь проверяется, не равен ли текущий символ какому-либо символу разделителю из массива символов delims, и если равен, то выйти из цикла. Указатель src_p проходит по сканируемой строке. После цикла он будет указывать на символ, следующий за лексемой (конец лексемы). А начало лексемы сохраняется в указателе lex_begin, который изначально указывает на начало обрезанной, сканируемой строки. После обнаружения границ лексемы, вычисляется её размер (её число символом), а затем сканируемая строка удаляется из динамической кучи. Затем указатели переустанавливаются на позиции в оригинальной строке (первый аргумент функции get_token()), а часть строки, которая ещё не была разобрана, присваивается в качестве содержимого двойному указателю next. Обратите внимание, что next является ссылкой на другой указатель (в данном случае, на указатель строки). Двойной указатель позволяет менять значение переменной типа char *, записывая новый адрес в next. Для первого вызова данной функции, next должен хранить адрес переменной указателя, которая указывает на строку и хранит адрес первой ячейки строки. Однако, при работе с двойным указателем возможна серьёзная и незаметная ошибка, если в качестве начального значения next передать адрес переменной, которая непосредственно указывает на строку, а не адрес переменной копии, которая содержит копию адреса строки. В следующем разделе подробно описана данная ситуация, и показан пример работы данной функции.

Пример работы get_token().

Ниже дан простой рабочий пример функции get_token(). Оригинальная строка с лексемами хранится в указателе test, копия адреса строки (копия переменной test) хранится в переменной copytest. Указатель tok хранит текущую распознанную лексему, а next - сканируемую часть строки. Данная программа разделяет строку test по пробелу и символу табуляции на подстроки, и выводит их. Также она выводит саму строку test до и после работы функции. Как можно убедиться по выводу, оригинальная строка не меняется.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "mem.h"
#include "str_utils.h"
int main(int argc, char **argv){
  char *test = "  They have  a    cat.\n \0";
  char *copytest = test;
  char **next = &copytest; /* has side effect on copytest */
  char *tok = NULL;
  
  printf("src:%s\n", test);
  printf("copytest:%s\n", copytest);
  while(*next != NULL){
    tok = get_token(*next, " \t\0", next);
    if(tok == NULL)
      break;
    printf("%s\n", tok);
    free(tok);
  }
  printf("src after:%s\n", test);
  printf("copytest after:%s\n", copytest);
  return 0;
}
  

Вывод данной программы:

src:  They have  a    cat.

copytest:  They have  a    cat.

They
have
a
cat.

src after:  They have  a    cat.

copytest:(null)

Обратите внимание, что в цикле есть дополнительная проверка на NULL указателя tok. Дело в том, что при получении последнего слова в строке (а именно "cat.\n"), указатель next будет указывать на подстроку, состоящую лишь из одних пробелов (плюс нулевой символ). Функция trim_separators() для таких строк возвращает NULL, так как по логике придётся урезать все символы в строке. В итоге get_token() также вернёт NULL, поскольку уже ничего не осталось для сканирования. Поэтому переменная tok сохранит значение NULL, на последнем шаге.

Теперь снова по поводу двойного указателя next. Как вы могли заметить, в вышеприведённом коде ему передаётся адрес переменной copytest, а не переменной test. Дело в том, что мы можем нечаянно затереть значение переменной test (именно переменной, а не самой строки). Для примера, изменим код следующим образом. Передадим адрес test в указатель next. В итоге мы получим следующий вывод.

src:  They have  a    cat.

copytest:  They have  a    cat.

They
have
a
cat.

src after:(null)
copytest:  They have  a    cat.

Как видите, сама строка не меняется, но изменилось значение переменной test. Теперь она содержит NULL, поскольку на последнем шаге, функция присваивает ей соответствующее значение. Отсюда следует, что операции вида:

*next = addr;
*next = NULL;

с двойными указателями (указатель на указатель), тройными, и какой-либо сколь угодно длинной цепочкой указателей создают побочный эффект.

Модификация функции get_token(). Экранирование разделителей.

Функция get_token() умеет возвращать новые подстроки (токены) из исходной строки, не меняя её. Однако она совершенно не умеет их экранировать, в случае, когда лексемы представляют собой более сложные объекты. Например, а что если лексема содержит символ, который мы выбрали в качестве разделителя?

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

1233,"John Cenna","Male",4.22,"2004, 2005, 2006",1
1234,"John Doe","Male",4.24,"2001, 2004, 2007",0
1235,"Maria Laws","Female",4.23,"2003, 2006, 2008",1

Данные значения формируют следующую таблицу:

Заметим, что в данном случае, значения отделяются друг от друга запятой, причём сам разделитель (запятая) не учитывается, когда он находится в кавычках. Это значит, что сам разделитель дополнительно экранирован (escaped) двойными кавычками.

Для таких особых случаев, была определена новая функция get_token_escaped(), которая в качестве дополнительного параметра принимает массив (строку) символов, экранирующих разделители. Символы разделители не должны пересекаться с данным массивом. Т.е. один и тот же символ должен быть либо управляющим, либо разделяющим но не одним и тем же одновременно. Если же это так, то функция будет возвращать NULL. Для контроля начала и конца экранируемой последовательности, была заведена отдельная переменная neflag. Переменная neflag указывает, не является ли текущий символ частью экранируемой последовательности (neflag => not escaped flag). Она равна 0, когда символ должен быть экранируем, и 1, когда символ не экранируется. В цикле сканирования, сначала текущий символ ищется среди экранирующих (escaped). Если он найден и он равен предыдущему управляющему символу, то устанавливаем соответствующий флаг neflag равным 0, так как была найдена пара - начала и конец экранируемой последовательности. Если же это другой экранирующий символ, не равный предыдущему, то если мы уже находимся в экранируемой последовательности, то ничего не надо делать (продолжаем поиск, в надежде, что мы отыщем нужную пару (пред. символ)). Иначе, если мы нашли его впервые, то запоминаем его в переменной esym, и сбрасываем флаг neflag в 0. Символ разделитель будет учтён, если он был обнаружен (flag == 1) и он не является частью экранируемой последовательности (neflag == 1).

Ниже дан код данной процедуры.

char *get_token_escaped(char *src, char *delims, char *escaped, char **next){
  if(src == NULL || delims == NULL || escaped == NULL)
    return NULL;
  char *delims_p = delims;
  char *escaped_p = escaped;
  /* the end of lexem (points to symbol that follows right after lexem */
  char *src_p = trim_separators(src, delims);
  /* the begining of the lexem */
  char *lex_begin = src_p;
  if(src_p == NULL){
    *next = NULL;
    return NULL;
  }
  
  /* check that (delims INTERSECTION escaped) IS NULL. */
  /* IF NOT => return NULL */
  int err = 0;
  while(*delims_p != '\0'){
    while(*escaped_p != '\0' && (err = (*escaped_p == *delims_p) ) != 1) escaped_p++;
    escaped_p = escaped;
    if(err){
      return NULL;
    }
    delims_p++;
  }
  delims_p = delims;
  
  /* flag that indicates reaching of delimeter */
  int flag = 0;
  /* flag that indicates that we are not in escaped sequence */
  int neflag = 1;
  /* previously saved escape character (i.e. the begining of the escaped seq.) */
  char *esym = (char)0;
  while(*src_p != '\0'){
    flag = 0;
    while(*escaped_p != '\0'){
      if(*src_p == *escaped_p && *src_p == esym){
        neflag = 1;
        esym = (char)0;
        break;
      }
      else if(*src_p == *escaped_p && neflag){
        neflag = 0;
        esym = *escaped_p;
        break;
      }
      escaped_p++;
    }
    while(*delims_p != '\0'){
      if(*delims_p == *src_p){
        flag = 1;
        break;
      }
      delims_p++;
    }
    if(flag && neflag)
      break;
    delims_p = delims;
    escaped_p = escaped;
    src_p++;
  }
  
  /* now src_p points to the symbol right after lexem */
  /* compute lexem size and reset pointers (from trimmed to the original src) */
  char *offset;
  size_t tok_size;
  offset = (src + strspn(src, delims));
  tok_size = (src_p - lex_begin);
  free(lex_begin);
  lex_begin = offset;
  src_p = offset + tok_size;
  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;
}

Пример её использования дан ниже:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "mem.h"
#include "str_utils.h"
int main(int argc, char **argv){
  char *test = "  They have  \"cats dogs mice  \"\n \0";
  char *copytest = test;
  char **next = &copytest; /* has side effect on copytest */
  char *tok = NULL;
  
  printf("src:%s\n", test);
  printf("copytest:%s\n", copytest);
  while(*next != NULL){
    tok = get_token_escaped(*next, " \t\0", "\"\0", next);
    if(tok == NULL)
      break;
    printf("%s\n", tok);
    free(tok);
  }
  printf("src after:%s\n", test);
  printf("copytest after:%s\n", copytest);
  return 0;
}

Вывод:

src:  They have  "cats dogs mice  "

copytest:  They have  "cats dogs mice  "

They
have
"cats dogs mice  "

src after:  They have  "cats dogs mice  "

copytest after:(null)

Заключение

Разработанная функция get_token() позволяет извлекать лексемы в отдельные новые строки. Она не меняет исходной строки, и имеет одинаковую последовательность вызовов. Из недостатков, она использует двойной указатель для сохранения текущей позиции сканера. Чтобы не затирать значение переменной, адрес которой содержит двойной указатель next, необходимо передавать адрес другой переменной, являющейся копией исходной (см. код выше). Функция также не умет экранировать символы разделители. Эту работу делает другая функция - get_token_escaped().

Функцию get_token_escaped() можно использовать при работе с CSV файлами. Однако ей должны передаваться непересекающиеся множества символов разделителей, и экранирующих символов. Иначе будет неоднозначность между ними. Функция не умеет пока анализировать такие неоднозначности, поэтому в таких случаях она вернёт NULL. Кроме того, она не допускает вложенных экранируемых последовательностей. Т.е. если был встречен экранируемый символ, всё что следует за ним, включительно до его клона (такого же символа, но в следующей позиции), считается как одна экранируемая последовательность.

Надеюсь, эти функции облегчат вам работу. Не забудьте, что они возвращают экземпляр новой строки в динамической куче, поэтому после их вызовов и проверки на NULL, необходимо вызывать free(), для освобождения памяти.