dqueue - A dynamic FIFO queue library for C

This is the first draft of dqueue, a dynamic queue library written in C, with a sample program to demonstrate it.

This is my first time writing any sort of library to be used as a generic subsection of other projects, so I’m sort of guessing as to what additional considerations I should have taken. The only major ones I made were to make the queue capable of taking any type of data, and having the queue functions set a value corresponding to the status of the queue so that even if something goes badly wrong it should be pretty apparent what it was and easy to fix.

The queue structure queue_t can hold any data type you want it to. Data is added the the queue by the queue_push() function, and data is retrieved from the queue with the queue_pop() function. When the queue fills up through calls to queue_push(), the library attempts to allocate a new block of memory tot the queue, and when a block is empty due to successive calls to queue_pop() the queue frees the block. When the queue is finished with, all the memory still assigned to it can be free’d with a call to queue_destroy(). In future, this function will also be able to optionally zero all the data associated with the queue.

I attempted to get a bit of a balance between performance and memory usage by having the program allocate blocks containing many data points instead of individual data points as needed. Was this a good solution to this? Should I have used a fixed size of block or was it a good idea to let the user define it? If a fixed size would be better how should I determine what it should be?

The program has been tested with Valgrind with a wide number of set ups and I’m yet to find any way of setting up the queue that produces errors that aren’t the end users fault (i.e. telling the library to use the wrong size of data to what it is then fed, or asking for a negative number of blocks to be allocated).

Is this code up to par? It does what I intended it to do, but I wonder about whether or not this could be done faster or in a way that is more memory efficient? Are there any reasons why this code might be difficult to use for someone else? It is intended as a library of sorts so that’s quite important.

dqueue.h

#ifndef DQUEUE_H
#define DQUEUE_H

#include <stdlib.h>

#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 index */

#define DEFAULT_BLOCK 256           /* By default use 256 bytes per block */

typedef struct {
    char ** base_p;                 /* Base pointer of the queue */
    unsigned int cur_block;         /* Index of the block containing the first element */
    unsigned int cur_block_pos;     /* Position of the first element within the block */
    unsigned int last_block;        /* Index of the block containing the last element */
    unsigned int last_block_pos;    /* Position of the last element within the block */
    unsigned int total_blocks;      /* Total number of blocks ever allocated to the queue */
    size_t block_size;              /* Number of elements in each block */
    size_t element_width;           /* Size of each element */
    int status;                     /* Status of the queue */
} queue_t;

queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_size);   /* Initialise the queue data structure and return a pointer to the first element */
void * queue_pop(queue_t * queue);                                                      /* Pop an element from the front of the queue */
int queue_push(const void * const element, queue_t * queue);                            /* Push an element to the back of the queue */
int queue_debug(const queue_t * const queue);                                           /* Dump information about the queue  */
void queue_destroy(queue_t * queue);                                                    /* Destroy the queue data structure */

#endif

dqueue.c

/* 
 * Filename:    dqueue.c
 * Author:      Jess Turner
 * Date:        13/10/17
 * Licence:     GNU GPL V3
 *
 * Library for a generic, dynamically allocated queue
 *
 * Functions:
 * queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_size);    - Initialise the queue data structure and return a pointer to the first element 
 * void * queue_pop(queue_t * queue);                                                       - Pop an element from the front of the queue
 * int queue_push(const void * const element, queue_t * queue);                             - Push an element to the back of the queue
 * int queue_debug(const queue_t * const queue);                                            - Dump information about the queue 
 * void queue_destroy(queue_t * queue);                                                     - Destroy the queue data structure
 *
 * 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
 *
 * Todo:
 * 
 */

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

queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_width)
{
    queue_t * queue;
    unsigned int i, j;

    if(block_size == 0)
        block_size = DEFAULT_BLOCK;

    if(!(queue = malloc(sizeof(queue_t))))
        return NULL;

    if((queue->block_size = block_size) <= 0 || (queue->total_blocks = block_num) <= 0 || (queue->element_width = element_width) <= 0) {
        queue->status = SIZE_ERROR;
        return queue;
    }

    if(!(queue->base_p = malloc(queue->total_blocks * sizeof(char *)))) {
        queue->status = MEM_ERROR;
        return queue;
    }

    for(i = 0; i < queue->total_blocks; i++) {
        if(!(queue->base_p[i] = malloc(queue->block_size * queue->element_width))) {
            fprintf(stderr, "Error: Could not allocate memory!n");
            
            for(j = 0; j < i; j++)
                free(queue->base_p[i]);

            free(queue->base_p);
        }
    }

    queue->cur_block = queue->last_block = 0;
    queue->cur_block_pos = queue->last_block_pos = 0;
    queue->status = QUEUE_OK;

    return queue;
}

