Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
myglob.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static char *pattern;
static size_t n;
static size_t *statesmem, *states, *nextstates;
void compileglob(const char *pattern0)
{
char *ptr = 0;
pattern = malloc(strlen(pattern0)+1);
if (!pattern) {
perror("malloc");
exit(EXIT_FAILURE);
}
ptr = pattern;
/* Coalesce runs of star operators */
while (*pattern0) {
if (*pattern0 != '*' || ptr == pattern || ptr[-1] != '*')
*ptr++ = *pattern0;
++pattern0;
}
n = strlen(pattern) + 1;
statesmem = malloc(2 * n * sizeof(size_t));
if(statesmem == 0) {
perror("malloc");
exit(EXIT_FAILURE);
}
states = statesmem;
nextstates = statesmem + n;
}
void endglob(void)
{
free(pattern);
free(statesmem);
}
int checkglob(const char *text)
{
size_t statescount = 0, nextstatescount = 0, i = 0, prev = 0;
/* Set initial states */
states[0] = 0;
statescount = 1;
if(pattern[0] == '*') {
states[1] = 1;
statescount = 2;
}
/* Simulate the NFA (each state = index into pattern) */
for (;;) {
nextstatescount = 0;
prev = (size_t) -1;
for (i = 0; i < statescount; ++i) {
size_t state = states[i];
if (pattern[state] == '*') {
/* Star - expect arbitrary number of chars */
if (prev != state) {
nextstates[nextstatescount++] = state;
}
nextstates[nextstatescount++] = state + 1;
prev = state + 1;
} else if (pattern[state] == '?') {
/* Question mark - expect single char */
if (*text) {
nextstates[nextstatescount++] = state + 1;
prev = state + 1;
}
} else if (pattern[state]) {
/* Normal state - expect specific char */
if (*text == pattern[state]) {
nextstates[nextstatescount++] = state + 1;
prev = state + 1;
}
} else {
/* Accepting (final) state */
if (!*text && prev != state) {
nextstates[nextstatescount++] = state;
prev = state;
}
}
}
if (nextstatescount == 0)
return 0;
if (!*text)
return nextstates[nextstatescount - 1] == n - 1;
/*
memcpy(states, nextstates, nextstatescount * sizeof(size_t));
to avoid a costly copy, just swap the pointer
*/
if (states == statesmem) {
states = statesmem + n;
nextstates = statesmem;
} else {
states = statesmem;
nextstates = statesmem + n;
}
statescount = nextstatescount;
++text;
}
/* not reached */
return 0;
}
int main(int argc, char **argv)
{
int i;
FILE *f;
char buf[1024];
if (argc<2)
return EXIT_FAILURE;
compileglob(argv[1]);
for (i = 2; i < argc; ++i) {
f = fopen(argv[i], "r");
if (!f) {
perror(argv[i]);
return 1;
}
while (fgets(buf, sizeof buf, f)) {
if (*buf && buf[strlen(buf)-1] == '\n')
buf[strlen(buf)-1] = 0;
if (checkglob(buf))
puts(buf);
}
fclose(f);
}
endglob();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment