Glob / Path Pattern Matcher (C)
Topics: strings, recursion, backtracking, wildcards
Problem
Implement glob matching for routing-table and .gitignore-style path patterns
over NUL-terminated strings:
bool glob_match(const char *pat, const char *name);
pat may contain:
? — matches exactly one character other than /.* — matches a (possibly empty) run of characters not containing /
(it does not cross a path-segment boundary).** — matches a (possibly empty) run of characters including /
(it can span any number of path segments).- any other byte matches itself, literally.
Special case: a leading **/ may stand for zero segments, so **/build must
also match build (not just a/b/build).
Key concepts
- Recursion with backtracking: a
* (or **) can consume different amounts of
input. Try each split — for each suffix of name: if the rest of the pattern matches that suffix, succeed — recursing on the remainder. a*a*a*a*b against
aaaa…b only matches if you find the right division of the as.
* stops at /: when scanning suffixes for a single *, break as soon as
you pass a /; ** keeps going across /.- Anchor on the empty cases: an empty pattern matches only an empty name; a
*/** may legitimately consume zero characters.
No allocation is needed — walk the two strings with pointers.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/glob && /tmp/glob
Sign in to submit your solution.