Latest news

Circular Queue for embedded systems

No comments

This post is part of the Memory Control Structures series. Also, read the other posts in the series:

Dear reader, how are you? We spoke a few days ago about a simple and efficient data structure for temporary storage of byte sequences, and it can be used in communications and data processing, the circular buffer, a resource with a policy of insertion and removal of data of the FIFO type. Well, in this article we will take advantage of the use of the circular buffer structure and transform it into an even more powerful data structure, a circular queue.

What is the difference between circular buffer and circular queue?

Essentially, they are identical, have insertion and removal policies based on FIFO, wrap around control, ie in case of overflow the index of writing or reading points to the beginning of the memory allocated to the data. The essential difference lies in the data size unit. In the circular buffer we can insert a string of bytes of variable length between 1 and the size of the allocated memory (since it is free), just as we can pull a string of data under the same range.

In the same essence, the circular queue allows the removal of byte chain, but limited in size to a logical subdivision of the memory area known as slots, so a circular queue has the capacity of N slots where each slot holds up to B bytes. The most attentive reader can see that this already refers to the use of the circular queue for storing larger volumes of data and can be used as a simple memory manager with fixed block size. Perfect, for example, to sort complex data types as a sequence of TCP or UDP datagrams. Look at the figure below:

See in the figure that for each row of the table there are several fields to fill. In the circular queue approach, each row in this table would have the size of a slot, so insertion would be by the copy of a slot and withdrawal by an entire row of the table in the order in which the slots arrive. In the Circular Buffer, we were interested in the order in which the bytes arrived.

Where could I apply one circular queue?

Dear reader, let’s go back to the case of the UART that I quoted in the article on circular buffers. We already know that by using them we can cause the UART to capture incoming bytes and order them for further processing. Now let’s imagine the case whereby this same UART traffic a protocol of communication, that contains several commands, but all of them with the same sequence of bytes. Taking, for example, the well-known MODBUS protocol, a Telegram (MODBUS standard structure) can contain the following fields as shown below:

Disregard the Start and End fields (usually they are treated by hardware), let’s see that the protocol has a common structure, with the exception of the Data field, which can be variable. Let us assume, to simplify the reasoning, that we know that the size of the Data field at its maximum use is known. Our UART already has the circular buffer to capture bytes that come between Start and End. It reads from the hardware register and adds to the circular buffer, however when assembling a MODBUS packet and sending for processing, another packet may already be ready for to arrive. Would not it be much better then to remove all bytes from the circular buffer and copy the ready-to-process message in the order they arrive? This is where the circular queue should enter. With it each slot would be a complete MODBUS command and sorted from the oldest to the most recent, allowing the application to worry about just one thing, pull out the complete message and execute the command. This helps avoid excessive CPU usage and allows the use of empty queue events to disable the decoder when it does not need to be used.

Thus a circular queue has great application in managers of complex communication protocols, that is, that do not treat byte chain, but messages preformatted and with a defined sequence. In addition, the circular queue can also be used for scheduling operating system tasks in the same way as the circular buffer. However, because it has its slots-like structure, it will be able to handle complex data structures such as a Task Control Block (data structure that contains all the information of the tasks to be executed).

Example of a circular queue

The implementation presented brings the basic routines for creating and manipulating a circular queue. An example of usage is also being provided to assist the user in basic data creation, insertion, and deletion so that he can then use it in his own applications. The supplied module is as independent of architecture as possible and its performance of the data copy depends on the implementation of the generally optimized memcpy function in the LIBC provided with the user’s favourite toolchain. Below are the files:

/**
 * @brief Simple circular queue implementation with basic management functions
 */

#ifndef __QUEUE_CIRC_H
#define __QUEUE_CIRC_H


/** circular queue management structure */
typedef struct {
  unsigned char *data;
  unsigned int  items;
  unsigned int  slots_number;
  unsigned int  wr_ptr;
  unsigned int  rd_ptr;
  int  slot_len;
} queue_circ_t;



/**
 * @brief insert a stream data with size lenght to the queue
 */
int queue_insert(queue_circ_t *q,void *data, unsigned int size);

/**
 *  @brief retrieves a stream of dat with specified size
 */
int queue_retrieve(queue_circ_t *q, void *data, unsigned int *size);

/**
 *  @brief check if queue is already full
 */
int queue_full(queue_circ_t *q);

/**
 * @brief makes the queue empty
 */
int queue_flush(queue_circ_t *q);

/**
 * @brief  check if queue is empty
 */
int queue_empty(queue_circ_t *q);

