Indigresso Wiki

Open Source Stuff for DASH7

User Tools

Site Tools


opentag:otlib:queue

Queue Module (OTlib)

OpenTag's Queue Module is an integral part of OTlib. The Queue Module is a FIFO data structure designed especially for managing protocol data. As such, it has features for reading-out and writing-in data, tracking data pointers, storing data attributes, and so on. Queues are also intended to store data in a Big Endian byte order (or “Network order” as it is sometimes known) as this is the common way protocols are designed.

Queues are ideally used through the Queue Module functions, although at times it can be more efficient to manipulate a queue directly.

The Queue Data Type

The Queue module is old… it was the first part of OpenTag, written as a personal exercise on a flight from Buffalo, NY to Chicago O'Hare during 01/2008 (JP had not done a FW/SW project for a few years and needed a refresh). For some reason the data type nomenclature has never been changed, even though the rest of OpenTag has, so the data type for a queue is “Queue”. It probably should be “ot_queue” or “ot_q” or something to that affect, but it is what it is!

typedef struct {
    ot_u16      alloc;
    ot_u16      length;
    Twobytes    options;
    ot_u8*      front;
    ot_u8*      back;
    ot_u8*      getcursor;
    ot_u8*      putcursor;
} Queue;
  • alloc: The number of bytes allocated to the Queue buffer
  • length: Current length of the queue (should be updated whenever reading-out or writing-in)
  • options: Implementation-specific data attributes (ignored by Queue Module)
  • front: Pointer to the front of the queue buffer
  • back: Pointer to the back of the queue (used especially for reserving footer space)
  • getcursor: Pointer to the next byte to read-out
  • putcursor: Pointer to the next byte to write-in

Most of these elements should be self-explanatory. One interesting feature is the “back” data element, which is really nice to use with protocols that tend to wrap or encapsulate other protocols. This way, it is easy to detect when the payload reaches the frame limit. Typically, the “front” pointer does not change once the queue is initialized, although it too may be used to offset the front of protocol frame. One pertinent example is the way background frame processing is implemented on top of the general-purpose foreground frame parsing model.

Queue Functions

Below are the main queue functions that you might see or use. For more information, see the Queue.h section below.

void q_init(Queue* q, ot_u8* buffer, ot_u16 alloc)
Links a Queue to a data buffer. Both must be supplied, as OpenTag assumes no malloc.

void q_empty(Queue* q)
Sets putcursor to front, getcursor to front, back to the true end of the queue, and options to 0. It does not actually wipe the data in the queue.

void q_writebyte(Queue* q, ot_u8 byte_in)
void q_writeshort(Queue* q, ot_u16 short_in)
void q_writeshort_be(Queue* q, ot_u16 short_in)
void q_writelong(Queue* q, ot_u32 long_in)
Functions to write-in one byte, two bytes, or four bytes into a queue. These functions do endian conversion (queues are always big endian) except for q_writeshort_be, which does not do endian conversion. These functions can work even when the queue is not short/long aligned at the time of calling.

ot_u8 q_readbyte(Queue* q)
ot_u16 q_readshort(Queue* q)
ot_u16 q_readshort_be(Queue* q)
ot_u32 q_readlong(Queue* q)
Identical to the write-in functions above, except they read-out.

void q_writestring(Queue* q, ot_u8* string, ot_int length)
void q_readstring(Queue* q, ot_u8* string, ot_int length)
Write-in/Read-out a stream of bytes. In the case of q_readstring, the string data must be allocated ahead of time, because OpenTag assumes no malloc.

Note

Write-in functions automatically adjust the data elements: length, putcursor. Read-out functions automatically adjust the data element getcursor.

OTlib/queue.h

Here is the code for queue.h. You may also refer to the doxygen code documentation.

#include "OT_types.h"
//#include "buffers.h"



/** @typedef Queue
  * 
  * The Queue data type does not contain the data in the queues themselves, just
  * information on how to get that data as well as any other useful variables.
  *
  * ot_u16 alloc        Allocation of the queue data, in bytes
  *
  * ot_u16 length       The current extent of the queue data, in bytes
  * Twobytes options    User flags
  * ot_u8* front        First address of queue data
  * ot_u8* back         Used for boundary checking (user adjustable)
  * ot_u8* getcursor    Cursor address for reading from queue
  * ot_u8* putcursor    Cursor address for writing to queue
  */
