K&R C Programs Exercise 5-7 - C Program Examples

Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage itself. How much faster is the program?

The K&R readlines from Section 5.6 calls a custom alloc to carve space out of a static buffer. This exercise moves storage to a flat char linestore[] array in main, which readlines uses directly. The function still writes pointers into lineptr[]. Speed difference: negligible in practice — the real alloc does no more work than maintaining a pointer; the exercise is about understanding where memory comes from.

Solution

/* K&R Exercise 5-7 — readlines storing lines in a caller-supplied array
 * Compile: gcc -ansi -Wall ex5-7.c -o ex5-7 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLINES  5000
#define MAXSTORE  100000

static char *lineptr[MAXLINES];

int my_getline(char *s, int lim)
{
    int c;
    char *p = s;
    while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
        *p++ = c;
    if (c == '\n') *p++ = c;
    *p = '\0';
    return p - s;
}

/* readlines now takes a storage buffer and its size from the caller */
int readlines(char *lineptr[], char *store, int maxlines, int maxstore)
{
    int len, nlines = 0;
    char *storeend = store + maxstore;
    char line[1000];

    while ((len = my_getline(line, sizeof line)) > 0) {
        if (nlines >= maxlines || store + len > storeend)
            return -1;
        line[len-1] = '\0';    /* strip newline */
        strcpy(store, line);
        lineptr[nlines++] = store;
        store += len;
    }
    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
    while (nlines-- > 0)
        printf("%s\n", *lineptr++);
}

int compare(const void *a, const void *b)
{
    return strcmp(*(const char **)a, *(const char **)b);
}

int main(void)
{
    static char linestore[MAXSTORE];   /* storage owned by main */
    int nlines;

    if ((nlines = readlines(lineptr, linestore, MAXLINES, MAXSTORE)) > 0) {
        qsort(lineptr, nlines, sizeof(char *), compare);
        writelines(lineptr, nlines);
    } else {
        fprintf(stderr, "input too large\n");
        return 1;
    }
    return 0;
}

Compile and Test

printf "banana\napple\ncherry\n" | gcc -ansi -Wall ex5-7.c -o ex5-7 && ./ex5-7

Sample Output

apple
banana
cherry

How Much Faster?

In practice, essentially the same speed. The original alloc just advances a pointer in a static buffer — O(1) per allocation, same as bumping the store pointer here. The exercise is about understanding the separation between where memory comes from (the caller) and how it’s used (the function). Moving the buffer to main makes the allocation visible and puts the caller in control of sizing.

What This Exercise Teaches

Caller-supplied storage — passing a buffer as a parameter instead of using internal static allocation; the function owns no storage, making it reentrant and testable
Pointer arithmetic for bump allocation — store += len moves the allocation pointer forward; checking store + len > storeend guards against overflow
Array of pointers to strings — lineptr[] holds pointers into linestore[]; sorting the pointer array sorts the lines without moving any string data

Set Up Your C Environment

← Exercise 5-6 |
Chapter 5 Solutions |
Exercise 5-8 →

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie