Unix tail command using stack

Question

I'm working on a version of the Unix tail command that works by iterating over a file, pushing line by line into a stack. Finally, the number of desired lines will be popped and printed to the screen. I have used void * (void pointers) as the data field of my stack nodes (the stack is basically a linked list with limitations) and due to that I had to do a bit of work with pointer casting and successive allocations with malloc() (one chunk per line). I wonder if there isn't a better (as in simpler, more readable and less memory intensive) way of accomplishing the same goal.

Main tail.c file

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../utils/type_definitions.h"
#include "../stack/stack_list/stack_list.h"
#define LINE_SIZE 256

int main(int argc, char *argv[])
{

  int number_of_lines;
  if (argc == 2) {
    number_of_lines = atoi(argv[1]);
  } else {
    printf("%s\n", "Error!");
    exit(1);
  }

  FILE *f;
  if (!(f = fopen("file.txt", "r"))) {
    printf("%s\n", "Error opening file!\n");
    exit(1);
  };

  // pushing lines into stack

  int i = 0;
  char *line, *temp = (char*)malloc(LINE_SIZE);
  Node *stack = stack_new();

  while (fgets(temp, sizeof(line), f) != NULL) {
    line = (char*)malloc(LINE_SIZE);
    strcpy(line, temp);
    stack_push((void*)line, &stack);
  }

  // poping and printing n lines to screen

  for (int i = 0; i < number_of_lines; i++) {
    printf("%s\n",(char*)stack_top(stack));
    stack_pop(&stack);
  }

  return 0;
}

Stack header file

#ifndef __STACK_H__
#define __STACK_H__

#include <stdbool.h>
#include "../../utils/type_definitions.h"

Node *stack_new();
void *stack_top(Node *head);
void stack_pop(Node **head);
bool stack_is_empty(Node *head);
void stack_push(void *x, Node **head);

#endif

Implementation of stack functions

Node *stack_new() {
    return NULL;
}

bool stack_is_empty(Node *head) {
    return head == NULL;
}

void *stack_top(Node *head) {
    return head->data;
}

void stack_pop(Node **head)
{
    if (*head == NULL) return;
    Node *temp = *head;
    *head = (*head)->next;
    free(temp);
}

void stack_push(void *x, Node **head)
{
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = x;
    new_node->next = *head;
    *head = new_node;
}

Edit - following are the includes missing from the file "implementations of stack functions".

#include "stack_list.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

Answer 1

• The stack approach is dubious. It uses too much memory (the entire file is eventually collected, while you only care about its tail). Consider a ring buffer instead.

• I don't see the point of #include <stdbool.h>

• Casting is unnecessary, as in (char*)stack_top(stack) - and even dangerous, as in (Node*)malloc(sizeof(Node)). Why you shouldn't cast malloc.

• Always test that malloc doesn't return NULL.

• A declaration

  int i = 0;
  

  is unnecessary.

• Nitpicking. #define LINE_SIZE 256 is a very optimistic estimate. Try to manage a file with really long lines.

Answer 2

You already have a good review with most of the points I was going to make (thanks vnp!). A few that aren't mentioned there:

• We need a definition of NULL before we use it. I recommend #include <stdlib.h>, for reasons evident in the next point.
• We need a declaration of malloc() before we use it. (This may be the reason you were casting the return value - that's wrong and dangerous). Both malloc() and free() are declared by #include <stdlib.h>.
• We need to include <stdio.h> for fopen() and printf().
• There's no checking that argv[1] converts to a positive integer. Since 0 isn't a useful value for input, we can work with atoi()'s appalling interface here, and error if number_of_lines <= 0.

• Error messages should go to stderr, not stdout. And to print a fixed line of text, we can use plain fputs() instead of the more heavyweight fprintf():

    fputs("Error!", stderr);
    return 1;
  

• We can use perror() to get more informative messages following errors that set errno:

  FILE *f = fopen("file.txt", "r");
  if (!f) {
      perror("file.txt");
      return EXIT_FAILURE;
  };
  

• Why are we opening a specific file anyway? That's very inflexible. It's more useful (and easier for us) to accept standard input, so we can operate within a pipeline.

• What is sizeof line doing in the fgets() call? line is a char*, but you probably want to read up to LINE_SIZE characters per line. At present, the code behaves very badly when the input has lines longer than 6 characters on my system (and on systems with 4-byte char*, lines longer than 2 chars would be a problem).

  while (fgets(temp, sizeof(line), f) != NULL) {
  

  It's also inefficient to read into temp only to allocate and copy into line - better to allocate first and read directly into line with no need for the copy.

• Memory allocated for temp has no free() - this could be fixed simply by making it a char[] instead of dynamically allocated. None of the lines read into the stack have a corresponding free(), and none of the stack nodes read but not printed has a free() - all meaning that we leak a vast amount of memory.
• When finally printing the contents, why add extra newlines in between each line of input? I'm not convinced that you've done any testing at all here.

---

Here's a slightly rewritten version fixing some of the above (but still not addressing the problem of storing far too much of the input):

int main(int argc, char *argv[])
{
    if (argc < 2) {
        fprintf(stderr, "usage: %s LINES\n", argv[0]);
        return EXIT_FAILURE;
    }

    int number_of_lines = atoi(argv[1]);
    if (number_of_lines <= 0) {
        fputs("LINES must be a positive number\n", stderr);
        return EXIT_FAILURE;
    }

    FILE *f = fopen("file.txt", "r");
    if (!f) {
        perror("file.txt");
        return EXIT_FAILURE;
    };

    // push lines into stack
    Node *stack = stack_new();
    for (;;) {
        char *line = malloc(LINE_SIZE);
        if (!line) {
            fputs("Out of memory\n", stderr);
            return EXIT_FAILURE;
        }
        if (!fgets(line, LINE_SIZE, f)) {
            /* assume end of file */
            free(line);
            break;
        }
        stack_push(line, &stack);
    }

    // pop and print n lines to screen
    for (int i = 0; i < number_of_lines; i++) {
        char *line = stack_top(stack);
        fputs(line, stdout);
        free(line);
        stack_pop(&stack);
    }

    // free the remainder of the stack
    while (stack) {
        free(stack_top(stack));
        stack_pop(&stack);
    }
}

Answer 3

ARRAY_SIZE()

Never use sizeof directly to get the size of an array. NEVER. It's very unsafe, as you can see in the bug that Toby found.

Alternatives:

• Pass the actual value
• Pass the result of ARRAY_SIZE(arr) (defined typically as #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])))

If you can use the second one, which is when you have a global static-duration array or an array local to the function, it's the best method, because if the size of the array is changed (for example if I had int a[FOO]; and then I decide to use a different size such as int a[BAR];), I don't need to change the rest of the code. And with recent compilers, such as GCC 8, you will receive a warning if you apply that to something that is not an array, so it is safe. With old compilers, there are still tricks to make this macro safe (you can find them in StackOverflow easily).

while (fgets(temp, ARRAY_SIZE(temp), f) != NULL) {

It was also misleading that you used sizeof a different array.

If you had written this code (and the definition of ARRAY_SIZE was a safe one for your compiler version), it would have not compiled, and you would have noticed that you don't have an array, so you would have had to write the actual value.