typedef struct {
    ot_u16      alloc;
    ot_u16      length;
    Twobytes    options;
    ot_u8*      front;
    ot_u8*      back;
    ot_u8*      getcursor;
    ot_u8*      putcursor;
} Queue;


/** @brief Generic initialization routine for Queues.
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param buffer   (ot_u8*) Queue data buffer
  * @param alloc    (ot_u16) allocated bytes for queue
  * @retval none
  * @ingroup Queue
  */
void q_init(Queue* q, ot_u8* buffer, ot_u16 alloc);


/** @brief Reposition the Queue pointers to a new buffer, don't change attributes
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param buffer   (ot_u8*) Queue data buffer
  * @retval none
  * @ingroup Queue
  *
  * Most commonly used when multiple frames are in the same queue.
  */
void q_rebase(Queue* q, ot_u8* buffer);



void q_copy(Queue* q1, Queue* q2);



/** @brief Empties the supplied Queue, but doesn't actually erase data
  * @param q        (Queue*) Pointer to the Queue ADT
  * @retval none
  * @ingroup Queue
  */
void q_empty(Queue* q);


/** @brief Starts a queue by loading in config data
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param offset   (ot_uint) bytes to offset the fist data writes from the front
  * @param options  (ot_u16) option bits.  user-defined usage.
  * @retval ot_u8*  Pointer to queue get & putcursor, or NULL if an error
  * @ingroup Queue
  */
ot_u8* q_start(Queue* q, ot_uint offset, ot_u16 options);



/** @brief Returns the current getcursor position, and then moves it forward
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param shift    (ot_int) bytes to move getcursor forward
  * @retval ot_u8*  Pointer to getcursor at original position
  * @ingroup Queue
  */
ot_u8* q_markbyte(Queue* q, ot_int shift);


/** @brief Writes a byte to a Queue's putcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param byte_in  (ot_u8) byte to write
  * @retval none
  * @ingroup Queue
  */
void q_writebyte(Queue* q, ot_u8 byte_in);


/** @brief Writes a 16 bit short integer to the Queue's putcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param short_in (ot_u16) Short integer to write
  * @retval none
  * @ingroup Queue
  * @note The _be variant will use big endian, which is fast for copying data
  *       from the UDB, given that the UDB is big endian and DASH7 also uses big
  *       endian for data streams.  The normal variant will do endian conversion
  *       in order to move integers from memory to the queue.
  */
void q_writeshort(Queue* q, ot_u16 short_in);
void q_writeshort_be(Queue* q, ot_u16 short_in);



/** @brief Writes a 32 bit long integer to the Queue's putcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @param long_in  (ot_u32) Long integer to write
  * @retval none
  * @ingroup Queue
  * @note The _be variant will use big endian, which is fast for copying data
  *       from the UDB, given that the UDB is big endian and DASH7 also uses big
  *       endian for data streams.  The normal variant will do endian conversion
  *       in order to move integers from memory to the queue.
  */
void q_writelong(Queue* q, ot_u32 long_in);



/** @brief Reads a byte at the Queue's getcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @retval ot_u8   Byte read
  * @ingroup Queue
  */
ot_u8 q_readbyte(Queue* q);


/** @brief Reads a 16 bit short integer at the Queue's getcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @retval ot_u16  Short integer read.
  * @ingroup Queue
  * @note The _be variant will use big endian, which is fast for copying data
  *       from the UDB, given that the UDB is big endian and DASH7 also uses big
  *       endian for data streams.  The normal variant will do endian conversion
  *       in order to move integers from memory to the queue.
  */
ot_u16 q_readshort(Queue* q);
ot_u16 q_readshort_be(Queue* q);


/** @brief Reads a 32 bit long integer at the Queue's getcursor, and advances it
  * @param q        (Queue*) Pointer to the Queue ADT
  * @retval ot_u32  Long integer read.
  * @ingroup Queue
  * @note The _be variant will use big endian, which is fast for copying data
  *       from the UDB, given that the UDB is big endian and DASH7 also uses big
  *       endian for data streams.  The normal variant will do endian conversion
  *       in order to move integers from memory to the queue.
  */
ot_u32 q_readlong(Queue* q);


void q_writestring(Queue* q, ot_u8* string, ot_int length);
void q_readstring(Queue* q, ot_u8* string, ot_int length);
opentag/otlib/queue.txt · Last modified: 2012/03/08 22:53 by jpnorair