2
\$\begingroup\$

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:      Alex Ferguson (highentropystring@gmail.com)
 * 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: %d\n", 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;
}
\$\endgroup\$
1
\$\begingroup\$

... 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 ...?

No - The idea of 1) grouping many blocks, versus 2) all blocks, versus 3) 1 block is trying to outsmart the system's malloc(). Focusing on designing the higher level code and let the allocator deal with memory management. This goes against this code's overall design goal, so following will try to live with the objective.

The biggest waste I see is if code used many queue_t that were to all be initially empty, this would fail OP block_num <= 0, obliging to create many non-zero memory size queue. In other words, let the queue grow as needed starting at 0.

Should I have used a fixed size of block or was it a good idea to let the user define it?

Simple drop the block size - that it - let it be 1.

If a fixed size would be better how should I determine what it should be?

See above.

Is this code up to par? ... could be done faster or in a way that is more memory efficient?

Certainly code can be more memory efficient, yet rarely is the goal unto itself. It is a balance. So is it efficient within the balance?

The biggest objection is the potential "chatter" of allocating/free'ing if the queue active size was near a block boundary. A hysteresis could avoid that. Only shrink when 25% latest peak. On a shrink, set the peak to 200% current size.

Are there any reasons why this code might be difficult to use ...?

The set-up is more limiting than I would care for to use in general. The only parameter needed is the size of the object. For queues of fixed length, I'd uses a single allocation for all the queue elements and control members.

// queue_init(unsigned int block_num, size_t block_size, size_t element_width)
queue_init(size_t element_width)

Other notes:

Nice dqueue.h set-up. Except I'd avoid #define MEM_ERROR, SIZE_ERROR, .... names as too likell to collide. Perhaps QUEUE_MEM_ERROR ....

Why call the type queue_t, prefix functions queue_... and then call the file dqueue.h. dqueue.c? I'd expect consitency - use queue.h. queue.c or change code.

I'd expect a function to return the current queue usage. (enrollments in queue)

Code looks tolerant of queue_destroy(queue); queue_destroy(queue);. This is good design and reflects well on the design of queue_destroy().

I am not a big fan of embedding fprintf(stderr, ... inside functions yet some error handling plan should be implemented and at least this code has one.

\$\endgroup\$
  • \$\begingroup\$ Thanks @chux! So you're saying that it would be more efficient to simply have one main block and then allocate individual pieces the exact size of the element to be stored as needed? I would have thought that making a call to malloc every time you need to store just one element and calling free every time you want to pop an element would be quite expensive performance wise, wouldn't it? What am I missing here? \$\endgroup\$ – DemonessJess Dec 23 '17 at 23:40
  • \$\begingroup\$ @psychedelic_alex Yes, more complex. Of course, allocate when needed, but by how much? Either a traditional 1 linked block for each new element or allocate in a power like series of 1,2,4,8, .... The free'ing could do the traditional of 1 to 1, but as eluded, the lower threshold could be as described (25% peak) with min thresholds - or even not at all until destroyed or the higher level code commanded a queue_right_size(). - lastly - avoid adding a layer on alloc()/realloc()/free() \$\endgroup\$ – chux Dec 23 '17 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.