Tail implementation in C

Question

Write the program tail, which prints the last n lines of its input. By default, n is 10, let us say, but it can be changed by an optional argument, si that tail -n prints the last n lines. The program should behave rationally no matter how unresonable the input or the value n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of section 5.6, not in a two-dimensional array of fixed size.

The exercise can be found on page 133 in K&R.

I will explain the way my program works. First it parses the value of the symbolic argument(if any). Based on the value of the symbolic argument the program will initialize a queue which stores pointer to each line.

Then, the program will read lines and push every line in the queue until the end of files is reached. When the end of file is reached all elements of the queue are printed out.

There are multiple files in my project:

main.c:

#include <stdio.h>
#include <stdlib.h>
#include "tail.h"

#define MAXLINES 100
#define LINESIZE 100

int main(int argc, char *argv[]) {
    int linesNumber = 10;

    if(argc > 2) {
        return 1;
    }
    else if(argc == 2) {
        linesNumber = atoi(argv[1] + 1);

        if(linesNumber == 0) {
            return 0;
        }

        initQueue(linesNumber, LINESIZE);
    }
    else {
        initQueue(linesNumber, LINESIZE);
    }

    readLines(LINESIZE, MAXLINES);

    printQueueElements();

    return 0;
}

linesNumber represent the variable that will store the size of the queue. By default this variable is 10. If the value of the symbolic argument is 0 there is no reasone to continue reading lines, so the program will terminate execution.

queue.c

#include <stdio.h>
#include <string.h>
#include "alloc.h"

static char **queue;
static int queueSize;

static int head = -1;
static int rear = -1;

static int isEmpty(void) {
    return (head == -1 && rear == -1);
}

static int isFull(void) {
    return (rear + 1) % queueSize == head ? 1 : 0; 
}

void initQueue(int lineNumbers, int sizeOfEachLine) {
    int i;

    queue = palloc(lineNumbers);
    queueSize = lineNumbers;

    for(i = 0; i < lineNumbers; i++) {
        queue[i] = alloc(sizeOfEachLine);
    }
}

char *dequeue(void) {
    char *returnValue;

    if(isEmpty()) {
        return NULL;
    }
    else if(head == rear) {
        returnValue = queue[head];
        head = -1;
        rear = -1;

        return returnValue;
    }

    returnValue = queue[head];
    head = (head + 1) % queueSize;

    return returnValue;    
}

void enqueue(char *source) {
    if(isFull()) {
        dequeue();
    }

    if(isEmpty()) {
        rear = 0;
        head = 0;
    }
    else {
        rear = (rear + 1) % queueSize;
    }

    strcpy(queue[rear], source);
}

void printQueueElements(void) {
    while(!isEmpty()) {
        printf("%s", dequeue());
    }
}

This is an array based implementation of a queue. I use the circular array data structure for my queue.

When the queue is full, enqueue will call dequeue to make space for the incoming element.

printQueueElements will dequeue each element and print it, since I don't need anymore the lines.

readlines.c:

#include <stdio.h>
#include "alloc.h"
#include "tail.h"

static int getLine(char *source, int lim) {
    int c;
    int i;

    c = getchar();
    lim--; /* 1 space for null charachter  */

    for(i = 0; c != EOF && c != '\n' && lim > 0; i++, c = getchar(), lim--) {
        source[i] = c;
    }

    if(c == '\n') {
        source[i] = '\n';
        i++;
    }

    source[i] = '\0';
    return i;
}

void readLines(int lineSize, int maxLines) {
    char *temp = alloc(lineSize);

    for(; maxLines && getLine(temp, lineSize); maxLines--) {
        enqueue(temp);
    }
}

This function will read each line and enqueue it.

alloc.c

#include <stdio.h>

#define ALLOCSIZE 10000

static char allocBuf[ALLOCSIZE];
static char *allocp = allocBuf; /* next free position  */

char *alloc(int allocSize) {
    if(allocBuf + ALLOCSIZE - allocp >= allocSize) {
        allocp += allocSize;
        return allocp - allocSize;
    }
    else {
        return NULL;        
    }
}

This function will return a pointer to a block of allocSize chars.

palloc.c

#include <stdio.h>

#define BLOCKSIZE 100000

static char *sharedBlock[BLOCKSIZE];
static char **pSharedBlock = sharedBlock;

char **palloc(int size) {
    if(sharedBlock + BLOCKSIZE - pSharedBlock >= size) {
        pSharedBlock += size;
        return pSharedBlock - size;
    }
    else {
        return NULL;
    }
}

This function wil return a pointer to a block of size pointers to char.

palloc and alloc are used to set the size of the queue dynamically. The malloc function was not introduced at this point, so I don't think it will be a valid solution if I use this function.

alloc.h

char *alloc(int);
char **palloc(int);

tail.h

/* input functions */

void readLines(int lineSize, int maxLines);

