Circular Queue

Overview

XWOS’s circular queue (xwcq) is a queue composed of NUM data buffers, each of size SIZE. These buffers are connected end-to-end, forming a ring.

pie
    title Circular Queue
    "Data Buffer 0" : 1
    "Data Buffer 1" : 1
    "Data Buffer 2" : 1
    "Data Buffer 3" : 1
    "Data Buffer 4" : 1
    "Data Buffer 5" : 1
    "Data Buffer 6" : 1
    "Data Buffer 7" : 1

Messages can be sent to the head of the queue or to the tail of the queue. Messages can be received from the head of the queue or from the tail of the queue.

Circular Queue Object and Object Descriptor

The circular queue object is a derived class of the XWOS object struct xwos_object. Similarly, the circular queue object uses the circular queue object descriptor xwcq_d to address validity and identity legitimacy issues.

The circular queue object descriptor consists of the circular queue object pointer and a tag:

typedef struct {
        struct xwcq * cq; /**< pointer to circular queue object */
        xwsq_t tik; /**< tag */
} xwcq_d;

When referencing an object through an object descriptor, the value of obj->magic is first checked to see if it is 0x58574F53U, which confirms that the pointer obj points to a valid XWOS object. Then the tag obj->tik is compared with tik to verify the object’s identity. Because an object’s tik is globally unique, when the object is freed, its tik is destructed to 0 by the destructor. When the memory address is reconstructed as a new object, its tik will certainly differ from the object descriptor’s tik.

Limitations

The circular queue has its own data buffers. User messages are copied into the data buffers, eliminating the need for additional dynamic memory allocation from the user. However, the circular queue buffer size is fixed, so users can only send data that is less than or equal to the buffer size.

Static Initialization and Destruction of Circular Queue

• Static initialization: xwcq_init()
  • Static means the user pre-defines thread structure objects, which are allocated memory by the compiler at compile time.
  • When initializing a circular queue, data buffers must be pre-defined.

#define BRDCQ_SIZE 64
#define BRDCQ_NUM  8
XWCQ_DEF_MEMPOOL(brdcq_mempool, BRDCQ_SIZE, BRDCQ_NUM);
struct xwcq brdcq;

xwer_t brd_init_xwcq(void)
{
        return xwcq_init(&brdcq, BRDCQ_SIZE, BRDCQ_NUM, brdcq_mempool);
}

• Destruction of statically initialized semaphore: xwcq_fini()

Dynamic Creation and Deletion of Circular Queue

XWOS does not provide CAPI for dynamic memory-based creation and deletion.

Sending Messages

Enqueue

Enqueue means sending a message to the tail of the circular queue. If the circular queue is full, the circular queue wraps around to the head position, overwriting the original data.

• xwcq_eq(): can be used in any context

Jump Queue

Jump queue means sending a message to the head of the circular queue. If the circular queue is full, the circular queue wraps around to the tail position, overwriting the original data.

• xwcq_jq(): can be used in any context

Receiving Messages

Receiving a message means taking a message from the circular queue. Once taken, the message no longer exists in the circular queue.

Head Dequeue

• xwcq_dq(): wait for a message, can only be used in thread context
• xwcq_dq_to(): timed wait for a message, can only be used in thread context
• xwcq_dq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwcq_trydq(): try to obtain a message, can be used in any context

Tail Dequeue

• xwcq_rq(): wait for a message, can only be used in thread context
• xwcq_rq_to(): timed wait for a message, can only be used in thread context
• xwcq_rq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwcq_tryrq(): try to obtain a message, can be used in any context

Copying Messages

Copying a message means copying a message from the circular queue without removing it from the queue.

Head Peek

• xwcq_pfq(): wait for a message, can only be used in thread context
• xwcq_pfq_to(): timed wait for a message, can only be used in thread context
• xwcq_pfq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwcq_trypfq(): try to obtain a message, can be used in any context

Tail Peek

• xwcq_prq(): wait for a message, can only be used in thread context
• xwcq_prq_to(): timed wait for a message, can only be used in thread context
• xwcq_prq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwcq_tryprq(): try to obtain a message, can be used in any context

Flushing the Circular Queue

Users can restore the circular queue to its initial state via xwcq_flush().

Getting Circular Queue Capacity

Users can obtain the circular queue’s capacity via xwcq_get_capacity(). The circular queue capacity is the number of data slots in the data buffer, i.e., the third parameter of xwcq_init().

Getting Individual Data Slot Size

Users can obtain the size of a single data slot via xwcq_get_size(). This is the second parameter of xwcq_init().

Getting Number of Valid Data Slots

Users can obtain the number of valid data slots in the circular queue via xwcq_get_availability(). A valid data slot is one that contains data available for reception.

Lifecycle Management of Circular Queue Objects

The circular queue object’s base class is the XWOS object struct xwos_object. The circular queue object also has two sets of lifecycle management CAPI:

• Lifecycle management CAPI accessed via object pointer: requires ensuring that the object is definitely valid when calling CAPI, and that there is no free-and-reallocate scenario where it becomes another object.

  • xwcq_grab(): increase reference count.
  • xwcq_put(): decrease reference count; when the reference count drops to 0, the garbage collection function is called to free the object.

• Lifecycle management CAPI accessed via object descriptor: used when the user cannot guarantee the object is valid or cannot guarantee the object won’t become another object.

  • xwcq_acquire(): verify the object is valid and legitimate through the object descriptor, then increase reference count.
  • xwcq_release(): verify the object is valid and legitimate through the object descriptor, then decrease reference count. When the reference count drops to 0, the garbage collection function is called to free the object.

CAPI Reference

• Header <xwmd/isc/xwcq.h>