Queue in C via array

Question

I have implemented a queue in C language with usage of an array of structures.

typedef struct{
    req_t     buffer[BUFFER_SIZE];   // buffer
    uint16_t    size;                          // length of the queue
    uint16_t    count;                 // number of elements present in the queue
    req_t     *p_head;                 // pointer to head of the queue (read end)
    req_t     *p_tail;                 // pointer to tail of the queue (write end)
}circular_buffer_t;

void init_cb(circular_buffer_t *p_cb){

    p_cb->p_head = p_cb->buffer;
    p_cb->p_tail = p_cb->buffer;
    p_cb->count = 0;
    p_cb->size = BUFFER_SIZE;

}

The problem is that above given implementation is usable only for storing the instances of req_t structures. Now I need to store instances of another structure and I don't know how to define the queue in more general way so that I will be able to use same queue for instances of different structures. Problem is that I need to know the structure type before buffer definition. Does anybody have any idea how to solve that?

    #ifndef CIRCULAR_BUFFER_H_
#define CIRCULAR_BUFFER_H_

#define BUFFER_SIZE 32

// macro creates variant of the queue for each struct type
#define define_queue(TYPE)                                                       \
                                                                               \
  // queue element definition                                                  \                                                                                
  typedef struct{                                                              \
    TYPE     buffer[BUFFER_SIZE];                                              \
    uint16_t size;                                                             \
    uint16_t count;                                                            \
    TYPE     *p_head;                                                          \
    TYPE     *p_tail;                                                          \
  }circular_buffer_##TYPE##_t                                                  \
                                                                               \
                                                                               \
  // queue init function definition                                            \                                                                               
  void init_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb){                       \
    p_cb->p_head = p_cb->buffer;                                               \
      p_cb->p_tail = p_cb->buffer;                                               \
      p_cb->count = 0;                                                           \
      p_cb->size = BUFFER_SIZE;                                                  \
  }                                                                            \
                                                                               \
  // queue enqueue function definition                                         \                                                                               
  BOOL enqueue_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb, TYPE *p_enq_elem){  \
                                                                               \    
    if(p_cb->count < p_cb->size){                                              \
                                                                               \
         taskENTER_CRITICAL();                                                     \
                                                                               \
            *(p_cb->p_tail) = *p_enq_elem;                                           \
            p_cb->p_tail = ((++(p_cb->p_tail) == (p_cb->buffer + p_cb->size)) ?      \
                      (p_cb->buffer) : (p_cb->p_tail));                        \
            p_cb->count++;                                                           \
                                                                               \
         taskEXIT_CRITICAL();                                                      \
                                                                               \
         return TRUE;                                                              \
                                                                               \
      }else{                                                                     \
                                                                               \
         return FALSE;                                                             \
                                                                               \
      }                                                                          \
                                                                               \
  }                                                                            \
                                                                               \
  // queue dequeue function definition                                         \                                                                               
  BOOL dequeue_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb, TYPE *p_deq_elem){  \
                                                                               \
    if((p_cb->count) != 0){                                                    \
                                                                               \
        taskENTER_CRITICAL();                                                      \
                                                                               \
            *p_deq_elem = *(p_cb->p_head);                                           \
            p_cb->p_head = ((++(p_cb->p_head) == (p_cb->buffer + p_cb->size)) ?      \
                      (p_cb->buffer) : (p_cb->p_head));                        \
            p_cb->count--;                                                           \
                                                                               \
        taskEXIT_CRITICAL();                                                       \
                                                                               \
        return TRUE;                                                               \
                                                                               \
     }else{                                                                      \
                                                                               \
        return FALSE;                                                              \
                                                                               \
     }                                                                           \
                                                                               \
  }                                                                            \


// macros for functions declarations
#define declare_init_cb(TYPE)    void init_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb)
#define declare_enqueue_cb(TYPE) BOOL enqueue_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb, TYPE p_enq_elem);
#define declare_dequeue_cb(TYPE) BOOL dequeue_cb_##TYPE(circular_buffer_##TYPE##_t *p_cb, TYPE p_deq_elem);                                                

#endif

