3
\$\begingroup\$

I need a queue in C for an embedded application in which I cannot allocate memory dynamically.

I avoided using void* for the queue elements (which is not convenient lifecycle-wise) by having the user provide their underlying array.

user_code.c:

#include "generic_queue.c"

typedef struct custom_t
{
    /* whatever */
} custom_t;

custom_t underlying_array[5];
queue_t queue;
queue_init(&queue, underlying_array, 5, sizeof(custom_t));

/* now use queue to do stuff */

generic_queue.h:

#ifndef INCLUDE_GUARD_GENERIC_QUEUE_H
#define INCLUDE_GUARD_GENERIC_QUEUE_H

#include <stddef.h>
#include <stdbool.h>
#include <pthread.h>

typedef struct queue_t
{
    void* array;
    size_t capacity;
    size_t sizeof_element;
    size_t in;
    size_t out;
    pthread_mutex_t mutex;
} queue_t;


/* return true on success */
bool queue_init(queue_t* queue, void* array, size_t capacity, size_t sizeof_element);
bool queue_front(queue_t * queue, void *dest);
bool queue_back(queue_t * queue, void *dest);
bool queue_push(queue_t *queue, void const *src);
bool queue_pop(queue_t *queue, void *dest);

/* assert on failure */
size_t queue_size(queue_t * queue);
size_t queue_capacity(queue_t * queue);
bool queue_empty(queue_t * queue);
bool queue_full(queue_t * queue);

#endif /* INCLUDE_GUARD_GENERIC_QUEUE_H */

genric_queue.c:

#include "generic_queue.h"

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h> /* memcpy */
#include <assert.h>
#include <pthread.h>


bool queue_init(queue_t* queue, void* array, size_t capacity, size_t sizeof_element)
{
    bool success;
    
    if ((queue == NULL) || (array == NULL) || (capacity < 2) || (sizeof_element == 0))
    {
        success = false;
    }
    else
    {
        pthread_mutex_lock(&queue->mutex);
        
        queue->array = array;
        queue->capacity = capacity;
        queue->sizeof_element = sizeof_element;
        queue->in = 0;
        queue->out = 0;
        success = true;
        
        pthread_mutex_unlock(&queue->mutex);
    }
    
    return success;
}

static void* index_to_address(queue_t const * queue, size_t index)
{
    void* address;
    assert(queue != NULL);
    
    /* No mutex here: this is an internal utility function */
    address = ((unsigned char*)queue->array) + (index * queue->sizeof_element);
    
    return address;
}

/* When used internally, mutex might be already locked, so an additional
 * "private" `lock_mutex` argument is needed */
static bool queue_front_internal(queue_t * queue, void *dest, bool lock_mutex)
{
    bool success;
    void *src;
    
    if ((queue == NULL) || (queue_empty(queue)) || (dest == NULL))
    {
        success = false;
    }
    else
    {
        if (lock_mutex) pthread_mutex_lock(&queue->mutex);
        
        src = index_to_address(queue, queue->out);
        memcpy(dest, src, queue->sizeof_element);
        success = true;
        
        if (lock_mutex) pthread_mutex_unlock(&queue->mutex);
    }
    return success;
}

bool queue_front(queue_t * queue, void *dest)
{
    return queue_front_internal(queue, dest, true);
}

bool queue_back(queue_t * queue, void *dest)
{
    bool success;
    size_t index;
    void *src;
    
    if ((queue == NULL) || (queue_empty(queue)) || (dest == NULL))
    {
        success = false;
    }
    else
    {
        pthread_mutex_lock(&queue->mutex);
        
        index = (queue->in == 0) ? queue->capacity - 1 : queue->in - 1;
        src = index_to_address(queue, index);
        memcpy(dest, src, queue->sizeof_element);
        success = true;
        
        pthread_mutex_unlock(&queue->mutex);
    }
    
    return success;
}

bool queue_push(queue_t *queue, void const *src)
{
    bool success;
    void *dest;
    
    if ((queue == NULL) || (queue_full(queue)) || (src == NULL))
    {
        success = false;
    }
    else
    {
        pthread_mutex_lock(&queue->mutex);
        
        dest = index_to_address(queue, queue->in);
        memcpy(dest, src, queue->sizeof_element);
        queue->in = (queue->in + 1) % queue->capacity;
        success = true;
        
        pthread_mutex_unlock(&queue->mutex);
    }
    
    return success;
}

bool queue_pop(queue_t *queue, void *dest)
{
    bool success;
    
    if ((queue == NULL) || (queue_empty(queue)))
    {
        success = false;
    }
    else
    {
        pthread_mutex_lock(&queue->mutex);
        
        if (dest != NULL)
        {
            queue_front_internal(queue, dest, false);
        }
        queue->out = (queue->out + 1) % queue->capacity;
        success = true;
        
        pthread_mutex_unlock(&queue->mutex);
    }
    
    return success;
}

size_t queue_size(queue_t * queue)
{
    size_t size;
    assert(queue != NULL);
    
    pthread_mutex_lock(&queue->mutex);
    
    if (queue->out <= queue->in)
    {
        size = queue->in - queue->out;
    }
    else
    {
        size = queue->in + queue->capacity - queue->out;
    }
    
    pthread_mutex_unlock(&queue->mutex);
    
    return size;
}

size_t queue_capacity(queue_t * queue)
{
    size_t capacity;
    assert(queue != NULL);
    
    pthread_mutex_lock(&queue->mutex);
    capacity = queue->capacity - 1; /* one of the array elements is reserved for the queue "in","out" pointers overhead */
    pthread_mutex_unlock(&queue->mutex);
    
    return capacity;
}

bool queue_empty(queue_t * queue)
{
    bool empty;
    assert(queue != NULL);
    
    pthread_mutex_lock(&queue->mutex);
    empty = (queue->in == queue->out);
    pthread_mutex_unlock(&queue->mutex);
    
    return empty;
}

bool queue_full(queue_t * queue)
{
    bool full;
    assert(queue != NULL);
    
    pthread_mutex_lock(&queue->mutex);
    full = (((queue->in + 1) % queue->capacity) == queue->out);
    pthread_mutex_unlock(&queue->mutex);
    
    return full;
}
\$\endgroup\$
  • \$\begingroup\$ Sorry, but VTC. This question is not about a code review, but a design review. It likely belong to SO. That said, there are quite a few design flaws here. \$\endgroup\$ – vnp Jan 14 at 0:31
  • \$\begingroup\$ I think if the full implementations were shown this could be brought on-topic. \$\endgroup\$ – Reinderien Jan 14 at 1:58
  • \$\begingroup\$ @vnp implementation added. \$\endgroup\$ – Sparkler Jan 14 at 2:54
  • \$\begingroup\$ @vnp Refactored. I think now it is less of a design review and more of a code review. \$\endgroup\$ – Sparkler Jan 15 at 4:05

Your Answer

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

Browse other questions tagged or ask your own question.