C / CAPSTONE PROJECTS
Project: a grep clone with buffered file search
Build a working grep clone that reads files in fixed-size blocks, rejoins lines split across block boundaries, and prints each match with its line number.
What you will learn
- Refill behind the leftover: fread(buf + held, 1, BUFSZ - held, f), not fread(buf, ...)
- Find lines with memchr and NUL-terminate over the '\n' before calling strstr
- memmove the unfinished tail to buf[0] so a line split by a read stays searchable
- Flush the final newline-less line, and decide what to do with lines bigger than the buffer
Understanding Project: a grep clone with buffered file search
grep is a line-oriented tool sitting on top of a byte-oriented file. Calling getline once per line is easy, but it pays a function call and often an allocation per line; reading 64 KiB at a time pays one stdio call per 64 KiB and then lets memchr find the newlines inside that block at memory speed. That trade shapes the whole program into two nested loops: an outer loop that refills the buffer, and an inner loop that walks the newlines already sitting in it.
A read boundary lands wherever the buffer size puts it, which is almost never on a newline, so most passes end with a fragment of a line at the tail of the buffer. Keep that fragment: memmove it to buf[0], remember its length in held, and refill at buf + held instead of buf. The invariant to hold in your head is that buf[0..held) is always the start of a line whose newline has not been read yet, which is exactly why it must not be searched or printed until that newline arrives. Line numbers, byte offsets, and "am I still inside an overlong line" are per-file state, so they live outside the outer loop.
A fixed buffer forces two decisions the naive version quietly gets wrong. If the input does not end in a newline, the last line exists only in held when the loop exits, so it needs a flush after the loop. If one line is longer than the buffer, held reaches BUFSZ, BUFSZ - held becomes 0, and fread(..., 0, ...) returns 0: the loop ends and the rest of the file disappears with no error at all, so you must either grow the buffer or drop that line with a diagnostic. The honest test for the finished program is that its output is byte-identical with BUFSZ 41 and BUFSZ 65536.
<stdio.h>
<string.h>
BUFSZ/* small on purpose; production code uses 64 * 1024 */
/* Print every line of `in` that contains `pat`, as name:lineno:line. */
static void grep_stream(FILE *in, const char *name, const char *pat)
{
char buf[BUFSZ + 1]; /* +1: room to NUL-terminate a full buffer */
size_t held = 0; /* buf[0..held) starts a line whose '\n' is unseen */
long lineno = 0;
int skipping = 0;
size_t n;
while ((n = fread(buf + held, 1, BUFSZ - held, in)) > 0) {
size_t len = held + n, start = 0;
char *nl;
while ((nl = memchr(buf + start, '\n', len - start)) != NULL) {
size_t end = (size_t)(nl - buf);
buf[end] = '\0'; /* terminate the line in place */
lineno++;
if (!skipping && strstr(buf + start, pat) != NULL)
printf("%s:%ld:%s\n", name, lineno, buf + start);
skipping = 0;
start = end + 1;
}
held = len - start; /* tail with no newline yet */
memmove(buf, buf + start, held);
if (held == BUFSZ) { /* full buffer, still no '\n' */
if (!skipping)
fprintf(stderr, "%s: line %ld too long, skipped\n",
name, lineno + 1);
skipping = 1;
held = 0;
}
}
if (held > 0 && !skipping) { /* last line, no trailing '\n' */
buf[held] = '\0';
lineno++;
if (strstr(buf, pat) != NULL)
printf("%s:%ld:%s\n", name, lineno, buf);
}
if (ferror(in))
perror(name);
}
int main(void)
{
const char *path = "sample.txt";
FILE *f = fopen(path, "wb");
if (f == NULL) { perror(path); return 1; }
fputs("alpha beta\n"
"gamma delta\n"
"beta carotene is not a beta blocker\n"
"epsilon\n"
"final line with no newline mentions beta", f);
fclose(f);
f = fopen(path, "rb");
if (f == NULL) { perror(path); return 1; }
grep_stream(f, path, "beta");
fclose(f);
remove(path);
return 0;
}
buf[0..held) always holds the beginning of a line whose newline has not been read yet, and every other part of the scan follows from keeping that true.
Worked examples
How a full buffer stalls the loop
Prints what each pass read and carried, and shows the silent stall when a single line fills the whole buffer.
<stdio.h>
<string.h>
BUFSZ
int main(void)
{
const char *path = "t.txt";
char buf[BUFSZ];
size_t held = 0, n, pass = 0;
FILE *f = fopen(path, "wb");
if (f == NULL) { perror(path); return 1; }
fputs("one\ntwo\nthreeeee\nfour", f); /* line 3 is 8 bytes plus '\n' */
fclose(f);
f = fopen(path, "rb");
if (f == NULL) { perror(path); return 1; }
while ((n = fread(buf + held, 1, BUFSZ - held, f)) > 0) {
size_t len = held + n, start = 0, lines = 0;
char *nl;
while ((nl = memchr(buf + start, '\n', len - start)) != NULL) {
lines++;
start = (size_t)(nl - buf) + 1;
}
held = len - start;
memmove(buf, buf + start, held);
pass++;
printf("pass %zu: read %zu bytes, %zu complete lines, %zu carried\n",
pass, n, lines, held);
}
printf("loop ended with %zu bytes stuck in the buffer\n", held);
fclose(f);
remove(path);
return 0;
}
Example explained
Line 1Pass 1 reads "one\ntwo\n": two newlines are found, start reaches 8, so nothing is carried.
Line 2Pass 2 reads the 8 bytes of "threeeee" with no newline in them, so held becomes 8 and the buffer is entirely one unfinished line.
Line 3With held == BUFSZ the request BUFSZ - held is 0, fread returns 0 without touching the stream, and the while condition ends the loop.
Line 4The last five bytes ("\nfour") are never read and no error is reported anywhere; the skipping branch in the main program is what prevents this.
Byte offsets that survive the boundary
Tracks the file offset of buf[0] so each match can be reported at its absolute byte offset, the way grep -b does.
<stdio.h>
<string.h>
BUFSZ
int main(void)
{
const char *path = "off.txt";
char buf[BUFSZ + 1];
size_t held = 0, n;
long base = 0; /* file offset of buf[0] */
FILE *f = fopen(path, "wb");
if (f == NULL) { perror(path); return 1; }
fputs("first line\nsecond has hit\nthird\nlast hit here\n", f);
fclose(f);
f = fopen(path, "rb");
if (f == NULL) { perror(path); return 1; }
/* every line here is shorter than BUFSZ, so the overlong case cannot occur */
while ((n = fread(buf + held, 1, BUFSZ - held, f)) > 0) {
size_t len = held + n, start = 0;
char *nl;
while ((nl = memchr(buf + start, '\n', len - start)) != NULL) {
size_t end = (size_t)(nl - buf);
buf[end] = '\0';
if (strstr(buf + start, "hit") != NULL)
printf("%ld:%s\n", base + (long)start, buf + start);
start = end + 1;
}
base += (long)start;
held = len - start;
memmove(buf, buf + start, held);
}
if (held > 0) { /* input that does not end in '\n' */
buf[held] = '\0';
if (strstr(buf, "hit") != NULL)
printf("%ld:%s\n", base, buf);
}
fclose(f);
remove(path);
return 0;
}
Example explained
Line 1base is defined as the file offset of buf[0], so a line starting at buf + start begins at file offset base + start.
Line 2base += start runs right after the inner loop, at the same moment the leftover is memmoved to the front, keeping the two consistent.
Line 3"second has hit" arrives in two pieces ("secon", then "d has hit\n") yet still reports offset 11, because the carry rejoins it before any search happens.
Line 4The trailing if (held > 0) block handles input with no final newline; this file ends in '\n', so it never runs here.
Important notes
strstr stops at the first NUL byte, so a line from a binary file is only searched up to that byte; binary-safe matching needs length-based search (memchr plus memcmp, or memmem where it is available).
Text produced on Windows ends lines with \r\n, and the '\r' stays at the end of each extracted line: end-anchored patterns stop matching and printed output overwrites itself on a terminal, so strip a trailing '\r' before matching.
Common mistakes
Calling strstr or printf on the buffer straight after fread: fread writes no NUL terminator, so the search runs past the fresh bytes into the previous pass's leftovers or uninitialised memory, printing matches that are not in the file.
Refilling with fread(buf, 1, BUFSZ, f) and restarting the scan at buf[0]: every line that straddles a read boundary is cut in two, so a pattern sitting on the cut is never found and every line number after it is wrong.
Treating a short fread as failure with something like if (n < BUFSZ) break; before scanning: the final read of a file is almost always short, so the tail of the file is silently discarded.
Try it yourself
Change, predict, then run
Change grep_stream so it returns the number of matching lines instead of printing them, and print that count once in main. Run it with BUFSZ set to 41 and then 4096 and confirm the count is 3 both times.
Open the C workspaceCheck your understanding
A grep clone reads a file in 4096-byte blocks. In one pass the buffer is full and the last '\n' in it is at index 4000. What has to happen to bytes 4001..4095 before the next fread?
- Nothing: they were already searched during this pass, so the next fread can start writing at buf[0].
- Search that fragment right away and discard it, since a partial line either contains the pattern or it does not.
- memmove them to buf[0], then fread into buf + 95 requesting at most 4001 bytes.
- fseek the stream back to the byte just after the last '\n' so the next block starts on a line boundary.
Show answer
Those 95 bytes are the start of a line whose newline has not been read, so they have not been searched and must be carried to buf[0], with the refill aimed at buf + 95 so they stay intact. Searching the fragment immediately misses any match that straddles the cut and reports a piece of a line as a whole line; the fseek trick re-reads data on every pass and fails outright on non-seekable input such as a pipe or stdin.