source: rtems/cpukit/score/include/rtems/score/chainimpl.h @ 3709987

Last change on this file since 3709987 was 3709987, checked in by Sebastian Huber <sebastian.huber@…>, on Aug 10, 2016 at 6:21:54 AM

score: Add _Chain_Initialize_one()

  • Property mode set to 100644
File size: 27.9 KB
Line 
1/**
2 * @file
3 *
4 * @brief Chain Handler API
5 */
6
7/*
8 *  Copyright (c) 2010 embedded brains GmbH.
9 *
10 *  COPYRIGHT (c) 1989-2014.
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_SCORE_CHAINIMPL_H
19#define _RTEMS_SCORE_CHAINIMPL_H
20
21#include <rtems/score/chain.h>
22#include <rtems/score/address.h>
23#include <rtems/score/assert.h>
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/**
30 * @addtogroup ScoreChain
31 */
32/**@{**/
33
34/**
35 *  @brief Chain initializer for an empty chain with designator @a name.
36 */
37#define CHAIN_INITIALIZER_EMPTY(name) \
38  { { { &(name).Tail.Node, NULL }, &(name).Head.Node } }
39
40/**
41 *  @brief Chain initializer for a chain with one @a node.
42 *
43 *  @see CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN().
44 */
45#define CHAIN_INITIALIZER_ONE_NODE( node ) \
46  { { { (node), NULL }, (node) } }
47
48/**
49 *  @brief Chain node initializer for a @a chain containing exactly this node.
50 *
51 *  @see CHAIN_INITIALIZER_ONE_NODE().
52 */
53#define CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN( chain ) \
54  { &(chain)->Tail.Node, &(chain)->Head.Node }
55
56/**
57 *  @brief Chain definition for an empty chain with designator @a name.
58 */
59#define CHAIN_DEFINE_EMPTY(name) \
60  Chain_Control name = CHAIN_INITIALIZER_EMPTY(name)
61
62/**
63 *  @brief Initialize a chain header.
64 *
65 *  This routine initializes @a the_chain structure to manage the
66 *  contiguous array of @a number_nodes nodes which starts at
67 *  @a starting_address.  Each node is of @a node_size bytes.
68 *
69 *  @param[in] the_chain specifies the chain to initialize
70 *  @param[in] starting_address is the starting address of the array
71 *         of elements
72 *  @param[in] number_nodes is the numebr of nodes that will be in the chain
73 *  @param[in] node_size is the size of each node
74 */
75void _Chain_Initialize(
76  Chain_Control *the_chain,
77  void          *starting_address,
78  size_t         number_nodes,
79  size_t         node_size
80);
81
82/**
83 * @brief Returns the node count of the chain.
84 *
85 * @param[in] chain The chain.
86 *
87 * @note It does NOT disable interrupts to ensure the atomicity of the
88 * operation.
89 *
90 * @retval The node count of the chain.
91 */
92size_t _Chain_Node_count_unprotected( const Chain_Control *chain );
93
94/**
95 * @brief Set off chain.
96 *
97 * This function sets the next field of the @a node to NULL indicating the @a
98 * node is not part of a chain.
99 *
100 * @param[in] node the node set to off chain.
101 */
102RTEMS_INLINE_ROUTINE void _Chain_Set_off_chain(
103  Chain_Node *node
104)
105{
106  node->next = NULL;
107#if defined(RTEMS_DEBUG)
108  node->previous = NULL;
109#endif
110}
111
112/**
113 * @brief Initializes a chain node.
114 *
115 * In debug configurations, the node is set off chain.  In all other
116 * configurations, this function does nothing.
117 *
118 * @param[in] the_node The chain node to initialize.
119 */
120RTEMS_INLINE_ROUTINE void _Chain_Initialize_node( Chain_Node *the_node )
121{
122#if defined(RTEMS_DEBUG)
123  _Chain_Set_off_chain( the_node );
124#else
125  (void) the_node;
126#endif
127}
128
129/**
130 * @brief Is the node off chain.
131 *
132 * This function returns true if the @a node is not on a chain.  A @a node is
133 * off chain if the next field is set to NULL.
134 *
135 * @param[in] node is the node off chain.
136 *
137 * @retval true The @a node is off chain.
138 * @retval false The @a node is not off chain.
139 */
140RTEMS_INLINE_ROUTINE bool _Chain_Is_node_off_chain(
141  const Chain_Node *node
142)
143{
144  return node->next == NULL;
145}
146
147/**
148 * @brief Are two nodes equal.
149 *
150 * This function returns true if @a left and @a right are equal,
151 * and false otherwise.
152 *
153 * @param[in] left is the node on the left hand side of the comparison.
154 * @param[in] right is the node on the left hand side of the comparison.
155 *
156 * @retval true @a left and @a right are equal.
157 * @retval false @a left and @a right are not equal.
158 */
159RTEMS_INLINE_ROUTINE bool _Chain_Are_nodes_equal(
160  const Chain_Node *left,
161  const Chain_Node *right
162)
163{
164  return left == right;
165}
166
167/**
168 * @brief Is the chain node pointer NULL.
169 *
170 * This function returns true if the_node is NULL and false otherwise.
171 *
172 * @param[in] the_node is the node pointer to check.
173 *
174 * @retval true @a the_node is @c NULL.
175 * @retval false @a the_node is not @c NULL.
176 */
177RTEMS_INLINE_ROUTINE bool _Chain_Is_null_node(
178  const Chain_Node *the_node
179)
180{
181  return (the_node == NULL);
182}
183
184/**
185 * @brief Return pointer to chain head.
186 *
187 * This function returns a pointer to the head node on the chain.
188 *
189 * @param[in] the_chain is the chain to be operated upon.
190 *
191 * @return This method returns the permanent head node of the chain.
192 */
193RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Head(
194  Chain_Control *the_chain
195)
196{
197  return &the_chain->Head.Node;
198}
199
200/**
201 * @brief Return pointer to immutable chain head.
202 *
203 * This function returns a pointer to the head node on the chain.
204 *
205 * @param[in] the_chain is the chain to be operated upon.
206 *
207 * @return This method returns the permanent head node of the chain.
208 */
209RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_head(
210  const Chain_Control *the_chain
211)
212{
213  return &the_chain->Head.Node;
214}
215
216/**
217 * @brief Return pointer to chain tail.
218 *
219 * This function returns a pointer to the tail node on the chain.
220 *
221 * @param[in] the_chain is the chain to be operated upon.
222 *
223 * @return This method returns the permanent tail node of the chain.
224 */
225RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Tail(
226  Chain_Control *the_chain
227)
228{
229  return &the_chain->Tail.Node;
230}
231
232/**
233 * @brief Return pointer to immutable chain tail.
234 *
235 * This function returns a pointer to the tail node on the chain.
236 *
237 * @param[in] the_chain is the chain to be operated upon.
238 *
239 * @return This method returns the permanent tail node of the chain.
240 */
241RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_tail(
242  const Chain_Control *the_chain
243)
244{
245  return &the_chain->Tail.Node;
246}
247
248/**
249 * @brief Return pointer to chain's first node.
250 *
251 * This function returns a pointer to the first node on the chain after the
252 * head.
253 *
254 * @param[in] the_chain is the chain to be operated upon.
255 *
256 * @return This method returns the first node of the chain.
257 */
258RTEMS_INLINE_ROUTINE Chain_Node *_Chain_First(
259  const Chain_Control *the_chain
260)
261{
262  return _Chain_Immutable_head( the_chain )->next;
263}
264
265/**
266 * @brief Return pointer to immutable chain's first node.
267 *
268 * This function returns a pointer to the first node on the chain after the
269 * head.
270 *
271 * @param[in] the_chain is the chain to be operated upon.
272 *
273 * @return This method returns the first node of the chain.
274 */
275RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_first(
276  const Chain_Control *the_chain
277)
278{
279  return _Chain_Immutable_head( the_chain )->next;
280}
281
282/**
283 * @brief Return pointer to chain's last node.
284 *
285 * This function returns a pointer to the last node on the chain just before
286 * the tail.
287 *
288 * @param[in] the_chain is the chain to be operated upon.
289 *
290 * @return This method returns the last node of the chain.
291 */
292RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Last(
293  const Chain_Control *the_chain
294)
295{
296  return _Chain_Immutable_tail( the_chain )->previous;
297}
298
299/**
300 * @brief Return pointer to immutable chain's last node.
301 *
302 * This function returns a pointer to the last node on the chain just before
303 * the tail.
304 *
305 * @param[in] the_chain is the chain to be operated upon.
306 *
307 * @return This method returns the last node of the chain.
308 */
309RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_last(
310  const Chain_Control *the_chain
311)
312{
313  return _Chain_Immutable_tail( the_chain )->previous;
314}
315
316/**
317 * @brief Return pointer the next node from this node.
318 *
319 * This function returns a pointer to the next node after this node.
320 *
321 * @param[in] the_node is the node to be operated upon.
322 *
323 * @return This method returns the next node on the chain.
324 */
325RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Next(
326  const Chain_Node *the_node
327)
328{
329  return the_node->next;
330}
331
332/**
333 * @brief Return pointer the immutable next node from this node.
334 *
335 * This function returns a pointer to the next node after this node.
336 *
337 * @param[in] the_node is the node to be operated upon.
338 *
339 * @return This method returns the next node on the chain.
340 */
341RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_next(
342  const Chain_Node *the_node
343)
344{
345  return the_node->next;
346}
347
348/**
349 * @brief Return pointer the previous node from this node.
350 *
351 * This function returns a pointer to the previous node on this chain.
352 *
353 * @param[in] the_node is the node to be operated upon.
354 *
355 * @return This method returns the previous node on the chain.
356 */
357RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Previous(
358  const Chain_Node *the_node
359)
360{
361  return the_node->previous;
362}
363
364/**
365 * @brief Return pointer the immutable previous node from this node.
366 *
367 * This function returns a pointer to the previous node on this chain.
368 *
369 * @param[in] the_node is the node to be operated upon.
370 *
371 * @return This method returns the previous node on the chain.
372 */
373RTEMS_INLINE_ROUTINE const Chain_Node *_Chain_Immutable_previous(
374  const Chain_Node *the_node
375)
376{
377  return the_node->previous;
378}
379
380/**
381 * @brief Is the chain empty.
382 *
383 * This function returns true if there a no nodes on @a the_chain and
384 * false otherwise.
385 *
386 * @param[in] the_chain is the chain to be operated upon.
387 *
388 * @retval true There are no nodes on @a the_chain.
389 * @retval false There are nodes on @a the_chain.
390 */
391RTEMS_INLINE_ROUTINE bool _Chain_Is_empty(
392  const Chain_Control *the_chain
393)
394{
395  return _Chain_Immutable_first( the_chain )
396    == _Chain_Immutable_tail( the_chain );
397}
398
399/**
400 * @brief Is this the first node on the chain.
401 *
402 * This function returns true if the_node is the first node on a chain and
403 * false otherwise.
404 *
405 * @param[in] the_node is the node the caller wants to know if it is
406 *            the first node on a chain.
407 *
408 * @retval true @a the_node is the first node on a chain.
409 * @retval false @a the_node is not the first node on a chain.
410 */
411RTEMS_INLINE_ROUTINE bool _Chain_Is_first(
412  const Chain_Node *the_node
413)
414{
415  return (the_node->previous->previous == NULL);
416}
417
418/**
419 * @brief Is this the last node on the chain.
420 *
421 * This function returns true if @a the_node is the last node on a chain and
422 * false otherwise.
423 *
424 * @param[in] the_node is the node to check as the last node.
425 *
426 * @retval true @a the_node is the last node on a chain.
427 * @retval false @a the_node is not the last node on a chain.
428 */
429RTEMS_INLINE_ROUTINE bool _Chain_Is_last(
430  const Chain_Node *the_node
431)
432{
433  return (the_node->next->next == NULL);
434}
435
436/**
437 * @brief Does this chain have only one node.
438 *
439 * This function returns true if there is only one node on @a the_chain and
440 * false otherwise.
441 *
442 * @param[in] the_chain is the chain to be operated upon.
443 *
444 * @return This function returns true if there is only one node on
445 *         @a the_chain and false otherwise.
446 *
447 * @retval true There is only one node on @a the_chain.
448 * @retval false There is more than one node on @a the_chain.
449 */
450RTEMS_INLINE_ROUTINE bool _Chain_Has_only_one_node(
451  const Chain_Control *the_chain
452)
453{
454  return _Chain_Immutable_first( the_chain )
455    == _Chain_Immutable_last( the_chain );
456}
457
458/**
459 * @brief Is this node the chain head.
460 *
461 * This function returns true if @a the_node is the head of @a the_chain and
462 * false otherwise.
463 *
464 * @param[in] the_chain is the chain to be operated upon.
465 * @param[in] the_node is the node to check for being the Chain Head.
466 *
467 * @retval true @a the_node is the head of @a the_chain.
468 * @retval false @a the_node is not the head of @a the_chain.
469 */
470RTEMS_INLINE_ROUTINE bool _Chain_Is_head(
471  const Chain_Control *the_chain,
472  const Chain_Node    *the_node
473)
474{
475  return (the_node == _Chain_Immutable_head( the_chain ));
476}
477
478/**
479 * @brief Is this node the chail tail.
480 *
481 * This function returns true if @a the_node is the tail of @a the_chain and
482 * false otherwise.
483 *
484 * @param[in] the_chain is the chain to be operated upon.
485 * @param[in] the_node is the node to check for being the Chain Tail.
486 *
487 * @retval true @a the_node is the tail of @a the_chain.
488 * @retval false @a the_node is not the tail of @a the_chain.
489 */
490RTEMS_INLINE_ROUTINE bool _Chain_Is_tail(
491  const Chain_Control *the_chain,
492  const Chain_Node    *the_node
493)
494{
495  return (the_node == _Chain_Immutable_tail( the_chain ));
496}
497
498/**
499 * @brief Initialize this chain as empty.
500 *
501 * This routine initializes the specified chain to contain zero nodes.
502 *
503 * @param[in] the_chain is the chain to be initialized.
504 */
505RTEMS_INLINE_ROUTINE void _Chain_Initialize_empty(
506  Chain_Control *the_chain
507)
508{
509  Chain_Node *head;
510  Chain_Node *tail;
511
512  _Assert( the_chain != NULL );
513
514  head = _Chain_Head( the_chain );
515  tail = _Chain_Tail( the_chain );
516
517  head->next = tail;
518  head->previous = NULL;
519  tail->previous = head;
520}
521
522/**
523 * @brief Initializes this chain to contain exactly the specified node.
524 *
525 * @param[in] the_chain The chain control.
526 * @param[in] the_node The one and only node.
527 */
528RTEMS_INLINE_ROUTINE void _Chain_Initialize_one(
529  Chain_Control *the_chain,
530  Chain_Node    *the_node
531)
532{
533  Chain_Node *head;
534  Chain_Node *tail;
535
536  _Assert( _Chain_Is_node_off_chain( the_node ) );
537
538  head = _Chain_Head( the_chain );
539  tail = _Chain_Tail( the_chain );
540
541  the_node->next = tail;
542  the_node->previous = head;
543
544  head->next = the_node;
545  head->previous = NULL;
546  tail->previous = the_node;
547}
548
549/**
550 * @brief Extract this node (unprotected).
551 *
552 * This routine extracts the_node from the chain on which it resides.
553 * It does NOT disable interrupts to ensure the atomicity of the
554 * extract operation.
555 *
556 * @param[in] the_node is the node to be extracted.
557 */
558RTEMS_INLINE_ROUTINE void _Chain_Extract_unprotected(
559  Chain_Node *the_node
560)
561{
562  Chain_Node *next;
563  Chain_Node *previous;
564
565  next           = the_node->next;
566  previous       = the_node->previous;
567  next->previous = previous;
568  previous->next = next;
569
570#if defined(RTEMS_DEBUG)
571  _Chain_Set_off_chain( the_node );
572#endif
573}
574
575/**
576 * @brief Get the first node (unprotected).
577 *
578 * This function removes the first node from the_chain and returns
579 * a pointer to that node.  It does NOT disable interrupts to ensure
580 * the atomicity of the get operation.
581 *
582 * @param[in] the_chain is the chain to attempt to get the first node from.
583 *
584 * @return This method returns the first node on the chain even if it is
585 *         the Chain Tail.
586 *
587 * @note This routine assumes that there is at least one node on the chain
588 *       and always returns a node even if it is the Chain Tail.
589 */
590RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_first_unprotected(
591  Chain_Control *the_chain
592)
593{
594  Chain_Node *head;
595  Chain_Node *old_first;
596  Chain_Node *new_first;
597
598  _Assert( !_Chain_Is_empty( the_chain ) );
599
600  head = _Chain_Head( the_chain );
601  old_first = head->next;
602  new_first = old_first->next;
603
604  head->next = new_first;
605  new_first->previous = head;
606
607#if defined(RTEMS_DEBUG)
608  _Chain_Set_off_chain( old_first );
609#endif
610
611  return old_first;
612}
613
614/**
615 * @brief Get the first node (unprotected).
616 *
617 * This function removes the first node from the_chain and returns
618 * a pointer to that node.  If the_chain is empty, then NULL is returned.
619 *
620 * @param[in] the_chain is the chain to attempt to get the first node from.
621 *
622 * @return This method returns the first node on the chain or NULL if the
623 *         chain is empty.
624 *
625 * @note It does NOT disable interrupts to ensure the atomicity of the
626 *       get operation.
627 */
628RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_unprotected(
629  Chain_Control *the_chain
630)
631{
632  if ( !_Chain_Is_empty(the_chain))
633    return _Chain_Get_first_unprotected(the_chain);
634  else
635    return NULL;
636}
637
638/**
639 * @brief Insert a node (unprotected).
640 *
641 * This routine inserts the_node on a chain immediately following
642 * after_node.
643 *
644 * @param[in] after_node is the node which will precede @a the_node on the
645 *            chain.
646 * @param[in] the_node is the node to be inserted.
647 *
648 * @note It does NOT disable interrupts to ensure the atomicity
649 *       of the extract operation.
650 */
651RTEMS_INLINE_ROUTINE void _Chain_Insert_unprotected(
652  Chain_Node *after_node,
653  Chain_Node *the_node
654)
655{
656  Chain_Node *before_node;
657
658  _Assert( _Chain_Is_node_off_chain( the_node ) );
659
660  the_node->previous    = after_node;
661  before_node           = after_node->next;
662  after_node->next      = the_node;
663  the_node->next        = before_node;
664  before_node->previous = the_node;
665}
666
667/**
668 * @brief Append a node (unprotected).
669 *
670 * This routine appends the_node onto the end of the_chain.
671 *
672 * @param[in] the_chain is the chain to be operated upon.
673 * @param[in] the_node is the node to be appended.
674 *
675 * @note It does NOT disable interrupts to ensure the atomicity of the
676 *       append operation.
677 */
678RTEMS_INLINE_ROUTINE void _Chain_Append_unprotected(
679  Chain_Control *the_chain,
680  Chain_Node    *the_node
681)
682{
683  Chain_Node *tail;
684  Chain_Node *old_last;
685
686  _Assert( _Chain_Is_node_off_chain( the_node ) );
687
688  tail = _Chain_Tail( the_chain );
689  old_last = tail->previous;
690
691  the_node->next = tail;
692  tail->previous = the_node;
693  old_last->next = the_node;
694  the_node->previous = old_last;
695}
696
697/**
698 * @brief Append a node on the end of a chain if the node is in the off chain
699 * state (unprotected).
700 *
701 * @note It does NOT disable interrupts to ensure the atomicity of the
702 *       append operation.
703 *
704 * @see _Chain_Append_unprotected() and _Chain_Is_node_off_chain().
705 */
706RTEMS_INLINE_ROUTINE void _Chain_Append_if_is_off_chain_unprotected(
707  Chain_Control *the_chain,
708  Chain_Node    *the_node
709)
710{
711  if ( _Chain_Is_node_off_chain( the_node ) ) {
712    _Chain_Append_unprotected( the_chain, the_node );
713  }
714}
715
716/**
717 * @brief Prepend a node (unprotected).
718 *
719 * This routine prepends the_node onto the front of the_chain.
720 *
721 * @param[in] the_chain is the chain to be operated upon.
722 * @param[in] the_node is the node to be prepended.
723 *
724 * @note It does NOT disable interrupts to ensure the atomicity of the
725 *       prepend operation.
726 */
727RTEMS_INLINE_ROUTINE void _Chain_Prepend_unprotected(
728  Chain_Control *the_chain,
729  Chain_Node    *the_node
730)
731{
732  _Chain_Insert_unprotected(_Chain_Head(the_chain), the_node);
733}
734
735/**
736 * @brief Append a node and check if the chain was empty before (unprotected).
737 *
738 * This routine appends the_node onto the end of the_chain.
739 *
740 * @param[in] the_chain is the chain to be operated upon.
741 * @param[in] the_node is the node to be appended.
742 *
743 * @note It does NOT disable interrupts to ensure the atomicity of the
744 *       append operation.
745 *
746 * @retval true The chain was empty before.
747 * @retval false The chain contained at least one node before.
748 */
749RTEMS_INLINE_ROUTINE bool _Chain_Append_with_empty_check_unprotected(
750  Chain_Control *the_chain,
751  Chain_Node    *the_node
752)
753{
754  bool was_empty = _Chain_Is_empty( the_chain );
755
756  _Chain_Append_unprotected( the_chain, the_node );
757
758  return was_empty;
759}
760
761/**
762 * @brief Prepend a node and check if the chain was empty before (unprotected).
763 *
764 * This routine prepends the_node onto the front of the_chain.
765 *
766 * @param[in] the_chain is the chain to be operated upon.
767 * @param[in] the_node is the node to be prepended.
768 *
769 * @note It does NOT disable interrupts to ensure the atomicity of the
770 *       prepend operation.
771 *
772 * @retval true The chain was empty before.
773 * @retval false The chain contained at least one node before.
774 */
775RTEMS_INLINE_ROUTINE bool _Chain_Prepend_with_empty_check_unprotected(
776  Chain_Control *the_chain,
777  Chain_Node    *the_node
778)
779{
780  bool was_empty = _Chain_Is_empty( the_chain );
781
782  _Chain_Prepend_unprotected( the_chain, the_node );
783
784  return was_empty;
785}
786
787/**
788 * @brief Get the first node and check if the chain is empty afterwards
789 * (unprotected).
790 *
791 * This function removes the first node from the_chain and returns
792 * a pointer to that node in @a the_node.  If the_chain is empty, then NULL is
793 * returned.
794 *
795 * @param[in] the_chain is the chain to attempt to get the first node from.
796 * @param[out] the_node is the first node on the chain or NULL if the chain is
797 * empty.
798 *
799 * @note It does NOT disable interrupts to ensure the atomicity of the
800 *       get operation.
801 *
802 * @retval true The chain is empty now.
803 * @retval false The chain contains at least one node now.
804 */
805RTEMS_INLINE_ROUTINE bool _Chain_Get_with_empty_check_unprotected(
806  Chain_Control *the_chain,
807  Chain_Node **the_node
808)
809{
810  bool is_empty_now = true;
811  Chain_Node *head = _Chain_Head( the_chain );
812  Chain_Node *tail = _Chain_Tail( the_chain );
813  Chain_Node *old_first = head->next;
814
815  if ( old_first != tail ) {
816    Chain_Node *new_first = old_first->next;
817
818    head->next = new_first;
819    new_first->previous = head;
820
821    *the_node = old_first;
822
823    is_empty_now = new_first == tail;
824  } else
825    *the_node = NULL;
826
827  return is_empty_now;
828}
829
830/**
831 * @brief Chain node order.
832 *
833 * @param[in] left The left node.
834 * @param[in] right The right node.
835 *
836 * @retval true According to the order the left node precedes the right node.
837 * @retval false Otherwise.
838 */
839typedef bool ( *Chain_Node_order )(
840  const Chain_Node *left,
841  const Chain_Node *right
842);
843
844/**
845 * @brief Inserts a node into the chain according to the order relation.
846 *
847 * After the operation the chain contains the node to insert and the order
848 * relation holds for all nodes from the head up to the inserted node.  Nodes
849 * after the inserted node are not moved.
850 *
851 * @param[in,out] chain The chain.
852 * @param[in,out] to_insert The node to insert.
853 * @param[in] order The order relation.
854 */
855RTEMS_INLINE_ROUTINE void _Chain_Insert_ordered_unprotected(
856  Chain_Control *chain,
857  Chain_Node *to_insert,
858  Chain_Node_order order
859)
860{
861  const Chain_Node *tail = _Chain_Immutable_tail( chain );
862  Chain_Node *next = _Chain_First( chain );
863
864  while ( next != tail && !( *order )( to_insert, next ) ) {
865    next = _Chain_Next( next );
866  }
867
868  _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
869}
870
871/**
872 * @brief The chain iterator direction.
873 */
874typedef enum {
875  /**
876   * @brief Iteration from head to tail.
877   */
878  CHAIN_ITERATOR_FORWARD,
879
880  /**
881   * @brief Iteration from tail to head.
882   */
883  CHAIN_ITERATOR_BACKWARD
884} Chain_Iterator_direction;
885
886/**
887 * @brief A chain iterator which is updated during node extraction if it is
888 * properly registered.
889 *
890 * @see _Chain_Iterator_initialize().
891 */
892typedef struct {
893  /**
894   * @brief Node for registration.
895   *
896   * Used during _Chain_Iterator_initialize() and _Chain_Iterator_destroy().
897   */
898  Chain_Node Registry_node;
899
900  /**
901   * @brief The direction of this iterator.
902   *
903   * Immutable after initialization via _Chain_Iterator_initialize().
904   */
905  Chain_Iterator_direction  direction;
906
907  /**
908   * @brief The current position of this iterator.
909   *
910   * The position is initialized via _Chain_Iterator_initialize().  It must be
911   * explicitly set after one valid iteration step, e.g. in case a next node in
912   * the iterator direction existed.  It is updated through the registration in
913   * case a node is extracted via _Chain_Iterator_registry_update().
914   */
915  Chain_Node *position;
916} Chain_Iterator;
917
918/**
919 * @brief A registry for chain iterators.
920 *
921 * Should be attached to a chain control to enable safe iteration through a
922 * chain in case of concurrent node extractions.
923 */
924typedef struct {
925  Chain_Control Iterators;
926} Chain_Iterator_registry;
927
928/**
929 * @brief Chain iterator registry initializer for static initialization.
930 *
931 * @param name The designator of the chain iterator registry.
932 */
933#define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
934  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
935
936/**
937 * @brief Initializes a chain iterator registry.
938 */
939RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(
940  Chain_Iterator_registry *the_registry
941)
942{
943  _Chain_Initialize_empty( &the_registry->Iterators );
944}
945
946/**
947 * @brief Updates all iterators present in the chain iterator registry in case
948 * of a node extraction.
949 *
950 * Must be called before _Chain_Extract_unprotected().
951 *
952 * @warning This function will look at all registered chain iterators to
953 *   determine if an update is necessary.
954 */
955RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_update(
956  Chain_Iterator_registry *the_registry,
957  Chain_Node              *the_node_to_extract
958)
959{
960  Chain_Node *iter_node;
961  Chain_Node *iter_tail;
962
963  iter_node = _Chain_Head( &the_registry->Iterators );
964  iter_tail = _Chain_Tail( &the_registry->Iterators );
965
966  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
967    Chain_Iterator *iter;
968
969    iter = (Chain_Iterator *) iter_node;
970
971    if ( iter->position == the_node_to_extract ) {
972      if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
973        iter->position = _Chain_Previous( the_node_to_extract );
974      } else {
975        iter->position = _Chain_Next( the_node_to_extract );
976      }
977    }
978  }
979}
980
981/**
982 * @brief Initializes the chain iterator.
983 *
984 * In the following example nodes inserted during the iteration are visited in
985 * case they are inserted after the current position in iteration order.
986 *
987 * @code
988 * #include <rtems/score/chainimpl.h>
989 * #include <rtems/score/isrlock.h>
990 *
991 * typedef struct {
992 *   Chain_Control           Chain;
993 *   Chain_Iterator_registry Iterators;
994 *   ISR_LOCK_MEMBER(        Lock )
995 * } Some_Control;
996 *
997 * void iterate(
998 *   Some_Control   *the_some,
999 *   void         ( *visitor )( Chain_Node * )
1000 * )
1001 * {
1002 *   ISR_lock_Context  lock_context;
1003 *   Chain_Iterator    iter;
1004 *   Chain_Node       *node;
1005 *   const Chain_Node *end;
1006 *
1007 *   end = _Chain_Immutable_tail( &the_some->Chain );
1008 *
1009 *   _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
1010 *
1011 *   _Chain_Iterator_initialize(
1012 *     &the_some->Chain,
1013 *     &the_some->Iterators,
1014 *     &iter,
1015 *     CHAIN_ITERATOR_FORWARD
1016 *   );
1017 *
1018 *   while ( ( node = _Chain_Iterator_next( &iter ) ) != end ) {
1019 *     _Chain_Iterator_set_position( &iter, node );
1020 *     _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
1021 *     ( *visitor )( node );
1022 *     _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
1023 *   }
1024 *
1025 *   _Chain_Iterator_destroy( &iter );
1026 *   _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
1027 * }
1028 * @endcode
1029 *
1030 * @param the_chain The chain to iterate.
1031 * @param the_registry The registry for the chain iterator.
1032 * @param the_iterator The chain iterator to initialize.
1033 * @param direction The iteration direction.
1034 *
1035 * @see _Chain_Iterator_next(), _Chain_Iterator_set_position() and
1036 * Chain_Iterator_destroy().
1037 *
1038 * @warning Think twice before you use a chain iterator.  Its current
1039 *   implementation is unfit for use in performance relevant components, due to
1040 *   the linear time complexity in _Chain_Iterator_registry_update().
1041 */
1042RTEMS_INLINE_ROUTINE void _Chain_Iterator_initialize(
1043  Chain_Control            *the_chain,
1044  Chain_Iterator_registry  *the_registry,
1045  Chain_Iterator           *the_iterator,
1046  Chain_Iterator_direction  direction
1047)
1048{
1049  _Chain_Initialize_node( &the_iterator->Registry_node );
1050  _Chain_Append_unprotected(
1051    &the_registry->Iterators,
1052    &the_iterator->Registry_node
1053  );
1054
1055  the_iterator->direction = direction;
1056
1057  if ( direction == CHAIN_ITERATOR_FORWARD ) {
1058    the_iterator->position = _Chain_Head( the_chain );
1059  } else {
1060    the_iterator->position = _Chain_Tail( the_chain );
1061  }
1062}
1063
1064/**
1065 * @brief Returns the next node in the iterator direction.
1066 *
1067 * In case a next node exists, then the iterator should be updated via
1068 * _Chain_Iterator_set_position() to continue with the next iteration step.
1069 *
1070 * @param the_iterator The chain iterator.
1071 */
1072RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
1073  const Chain_Iterator *the_iterator
1074)
1075{
1076  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
1077    return _Chain_Next( the_iterator->position );
1078  } else {
1079    return _Chain_Previous( the_iterator->position );
1080  }
1081}
1082
1083/**
1084 * @brief Sets the iterator position.
1085 *
1086 * @param the_iterator The chain iterator.
1087 * @param the_node The new iterator position.
1088 */
1089RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(
1090  Chain_Iterator *the_iterator,
1091  Chain_Node     *the_node
1092)
1093{
1094  the_iterator->position = the_node;
1095}
1096
1097/**
1098 * @brief Destroys the iterator.
1099 *
1100 * Removes the iterator from its registry.
1101 *
1102 * @param the_iterator The chain iterator.
1103 */
1104RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(
1105  Chain_Iterator *the_iterator
1106)
1107{
1108  _Chain_Extract_unprotected( &the_iterator->Registry_node );
1109}
1110
1111/** @} */
1112
1113#ifdef __cplusplus
1114}
1115#endif
1116
1117#endif
1118/* end of include file */
Note: See TracBrowser for help on using the repository browser.