/** declare a initialized circular queue
 * name - name of the allocated queue structure
 * slot_size -size in bytes of each slot
 * noof_slots - number of slots (elements) in this queue
 */
#define CIRCULAR_QUEUE_DECLARE(name,slot_size, noof_slots)    \
        unsigned char queue_memory_##name[(slot_size + sizeof(unsigned int)) * noof_slots];\
        queue_circ_t name = {                                 \
          .data = &queue_memory_##name[0],                    \
          .items = 0,                                         \
          .slots_number = noof_slots,                         \
          .wr_ptr = 0,                                        \
          .rd_ptr = 0,                                        \
          .slot_len = slot_size + sizeof(int)                 \
        }

#endif

In the file circ_queue.h the user will have available all the routines to instantiate and use their queue in a personalized way, at the end a macro (just like in the circular bufffer) is also available so that it is possible to initialize a totally initialized structure and ready For use. In addition, the checking routines are provided to check for a full or empty queue, in addition to the flush routine, which cleans it.

Below we’ll take a look at the implementation (as usual). See:

#include <string.h>
#include "queue_circ.h"


int queue_insert(queue_circ_t *q,void *data, unsigned int size)
{
  int ret = -1;

  if(q == NULL) {
    /* check your queue parameter */
    return(ret);
  } else {

    /* points the insertion index in correct queue
     * memory region
     */
    unsigned char *ptr = (unsigned char *)q->data;
    int pos = q->wr_ptr * q->slot_len;

    if(size > q->slot_len) {
      /* data will not fit in this slot */
      ret = -1;
    } else {
      /* the first 4 bytes are the size of slot in bytes */
      memcpy(&ptr[pos], &size, sizeof(size));
      /* insert the data */
      memcpy(&ptr[pos + sizeof(size)], data, size);
      /* update the indexes */
      q->wr_ptr = (q->wr_ptr + 1) % q->slots_number;
      ++q->items;
      ret = 0;
    }
  }
  return(ret);
}


int queue_retrieve(queue_circ_t *q,  void *data, unsigned int *size)
{
  int ret = -1;

  if(q == NULL || size == NULL) {
    /* check your queue parameter */
    return(ret);
  } else {

    /* points the insertion index in correct queue
     * memory region
     */
    unsigned char *ptr = (unsigned char *)q->data;
    int pos = q->rd_ptr * q->slot_len;

      /* the first 4 bytes are the size of slot in bytes */
      memcpy(&size,&ptr[pos], sizeof(size));
      /* retrieve the data */
      memcpy(data,&ptr[pos + sizeof(size)], size);
      /* update the indexes */
      q->rd_ptr = (q->rd_ptr + 1) % q->slots_number;
      --q->items;
      ret = 0;
  }
  return(ret);
}


int queue_full(queue_circ_t *q)
{
  int ret = 0;
  if(q->items >= q->slots_number) {
    ret = 1;
  }
  return(ret);
}


int queue_flush(queue_circ_t *q)
{
  int ret = 0;

  if(q != NULL) {
    q->wr_ptr = q->rd_ptr;
    q->items = 0;
  } else {
    ret = -1;
  }
  return(ret);
}


int queue_empty(queue_circ_t *q)
{
  return((q->items == 0? 1: 0));
}

Notice that the implementation of the Circular Queue is very similar to the Circular Buffer, in addition to the implicit protection of memory leakage using circular increment. For the most attentive reader, the main difference is in lines 18 and 19 for insertion, and lines 51 to 57 for removal. Notice that in the Circular Buffer we used the indexes to directly access the byte specified by it, but the queue is logically subdivided into slots, that is, smaller areas of smaller memory combined into a single memory area. Therefore, for correct access, we use the indexes in conjunction with the size of each slot, multiplying them with each other and obtaining the beginning of slot memory. In addition, logically 4 bytes are reserved for each slot that stores the amount of data inserted in it, and when performing a retrieve, the amount of bytes will be returned so that the user knows how much was in the slot accessed.

Conclusion

The circular buffer is versatile and may have its structure used to construct more complex data types, such as the Circular Queue example, a secure and efficient structure for temporary storage with the additional provision of an associated memory block to deal with larger and more complex data types. The simple implementation provided in this article meets the needs of using communication stacks for message processing that are extracted from on-chip controllers such as USB, UART, CAN, and protocols written on top of these interfaces.

I hope you enjoyed it. To the next!

Example in Github

FelipeCircular Queue for embedded systems

Leave a Reply

Your email address will not be published. Required fields are marked *