As per K & R exercise 5-13
Write the program tail, which prints the last n lines of its input. By default, n is 10, say, but it can be changed by an optional argument, so that
tail -n
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of 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.
I've written my own version of tail in C. It uses a newer version of a library for a dynamic queue that I also wrote and submitted here before (I've made a lot of changes to it since then). I'd like to get some feedback on how my code performs, both memory wise and speed wise, and how I might improve this in the future. I've compared its performance to the GNU implementation of tail and found that for small files my program uses less memory but for larger files it uses a fair bit more (although I did find that GNU tail leaks memory - 96 bytes according to Valgrind) and I was hoping I could get some insight as to how it does this better.
tail.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dqueue.h>
#define MAX_LEN 256
#define MAX_LINES 32
#define DEFAULT_TAIL 10
int getlinep(char *s, int lim);
int main(int argc, char *argv[])
{
char *line;
char *temp;
int tail_len = DEFAULT_TAIL;
queue_t * queue = NULL;
int elements;
int len;
if(!(queue = queue_init(sizeof(char *)))) {
fprintf(stderr, "Error %d: Could not initialise queue!\n", MEM_ERROR);
return MEM_ERROR;
}
if(argc >= 2) {
if(atoi(*(++argv))) {
tail_len = -atoi(*argv);
if(tail_len <= 0 || tail_len > MAX_LEN)
tail_len = DEFAULT_TAIL;
}
}
for(elements = 0; elements < tail_len; elements++) {
if(!(line = malloc(MAX_LEN))) {
fprintf(stderr, "Error: Memory allocation failure!\n");
return MEM_ERROR;
}
if(!getlinep(line, MAX_LEN)) {
free(line);
if(elements == 0) {
queue_destroy(&queue);
return EXIT_SUCCESS;
}
break;
}
queue_push(&line, queue);
}
if(elements == tail_len) {
if(!(temp = malloc(MAX_LEN))) {
fprintf(stderr, "Error: Memory allocation failure!\n");
return MEM_ERROR;
}
for(;;) {
if(!(len = getlinep(temp, MAX_LEN))) {
free(temp);
break;
}
queue_pop(&line, queue);
memcpy(line, temp, len + 1);
queue_push(&line, queue);
}
}
while(elements-- > 0) {
queue_pop(&line, queue);
printf("%s", line);
free(line);
}
queue_destroy(&queue);
return EXIT_SUCCESS;
}
int getlinep(char *s, int lim)
{
int i;
for(i = 0; i < lim - 1 && (*s = getchar()) != EOF && *s != '\n'; i++, s++)
;
if(*s == '\n') {
s++;
i++;
}
*s = '\0';
return i;
}
dqueue.h
#ifndef DQUEUE_H
#define DQUEUE_H
#include <stdlib.h> /* Needed for size_t */
#define QUEUE_OK 0
#define MEM_ERROR -1 /* Memory allocation error */
#define SIZE_ERROR -2 /* Queue dimension error */
#define INDEX_ERROR -3 /* No data at given index */
#define BLOCK_SIZE 1024
typedef struct queue_element_t
{
void * data; /* Contains the data stored at this node */
void * next; /* Contains the pointer to the next element, or NULL if it's the tail node */
} queue_element_t;
typedef struct
{
queue_element_t * head; /* Pointer to the head of the queue */
queue_element_t * tail; /* Pointer to the tail of the queue */
size_t size; /* The number of elements in the queue */
size_t element_width; /* The size of each element in the queue */
size_t tail_pos; /* The byte offset of the data being pushed into the queue (i.e. in the tail block) */
size_t head_pos; /* The byte offset of the data being popped out of the queue (i.e. in the head block) */
int status;
} queue_t;
queue_t * queue_init(size_t element_size); /* Initialise the queue data structure */
void queue_pop(void * const element, queue_t * queue); /* Pop an element from the front of the queue, deals with cleanup when the head node is empty */
int queue_push(const void * const element, queue_t * queue); /* Push an element to the back of the queue, creates a new block when tail node is full */
int queue_debug(const queue_t * const queue); /* Print information about the queue, returns the queue status if a valid queue pointer is given */
void queue_destroy(queue_t * queue); /* Destroy the queue data structure and any associated nodes */
#endif
dqueue.c
/*
* Filename: dqueue.c
* Author: Jess Turner
* Date: 17/02/18
* Licence: GNU GPL V3
*
* Library for a lightweight, generic, and dynamically allocated queue
*
* Return/exit codes:
* QUEUE_OK - No error
* SIZE_ERROR - Queue size error (invalid block size or number of elements)
* MEM_ERROR - Memory allocation error
* INDEX_ERROR - Couldn't pop data from the queue
*
* All functions returning pointers will return NULL on memory allocation faliure, else they will specify an error in queue->status for the user to handle
*
* Todo:
* - Add secure versions of queue_destroy() and queue_pop() to overwrite memory blocks that are no longer in use
*
*/
#include <dqueue.h>
#include <stdio.h>
#include <string.h>
queue_t * queue_init(size_t element_width)
{
queue_t * queue;
if(!(queue = malloc(sizeof(queue_t))))
return NULL;
if(BLOCK_SIZE % element_width != 0 || (queue->element_width = element_width) <= 0) {
queue->status = SIZE_ERROR;
return queue;
}
queue->tail_pos = 0;
queue->head_pos = 0;
queue->tail = NULL;
queue->head = NULL;
queue->size = 0;
queue->status = QUEUE_OK;
return queue;
}
void queue_destroy(queue_t * queue)
{
queue_element_t * temp;
if(queue == NULL)
return;
while(queue->head) {
free(queue->head->data);
temp = queue->head->next;
free(queue->head);
queue->head = temp;
}
queue->size = 0;
queue->status = 0;
queue->element_width = 0;
queue->tail_pos = 0;
queue->head_pos = 0;
queue->tail = NULL;
free(queue);
}
int queue_push(const void * const element, queue_t * queue)
{
queue_element_t * new_element;
if(queue->tail_pos == 0) {
if(!(new_element = malloc(sizeof(queue_element_t)))) {
queue->status = MEM_ERROR;
return queue->status;
}
if(!(new_element->data = malloc(BLOCK_SIZE))) {
free(new_element);
queue->status = MEM_ERROR;
return queue->status;
}
if(queue->head == NULL)
queue->head = new_element;
else
queue->tail->next = new_element;
queue->tail = new_element;
queue->tail->next = NULL;
queue->size++;
}
memcpy(queue->tail->data + queue->tail_pos, element, queue->element_width);
queue->tail_pos += queue->element_width;
if(queue->tail_pos >= BLOCK_SIZE)
queue->tail_pos = 0;
return queue->status;
}
void queue_pop(void * const element, queue_t * queue)
{
queue_element_t * temp;
if(queue->head == NULL || ((queue->head == queue->tail) && (queue->head_pos == queue->tail_pos))) {
if(queue->tail_pos == 0) { /* Catch an error related to reseting the tail position and incrementing a block after a block has been filled */
queue->tail_pos = BLOCK_SIZE;
} else {
queue->status = INDEX_ERROR;
return;
}
}
memcpy(element, queue->head->data + queue->head_pos, queue->element_width);
queue->head_pos += queue->element_width;
if(queue->head_pos >= BLOCK_SIZE) {
free(queue->head->data);
temp = queue->head;
queue->head = queue->head->next;
free(temp);
queue->head_pos = 0;
queue->size--;
}
}
int queue_debug(const queue_t * const queue)
{
if(queue == NULL) {
printf("Error: Invalid queue pointer!\n");
return MEM_ERROR;
}
if(queue->status == QUEUE_OK) {
printf("Queue is %d blocks long with an element width of %d bytes with each block containing %d elements\nQueue head is at %p and the current element is %p\n", (int)queue->size, (int)queue->element_width, BLOCK_SIZE / (int)queue->element_width, (void *)queue->head, (void *)queue->tail);
} else if(queue->status == MEM_ERROR) {
printf("Memory error in queue!\n");
} else if(queue->status == SIZE_ERROR) {
printf("Size error in queue!\n");
} else if(queue->status == INDEX_ERROR) {
printf("Index error in queue!\n");
}
return queue->status;
}
queue_debug()
, why codeprintf("... %d ...\n", (int)queue->size, ...);
versusprintf("... %zu ...\n", queue->size, ...);
? I am confident you are aware of"%zu"
andsize_t
as you rightly coded"%p"
with avoid*
casted pointer. \$\endgroup\$