?lang_form? ?lang_select? ?lang_submit? ?lang_endform?
{HEADER END}
{BLAME START}

library

?curdirlinks? -

Blame information for rev 32

Line No. Rev Author Line
1 32 kaklik /* struct_queue.h
2 *************************************************************************
3 * Filename: struct_queue.h
4 * Dependancies: generic.h
5 * Processor: Any
6 * Hardware: Any
7 * Assembler: NA
8 * Linker: Any
9 * Company: Microchip Technology, Inc.
10 *************************************************************************
11 * Software License Agreement:
12 *
13 * The software supplied herewith by Microchip Technology Incorporated
14 * (the Company) for its PICmicro Microcontroller is intended and
15 * supplied to you, the Company's customer, for use solely and
16 * exclusively on Microchip PICmicro Microcontroller products. The
17 * software is owned by the Company and/or its supplier, and is
18 * protected under applicable copyright laws. All rights are reserved.
19 * Any use in violation of the foregoing restrictions may subject the
20 * user to criminal sanctions under applicable laws, as well as to
21 * civil liability for the breach of the terms and conditions of this
22 * license.
23 *
24 * THIS SOFTWARE IS PROVIDED IN AN "AS IS" CONDITION. NO WARRANTIES,
25 * WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING, BUT NOT LIMITED
26 * TO, IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
27 * PARTICULAR PURPOSE APPLY TO THIS SOFTWARE. THE COMPANY SHALL NOT,
28 * IN ANY CIRCUMSTANCES, BE LIABLE FOR SPECIAL, INCIDENTAL OR
29 * CONSEQUENTIAL DAMAGES, FOR ANY REASON WHATSOEVER.
30 *************************************************************************
31 * File Description:
32 *
33 * This file defines primative operations and data structures that provide
34 * a queue abstraction for same-sized structs of data.
35 *
36 * !!!! IMPORTANT: The caller is responsible for copying the data. !!!!
37 *
38 * StructQueue Operations:
39 *
40 * StructQueueInit - Initializes a queue and makes it empty.
41 * StructQueueAdd - Adds an item to a queue.
42 * StructQueueRemove - Removes an item from a queue.
43 * StructQueueIsFull - Checks to see if a queue is full.
44 * StructQueueIsNotFull - Checks to see if a queue is not full.
45 * StructQueueIsEmpty - Checks to see if a queue is empty.
46 * StructQueueIsNotEmpty - Checks to see if a queue is not empty.
47 * StructQueueCount - Provides the count of items a queue.
48 *
49 * Usage:
50 *
51 * Code using the struct queue operations must define and allocate a
52 * struct-queue structure. A struct-queue structure must have the
53 * following members.
54 *
55 * head - Contains the index to the current head item
56 * tail - Contains the incex to the current tail item
57 * count - Contains the current number of items in the queue
58 * buffer[] - Array of queue items
59 *
60 * Example:
61 *
62 * // This structure defines the items the queue will hold.
63 * typedef struct _my_structure
64 * {
65 * //... Define any desired number of elements
66 * } QUEUE_ITEM;
67 *
68 * // This defines how many items the queue will hold.
69 * #define SIZE_OF_MY_QUEUE 8
70 *
71 * // This is the queue data structure.
72 * typedef struct _my_queue
73 * {
74 * int head;
75 * int tail;
76 * int count;
77 * QUEUE_ITEM buffer[SIZE_OF_MY_QUEUE];
78 * } MY_QUEUE;
79 *
80 * Then, allocate as many queues of this type as desired.
81 *
82 * Example:
83 *
84 * MY_QUEUE my_queue1;
85 * MY_QUEUE my_queue2;
86 * //...
87 *
88 * Before a queue can be used, it must be initialized using the
89 * StructQueueInit operation.
90 *
91 * Example:
92 *
93 * StructQueueInit(&my_queue1, SIZE_OF_MY_QUEUE);
94 *
95 * Before peforming an operation that will change the state of a
96 * queue (StructQueueAdd or StructQueueRemove), it is necessary to
97 * check the state of the queue to make sure it is safe to perform
98 * the desired task. (See examples, below.)
99 *
100 * IMPORTANT:
101 *
102 * The caller is responsible for copying the data. The StructQueueAdd
103 * and StructQueueRemove operations will only provide pointers to the
104 * item in the array. They do not copy any data.
105 *
106 * Example:
107 *
108 * QUEUE_ITEM *p_item;
109 *
110 * // Remove an item
111 * if (StructQueueIsNotFull(&my_queue1, SIZE_OF_MY_QUEUE))
112 * {
113 * p_item = StructQueueAdd(&my_queue1, SIZE_OF_MY_QUEUE);
114 * p_item-><member1> = <value1>;
115 * p_item-><member2> = <value2>;
116 * p_item-><member3> = <value3>;
117 * //...
118 * }
119 *
120 * Were <member1> through <member3> are members of the QUEUE_ITEM
121 * structure and <value1> through <value3> are data values appropriate
122 * to that member.
123 *
124 * IMPORTANT:
125 *
126 * The struct queue operations are not atomic and they must be used
127 * in combination to be effective. The caller is responsible for
128 * guarding sequences of operations to ensure that they will execute
129 * atomically, meaning that they will not be interrupted mid-sequence
130 * by code that will also modify the queue. For example, if the queue
131 * is used to synchronize data between a main thread of execution and
132 * an Interrupt Service Routine (ISR).
133 *
134 * Example Thread Sequence:
135 *
136 * QUEUE_ITEM *p_item;
137 *
138 * // Ensure ISR cannot execute by masking appropriate interrupt.
139 *
140 * // Remove an item
141 * if (StructQueueIsNotFull(&my_queue1, SIZE_OF_MY_QUEUE))
142 * {
143 * p_item = StructQueueAdd(&my_queue1, SIZE_OF_MY_QUEUE);
144 * p_item-><member1> = <value1>;
145 * p_item-><member2> = <value2>;
146 * p_item-><member3> = <value3>;
147 * //...
148 * }
149 *
150 * // Unmask the interrupt, allowing the ISR to execute when ready.
151 *
152 * Example ISR Sequence:
153 *
154 * QUEUE_ITEM *p_item;
155 *
156 * // Add an item
157 * if (StructQueueIsNotFull(&my_queue1, SIZE_OF_MY_QUEUE))
158 * {
159 * p_item = StructQueueAdd(&my_queue1, SIZE_OF_MY_QUEUE);
160 * p_item-><member1> = <value1>;
161 * p_item-><member2> = <value2>;
162 * p_item-><member3> = <value3>;
163 * //...
164 * }
165 *
166 * The ISR seqeunce generally does not need to be guarded since it
167 * cannot execute during the guarded sequence if its interrupt has
168 * been disabled.
169 *
170 * Notes:
171 *
172 * It is an error to enqueue an item into a full queue and it will
173 * result in an access violation. before performing a StructQueueAdd
174 * operation, the caller must first use one or more of the other
175 * operations to determine if the queue has room.
176 *
177 * It is an error to dequeue an item from an empty queue and it will
178 * result in an access violation. Before performing a
179 * StructQueueRemove operation, the caller must first perform one or
180 * more of the other primatives to ensure that the queue has an item
181 * to remove.
182 *
183 * A particular type of queue may only contain one type of item
184 * unless a union type is used for the queue's buffer array.
185 *
186 * The struct-queue primative operations are defined as typless
187 * macros. Thus, they will behave the same for any type of buffer
188 * array as long as the queue structure has the same member names.
189 *
190 * Change History:
191 *
192 * Author Date Comment
193 *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
194 * Bud Caldwell 9/26/2007 Original Implementation.
195 *************************************************************************/
196  
197 #ifndef STRUCT_QUEUE_H
198 #define STRUCT_QUEUE_H
199  
200  
201 /* StructQueueInit
202 *************************************************************************
203 * Precondition: None
204 *
205 * Input: q Pointer to the queue data structure
206 *
207 * N Number of elements in the queue data buffer array
208 *
209 * Output: None
210 *
211 * Returns: zero (0)
212 *
213 * Side Effects: The queue structure has been initialized and is ready
214 * to use.
215 *
216 * Overview: This operation initializes a queue and makes it empty.
217 *
218 * Note: This operation is implemented with a macro that
219 * supports queues of any type of data items.
220 *************************************************************************/
221  
222 #define StructQueueInit(q,N) ( (q)->head = (N), \
223 (q)->tail = (N), \
224 (q)->count = 0 )
225  
226  
227 /* StructQueueAdd
228 *************************************************************************
229 * Precondition: The queue must have been initialized and must not
230 * currently be full.
231 *
232 * Input: q Pointer to the queue data structure
233 *
234 * N Number of elements in the queue data buffer array
235 *
236 * Output: None
237 *
238 * Returns: The address of the new item in the queue.
239 *
240 * Side Effects: The item has been added to the queue.
241 *
242 * IMPORTANT! No data has been copied to the item.
243 *
244 * Overview: This operation adds (enqueues) a new item into the
245 * queue data buffer and updates the head index,
246 * handling buffer wrap correctly.
247 *
248 * Notes: The caller must first ensure that the queue is not
249 * full by performing one of the other operations (such
250 * as "StructQueueIsNotFull") before performing this
251 * operation. Adding an item into a full queue will
252 * cause an access violation.
253 *
254 * This operation is implemented with a macro that
255 * supports queues of any type of data items.
256 *************************************************************************/
257  
258 #define StructQueueAdd(q,N) ( (q)->count++, \
259 ( ((q)->head < (N-1)) ? \
260 ((q)->head++) : \
261 ((q)->head=0) ), \
262 &(q)->buffer[(q)->head] )
263  
264  
265 /* StructQueueRemove
266 *************************************************************************
267 * Precondition: The queue must have been initialized and not currently
268 * be empty.
269 *
270 * Input: q Pointer to the queue data structure
271 *
272 * N Number of elements in the queue data buffer array
273 *
274 * Output: None
275 *
276 * Returns: The item removed.
277 *
278 * Side Effects: The item has been removed from the queue.
279 *
280 * IMPORTANT! No data has been copied from the item.
281 *
282 * Overview: This routine removes (dequeues) an item from the
283 * queue data buffer and updates the tail index,
284 * handling buffer wrap correctly.
285 *
286 * Notes: The caller must first ensure that the queue is not
287 * empty by calling one or more of the other operations
288 * (such as "StructQueueIsNotEmpty") before performing this
289 * operation. Dequeueing an item from an empty queue
290 * will cause an access violation.
291 *
292 * This operation is implemented with a macro that
293 * supports queues of any type of data items.
294 *************************************************************************/
295  
296 #define StructQueueRemove(q,N) ( (q)->count--, \
297 ( ((q)->tail < (N-1)) ? \
298 ((q)->tail++) : \
299 ((q)->tail=0) ), \
300 &(q)->buffer[(q)->tail] )
301  
302  
303 /* StructQueuePeekTail
304 *************************************************************************
305 * Precondition: The queue must have been initialized and not currently
306 * be empty.
307 *
308 * Input: q Pointer to the queue data structure
309 *
310 * N Number of elements in the queue data buffer array
311 *
312 * Output: None
313 *
314 * Returns: The item at the tail of the queue.
315 *
316 * Side Effects: None
317 *
318 * IMPORTANT! No data has been copied from the item.
319 *
320 * Overview: This routine provides access to an item in the
321 * queue data buffer at the tail index position,
322 * handling buffer wrap correctly.
323 *
324 * Notes: The caller must first ensure that the queue is not
325 * empty by calling one or more of the other operations
326 * (such as "StructQueueIsNotEmpty") before performing this
327 * operation.
328 *
329 * This operation is implemented with a macro that
330 * supports queues of any type of data items.
331 *************************************************************************/
332  
333 #define StructQueuePeekTail(q,N) ( ((q)->tail < (N-1)) ? \
334 &(q)->buffer[(q)->tail+1] : \
335 &(q)->buffer[0] )
336  
337  
338 /* StructQueueIsFull
339 *************************************************************************
340 * Precondition: The queue must be initialized.
341 *
342 * Input: q Pointer to the queue data structure
343 *
344 * N Number of elements in the queue data buffer array
345 *
346 * Output: None
347 *
348 * Returns: TRUE if the queue is full, FALSE otherwise.
349 *
350 * Side Effects: None
351 *
352 * Overview: This routine checks to see if the queue is full.
353 *
354 * Note: This operation is implemented with a macro that
355 * supports queues of any type of data items.
356 *************************************************************************/
357  
358 #define StructQueueIsFull(q,N) ( (q)->count >= N )
359  
360  
361 /* StructQueueIsNotFull
362 *************************************************************************
363 * Precondition: The queue must be initialized.
364 *
365 * Input: q Pointer to the queue data structure
366 *
367 * N Number of elements in the queue data buffer array
368 *
369 * Output: None
370 *
371 * Returns: FALSE if the queue is full, TRUE otherwise.
372 *
373 * Side Effects: None
374 *
375 * Overview: This routine checks to see if the queue is full.
376 *
377 * Note: This operation is implemented with a macro that
378 * supports queues of any type of data items.
379 *************************************************************************/
380  
381 #define StructQueueIsNotFull(q,N) ( (q)->count < N )
382  
383  
384 /* StructQueueIsEmpty
385 *************************************************************************
386 * Precondition: The queue must be initialized.
387 *
388 * Input: q Pointer to the queue data structure
389 *
390 * N Number of elements in the queue data buffer array
391 *
392 * Output: None
393 *
394 * Returns: TRUE if the queue is empty, FALSE otherwise.
395 *
396 * Side Effects: None
397 *
398 * Overview: This routine checks to see if the queue is empty.
399 *
400 * Note: This operation is implemented with a macro that
401 * supports queues of any type of data items.
402 *************************************************************************/
403  
404 #define StructQueueIsEmpty(q,N) ( (q)->count == 0 )
405  
406  
407 /* StructQueueIsNotEmpty
408 *************************************************************************
409 * Precondition: The queue must be initialized.
410 *
411 * Input: q Pointer to the queue data structure
412 *
413 * N Number of elements in the queue data buffer array
414 *
415 * Output: None
416 *
417 * Returns: FALSE if the queue is empty, TRUE otherwise.
418 *
419 * Side Effects: None
420 *
421 * Overview: This routine checks to see if the queue is not empty.
422 *
423 * Note: This operation is implemented with a macro that
424 * supports queues of any type of data items.
425 *************************************************************************/
426  
427 #define StructQueueIsNotEmpty(q,N) ( (q)->count != 0 )
428  
429  
430 /* StructQueueSpaceAvailable
431 *************************************************************************
432 * Precondition: The queue must be initialized.
433 *
434 * Input: q Pointer to the queue data structure
435 *
436 * N Number of elements in the queue data buffer array
437 *
438 * Output: None
439 *
440 * Returns: TRUE if the queue has the indicated number of slots
441 available, FALSE otherwise.
442 *
443 * Side Effects: None
444 *
445 * Overview: This routine checks to see if the queue has at least
446 * the specified number of slots free.
447 *
448 * Note: This operation is implemented with a macro that
449 * supports queues of any type of data items.
450 *************************************************************************/
451  
452 #define StructQueueSpaceAvailable(c,q,N) ( ((q)->count + c) <= N )
453  
454  
455 /* StructQueueCount
456 *************************************************************************
457 * Precondition: The queue must be initialized.
458 *
459 * Input: q Pointer to the queue data structure
460 *
461 * N Number of elements in the queue data buffer array
462 *
463 * Output: None
464 *
465 * Returns: The number of items in the queue.
466 *
467 * Side Effects: None
468 *
469 * Overview: This routine provides the number of items in the queue.
470 *
471 * Note: This operation is implemented with a macro that
472 * supports queues of any type of data items.
473 *************************************************************************/
474  
475 #define StructQueueCount(q,N) ( (q)->count )
476  
477  
478 #endif // STRUCT_QUEUE_H
479 /*************************************************************************
480 * EOF struct_queue.c
481 */
482  
{BLAME END}
{FOOTER START}

Powered by WebSVN v2.8.3