#StackBounty: #performance #c #memory-management Tail implementation using a dynamic queue library in C

Bounty: 50

As per K & R exercise 5-13 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);
        }
    }

    for(; elements > 0; elements--) {
        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 = '';

    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:      Alexis Ferguson (highentropystring@gmail.com)
 * 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 elementsnQueue head is at %p and the current element is %pn", (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;
}


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.