Structures I am going to use with the queue

    typedef struct{
    uint32_t addr;          // address of the alarm signal
    BOOL     critical;      // alarm is critical (=TRUE), alarm is non critical (=FALSE)
    BOOL     set;           // alarm was set     (=TRUE)
    BOOL     cleared;       // alarm was cleared (=TRUE)
    BOOL     communicated;  // alarm is communicated to Main Controller (=TRUE)
    uint8_t  code;          // alarm code   (0 - 255) - permanently 180
    uint8_t  no;            // alarm number (0 - 255)
    uint8_t  no_flashes;    // number of LED flashes if the alarm is active
}alarm_t;

and

 typedef struct{
    msg_e req_type;                              // request type
    uint8_t         blk_no;                      // block number
    uint8_t         no_records;                  // number of influenced records
    uint8_t         data_id[MAX_NO_RECORDS];     // data id, max. number of records in one block
    uint16_t        value[MAX_NO_RECORDS];       // written value, max. number of records in one block
    uint8_t         cleared_alarm_no;            // number of the alarm which should be cleared
    uint8_t         flash_load;                  // 0 = Go into flash load mode
    uint8_t         mode[6];                     // 000000 - Normal, BOOTBL - Boot block
    uint8_t         data_block[BLOCK_SIZE];      // one block in flash memory
    uint8_t         flash_page_number;           // page number in flash memory (starting at 1)
    uint8_t         flash_block_number;          // block number in flash memory (starting at 1)
}req_t;

One solution is dynamic allocation and storing generic pointers. — Some programmer dude, Sep 08 '17 at 10:24
Another solution is to make it store opaque binary data of a size given when its initialized, and then use `memcpy()` and `void *` to implement storing and accessing. — unwind, Sep 08 '17 at 10:28
The req_t is a C struct. Unfortunately I need to use implementation via array. — Steve, Sep 08 '17 at 10:50
@Steve If you want to store different types in the same place, a `union` is usually what you want. It's like a `struct`, but with all members starting at the same offset. The size of the union is determined by the size of the largest member. In this case, however, you also need some indicator in each queue slot which determines which type is stored there. — SBS, Sep 08 '17 at 12:48

score 6 · Answer 1 · answered Sep 08 '17 at 10:39

If you want to store any type of struct in your queue, you have to use void * type and store in the queue only the pointers to any structs.

typedef struct{
    void      *buffer[BUFFER_SIZE];   // buffer
    uint16_t  size;                          // length of the queue
    uint16_t  count;                 // number of elements present in the queue
    void      *p_head;                 // pointer to head of the queue (read end)
    void      *p_tail;                 // pointer to tail of the queue (write end)
}circular_buffer_t;

Then, you have just to put any pointer in your queue like this:

circular_buffer_t p_cb;
my_struct_t       *my_struct = malloc(sizeof(my_struct_t));

// set
p_cb.buffer[0] = (void*)my_struct;

// get
(my_struct_t*)p_cb.buffer[0];

This solution must be combined with an enum used to indicate what type that is stored, and possibly also the size of one object of that type. — Lundin, Sep 08 '17 at 14:18

score 3 · Answer 2 · answered Sep 08 '17 at 10:56

3

1. Storing structs by value

If you specify the struct size when creating the queue, you can use it to store actual structs (copied by value) into the buffer.

typedef struct {
    u32 capacity;
    u32 element_size;
    u8 * head;    // next free slot 
    u8 * tail;    // oldest enqueued item
    u8 * buffer;
    u8 * buffer_end;
} circular_buffer_t;

void circbuff_init(circular_buffer_t *p_cb, u8 *buffer, u32 element_size, u32 capacity)
{
    p_cb->capacity = capacity;
    p_cb->element_size = element_size;
    p_cb->buffer = buffer;
    p_cb->buffer_end = buffer + (capacity * element_size);
    p_cb->head = buffer;
    p_cb->tail = buffer;
}

Note that .count is redundant, you can calculate it at any time, and removing it makes reader/writer syncronization easier (in case that you read and write from different interrupts).

You need to take care to pass the correct buffer size and element_size:

