I've created a regular expression (regex) parsing library in C, and would like some feedback on it. Speed is really important to me, but any and all suggestions are acceptable.
#include <ctype.h>
static int regex_matchHere(const char *regex, char *s, int *len);
static int regex_matchGroup(int c, int group);
static int regex_matchQuantity(int quant, int c, const char *regex, char *s, int *len);
int regex_match(const char *regex, char *s, int *len)
{
char *p = s;
/* force match from the beginning of the string */
if (regex[0] == '^') return (regex_matchHere(regex + 1, s, len) ? 0 : -1);
/* iterate the string to find matching position */
do
{
*len = 0;
if (regex_matchHere(regex, p, len)) return (int)(p - s);
} while (*p++ != '\0');
return -1;
}
static int regex_matchHere(const char *regex, char *s, int *len)
{
int c = regex[0];
if (regex[0] == '\0') return 1; /* end of regex = full match */
else if (regex[0] == '$' && regex[1] == '\0') return (*s == '\0'); /* check end of string */
else if (regex[0] == '\\' && regex[1] != '\0') /* check escaped symbol */
{
c = regex[1];
if (c != '^' && c != '$' && c != '\\' && c != '+' && c != '*' && c != '-' && c != '?') c = c | 0x100;
regex = regex + 1;
}
/* check for special operators *,+,?,- */
if (regex[1] == '*' || regex[1] == '+' || regex[1] == '-' || regex[1] == '?') return regex_matchQuantity(regex[1], c, regex+2, s, len);
else if (*s != '\0' && regex_matchGroup(*s, c))
{
*len = *len + 1;
return regex_matchHere(regex+1, s+1, len);
}
return 0;
}
static int regex_matchGroup(int c, int group)
{
if ((group & 0xff) == '.') group ^= 0x100;
if (group < 0x100) return c == group; /* a single char */
/* a meta char, like \d, ... */
switch (group & 0xff)
{
case 'd': return isdigit(c);
case 's': return isspace(c);
case 'D': return !isdigit(c);
case 'S': return !isspace(c);
case '.': return 1;
}
return 0;
}
static int regex_matchQuantity(int quant, int c, const char *regex, char *s, int *len)
{
if (quant == '?')
{
if (regex_matchGroup(*s, c))
{
*len = *len + 1;
s = s + 1;
}
return regex_matchHere(regex, s, len);
}
if (quant == '+' || quant == '*') /* match as much as possible */
{
char *p;
for (p = s; *p != '\0' && regex_matchGroup(*p, c); p++) *len = *len + 1;
if (quant == '+' && p == s) return 0;
do
{
if (regex_matchHere(regex, p, len)) return 1;
*len = *len - 1;
} while (p-- > s);
}
else if (quant == '-') /* match as little as possible */
{
do
{
if (regex_matchHere(regex, s, len)) return 1;
*len = *len + 1;
} while (*s != '\0' && regex_matchGroup(*s++, c));
}
return 0;
}