static initialization of queue

Question

I'm working on a high-reliance implementation of an algorithm for an embedded system.

in main.c:

    //.. in main()
    int queue_buffer[QUEUE_LEN + 1] = { 0 };
    Queue queue;
    queue_init(&queue, QUEUE_LEN, queue_buffer);
    do_things_on_queue(&queue);
    //.. in main()

in queue.c:

void queue_init(Queue *q, int len, int *data) {
    q->head = 0;
    q->tail = 0;
    q->len = len;
    q->data = data; // an array of length `len + 1`
}

in queue.h:

typedef struct queue {
    int head;
    int tail;
    int len;
    int *data;
} Queue;

I would like to 1. have main.c to not know about Queue; and 2. not use malloc for intializing queue_buffer_ but rather do it statically.

this implies that ideally main.c would be:

    //.. in some function
    Queue *queue = queue_init(something_eventually);
    do_things_with_queue(queue);
    //.. in some function

Is it possible to modify queue_init in queue.cto achieve this in C99? If so, what's the best approach?

---

Tentative Solutions

I am aware of the technique discussed in this post yet they seems unfeasible without using malloc. I know for sure that I will simultaneously have 4 queues at most. This makes me think that I could declare a memory pool for the queues as a static global array of queues of size 4. Is it ok to use global variables in this case?

@KamilKuk suggested to just have queue_init to return the structure itself since QUEUE_LEN is known at compile time. This requires the following:

in queue.c:

Queue queue_init(void) {
    Queue q;
    
    q.head = 0;
    q.tail = 0;
    q.len = QUEUE_LEN;
    for (int i=0; i < QUEUE_LEN; i++)
        q.data[i] = 0;
    return q;
}

in queue.h:

typedef struct queue {
    int head;
    int tail;
    int len;
    int data[QUEUE_LEN];
} Queue;

Queue queue_init(void);

This appears to greatly simplify the structure initialization. However this does not solve the privacy problem, since main.c should know about Queue to initialize this struct.

---

Thank you.

Answer 1

I would typically do:

// queue.h
#define QUEUE_INIT(data, len)  { .len = len, .data = data }
#define QUEUE_INIT_ON_STACK(len)  QUEUE_INIT((char[len]){0}, len)

// main.c
static Queue queue = QUEUE_INIT_ON_STACK(QUEUE_LEN  + 1);

---

As for PIMPL idiom, it's easy to implement with descriptors just like file descriptors in LINUX, especially when the count is static.

// queue.h
typedef Queue int;
void do_things_with_queue(Queue);

// queue.c
struct RealQueue { stuff; };
static struct RealQeueue arr[4] = { stuff };
static struct RealQeueue *get_RealQueue(Queue i) {
     assert(0 <= i && i < sizeof(arr)/sizeof(*arr));
     return &arr[i];
}
void do_things_with_queue(Queue i) {
    struct RealQueue *queue = get_RealQueue(i);
}

// main.c
static Queue queue = 1;
// etc.

Or you can break all hell and synchronize alignment between source and header file:

// queue.h
struct Queue {
    // This has to be adjusted __for each compiler and environment__
    alignas(60) char data[123];
};
 
#define QUEUE_INIT() { 0xAA, 0xBB, etc.. constant precomputed data }

// queue.c
struct RealQeueue { stuff; };
static_assert(alingof(struct RealQueue) == alignof(struct Queue), "");
static_assert(sizeof(struct RealQueue) == sizeof(struct Queue), "");
void do_things_with_queue(Queue *i) {
    struct RealQueue *queue = (struct RealQueue*)i->data;
}

Answer 2

The best way to do this is to pass a buffer and its size to the init function, exactly as you already have.

It is a very bad idea to worry about calling a function versus having the data fixed at compile time. Both the execution time and code size for a tiny initialization like this is negligible. Making your code interface awkward just to save a few instructions at startup is not just a waste of effort, it makes the code hard to maintain and risks introducing bugs.

There are a number of embedded systems or libraries that provide a macro which declares both the storage array and the control structure in one go and gives them a name which is known only to the library, and then you have to use a macro to generate the name every time you access the item. For an example of this you might look at osMailQDef in CMSIS-OS. I don't really recommend this method though. It is too easy to get wrong, whereas doing it the usual way is easy to read and any reviewer will be able to spot a mistake straight away.

Answer 3

I would like to 1. have main.c to not know about Queue; and 2. not use malloc for intializing queue_buffer_ but rather do it statically.

this implies that ideally main.c would be:

    //.. in some function
    Queue queue = queue_init(something_eventually);
   do_things_with_queue(&queue);
   //.. in some function

No, your objectives do not imply a solution as described. You cannot declare or use an object of type Queue anywhere that the definition of that type is not visible. That follows directly from the language's rules, but if you want a more meaningful justification then consider that even if main does not access any of the members of Queue, it still needs the definition simply to know how much space to reserve for one.

It's not obvious to me that it serves a useful purpose to make type Queue opaque in main.c (or anywhere), but if that's what you want then in that scope you can forward declare it, never define it, and work only with pointers to it:

typedef struct queue Queue;

// ...

    Queue *queue = queue_init(something_eventually);
    do_things_with_queue(queue);

For that to work without dynamic memory allocation, the pointed-to Queue objects must have static storage duration, but that does not mean that they need to be globals -- either in the sense of being accessible via a name with external linkage, or in the sense of being declared at file scope.

Additionally, you have the option of allocating the data arrays automatically, as in your example code, so as to not tie up that memory in queues when they are not in use. If you prefer, you can wrap that up in a macro or two for a bit of additional ease of use (left as an exercise).

For example,
queue.h

typedef struct queue Queue;

Queue *queue_init(int queue_size, int queue_data[]);
void queue_release(Queue *queue);

queue.c

#include "queue.h"

struct queue {
    int head;
    int tail;
    int len;
    int *data;
};

Queue *queue_init(int queue_len, int queue_data[]) {
    // queue_pool has static storage duration and no linkage
    static Queue queue_pool[4] = {{0}};

    // Find an available Queue, judging by the data pointers

    for (Queue *queue = queue_pool;
            queue < queue_pool + sizeof(queue_pool) / sizeof(*queue_pool);
            queue++) {
        if (queue->data == NULL) {
            // This one will do.  Initialize it and return a pointer to it.
            queue->head = 0;
            queue->tail = 0;
            queue->len = queue_len;
            queue->data = queue_data;

            return queue;
        }
    }

    // no available Queue
    return NULL;
}

void queue_release(Queue *queue) {
    if (queue) {
        queue->data = NULL;
    }
}

main.c

    // ... in some function

    int queue_data[SOME_QUEUE_LENGTH];
    Queue *queue = queue_init(SOME_QUEUE_LENGTH, queue_data);
    do_things_with_queue(queue);
    queue_release(queue);

    // ...

Of course, if you prefer, you can put the queue data directly into the queue structure, as in your tentative solution, and maybe provide a flag there to indicate whether the queue is presently in use. That would relieve users of any need to provide storage, at the cost of tying up the storage for all the elements of all the queues for the whole duration of the program.