source: rtems/cpukit/sapi/include/rtems/chain.h @ 059529e

Last change on this file since 059529e was 059529e, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 21, 2016 at 8:15:02 AM

score: Add debug support to chains

This helps to detect

  • double insert, append, prepend errors, and
  • get from empty chain errors.
  • Property mode set to 100644
File size: 19.7 KB
Line 
1/**
2 * @file
3 *
4 * @brief Chain API
5 */
6
7/*
8 *  Copyright (c) 2010-2014 embedded brains GmbH.
9 *
10 *  COPYRIGHT (c) 1989-2008.
11 *  On-Line Applications Research Corporation (OAR).
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.org/license/LICENSE.
16 */
17
18#ifndef _RTEMS_CHAIN_H
19#define _RTEMS_CHAIN_H
20
21#include <rtems/score/chainimpl.h>
22#include <rtems/rtems/event.h>
23
24#ifdef __cplusplus
25extern "C" {
26#endif
27
28/**
29 * @defgroup ClassicChains Chains
30 *
31 * @ingroup ClassicRTEMS
32 *
33 * @brief Chain API
34 */
35/**@{**/
36
37typedef Chain_Node rtems_chain_node;
38
39typedef Chain_Control rtems_chain_control;
40
41/**
42 *  @brief Chain initializer for an empty chain with designator @a name.
43 */
44#define RTEMS_CHAIN_INITIALIZER_EMPTY( name ) \
45  CHAIN_INITIALIZER_EMPTY( name )
46
47/**
48 *  @brief Chain initializer for a chain with one @a node.
49 *
50 *  @see RTEMS_CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN().
51 */
52#define RTEMS_CHAIN_INITIALIZER_ONE_NODE( node ) \
53  CHAIN_INITIALIZER_ONE_NODE( node )
54
55/**
56 *  @brief Chain node initializer for a @a chain containing exactly this node.
57 *
58 *  @see RTEMS_CHAIN_INITIALIZER_ONE_NODE().
59 */
60#define RTEMS_CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN( chain ) \
61  CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN( chain )
62
63/**
64 *  @brief Chain definition for an empty chain with designator @a name.
65 */
66#define RTEMS_CHAIN_DEFINE_EMPTY( name ) \
67  rtems_chain_control name = RTEMS_CHAIN_INITIALIZER_EMPTY( name )
68
69/**
70 * @brief Appends the @a node to the @a chain and sends the @a events to the
71 * @a task if the @a chain was empty before the append.
72 *
73 * @see rtems_chain_append_with_empty_check() and rtems_event_send().
74 *
75 * @retval RTEMS_SUCCESSFUL Successful operation.
76 * @retval RTEMS_INVALID_ID No such task.
77 */
78rtems_status_code rtems_chain_append_with_notification(
79  rtems_chain_control *chain,
80  rtems_chain_node *node,
81  rtems_id task,
82  rtems_event_set events
83);
84
85/**
86 * @brief Prepends the @a node to the @a chain and sends the @a events to the
87 * @a task if the @a chain was empty before the prepend.
88 *
89 * @see rtems_chain_prepend_with_empty_check() and rtems_event_send().
90 *
91 * @retval RTEMS_SUCCESSFUL Successful operation.
92 * @retval RTEMS_INVALID_ID No such task.
93 */
94rtems_status_code rtems_chain_prepend_with_notification(
95  rtems_chain_control *chain,
96  rtems_chain_node *node,
97  rtems_id task,
98  rtems_event_set events
99);
100
101/**
102 * @brief Gets the first @a node of the @a chain and sends the @a events to the
103 * @a task if the @a chain is empty after the get.
104 *
105 * @see rtems_chain_get_with_empty_check() and rtems_event_send().
106 *
107 * @retval RTEMS_SUCCESSFUL Successful operation.
108 * @retval RTEMS_INVALID_ID No such task.
109 */
110rtems_status_code rtems_chain_get_with_notification(
111  rtems_chain_control *chain,
112  rtems_id task,
113  rtems_event_set events,
114  rtems_chain_node **node
115);
116
117/**
118 * @brief Gets the first @a node of the @a chain and sends the @a events to the
119 * @a task if the @a chain is empty afterwards.
120 *
121 * @see rtems_chain_get() and rtems_event_receive().
122 *
123 * @retval RTEMS_SUCCESSFUL Successful operation.
124 * @retval RTEMS_TIMEOUT Timeout.
125 */
126rtems_status_code rtems_chain_get_with_wait(
127  rtems_chain_control *chain,
128  rtems_event_set events,
129  rtems_interval timeout,
130  rtems_chain_node **node
131);
132
133/**
134 * @brief Initialize a chain Header.
135 *
136 * This routine initializes @a the_chain structure to manage the
137 * contiguous array of @a number_nodes nodes which starts at
138 * @a starting_address.  Each node is of @a node_size bytes.
139 *
140 * @param[in] the_chain specifies the chain to initialize
141 * @param[in] starting_address is the starting address of the array
142 *        of elements
143 * @param[in] number_nodes is the number of nodes that will be in the chain
144 * @param[in] node_size is the size of each node
145 */
146RTEMS_INLINE_ROUTINE void rtems_chain_initialize(
147  rtems_chain_control *the_chain,
148  void                *starting_address,
149  size_t               number_nodes,
150  size_t               node_size
151)
152{
153  _Chain_Initialize(
154    the_chain,
155    starting_address,
156    number_nodes,
157    node_size
158  );
159}
160
161/**
162 * @brief Initialize this chain as empty.
163 *
164 * This routine initializes the specified chain to contain zero nodes.
165 *
166 * @param[in] the_chain is the chain to be initialized.
167 */
168RTEMS_INLINE_ROUTINE void rtems_chain_initialize_empty(
169  rtems_chain_control *the_chain
170)
171{
172  _Chain_Initialize_empty( the_chain );
173}
174
175/**
176 * @brief Set off chain.
177 *
178 * This function sets the next and previous fields of the @a node to NULL
179 * indicating the @a node is not part of a chain.
180 *
181 * @param[in] node the node set to off chain.
182 */
183RTEMS_INLINE_ROUTINE void rtems_chain_set_off_chain(
184  rtems_chain_node *node
185)
186{
187  _Chain_Set_off_chain( node );
188}
189
190/**
191 * @brief Initializes a chain node.
192 *
193 * In debug configurations, the node is set off chain.  In all other
194 * configurations, this function does nothing.
195 *
196 * @param[in] the_node The chain node to initialize.
197 */
198RTEMS_INLINE_ROUTINE void rtems_chain_initialize_node(
199  rtems_chain_node *node
200)
201{
202  _Chain_Initialize_node( node );
203}
204
205/**
206 * @brief Is the node off chain.
207 *
208 * This function returns true if the @a node is not on a chain. A @a node is
209 * off chain if the next and previous fields are set to NULL.
210 *
211 * @param[in] node is the node off chain.
212 *
213 * @retval true The node is off chain.
214 * @retval false The node is not off chain.
215 */
216RTEMS_INLINE_ROUTINE bool rtems_chain_is_node_off_chain(
217  const rtems_chain_node *node
218)
219{
220  return _Chain_Is_node_off_chain( node );
221}
222
223/**
224 * @brief Is the chain node pointer NULL.
225 *
226 * This function returns true if the_node is NULL and false otherwise.
227 *
228 * @param[in] the_node is the node pointer to check.
229 *
230 * @retval true The chain node pointer is NULL.
231 * @retval false The chain node pointer is not NULL.
232 */
233RTEMS_INLINE_ROUTINE bool rtems_chain_is_null_node(
234  const rtems_chain_node *the_node
235)
236{
237  return _Chain_Is_null_node( the_node );
238}
239
240/**
241 * @brief Return pointer to Chain Head
242 *
243 * This function returns a pointer to the first node on the chain.
244 *
245 * @param[in] the_chain is the chain to be operated upon.
246 *
247 * @return This method returns the permanent node of the chain.
248 */
249RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_head(
250  rtems_chain_control *the_chain
251)
252{
253  return _Chain_Head( the_chain );
254}
255
256/**
257 * @brief Return pointer to immutable Chain Head
258 *
259 * This function returns a pointer to the head node on the chain.
260 *
261 * @param[in] the_chain is the chain to be operated upon.
262 *
263 * @return This method returns the permanent head node of the chain.
264 */
265RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_head(
266  const rtems_chain_control *the_chain
267)
268{
269  return _Chain_Immutable_head( the_chain );
270}
271
272/**
273 * @brief Return pointer to Chain Tail
274 *
275 * This function returns a pointer to the tail node on the chain.
276 *
277 * @param[in] the_chain is the chain to be operated upon.
278 *
279 * @return This method returns the permanent tail node of the chain.
280 */
281RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_tail(
282  rtems_chain_control *the_chain
283)
284{
285  return _Chain_Tail( the_chain );
286}
287
288/**
289 * @brief Return pointer to immutable Chain Tail
290 *
291 * This function returns a pointer to the tail node on the chain.
292 *
293 * @param[in] the_chain is the chain to be operated upon.
294 *
295 * @return This method returns the permanent tail node of the chain.
296 */
297RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_tail(
298  const rtems_chain_control *the_chain
299)
300{
301  return _Chain_Immutable_tail( the_chain );
302}
303
304/**
305 * @brief Return pointer to Chain's First node after the permanent head.
306 *
307 * This function returns a pointer to the first node on the chain after the
308 * head.
309 *
310 * @param[in] the_chain is the chain to be operated upon.
311 *
312 * @return This method returns the first node of the chain.
313 */
314RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_first(
315  rtems_chain_control *the_chain
316)
317{
318  return _Chain_First( the_chain );
319}
320
321/**
322 * @brief Return pointer to immutable Chain's First node
323 *
324 * This function returns a pointer to the first node on the chain after the
325 * head.
326 *
327 * @param[in] the_chain is the chain to be operated upon.
328 *
329 * @return This method returns the first node of the chain.
330 */
331RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_first(
332  const rtems_chain_control *the_chain
333)
334{
335  return _Chain_Immutable_first( the_chain );
336}
337
338/**
339 * @brief Return pointer to Chain's Last node before the permanent tail.
340 *
341 * This function returns a pointer to the last node on the chain just before
342 * the tail.
343 *
344 * @param[in] the_chain is the chain to be operated upon.
345 *
346 * @return This method returns the last node of the chain.
347 */
348RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_last(
349  rtems_chain_control *the_chain
350)
351{
352  return _Chain_Last( the_chain );
353}
354
355/**
356 * @brief Return pointer to immutable Chain's Last node
357 *
358 * This function returns a pointer to the last node on the chain just before
359 * the tail.
360 *
361 * @param[in] the_chain is the chain to be operated upon.
362 *
363 * @return This method returns the last node of the chain.
364 */
365RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_last(
366  const rtems_chain_control *the_chain
367)
368{
369  return _Chain_Immutable_last( the_chain );
370}
371
372/**
373 * @brief Return pointer the next node from this node
374 *
375 * This function returns a pointer to the next node after this node.
376 *
377 * @param[in] the_node is the node to be operated upon.
378 *
379 * @return This method returns the next node on the chain.
380 */
381RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_next(
382  rtems_chain_node *the_node
383)
384{
385  return _Chain_Next( the_node );
386}
387
388/**
389 * @brief Return pointer the immutable next node from this node
390 *
391 * This function returns a pointer to the next node after this node.
392 *
393 * @param[in] the_node is the node to be operated upon.
394 *
395 * @return This method returns the next node on the chain.
396 */
397RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_next(
398  const rtems_chain_node *the_node
399)
400{
401  return _Chain_Immutable_next( the_node );
402}
403
404/**
405 * @brief Return pointer the previous node from this node
406 *
407 * This function returns a pointer to the previous node on this chain.
408 *
409 * @param[in] the_node is the node to be operated upon.
410 *
411 * @return This method returns the previous node on the chain.
412 */
413RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_previous(
414  rtems_chain_node *the_node
415)
416{
417  return _Chain_Previous( the_node );
418}
419
420/**
421 * @brief Return pointer the immutable previous node from this node.
422 *
423 * This function returns a pointer to the previous node on this chain.
424 *
425 * @param[in] the_node is the node to be operated upon.
426 *
427 * @return This method returns the previous node on the chain.
428 */
429RTEMS_INLINE_ROUTINE const rtems_chain_node *rtems_chain_immutable_previous(
430  const rtems_chain_node *the_node
431)
432{
433  return _Chain_Immutable_previous( the_node );
434}
435
436/**
437 * @brief Are Two nodes equal.
438 *
439 * This function returns true if @a left and @a right are equal,
440 * and false otherwise.
441 *
442 * @param[in] left is the node on the left hand side of the comparison.
443 * @param[in] right is the node on the left hand side of the comparison.
444 *
445 * @retval true @a left is equal to @a right.
446 * @retval false @a left is not equal to @a right
447 */
448RTEMS_INLINE_ROUTINE bool rtems_chain_are_nodes_equal(
449  const rtems_chain_node *left,
450  const rtems_chain_node *right
451)
452{
453  return _Chain_Are_nodes_equal( left, right );
454}
455
456/**
457 * @brief Is the chain empty
458 *
459 * This function returns true if there a no nodes on @a the_chain and
460 * false otherwise.
461 *
462 * @param[in] the_chain is the chain to be operated upon.
463 *
464 * @retval true The chain is empty.
465 * @retval false The chain is not empty.
466 */
467RTEMS_INLINE_ROUTINE bool rtems_chain_is_empty(
468  const rtems_chain_control *the_chain
469)
470{
471  return _Chain_Is_empty( the_chain );
472}
473
474/**
475 * @brief Is this the first node on the chain.
476 *
477 * This function returns true if the_node is the first node on a chain and
478 * false otherwise.
479 *
480 * @param[in] the_node is the node the caller wants to know if it is
481 *            the first node on a chain.
482 *
483 * @retval true @a the_node is the first node on a chain.
484 * @retval false @a the_node is not the first node on a chain.
485 */
486RTEMS_INLINE_ROUTINE bool rtems_chain_is_first(
487  const rtems_chain_node *the_node
488)
489{
490  return _Chain_Is_first( the_node );
491}
492
493/**
494 * @brief Is this the last node on the chain.
495 *
496 * This function returns true if @a the_node is the last node on a chain and
497 * false otherwise.
498 *
499 * @param[in] the_node is the node to check as the last node.
500 *
501 * @retval true @a the_node is the last node on a chain.
502 * @retval false @a the_node is not the last node on a chain
503 */
504RTEMS_INLINE_ROUTINE bool rtems_chain_is_last(
505  const rtems_chain_node *the_node
506)
507{
508  return _Chain_Is_last( the_node );
509}
510
511/**
512 * @brief Does this chain have only one node.
513 *
514 * This function returns true if there is only one node on @a the_chain and
515 * false otherwise.
516 *
517 * @param[in] the_chain is the chain to be operated upon.
518 *
519 * @retval true The chain has only one node.
520 * @retval false The chain has more than one nodes.
521 */
522RTEMS_INLINE_ROUTINE bool rtems_chain_has_only_one_node(
523  const rtems_chain_control *the_chain
524)
525{
526  return _Chain_Has_only_one_node( the_chain );
527}
528
529/**
530 * @brief Is this node the chain head.
531 *
532 * This function returns true if @a the_node is the head of the_chain and
533 * false otherwise.
534 *
535 * @param[in] the_chain is the chain to be operated upon.
536 * @param[in] the_node is the node to check for being the Chain Head.
537 *
538 * @retval true @a the_node is the head of @a the_chain.
539 * @retval false @a the_node is not the head of @a the_chain.
540 */
541RTEMS_INLINE_ROUTINE bool rtems_chain_is_head(
542  const rtems_chain_control *the_chain,
543  const rtems_chain_node *the_node
544)
545{
546  return _Chain_Is_head( the_chain, the_node );
547}
548
549/**
550 * @brief Is this node the chain tail.
551 *
552 * This function returns true if the_node is the tail of the_chain and
553 * false otherwise.
554 *
555 * @param[in] the_chain is the chain to be operated upon.
556 * @param[in] the_node is the node to check for being the Chain Tail.
557 *
558 * @retval true @a the_node is the tail of @a the_chain.
559 * @retval false @a the_node is not the tail of @a the_chain.
560 */
561RTEMS_INLINE_ROUTINE bool rtems_chain_is_tail(
562  const rtems_chain_control *the_chain,
563  const rtems_chain_node *the_node
564)
565{
566  return _Chain_Is_tail( the_chain, the_node );
567}
568
569/**
570 * @brief Extract the specified node from a chain.
571 *
572 * This routine extracts @a the_node from the chain on which it resides.
573 * It disables interrupts to ensure the atomicity of the
574 * extract operation.
575 *
576 * @arg the_node specifies the node to extract
577 */
578void rtems_chain_extract(
579  rtems_chain_node *the_node
580);
581
582/**
583 * @brief Extract the specified node from a chain (unprotected).
584 *
585 * This routine extracts @a the_node from the chain on which it resides.
586 *
587 * NOTE: It does NOT disable interrupts to ensure the atomicity of the
588 * append operation.
589 */
590RTEMS_INLINE_ROUTINE void rtems_chain_extract_unprotected(
591  rtems_chain_node *the_node
592)
593{
594  _Chain_Extract_unprotected( the_node );
595}
596
597/**
598 * @brief Obtain the first node on a chain.
599 *
600 * This function removes the first node from @a the_chain and returns
601 * a pointer to that node.  If @a the_chain is empty, then NULL is returned.
602 *
603 * @return This method returns a pointer a node.  If a node was removed,
604 *         then a pointer to that node is returned.  If @a the_chain was
605 *         empty, then NULL is returned.
606 *
607 *  NOTE: It disables interrupts to ensure the atomicity of the get operation.
608 */
609rtems_chain_node *rtems_chain_get(
610  rtems_chain_control *the_chain
611);
612
613/**
614 * @brief See _Chain_Get_unprotected().
615 */
616RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_get_unprotected(
617  rtems_chain_control *the_chain
618)
619{
620  return _Chain_Get_unprotected( the_chain );
621}
622
623/**
624 * @brief See _Chain_Get_first_unprotected().
625 */
626RTEMS_INLINE_ROUTINE rtems_chain_node *rtems_chain_get_first_unprotected(
627  rtems_chain_control *the_chain
628)
629{
630  return _Chain_Get_first_unprotected( the_chain );
631}
632
633/**
634 * @brief Insert a node on a chain
635 *
636 * This routine inserts @a the_node on a chain immediately following
637 * @a after_node. 
638 *
639 * NOTE: It disables interrupts to ensure the atomicity
640 * of the extract operation.
641 */
642void rtems_chain_insert(
643  rtems_chain_node *after_node,
644  rtems_chain_node *the_node
645);
646
647/**
648 * @brief See _Chain_Insert_unprotected().
649 */
650RTEMS_INLINE_ROUTINE void rtems_chain_insert_unprotected(
651  rtems_chain_node *after_node,
652  rtems_chain_node *the_node
653)
654{
655  _Chain_Insert_unprotected( after_node, the_node );
656}
657
658/**
659 * @brief Append a node on the end of a chain.
660 *
661 * This routine appends @a the_node onto the end of @a the_chain.
662 *
663 * NOTE: It disables interrupts to ensure the atomicity of the
664 * append operation.
665 */
666void rtems_chain_append(
667  rtems_chain_control *the_chain,
668  rtems_chain_node    *the_node
669);
670
671/**
672 * @brief Append a node on the end of a chain (unprotected).
673 *
674 * This routine appends @a the_node onto the end of @a the_chain.
675 *
676 * NOTE: It does NOT disable interrupts to ensure the atomicity of the
677 * append operation.
678 */
679RTEMS_INLINE_ROUTINE void rtems_chain_append_unprotected(
680  rtems_chain_control *the_chain,
681  rtems_chain_node    *the_node
682)
683{
684  _Chain_Append_unprotected( the_chain, the_node );
685}
686
687/**
688 * @brief Prepend a node.
689 *
690 * This routine prepends the_node onto the front of the_chain.
691 *
692 * @param[in] the_chain is the chain to be operated upon.
693 * @param[in] the_node is the node to be prepended.
694 *
695 * NOTE: It disables interrupts to ensure the atomicity of the
696 *       prepend operation.
697 */
698void rtems_chain_prepend(
699  rtems_chain_control *the_chain,
700  rtems_chain_node    *the_node
701);
702
703/**
704 * @brief Prepend a node (unprotected).
705 *
706 * This routine prepends the_node onto the front of the_chain.
707 *
708 * @param[in] the_chain is the chain to be operated upon.
709 * @param[in] the_node is the node to be prepended.
710 *
711 * NOTE: It does NOT disable interrupts to ensure the atomicity of the
712 *       prepend operation.
713 */
714RTEMS_INLINE_ROUTINE void rtems_chain_prepend_unprotected(
715  rtems_chain_control *the_chain,
716  rtems_chain_node    *the_node
717)
718{
719  _Chain_Prepend_unprotected( the_chain, the_node );
720}
721
722/**
723 * @brief Checks if the @a chain is empty and appends the @a node.
724 *
725 * Interrupts are disabled to ensure the atomicity of the operation.
726 *
727 * @retval true The chain was empty before the append.
728 * @retval false The chain contained at least one node before the append.
729 */
730bool rtems_chain_append_with_empty_check(
731  rtems_chain_control *chain,
732  rtems_chain_node *node
733);
734
735/**
736 * @brief Checks if the @a chain is empty and prepends the @a node.
737 *
738 * Interrupts are disabled to ensure the atomicity of the operation.
739 *
740 * @retval true The chain was empty before the prepend.
741 * @retval false The chain contained at least one node before the prepend.
742 */
743bool rtems_chain_prepend_with_empty_check(
744  rtems_chain_control *chain,
745  rtems_chain_node *node
746);
747
748/**
749 * @brief Tries to get the first @a node and check if the @a chain is empty
750 * afterwards.
751 *
752 * This function removes the first node from the @a chain and returns a pointer
753 * to that node in @a node.  If the @a chain is empty, then @c NULL is returned.
754 *
755 * Interrupts are disabled to ensure the atomicity of the operation.
756 *
757 * @retval true The chain is empty after the node removal.
758 * @retval false The chain contained at least one node after the node removal.
759 */
760bool rtems_chain_get_with_empty_check(
761  rtems_chain_control *chain,
762  rtems_chain_node **node
763);
764
765/**
766 * @brief Returns the node count of the chain.
767 *
768 * @param[in] chain The chain.
769 *
770 * @note It does NOT disable interrupts to ensure the atomicity of the
771 * operation.
772 *
773 * @return The node count of the chain.
774 */
775RTEMS_INLINE_ROUTINE size_t rtems_chain_node_count_unprotected(
776  const rtems_chain_control *chain
777)
778{
779  return _Chain_Node_count_unprotected( chain );
780}
781
782/** @} */
783
784#ifdef __cplusplus
785}
786#endif
787
788#endif
789/* end of include file */
Note: See TracBrowser for help on using the repository browser.