|
1 /* |
|
2 LUFA Library |
|
3 Copyright (C) Dean Camera, 2010. |
|
4 |
|
5 dean [at] fourwalledcubicle [dot] com |
|
6 www.fourwalledcubicle.com |
|
7 */ |
|
8 |
|
9 /* |
|
10 Copyright 2010 Dean Camera (dean [at] fourwalledcubicle [dot] com) |
|
11 |
|
12 Permission to use, copy, modify, distribute, and sell this |
|
13 software and its documentation for any purpose is hereby granted |
|
14 without fee, provided that the above copyright notice appear in |
|
15 all copies and that both that the copyright notice and this |
|
16 permission notice and warranty disclaimer appear in supporting |
|
17 documentation, and that the name of the author not be used in |
|
18 advertising or publicity pertaining to distribution of the |
|
19 software without specific, written prior permission. |
|
20 |
|
21 The author disclaim all warranties with regard to this |
|
22 software, including all implied warranties of merchantability |
|
23 and fitness. In no event shall the author be liable for any |
|
24 special, indirect or consequential damages or any damages |
|
25 whatsoever resulting from loss of use, data or profits, whether |
|
26 in an action of contract, negligence or other tortious action, |
|
27 arising out of or in connection with the use or performance of |
|
28 this software. |
|
29 */ |
|
30 |
|
31 /** \file |
|
32 * |
|
33 * Ultra lightweight ring buffer, for fast insertion/deletion. |
|
34 */ |
|
35 |
|
36 #ifndef _ULW_RING_BUFF_H_ |
|
37 #define _ULW_RING_BUFF_H_ |
|
38 |
|
39 /* Includes: */ |
|
40 #include <util/atomic.h> |
|
41 |
|
42 #include <stdint.h> |
|
43 #include <stdbool.h> |
|
44 |
|
45 /* Defines: */ |
|
46 /** Size of each ring buffer, in data elements - must be between 1 and 255. */ |
|
47 #define BUFFER_SIZE 128 |
|
48 |
|
49 /** Maximum number of data elements to buffer before forcing a flush. |
|
50 * Must be less than BUFFER_SIZE |
|
51 */ |
|
52 #define BUFFER_NEARLY_FULL 96 |
|
53 |
|
54 /** Type of data to store into the buffer. */ |
|
55 #define RingBuff_Data_t uint8_t |
|
56 |
|
57 /** Datatype which may be used to store the count of data stored in a buffer, retrieved |
|
58 * via a call to \ref RingBuffer_GetCount(). |
|
59 */ |
|
60 #if (BUFFER_SIZE <= 0xFF) |
|
61 #define RingBuff_Count_t uint8_t |
|
62 #else |
|
63 #define RingBuff_Count_t uint16_t |
|
64 #endif |
|
65 |
|
66 /* Type Defines: */ |
|
67 /** Type define for a new ring buffer object. Buffers should be initialized via a call to |
|
68 * \ref RingBuffer_InitBuffer() before use. |
|
69 */ |
|
70 typedef struct |
|
71 { |
|
72 RingBuff_Data_t Buffer[BUFFER_SIZE]; /**< Internal ring buffer data, referenced by the buffer pointers. */ |
|
73 RingBuff_Data_t* In; /**< Current storage location in the circular buffer */ |
|
74 RingBuff_Data_t* Out; /**< Current retrieval location in the circular buffer */ |
|
75 RingBuff_Count_t Count; |
|
76 } RingBuff_t; |
|
77 |
|
78 /* Inline Functions: */ |
|
79 /** Initializes a ring buffer ready for use. Buffers must be initialized via this function |
|
80 * before any operations are called upon them. Already initialized buffers may be reset |
|
81 * by re-initializing them using this function. |
|
82 * |
|
83 * \param[out] Buffer Pointer to a ring buffer structure to initialize |
|
84 */ |
|
85 static inline void RingBuffer_InitBuffer(RingBuff_t* const Buffer) |
|
86 { |
|
87 ATOMIC_BLOCK(ATOMIC_RESTORESTATE) |
|
88 { |
|
89 Buffer->In = Buffer->Buffer; |
|
90 Buffer->Out = Buffer->Buffer; |
|
91 } |
|
92 } |
|
93 |
|
94 /** Retrieves the minimum number of bytes stored in a particular buffer. This value is computed |
|
95 * by entering an atomic lock on the buffer while the IN and OUT locations are fetched, so that |
|
96 * the buffer cannot be modified while the computation takes place. This value should be cached |
|
97 * when reading out the contents of the buffer, so that as small a time as possible is spent |
|
98 * in an atomic lock. |
|
99 * |
|
100 * \note The value returned by this function is guaranteed to only be the minimum number of bytes |
|
101 * stored in the given buffer; this value may change as other threads write new data and so |
|
102 * the returned number should be used only to determine how many successive reads may safely |
|
103 * be performed on the buffer. |
|
104 * |
|
105 * \param[in] Buffer Pointer to a ring buffer structure whose count is to be computed |
|
106 */ |
|
107 static inline RingBuff_Count_t RingBuffer_GetCount(RingBuff_t* const Buffer) |
|
108 { |
|
109 RingBuff_Count_t Count; |
|
110 |
|
111 ATOMIC_BLOCK(ATOMIC_RESTORESTATE) |
|
112 { |
|
113 Count = Buffer->Count; |
|
114 } |
|
115 |
|
116 return Count; |
|
117 } |
|
118 |
|
119 /** Atomically determines if the specified ring buffer contains any free space. This should |
|
120 * be tested before storing data to the buffer, to ensure that no data is lost due to a |
|
121 * buffer overrun. |
|
122 * |
|
123 * \param[in,out] Buffer Pointer to a ring buffer structure to insert into |
|
124 * |
|
125 * \return Boolean true if the buffer contains no free space, false otherwise |
|
126 */ |
|
127 static inline bool RingBuffer_IsFull(RingBuff_t* const Buffer) |
|
128 { |
|
129 return (RingBuffer_GetCount(Buffer) == BUFFER_SIZE); |
|
130 } |
|
131 |
|
132 /** Atomically determines if the specified ring buffer contains any data. This should |
|
133 * be tested before removing data from the buffer, to ensure that the buffer does not |
|
134 * underflow. |
|
135 * |
|
136 * If the data is to be removed in a loop, store the total number of bytes stored in the |
|
137 * buffer (via a call to the \ref RingBuffer_GetCount() function) in a temporary variable |
|
138 * to reduce the time spent in atomicity locks. |
|
139 * |
|
140 * \param[in,out] Buffer Pointer to a ring buffer structure to insert into |
|
141 * |
|
142 * \return Boolean true if the buffer contains no free space, false otherwise |
|
143 */ |
|
144 static inline bool RingBuffer_IsEmpty(RingBuff_t* const Buffer) |
|
145 { |
|
146 return (RingBuffer_GetCount(Buffer) == 0); |
|
147 } |
|
148 |
|
149 /** Inserts an element into the ring buffer. |
|
150 * |
|
151 * \note Only one execution thread (main program thread or an ISR) may insert into a single buffer |
|
152 * otherwise data corruption may occur. Insertion and removal may occur from different execution |
|
153 * threads. |
|
154 * |
|
155 * \param[in,out] Buffer Pointer to a ring buffer structure to insert into |
|
156 * \param[in] Data Data element to insert into the buffer |
|
157 */ |
|
158 static inline void RingBuffer_Insert(RingBuff_t* const Buffer, |
|
159 const RingBuff_Data_t Data) |
|
160 { |
|
161 *Buffer->In = Data; |
|
162 |
|
163 if (++Buffer->In == &Buffer->Buffer[BUFFER_SIZE]) |
|
164 Buffer->In = Buffer->Buffer; |
|
165 |
|
166 ATOMIC_BLOCK(ATOMIC_RESTORESTATE) |
|
167 { |
|
168 Buffer->Count++; |
|
169 } |
|
170 } |
|
171 |
|
172 /** Removes an element from the ring buffer. |
|
173 * |
|
174 * \note Only one execution thread (main program thread or an ISR) may remove from a single buffer |
|
175 * otherwise data corruption may occur. Insertion and removal may occur from different execution |
|
176 * threads. |
|
177 * |
|
178 * \param[in,out] Buffer Pointer to a ring buffer structure to retrieve from |
|
179 * |
|
180 * \return Next data element stored in the buffer |
|
181 */ |
|
182 static inline RingBuff_Data_t RingBuffer_Remove(RingBuff_t* const Buffer) |
|
183 { |
|
184 RingBuff_Data_t Data = *Buffer->Out; |
|
185 |
|
186 if (++Buffer->Out == &Buffer->Buffer[BUFFER_SIZE]) |
|
187 Buffer->Out = Buffer->Buffer; |
|
188 |
|
189 ATOMIC_BLOCK(ATOMIC_RESTORESTATE) |
|
190 { |
|
191 Buffer->Count--; |
|
192 } |
|
193 |
|
194 return Data; |
|
195 } |
|
196 |
|
197 #endif |