circbuff_init(p_cb, buffer, sizeof(SomeStruct), sizeof(buffer) / sizeof(SomeStruct));

And then you just copy each element:

bool circbuff_dequeue(circular_buffer_t *hnd, void *dst)
{
    // if empty, do nothing
    if (circbuff_isEmpty(hnd))
        return false;

    memcpy(dst, hnd->tail, hnd->element_size);
    hnd->tail = modulo_increment(hnd, hnd->tail);
    return true;
}

2. Storing pointers to structs

This is already mentioned in some other answer.

3. Using a macro to create a typed buffer for each struct type

This is similar to how klib works. You would have to call certain macros to define each concrete type of circular buffer (for each struct), but then you would have compile time type safety.

answered Sep 08 '17 at 10:56

vgru

49,838
16
120
201

Thank you for your answer Groo. I would like to use the third mentioned variant but I don't know how I place the function prototypes into .h file. I have defined separate .c module called circular_buffer.c. There are defined the init_cb, enqueue_cb and dequeue_cb and these functions are publicated in associated header file. – Steve Sep 08 '17 at 12:38
This macro should append the struct name to the type of the circ buffer and all functions (e.g. `circular_buffer_ ## TYPE ## _t`, `init_cb_ ## TYPE`, etc). You can check [this answer](https://stackoverflow.com/a/16523865/69809) in the thread mentioned by @TheJavatar to see the general idea. – vgru Sep 08 '17 at 13:11
I think that I understand the basic idea with universal macro which creates the versions of individual functions for various struct types. But I am not able to invent how to create the function prototypes in the associated .h file. As far as I understand correctly the macro creates definitions of the functions but I also need the declarations for .h file. Shall I define special macro for the function declarations? But where to place this macro? – Steve Sep 08 '17 at 16:27
With this approach, you typically create all functions in the header file, as static functions, something [like this](https://github.com/attractivechaos/klib/blob/master/klist.h). Otherwise, yes, you would need to create separate macros for the compilation unit, and separate for function prototypes. – vgru Sep 08 '17 at 19:50
I am going to remove the circular_buffer.c module and define the circular_buffer.h module in above given manner (please see the original question). As soon as I will want to use the circular buffer in any of my .c modules I will include the circular_buffer.h file and I will call the define_queue(TYPE) macro with appropriate TYPE value in the "local functions definition" part of the .c module. Then I will call the declare macros in "local functions declaration" part of the .c module. Is it correct? – Steve Sep 10 '17 at 10:37
Well, a c translation unit (".c module") doesn't really have "parts" you are referring to (definition/declaration), you can include headers at any place, define function prototypes and functions anywhere you like. But if I understood correctly, `define_queue(TYPE)` will create the struct definition and all the necessary functions, and then you will declare a field or a variable somewhere below that point. That seems correct, yes. – vgru Sep 10 '17 at 13:55
Note also that the first approach (just copying structs by value through a void* parameter) will compile to the same code as the "generic macro" version (except for buffer of `int`s, or `char`s, which can be copied without `memcpy`). So if you don't feel comfortable with the macro weirdness, just use the simpler variant, although the compiler won't stop you from passing pointers to wrong struct types in that case. In any case, enable all warnings for your compiler and treat them as errors (`-Wall`, `-Werror`), you will have less run-time issues that way. – vgru Sep 10 '17 at 14:00
And finally, as I mentioned in my answer, you don't need locking if you have a single producer + single consumer (on different threads), and get rid of the `count` field. – vgru Sep 10 '17 at 14:04
Thank you very much for your useful tips. It is very helpful for me. – Steve Sep 10 '17 at 19:40

score 2 · Answer 3 · answered Sep 08 '17 at 10:25

2

What you want, is in fact a structure with a generic type field. The C language doesn't provide support for that. The best you can do it's to try to emulate that behavior. One way to do that is using macros or using generic pointers. Look here for more info about that: Pseudo-generics in C

answered Sep 08 '17 at 10:25

The Javatar

695
5
15

Thank you for your answer The Javatar. I have read the link you have posted. Does it mean that I should define some macro with parameter (for example TYPE) and after calling this macro creates an unique type of circular_buffer_t struct for given TYPE and also creates unique set of functions init_cb, enqueue_cb, dequeue_cb for given TYPE. But I don't know how should look like the function prototypes for the header file? – Steve Sep 08 '17 at 11:06
Except.. C _does_ provide `_Generic` since 6 years back. This answer and the linked one are a bit outdated. – Lundin Sep 08 '17 at 14:20

score 2 · Accepted Answer · answered Sep 08 '17 at 13:08

2

Like I've mentioned in my comment above, I'd recommend using a union to store different types in one queue slot. Additionally, some type indicator is needed to distinguish them. Here's an example:

First, redefine req_t as req_t1, adding a type indicator as the first member:

typedef struct _req_t1
    {
    int type;
    // append the members of your first structure here
    }
req_t1;

Define the second type to be stored in an analogous way as req_t2:

typedef struct _req_t2
    {
    int type;
    // append the members of your second structure here
    }
req_t2;

Now redefine req_t as a union, containing both types, plus a standalone member that represents the type indicator, in order to test for the stored type:

typedef union _req_t
    {
    int    type;
    req_t1 item1;
    req_t2 item2;
    }
req_t;

Now you can use your circular buffer as before. However, req_t is now a compound member that might be interpreted as either type.

typedef struct _circular_buffer_t
    {
    req_t     buffer [BUFFER_SIZE]; // buffer
    uint16_t  size;                 // length of the queue
    uint16_t  count;                // number of elements present in the queue
    req_t    *p_head;               // pointer to head of the queue (read end)
    req_t    *p_tail;               // pointer to tail of the queue (write end)
    }
circular_buffer_t;

To access the head, you use p_head->type to identify the type that's contained in this slot. If it indicates req_t1, you use p_head->item1 to access the members of req_t1, otherwise p_head->item2 for req_t2. This approach can be extended to any number of types.

answered Sep 08 '17 at 13:08

SBS

806
5
13

1

This is a bad idea since a "variant" (which is what such a union is called) will waste vast amounts of memory. Note that the OP wants arrays of these. – Lundin Sep 08 '17 at 14:22
@Lundin The original code already uses structures of req_t as array members (see above). What I'm proposing is just an easy extension of this design. In case of a union, the biggest member determines its size, since all members start at the same offset and thus overlap. Hence, this approach doesn't waste significantly more memory than the original code. – SBS Sep 08 '17 at 14:29
1

@Lundin I think it's only a problem if the items in the union aren't similarly sized. If they're all approximately the same size, then it's not a problem. Or is there some other mechanism that the "vast amounts of memory" you speak of come from? – Russ Schultz Sep 08 '17 at 19:11
1

@SBS Thank you for your suggestion. I am going to use the queue with very different structs (please see the original question). Could it be a problem? – Steve Sep 10 '17 at 10:50
@Steve Take the value BUFFER_SIZE and multiply it by the size of the largest struct you're going to store - then you know how big your queue will be in memory. I guess you won't run into a problem, because memory usually isn't a problem anymore today. – SBS Sep 10 '17 at 18:35
1

@SBS Thank you for your answer. I was afraid of some problems mentioned by Russ Schultz. – Steve Sep 10 '17 at 19:44
@Steve Yes, I've read his comment. Actually, you have to store the structures anywhere in memory anyway, so you need enough memory for all struct instances in memory with any of the suggested approaches. My approach with unions of course has some overhead, because you're wasting some space whenever you store one of the smaller structs. However, you can calculate the amount of memory required exactly beforehand, using the formula I've given in my comment above, so you won't face an unpleasant surprise at runtime. My suggestion has the advantage of saving you from extensive code rewriting. – SBS Sep 10 '17 at 19:53
1

@SBS Thank you for your help. Your solution is probably the best understandable for me. – Steve Sep 10 '17 at 20:03
@Steve I'm glad to have helped you. Please don't forget to mark my solution as "accepted answer" if you think it solves your problem. Thanks! – SBS Sep 10 '17 at 20:11

Queue in C via array

4 Answers4

1. Storing structs by value

2. Storing pointers to structs

3. Using a macro to create a typed buffer for each struct type