4

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;
Improve this question
5
  • 1
    What is in the req_t data type? Commented Sep 8, 2017 at 10:24
  • 4
    One solution is dynamic allocation and storing generic pointers. Commented Sep 8, 2017 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. Commented Sep 8, 2017 at 10:28
  • The req_t is a C struct. Unfortunately I need to use implementation via array. Commented Sep 8, 2017 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. Commented Sep 8, 2017 at 12:48

4 Answers 4

Reset to default
6

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];
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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

Improve this answer

9 Comments

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.
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 in the thread mentioned by @TheJavatar to see the general idea.
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?
With this approach, you typically create all functions in the header file, as static functions, something like this. Otherwise, yes, you would need to create separate macros for the compilation unit, and separate for function prototypes.
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?
|
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.

Improve this answer

9 Comments

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 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?
@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?
@SBS Thank you for your answer. I was afraid of some problems mentioned by Russ Schultz.
@SBS Thank you for your help. Your solution is probably the best understandable for me.
|
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

Improve this answer

2 Comments

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?
Except.. C does provide _Generic since 6 years back. This answer and the linked one are a bit outdated.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.