带有指针的C数组中的队列

I have tried to implement queue by array and pointers in C language. The queue is modeled by C structure

我试图用C语言实现数组队列和指针。队列由C结构建模

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

I have implemented function for queue initialization

我已经实现了队列初始化的功能

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;

}

and function for inserting onto the queue

和插入队列的功能

BOOL enqueue_cb(circular_buffer_t *p_cb, main_controller_req_t *p_enq_elem){

    if(p_cb->count < p_cb->size){

        // queue contains at least one free element

        taskENTER_CRITICAL();

            // insert the element at the tail of queue
            *(p_cb->p_tail) = *p_enq_elem;
            // incrementing modulo size
            p_cb->p_tail = (((p_cb->p_tail++) == (p_cb->buffer + p_cb->size)) ? (p_cb->buffer) : (p_cb->p_tail));
            // one element added
            p_cb->count++;

        taskEXIT_CRITICAL();

        return TRUE;

    }else{

        // queue is full
        return FALSE;

    }

}

The enqueue_cb function works well until the tail reaches BUFFER_SIZE. Then the program crashes and uC resets. The problem is in p_tail pointer update but I don't understand why. Please can anybody help me? Thanks in advance.

enqueue_cb函数运行良好,直到尾部达到BUFFER_SIZE。程序崩溃,uC重置。问题在于p_tail指针更新,但我不明白为什么。请有人帮帮我吗?提前致谢。

1 个解决方案

#1

The problem is in your test... You check for overrun, but before incrementing the pointer, this causes p_cb->p_tailto go past the end of your circular buffer.

问题在于您的测试...您检查是否超限,但在递增指针之前,这会导致p_cb-> p_tail超过循环缓冲区的末尾。

 p_cb->p_tail = ((p_cb->p_tail++) == (p_cb->buffer + p_cb->size)) 
                    ? (p_cb->buffer) 
                    : (p_cb->p_tail);

You must test the value of tail after incrementing.

您必须在递增后测试尾部的值。

 p_cb->p_tail = (++(p_cb->p_tail) >= (p_cb->buffer + p_cb->size)) 
                    ? p_cb->buffer 
                    : p_cb->p_tail;

As an aside, a linked list is not a very efficient way of implementing a circular buffer. Have you considered using a simple fifo buffer implementation?

另外,链表不是实现循环缓冲区的非常有效的方法。您是否考虑过使用简单的fifo缓冲区实现?

The fifo construct is so common, that it's useful to have a universal macro implementation for C. It is thread-safe (no locks needed) if you only have one producer and one consumer.

fifo结构非常常见,因此对C进行通用宏实现很有用。如果你只有一个生产者和一个消费者,它是线程安全的(不需要锁定)。

These macros are very easy to optimize by the compiler.

这些宏很容易被编译器优化。

It's a good tool to have in one's toolbox.

这是一个很好的工具,可以放在一个工具箱中。

// save these macros in a header file.
#define fifo_reset(fifo) \
     { (fifo).head = (fifo).tail = (fifo).buffer; }

#define fifo_elements(fifo) \
    (sizeof((fifo).buffer) / sizeof((fifo).buffer[0])

#define fifo_count(fifo) \
    (((fifo).tail >= (fifo).head)) ? ((fifo).tail - (fifo).head) : (((fifo).tail - (fifo).head) + fifo_elements(fifo))

#define fifo_free_space(fifo) \
    (fifo_elements(fifo) - (fifo_count(fifo) + 1))

#define __fifo_advance(fifo, ptr) /* this is "private" */\
    (( ((ptr) + 1) < (fifo).buffer + fifo_elements(fifo))) ? ((ptr) + 1) : (fifo).buffer )

#define fifo_full(fifo) \
    (__fifo_advance(fifo, (fifo).head) == (fifo).tail)

#define fifo_empty(fifo) \
    ((fifo).head == (fifo).tail)

#define fifo_pop(fifo, el)  \
    ( (fifo).head = ((el) = *(fifo).head, __fifo_advance(fifo, (fifo).head)) )

#define fifo_push(fifo, el)  \
    ( (fifo).tail = (*((fifo).tail) = (el), __fifo_advance(fifo, (fifo).tail)) )

// Now, any struct with head, tail, and fixed-length buffer is a fifo.
struct char_fifo_128
{
  char buffer[128];  
  char* head;
  char* tail;
};

struct main_controller_req_t
{
    // all data types are _movable_ using '='
    char any[128];
    int data;
    float more_data;
    char* dupstr;
};

#define BUFFER_SIZE 256

struct controller_fifo
{
  main_controller_req_t     buffer[BUFFER_SIZE];   // buffer
  main_controller_req_t*    head;
  main_controller_req_t*    tail;
};

int main()
{
  char c = 0;
  int elements_stored;
  controller_fifo queue;
  main_controller_req_t req;

  fifo_reset(queue);  // MUST call before using fifo

  // always check if space/data is available.
  if (!fifo_full(queue))
  {
      fifo_push(queue, req);
  }
  elements_stored = fifo_count(queue);

  if (!fifo_empty(queue))
  {
      fifo_pop(queue, req);
  }

  fifo_reset(queue);   // fifo reset is NOT thread-safe


  char_fifo_128* buffer = (char_fifo_128*)malloc(sizeof(char_fifo_128));

  fifo_reset(*buffer);

  if (!fifo_full(*buffer))
  {
      // ...
      fifo_push(*buffer, req);
  }
  elements_stored = fifo_count(*fifo);

  if (!fifo_empty(*buffer))
  {
      fifo_pop(*buffer, c);
  }

  free(buffer);
  return 0;
}

#1