void queue_destroy(queue_t * queue)
{
    while(queue->cur_block < queue->total_blocks)
        free(queue->base_p[queue->cur_block++]);
    
    queue->cur_block        = 0;
    queue->cur_block_pos    = 0;
    queue->last_block       = 0;
    queue->last_block_pos   = 0;
    queue->total_blocks     = 0;
    queue->block_size       = 0;
    queue->element_width    = 0;
    queue->status           = 0;

    free(queue->base_p);
    queue->base_p           = NULL;
    free(queue);
}

int queue_push(const void * const element, queue_t * queue)
{
    memcpy(queue->base_p[queue->last_block] + queue->last_block_pos * queue->element_width, element, queue->element_width);

    if(queue->last_block == (queue->total_blocks - queue->cur_block) - 1 && queue->last_block_pos == queue->block_size - 1) {
        queue->total_blocks++;
        queue->last_block++;
        queue->last_block_pos = 0;

        if(!(queue->base_p = realloc(queue->base_p, (queue->total_blocks - queue->cur_block) * sizeof(void *)))) {
            fprintf(stderr, "Error: Could not reallocate memory!n");
            queue->status = MEM_ERROR;
            queue->total_blocks--;
            queue->last_block--;
            queue->last_block_pos = queue->block_size - 1;
            return MEM_ERROR;
        }

        if(!(queue->base_p[queue->last_block] = malloc(queue->block_size * queue->element_width))) {
            fprintf(stderr, "Error: Could not allocate memory!n");
            queue->total_blocks--;
            queue->last_block--;
            queue->last_block_pos = queue->block_size - 1;
            queue->status = MEM_ERROR;
            return MEM_ERROR;
        }
    } else if(queue->last_block_pos == queue->block_size - 1) {
        queue->last_block++;
        queue->last_block_pos = 0;
    } else {
        queue->last_block_pos++;
    }
    
    return QUEUE_OK;
}

void * queue_pop(queue_t * queue)
{
    void * data;

    if(queue->last_block == queue->cur_block && queue->cur_block_pos == queue->last_block_pos) {
        fprintf(stderr, "Error: Queue empty!n");
        queue->status = INDEX_ERROR;
        return NULL;
    }

    if(!(data = malloc(queue->element_width))) {
        fprintf(stderr, "Error: Could not allocate memory!n");
        queue->status = MEM_ERROR;
        return NULL;
    }

    if(queue->cur_block_pos == queue->block_size - 1) {
        memcpy(data, queue->base_p[queue->cur_block] + queue->cur_block_pos * queue->element_width, queue->element_width);
        free(queue->base_p[queue->cur_block]);

        queue->cur_block++;
        queue->cur_block_pos = 0;
    } else {
        memcpy(data, queue->base_p[queue->cur_block] + queue->cur_block_pos * queue->element_width, queue->element_width);
        queue->cur_block_pos++;
    }

    return data;
}

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 has %d blocks of size %d and each element is %d bytes wide!n", (queue->total_blocks - queue->cur_block), (int)queue->block_size, (int)queue->element_width);
    else if(queue->status == MEM_ERROR)
        printf("Memory error in queue!n");
    else if(queue->status == SIZE_ERROR)
        printf("Size error in queue");

    return queue->status;
}

main.c

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

#define EXEC_SUCCESS 0

int main()
{
    queue_t * queue = NULL;
    unsigned int blocks = 8192;
    int block_size = 1024;
    int new_element = 0;
    int * returned_element;
    int i;

    if(!(queue = queue_init(blocks, block_size, sizeof(int)))) {
        fprintf(stderr, "Error %d: Could not initialise queue!n", MEM_ERROR);
        return MEM_ERROR;
    }

    if(queue->status != QUEUE_OK) {
        fprintf(stderr, "General queue error: %dn", queue->status);
        return queue->status;
    }

    for(i = 33554432; i > 0; i--, new_element++)
        queue_push(&new_element, queue);

    for(i = 33554432; i > 0; i--) {
        if((returned_element = queue_pop(queue)) == NULL) {
            fprintf(stderr, "Error %d: Could not pop queue!n", queue->status);
            break;
        }

        free(returned_element);
    }

    queue_destroy(queue);

    return EXEC_SUCCESS;
}