/* queue related functions  */

void initQueue(int lineNumbers, int sizeOfEachElement);
void enqueue(char *source);
void printQueueElements(void);

char *dequeue(void);
int getSimbolicArgValue(char* source);

Answer 1

I don't think the program meets the requirements (i.e. "behave rationally no matter how unresonable the input") because it fails if the line size is greater than LINESIZE.

To behave rationally it would perhaps, ideally:

• At least detect if a line is "too large" and fail properly
• Or, properly handle a huge line (which fits on disk but is too large to fit in memory)

I'd suggest writing 2 versions.

1. The first version should guess how long each line is (e.g. 200 bytes). If the user asks for 10 lines, it should therefore fseek to the last 2000 bytes of the file, try to parse the last 2000 bytes, and display the result if successful.

   If it doesn't find the right number of lines in the last 2000 bytes, then either try again with the previous 2000 bytes, or fail over to scanning the entire file.

2. When it scans the entire file, it should remember the start (byte offset) of the most recent 10 lines, so that when it reaches the end of the file it can print the end of the file from the 10th-most-recent byte offset. I see no need to remember the contents of each line.

The first is just a speed optimization for normal large files (assuming that fseek is faster than parsing). If it just needs to be correct instead of fast then only implement the 2nd version.

---

tail usually accepts a filename as an input parameter, and files are usually seekable.

If it's reading from stdin then stdin may not be seekable, in which you case you must buffer the lines which you read (and intend to print) in memory.

---

I don't fully agree with your decision not to use malloc.

If you want to use your palloc function I think it has too many pointers (surely you want an array of bytes, not an array of byte-pointers), and should be like this instead:

#define BLOCKSIZE 100000

static char sharedBlock[BLOCKSIZE];
static size_t alreadyAllocated;

char *palloc(int size) {
    if(size + alreadyAllocated <= BLOCKSIZE) {
        char* rc = &sharedBlock[alreadyAllocated];
        alreadyAllocated += size;
        return rc;
    }
    else {
        return NULL;
    }
}

---

I haven't analyzed/inspected your readline.c and queue.c in detail.

Answer 2

That is a lot of code for the job. It can be done significantly more easily in two areas:

• use an array instead of a queue
• use the POSIX function, getline, which will handle lines of any size.

If you don't want to use getline (which admittedly might not have existed when K&R wrote their book), concentrate on writing its equivalent.

Here is a version that uses an allocated array or char* pointers. The array is zeroed (by calloc) so that we can tell whether the entry holds a line (which might not be so if the input is less than 10 (or the requested number of) lines.

int
tail(size_t n_lines, FILE *fp)
{
    char **lines = calloc(sizeof(char*), n_lines);
    if (!lines) {
        perror("calloc");
        return -1;
    }
    size_t size = 0;
    size_t in = 0;
    for (char *ln = 0; getline(&ln, &size, fp) > 0; in = (in + 1) % n_lines) {
        if (lines[in]) {
            free(lines[in]);
        }
        lines[in] = ln;
        ln = NULL;
        size = 0;
    }
    for (size_t i = 0; i < n_lines; ++i) {
        if (lines[in]) {
            printf("%s", lines[in]);
            free(lines[in]);
        }
        in = (in + 1) % n_lines;
    }
    free(lines);
    return 0;
}

Answer 3

For a general tail implementation, there are two distinct cases that have very different optimal solutions:

• When the input is seekable, you can read it backwards from the end (by seeking to the end and then repeatedly reading a block of, say, a couple of kilobytes and seeking backwards to the previous block) to find the beginning of the n-th last line, and then just read and print the content of the file starting from that position. Done properly, this will allow you to solve the problem using a constant amount of memory.

• If the input is not seekable, you'll have to read it sequentially and buffer the n last lines you've seen so far. The task, then, is to do this as efficiently as possible.

  As the other answers have pointed out, you cannot generally assume an upper limit on the length of a line; it's quite possible to have a file with several gigabytes of text and no line breaks at all, making it all one long line. The simplest solution to this issue is probably to use POSIX getline(); if you can't or don't want to use it, you'll have to implement your own e.g. using fgets() and realloc().

  Alternatively, you could simply allocate a circular buffer to store the last k bytes of the file, while keeping track (in another circular buffer) of the starting positions of the last n lines in it. Before reading each new block of input, check if you have room to do so without overwriting the n-th last line; if not, increase (e.g. double) the buffer size with realloc().

  If you really want to optimize you code for the worst case, you could, if the buffer gets too large, even consider switching to a different storage method where you split the buffer into chunks of, say, a few megabytes each, and store each of them in an mmap()ed temp file. The main advantage of this method (over just letting the OS swap out parts of your buffer) is that you can efficiently discard old swapped-out data just by unmapping the file without having to first read it back into RAM. However, this is probably getting a bit too advanced for this exercise.