xqueue.h

00001 /** \file xqueue.h
00002  * 
00003  * Definition and prototypes for xqueue data structure. xqueue is designed for use
00004  * in communication systems and concurrent environments where two processes may
00005  * access the queue, though exclusively one will read and one will write. Read and
00006  * write counts are tracked separately for this reason.
00007  * 
00008  * xqueues are initialized with the address of a buffer and its size, which must
00009  * be a power of two. This is to allow for simple circular access to the buffer
00010  * via masking, instead using a costly modulo operator.
00011  *
00012  * \author Jeff C. Jensen
00013  * \date 2013-12-09
00014  * \copyright Copyright (C) 2013, Jeff C. Jensen, Edward A. Lee, and Sanjit A. Seshia.
00015  *            This software accompanies An Introductory Lab in Embedded and Cyber-Physical Systems
00016  *            and is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0
00017  *            Unported License. See http://leeseshia.org/lab.
00018  */
00019 
00020 #ifndef _XQUEUE_H
00021 #define _XQUEUE_H
00022 
00023 #include "irobotTypes.h"
00024 
00025 /// xqueue_t structure: queue with arbitrary length.
00026 /// Separation of write/read count allows for use in concurrent environments
00027 typedef struct{
00028     uint8_t     *data;              ///< Assigned on initialization to existing buffer
00029     size_t      head;               ///< Buffer write index
00030     size_t      tail;               ///< Buffer read index
00031     size_t      rCount;             ///< Read count
00032     size_t      wCount;             ///< Write count
00033     size_t      capacity;           ///< Maximum size of the data buffer (must be a power of 2, <= 0x8000)
00034     size_t      capacityMask;       ///< Mask used instead of costly modulo operator
00035 } xqueue_t;
00036 
00037 /// Initialize a queue
00038 void xqueue_init(
00039     xqueue_t * const queue,         ///< [out]  Queue struct to initialize
00040     uint8_t * const dataBuffer,     ///< [out]  Raw buffer to which queue will attach
00041     const size_t size               ///< [in]   Size of the raw buffer
00042 );
00043 
00044 /// Number of used elements in the queue
00045 /// \return number of elements in the queue
00046 size_t xqueue_count(
00047     const xqueue_t * const queue    ///< [in]   Target queue
00048 );
00049 
00050 /// Whether or not the queue is empty
00051 /// \return Queue is empty?
00052 bool xqueue_empty(
00053     const xqueue_t * const queue    ///< [in]   Target queue
00054 );
00055 
00056 /// Whether or not the queue is full
00057 /// \return Queue is full?
00058 bool xqueue_full(
00059     const xqueue_t * const queue    ///< [in]   Target queue
00060 );
00061 
00062 /// Number of free elements in the queue
00063 /// \return number of free elements in the queue
00064 size_t xqueue_space(
00065     const xqueue_t * const queue    ///< [in]   Target queue
00066 );
00067 
00068 /// Front element of the queue
00069 /// \return Front element of the queue
00070 uint8_t xqueue_front(
00071     const xqueue_t * const queue    ///< [in]   Target queue
00072 );
00073 
00074 /// Return the back (most recently added) element of the queue
00075 /// \return Back element of the queue
00076 uint8_t xqueue_back(
00077     const xqueue_t * const queue    ///< [in]   Target queue
00078 );
00079 
00080 /// Index an element of the queue
00081 /// \return Indexed element of the queue
00082 uint8_t xqueue_at(
00083     const xqueue_t * const queue,   ///< [in]   Target queue
00084     const size_t index              ///< [in]   Element index
00085 );
00086 
00087 /// Clears a queue; retains buffer address and maximum size
00088 void xqueue_clear(
00089     xqueue_t * const queue          ///< [in/out]   Target queue
00090 );
00091 
00092 /// Push a single element on to a queue
00093 /// \return Value pushed
00094 uint8_t xqueue_push(
00095     xqueue_t * const queue,         ///< [in/out]   Target queue
00096     const uint8_t value             ///< [in]   byte to add to queue
00097 );
00098 
00099 /// Push 8 bits (one element) to a queue
00100 #define xqueue_push8 xqueue_push
00101 
00102 /// Push a 16-bit number to the queue (2 elements)
00103 void xqueue_push16(
00104     xqueue_t * const queue,         ///< [in/out]   Target queue
00105     const uint16_t value            ///< [in]   Element to push
00106 );
00107 
00108 /// Push a 32-bit number to the queue (4 elements)
00109 void xqueue_push32(
00110     xqueue_t * const queue,         ///< [in/out]   Target queue
00111     const uint32_t value            ///< [in]   Element to push
00112 );
00113 
00114 /// Push a stream on to a queue (faster than push_string)
00115 void xqueue_push_buffer(
00116     xqueue_t * const queue,         ///< [in/out]   Target queue
00117     const uint8_t * values,         ///< [in]   Stream to push to queue
00118     const size_t nvalues            ///< [in]   Number of elements to push
00119 );
00120 
00121 /// Push a (null-terminated) string on to a queue
00122 void xqueue_push_string(
00123     xqueue_t * const queue,         ///< [in/out]   Target queue
00124     const unsigned char * str       ///< [in]   String to push to queue (NULL element is not pushed)
00125 );
00126 
00127 /// Pop an element from a queue
00128 /// \return Front (removed) element of the queue
00129 uint8_t xqueue_pop(
00130     xqueue_t * const queue          ///< [in/out]   Target queue
00131 );
00132 
00133 /// Pop an 8-bit value from a queue
00134 #define xqueue_pop8 xqueue_pop
00135 
00136 /// Pop 16 bits (two elements) from a queue
00137 /// \return Packed 16-bit integer containing front two (removed) elements of the queue.
00138 uint16_t xqueue_pop16(
00139     xqueue_t * const queue          ///< [in/out]   Target queue
00140 );
00141 
00142 /// Pop 32 bits (four elements) from a queue
00143 /// \return Packed 32-bit integer containing front four (removed) elements of the queue.
00144 uint32_t xqueue_pop32(
00145     xqueue_t * const queue          ///< [in/out]   Target queue
00146 );
00147 
00148 /// Pop a sequence of elements from a queue
00149 void xqueue_pop_buffer(
00150     xqueue_t * const queue,         ///< [in/out]   Target queue
00151     uint8_t * values,               ///< [out]  Stream to fill with values
00152     const size_t nvalues            ///< [in]   Number of elements to pop
00153 );
00154 
00155 /// Pop an element from a queue; do not return value (fast)
00156 void xqueue_drop(
00157     xqueue_t * const queue          ///< [in/out]   Target queue
00158 );
00159 
00160 /// Pop many elements from a queue (fast)
00161 void xqueue_drop_many(
00162     xqueue_t * const queue,         ///< [in/out]   Target queue
00163     size_t nvalues                  ///< [in]   Number of elements to pop
00164 );
00165 
00166 /// Checksum of n elements currently in the queue
00167 /// \returns 8-bit checksum of n front elements of the queue, queue[fromCount] to queue[fromCount + nvalues]
00168 uint8_t xqueue_checksum(
00169     const xqueue_t * const queue,   ///< [in]   Target queue
00170     size_t nvalues,                 ///< [in]   Number of values over which to sum
00171     const size_t nAdvance           ///< [in]   Number of elements to advance before calculating checksum
00172 );
00173 
00174 
00175 #endif  // _XQUEUE_H