Быстрое определения наличия подстроки (или регулярного выражения) с помощью re2c

Утилита re2c ( http://re2c.org/ ) транслирует регулярные выражения в код на языке С. В некоторых случаях таким способом можно добиться существенного прироста производительности обработки строк по сравнению с традиционными подходами.

Пример использования re2c для одновременного поиска нескольких подстрок. Подстроки ищутся не в zero-terminated строке, а в блоке произвольных байт. Блок задается адресом начала и длиной:


/* re_scan.l */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static int
scan(char *cursor, size_t l) {
	char *marker;
	char *ctxmarker;
	char *limit = cursor + l;
#define YYCTYPE         char
#define YYPEEK()        (cursor >= limit ? 0 : (*cursor == 0 ? 255 : *cursor))
#define YYSKIP()        ++cursor
#define YYBACKUP()      marker = cursor
#define YYBACKUPCTX()   ctxmarker = cursor
#define YYRESTORE()     cursor = marker
#define YYRESTORECTX()  cursor = ctxmarker
	for(;;) {
/*!re2c
	re2c:indent:top = 2;
	re2c:yyfill:enable = 0;
	[\001-\377]* ("xxx"|"abc"|"def"){ return 1; }
	*				{ return 0; }
*/
	}
	return 0;
}

int
main(int argc, char *argv[])
{
	int r;

	if (argc < 2) {
		fprintf(stderr, "Usage: %s STRING\n", argv[0]);
		return 1;
	}

	r = scan(argv[1], strlen(argv[1]));
	if (r) {
		printf("substring found\n");
	} else {
		printf("substring not found\n");
	}
	return 0;
}

Матчинг происходит в функции scan.

"xxx"|"abc"|"def" - подстроки, которые нужно искать. Можно использовать не только фиксированные строки, но и регулярные выражения

# генерируем C-код
$ re2c --input custom -o re_scan.c re_scan.l
# компилируем пример
$ cc -O2 -Wall -pedantic re_scan.c -o re_scan
# проверяем
$ ./re_scan abracadabra
substring not found
$ ./re_scan abrabcadabra
substring found

Blog: