episode ★A: original tool
lines
argument parsing · range structs · sort & merge · early-exit streaming
A Tool That Doesn't Exist
Every episode until now had a reference. We knew what the output should look like because we had the real tool to compare against.
lines has no man page. It doesn't exist in Unix. We're building it from a problem statement, which means the hardest part isn't the implementation. It's getting the specification right first.
The problem: you want a specific line from a file. Not the first N. Not the last N. Line 7. Lines 3, 11, and 22. Lines 5 through 12. No standard tool does exactly this without you having to write a script or remember awkward sed syntax.
$ lines file.txt # first line (default) $ lines 7 file.txt # line 7 $ lines 4 7 12 file.txt # lines 4, 7, and 12 $ lines 3,7 file.txt # lines 3 through 7 inclusive $ lines 1,3 10,15 file.txt # lines 1-3 and 10-15
Designing It Before Writing It
With cat, head, and tail, the design was done for us. We just had to understand it. With lines, every decision needs a reason.
Here are the choices, with the reasoning:
No arguments → first line. The most common one-off question about a file is "what's at the top?" One-indexed, matching human counting. Consistent with how people talk about files.
Comma syntax for ranges. 3,7 reads as "3 to 7" intuitively. No conflicts with any shell metacharacter when unquoted. The alternative, 3-7, looks like subtraction or a flag prefix.
File vs stdin behavior differs. On a file, we exit as soon as we've printed all requested lines. There's no point reading a 2 GB file when you wanted line 7. On stdin, we read to EOF, because closing stdin early would disrupt pipeline producers.
Numeric-only arguments are line specs; everything else is a filename. Simple and unambiguous for any real usage. The edge case, a file named 42, is documented and accepted.
The C Concept: Structs and Argument Parsing
The first real challenge isn't streaming. We know how to do that. It's parsing. With head, arguments were simple: one flag, one value. With lines, the argument list can contain any mixture of specs and filenames, in any order.
Representing a Range
A single line like 7 is just the range [7, 7]. A range like 3,7 is [3, 7]. One struct handles both:
typedef struct
{
int start;
int end;
} t_range;
Arguments are scanned left-to-right. Anything that looks like a spec (is_line_spec() returns true) becomes a t_range. The first non-spec argument is treated as a filename.
Why Sort and Merge?
After collecting all the ranges, we sort them by start line and then merge any that overlap or are adjacent. This matters for two reasons:
First, sorting lets the streaming loop move forward through ranges in order, so we only need one forward pass. If ranges were unsorted, we'd need to go back, which we can't do on stdin and would be wasteful on files.
Second, merging prevents duplicate output. lines 3,7 5,10 file.txt should print lines 3 to 10 once, not print lines 5 to 7 twice.
Overlapping ranges collapse into one. Adjacent ranges ([3,5] and [6,9]) merge too. The streaming loop then has a clean, non-overlapping list to work from.
Why lseek Doesn't Help Here
In the tail chapter, lseek was the big win. For a regular file we jumped straight to the part we wanted and skipped the rest. lines looks like the same kind of problem. If someone asks for line 500, why read lines 1 through 499?
Because we have no choice. lseek moves by byte offset, and the kernel has no concept of lines. A file is just a sequence of bytes, and there is no index mapping "line 500" to a byte position, because lines can be any length. To find line 500 you must count 499 newlines from the start, which means reading every byte up to that point. There is no shortcut.
Seeking to a byte is O(1). Seeking to a line is O(bytes before that line). The only way to make arbitrary line access fast is to build an index first: a pass that records the byte offset of every line, kept in memory or in a sidecar file. That is exactly what text editors and databases do, and it is why grep on a huge file is not free.
So lines reads forward from the start and accepts it. On files, the one optimization available to us is stopping the moment the last requested line is printed. On stdin we cannot even do that, because there is no way to know the stream has ended until it ends.
The Build
is_line_spec and parse_spec
int is_line_spec(char *s)
{
int commas;
commas = 0;
if (!s || !*s)
return (0);
while (*s)
{
if (*s == ',')
commas++;
else if (*s < '0' || *s > '9')
return (0);
s++;
}
return (commas <= 1);
}
int parse_spec(char *s, t_range *r)
{
int i;
i = 0;
while (s[i] && s[i] != ',')
i++;
if (s[i] == '\0')
{
r->start = to_number(s);
r->end = r->start;
}
else
{
r->start = to_number(s);
r->end = to_number(s + i + 1);
}
if (r->start <= 0 || r->end <= 0 || r->end < r->start)
{
write(2, "lines: invalid spec: ", 21);
write(2, s, str_len(s));
write(2, "\n", 1);
return (0);
}
return (1);
}
Sort and Merge
void sort_ranges(t_range *ranges, int n)
{
t_range tmp;
int i;
int j;
i = 1;
while (i < n)
{
tmp = ranges[i];
j = i - 1;
while (j >= 0 && ranges[j].start > tmp.start)
{
ranges[j + 1] = ranges[j];
j--;
}
ranges[j + 1] = tmp;
i++;
}
}
int merge_ranges(t_range *ranges, int n)
{
int out;
int i;
if (n == 0)
return (0);
out = 0;
i = 1;
while (i < n)
{
if (ranges[i].start <= ranges[out].end + 1)
{
if (ranges[i].end > ranges[out].end)
ranges[out].end = ranges[i].end;
}
else
{
out++;
ranges[out] = ranges[i];
}
i++;
}
return (out + 1);
}
The Streaming Loop
The key design here is early exit. On files, once we've printed everything in the last range, we return immediately and don't read the rest. On stdin, we read to EOF regardless, so the pipeline producer can finish cleanly.
void stream_lines(int fd, t_range *ranges, int n_ranges, int is_stdin)
{
char buffer[BUFFER_SIZE];
ssize_t bytes_read;
int current_line;
int range_idx;
int start;
int i;
current_line = 1;
range_idx = 0;
while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
{
i = 0;
while (i < bytes_read)
{
if (!is_stdin && range_idx >= n_ranges)
return;
while (range_idx < n_ranges &&
current_line > ranges[range_idx].end)
range_idx++;
if (!is_stdin && range_idx >= n_ranges)
return;
start = i;
while (i < bytes_read && buffer[i] != '\n')
i++;
if (i < bytes_read)
i++;
if (range_idx < n_ranges &&
current_line >= ranges[range_idx].start &&
current_line <= ranges[range_idx].end)
{
write(1, buffer + start, i - start);
}
current_line++;
}
}
if (bytes_read < 0)
write(2, "lines: read error\n", 18);
}
Walking Through an Example
Trace it on a seven-line file with the call lines 2 5,6 file.txt. After parsing, the ranges are [2,2] and [5,6]; sorting and merging leave them unchanged.
1 apple below range[0].start (2) skip
2 banana inside range[0] PRINT, range[0] done -> range_idx = 1
3 cherry below range[1].start (5) skip
4 date below range[1].start (5) skip
5 elderberry inside range[1] PRINT
6 fig inside range[1] PRINT, range[1] done -> range_idx = 2
range_idx (2) >= n_ranges (2), not stdin -> return
7 grape never read
That final line is the early exit in action. The moment range_idx runs past the last range and we are reading a file, we return without touching the rest. On a million-line file asked for line 7, that is the difference between reading seven lines and reading a million.
Stdin: Why It Exits Only at EOF
On a file we stop early. On stdin we deliberately do not, even after every requested line has been printed. That looks wasteful, and there are two reasons it is correct.
First, the pipeline. In some-program | lines 3, the producer is writing into our stdin. If lines closed that end early, the next write from some-program would hit a broken pipe. Depending on the program, that means an error, a half-finished job, or temp files left behind. Reading to EOF lets the producer finish on its own terms.
Second, interactive use. When someone types straight into the terminal and presses Ctrl+D, they expect the program to behave predictably all the way to the end. Closing stdin after line 3 would leave further keystrokes going nowhere. Neither concern exists for a file, which is exactly why stopping early there is a pure win.
The Full Implementation
#include <unistd.h>
#include <fcntl.h>
#define BUFFER_SIZE 4096
#define MAX_RANGES 64
typedef struct
{
int start;
int end;
} t_range;
int str_len(char *s)
{
int n;
n = 0;
while (s && s[n])
n++;
return (n);
}
int to_number(char *s)
{
int res;
res = 0;
while (*s >= '0' && *s <= '9')
{
res = res * 10 + (*s - '0');
s++;
}
return (res);
}
int is_line_spec(char *s)
{
int commas;
commas = 0;
if (!s || !*s)
return (0);
while (*s)
{
if (*s == ',')
commas++;
else if (*s < '0' || *s > '9')
return (0);
s++;
}
return (commas <= 1);
}
int parse_spec(char *s, t_range *r)
{
int i;
i = 0;
while (s[i] && s[i] != ',')
i++;
if (s[i] == '\0')
{
r->start = to_number(s);
r->end = r->start;
}
else
{
r->start = to_number(s);
r->end = to_number(s + i + 1);
}
if (r->start <= 0 || r->end <= 0 || r->end < r->start)
{
write(2, "lines: invalid spec: ", 21);
write(2, s, str_len(s));
write(2, "\n", 1);
return (0);
}
return (1);
}
void sort_ranges(t_range *ranges, int n)
{
t_range tmp;
int i;
int j;
i = 1;
while (i < n)
{
tmp = ranges[i];
j = i - 1;
while (j >= 0 && ranges[j].start > tmp.start)
{
ranges[j + 1] = ranges[j];
j--;
}
ranges[j + 1] = tmp;
i++;
}
}
int merge_ranges(t_range *ranges, int n)
{
int out;
int i;
if (n == 0)
return (0);
out = 0;
i = 1;
while (i < n)
{
if (ranges[i].start <= ranges[out].end + 1)
{
if (ranges[i].end > ranges[out].end)
ranges[out].end = ranges[i].end;
}
else
{
out++;
ranges[out] = ranges[i];
}
i++;
}
return (out + 1);
}
void stream_lines(int fd, t_range *ranges, int n_ranges, int is_stdin)
{
char buffer[BUFFER_SIZE];
ssize_t bytes_read;
int current_line;
int range_idx;
int start;
int i;
current_line = 1;
range_idx = 0;
while ((bytes_read = read(fd, buffer, BUFFER_SIZE)) > 0)
{
i = 0;
while (i < bytes_read)
{
if (!is_stdin && range_idx >= n_ranges)
return;
while (range_idx < n_ranges &&
current_line > ranges[range_idx].end)
range_idx++;
if (!is_stdin && range_idx >= n_ranges)
return;
start = i;
while (i < bytes_read && buffer[i] != '\n')
i++;
if (i < bytes_read)
i++;
if (range_idx < n_ranges &&
current_line >= ranges[range_idx].start &&
current_line <= ranges[range_idx].end)
{
write(1, buffer + start, i - start);
}
current_line++;
}
}
if (bytes_read < 0)
write(2, "lines: read error\n", 18);
}
int main(int argc, char **argv)
{
t_range ranges[MAX_RANGES];
int n_ranges;
int arg_idx;
int fd;
n_ranges = 0;
arg_idx = 1;
while (arg_idx < argc && is_line_spec(argv[arg_idx]))
{
if (n_ranges >= MAX_RANGES)
{
write(2, "lines: too many ranges\n", 23);
return (1);
}
if (!parse_spec(argv[arg_idx], &ranges[n_ranges]))
return (1);
n_ranges++;
arg_idx++;
}
if (n_ranges == 0)
{
ranges[0].start = 1;
ranges[0].end = 1;
n_ranges = 1;
}
sort_ranges(ranges, n_ranges);
n_ranges = merge_ranges(ranges, n_ranges);
if (arg_idx >= argc)
{
stream_lines(0, ranges, n_ranges, 1);
return (0);
}
while (arg_idx < argc)
{
fd = open(argv[arg_idx], O_RDONLY);
if (fd == -1)
{
write(2, "lines: cannot open ", 19);
write(2, argv[arg_idx], str_len(argv[arg_idx]));
write(2, "\n", 1);
arg_idx++;
continue;
}
stream_lines(fd, ranges, n_ranges, 0);
close(fd);
arg_idx++;
}
return (0);
}
The Test
$ cc -Wall -Wextra -o lines lines.c # create a numbered test file $ seq 20 > test.txt # basic cases $ ./lines test.txt # → 1 $ ./lines 5 test.txt # → 5 $ ./lines 3,7 test.txt # → 3 4 5 6 7 $ ./lines 1,3 18,20 test.txt # → 1 2 3 18 19 20 # overlapping specs: should merge and deduplicate $ ./lines 5 5 3,6 test.txt # → 3 4 5 6 (not 5 twice) # stdin path $ printf "one\ntwo\nthree\nfour\nfive\n" | ./lines 2,4 two three four # early exit on large file $ seq 1000000 > big.txt $ time ./lines 3 big.txt $ time sed -n '3p' big.txt # compare timing
The last test is the interesting one. lines 3 big.txt reads exactly enough to reach line 3 and stops. sed scans the whole file. On a million-line file, the difference should be visible.
Known Limitations
An honest tool names what it does not do. lines has three limits worth stating out loud.
A fixed number of ranges. MAX_RANGES is 64. That is far more than any real invocation needs, but a production tool would grow the array dynamically. We meet malloc for the first time in the sort episode and could revisit this then.
A fixed line length. A line longer than BUFFER_SIZE with no newline is split across two iterations of the loop. That is fine for ordinary text. For binary data, reach for the byte-oriented tools instead.
Numeric file names. A file literally named 42 is read as a line spec, not a filename. That is the price of the simple parsing rule. A production tool would accept -- to force everything after it to be treated as filenames.
What We Actually Learned
This episode introduced something none of the previous tools required: design decisions with no reference implementation. Every choice (the syntax, the defaults, how specs are separated from filenames, when to exit early) had to come from reasoning about what would actually be useful.
We also hit the most important insight of the series so far:
There is no efficient way to seek to a line by number. You must count from the beginning. This is not a Unix limitation. It's a consequence of how text files are structured. Understanding it explains why tools like databases, grep, and text editors maintain their own indexes.
lseek() moves by byte offset, not by line number. The kernel has no concept of lines. To find line 500, you must count 499 newline characters. The forward scan here is not the naive approach. It's the correct one, and the early exit on files is the one optimization genuinely available to us.
Next: wc(1), and the surprising complexity of counting something as simple as a word.