source: rtems/cpukit/score/include/rtems/score/chainimpl.h @ 796f12a

Last change on this file since 796f12a was 796f12a, checked in by Sebastian Huber <sebastian.huber@…>, on Aug 19, 2016 at 11:37:01 AM

score: Add missing const qualifiers

  • Property mode set to 100644
File size: 27.3 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 Extract this node (unprotected).
524 *
525 * This routine extracts the_node from the chain on which it resides.
526 * It does NOT disable interrupts to ensure the atomicity of the
527 * extract operation.
528 *
529 * @param[in] the_node is the node to be extracted.
530 */
531RTEMS_INLINE_ROUTINE void _Chain_Extract_unprotected(
532  Chain_Node *the_node
533)
534{
535  Chain_Node *next;
536  Chain_Node *previous;
537
538  next           = the_node->next;
539  previous       = the_node->previous;
540  next->previous = previous;
541  previous->next = next;
542
543#if defined(RTEMS_DEBUG)
544  _Chain_Set_off_chain( the_node );
545#endif
546}
547
548/**
549 * @brief Get the first node (unprotected).
550 *
551 * This function removes the first node from the_chain and returns
552 * a pointer to that node.  It does NOT disable interrupts to ensure
553 * the atomicity of the get operation.
554 *
555 * @param[in] the_chain is the chain to attempt to get the first node from.
556 *
557 * @return This method returns the first node on the chain even if it is
558 *         the Chain Tail.
559 *
560 * @note This routine assumes that there is at least one node on the chain
561 *       and always returns a node even if it is the Chain Tail.
562 */
563RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_first_unprotected(
564  Chain_Control *the_chain
565)
566{
567  Chain_Node *head;
568  Chain_Node *old_first;
569  Chain_Node *new_first;
570
571  _Assert( !_Chain_Is_empty( the_chain ) );
572
573  head = _Chain_Head( the_chain );
574  old_first = head->next;
575  new_first = old_first->next;
576
577  head->next = new_first;
578  new_first->previous = head;
579
580#if defined(RTEMS_DEBUG)
581  _Chain_Set_off_chain( old_first );
582#endif
583
584  return old_first;
585}
586
587/**
588 * @brief Get the first node (unprotected).
589 *
590 * This function removes the first node from the_chain and returns
591 * a pointer to that node.  If the_chain is empty, then NULL is returned.
592 *
593 * @param[in] the_chain is the chain to attempt to get the first node from.
594 *
595 * @return This method returns the first node on the chain or NULL if the
596 *         chain is empty.
597 *
598 * @note It does NOT disable interrupts to ensure the atomicity of the
599 *       get operation.
600 */
601RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Get_unprotected(
602  Chain_Control *the_chain
603)
604{
605  if ( !_Chain_Is_empty(the_chain))
606    return _Chain_Get_first_unprotected(the_chain);
607  else
608    return NULL;
609}
610
611/**
612 * @brief Insert a node (unprotected).
613 *
614 * This routine inserts the_node on a chain immediately following
615 * after_node.
616 *
617 * @param[in] after_node is the node which will precede @a the_node on the
618 *            chain.
619 * @param[in] the_node is the node to be inserted.
620 *
621 * @note It does NOT disable interrupts to ensure the atomicity
622 *       of the extract operation.
623 */
624RTEMS_INLINE_ROUTINE void _Chain_Insert_unprotected(
625  Chain_Node *after_node,
626  Chain_Node *the_node
627)
628{
629  Chain_Node *before_node;
630
631  _Assert( _Chain_Is_node_off_chain( the_node ) );
632
633  the_node->previous    = after_node;
634  before_node           = after_node->next;
635  after_node->next      = the_node;
636  the_node->next        = before_node;
637  before_node->previous = the_node;
638}
639
640/**
641 * @brief Append a node (unprotected).
642 *
643 * This routine appends the_node onto the end of the_chain.
644 *
645 * @param[in] the_chain is the chain to be operated upon.
646 * @param[in] the_node is the node to be appended.
647 *
648 * @note It does NOT disable interrupts to ensure the atomicity of the
649 *       append operation.
650 */
651RTEMS_INLINE_ROUTINE void _Chain_Append_unprotected(
652  Chain_Control *the_chain,
653  Chain_Node    *the_node
654)
655{
656  Chain_Node *tail;
657  Chain_Node *old_last;
658
659  _Assert( _Chain_Is_node_off_chain( the_node ) );
660
661  tail = _Chain_Tail( the_chain );
662  old_last = tail->previous;
663
664  the_node->next = tail;
665  tail->previous = the_node;
666  old_last->next = the_node;
667  the_node->previous = old_last;
668}
669
670/**
671 * @brief Append a node on the end of a chain if the node is in the off chain
672 * state (unprotected).
673 *
674 * @note It does NOT disable interrupts to ensure the atomicity of the
675 *       append operation.
676 *
677 * @see _Chain_Append_unprotected() and _Chain_Is_node_off_chain().
678 */
679RTEMS_INLINE_ROUTINE void _Chain_Append_if_is_off_chain_unprotected(
680  Chain_Control *the_chain,
681  Chain_Node    *the_node
682)
683{
684  if ( _Chain_Is_node_off_chain( the_node ) ) {
685    _Chain_Append_unprotected( the_chain, the_node );
686  }
687}
688
689/**
690 * @brief Prepend a node (unprotected).
691 *
692 * This routine prepends the_node onto the front of the_chain.
693 *
694 * @param[in] the_chain is the chain to be operated upon.
695 * @param[in] the_node is the node to be prepended.
696 *
697 * @note It does NOT disable interrupts to ensure the atomicity of the
698 *       prepend operation.
699 */
700RTEMS_INLINE_ROUTINE void _Chain_Prepend_unprotected(
701  Chain_Control *the_chain,
702  Chain_Node    *the_node
703)
704{
705  _Chain_Insert_unprotected(_Chain_Head(the_chain), the_node);
706}
707
708/**
709 * @brief Append a node and check if the chain was empty before (unprotected).
710 *
711 * This routine appends the_node onto the end of the_chain.
712 *
713 * @param[in] the_chain is the chain to be operated upon.
714 * @param[in] the_node is the node to be appended.
715 *
716 * @note It does NOT disable interrupts to ensure the atomicity of the
717 *       append operation.
718 *
719 * @retval true The chain was empty before.
720 * @retval false The chain contained at least one node before.
721 */
722RTEMS_INLINE_ROUTINE bool _Chain_Append_with_empty_check_unprotected(
723  Chain_Control *the_chain,
724  Chain_Node    *the_node
725)
726{
727  bool was_empty = _Chain_Is_empty( the_chain );
728
729  _Chain_Append_unprotected( the_chain, the_node );
730
731  return was_empty;
732}
733
734/**
735 * @brief Prepend a node and check if the chain was empty before (unprotected).
736 *
737 * This routine prepends the_node onto the front of the_chain.
738 *
739 * @param[in] the_chain is the chain to be operated upon.
740 * @param[in] the_node is the node to be prepended.
741 *
742 * @note It does NOT disable interrupts to ensure the atomicity of the
743 *       prepend operation.
744 *
745 * @retval true The chain was empty before.
746 * @retval false The chain contained at least one node before.
747 */
748RTEMS_INLINE_ROUTINE bool _Chain_Prepend_with_empty_check_unprotected(
749  Chain_Control *the_chain,
750  Chain_Node    *the_node
751)
752{
753  bool was_empty = _Chain_Is_empty( the_chain );
754
755  _Chain_Prepend_unprotected( the_chain, the_node );
756
757  return was_empty;
758}
759
760/**
761 * @brief Get the first node and check if the chain is empty afterwards
762 * (unprotected).
763 *
764 * This function removes the first node from the_chain and returns
765 * a pointer to that node in @a the_node.  If the_chain is empty, then NULL is
766 * returned.
767 *
768 * @param[in] the_chain is the chain to attempt to get the first node from.
769 * @param[out] the_node is the first node on the chain or NULL if the chain is
770 * empty.
771 *
772 * @note It does NOT disable interrupts to ensure the atomicity of the
773 *       get operation.
774 *
775 * @retval true The chain is empty now.
776 * @retval false The chain contains at least one node now.
777 */
778RTEMS_INLINE_ROUTINE bool _Chain_Get_with_empty_check_unprotected(
779  Chain_Control *the_chain,
780  Chain_Node **the_node
781)
782{
783  bool is_empty_now = true;
784  Chain_Node *head = _Chain_Head( the_chain );
785  Chain_Node *tail = _Chain_Tail( the_chain );
786  Chain_Node *old_first = head->next;
787
788  if ( old_first != tail ) {
789    Chain_Node *new_first = old_first->next;
790
791    head->next = new_first;
792    new_first->previous = head;
793
794    *the_node = old_first;
795
796    is_empty_now = new_first == tail;
797  } else
798    *the_node = NULL;
799
800  return is_empty_now;
801}
802
803/**
804 * @brief Chain node order.
805 *
806 * @param[in] left The left node.
807 * @param[in] right The right node.
808 *
809 * @retval true According to the order the left node precedes the right node.
810 * @retval false Otherwise.
811 */
812typedef bool ( *Chain_Node_order )(
813  const Chain_Node *left,
814  const Chain_Node *right
815);
816
817/**
818 * @brief Inserts a node into the chain according to the order relation.
819 *
820 * After the operation the chain contains the node to insert and the order
821 * relation holds for all nodes from the head up to the inserted node.  Nodes
822 * after the inserted node are not moved.
823 *
824 * @param[in,out] chain The chain.
825 * @param[in,out] to_insert The node to insert.
826 * @param[in] order The order relation.
827 */
828RTEMS_INLINE_ROUTINE void _Chain_Insert_ordered_unprotected(
829  Chain_Control *chain,
830  Chain_Node *to_insert,
831  Chain_Node_order order
832)
833{
834  const Chain_Node *tail = _Chain_Immutable_tail( chain );
835  Chain_Node *next = _Chain_First( chain );
836
837  while ( next != tail && !( *order )( to_insert, next ) ) {
838    next = _Chain_Next( next );
839  }
840
841  _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
842}
843
844/**
845 * @brief The chain iterator direction.
846 */
847typedef enum {
848  /**
849   * @brief Iteration from head to tail.
850   */
851  CHAIN_ITERATOR_FORWARD,
852
853  /**
854   * @brief Iteration from tail to head.
855   */
856  CHAIN_ITERATOR_BACKWARD
857} Chain_Iterator_direction;
858
859/**
860 * @brief A chain iterator which is updated during node extraction if it is
861 * properly registered.
862 *
863 * @see _Chain_Iterator_initialize().
864 */
865typedef struct {
866  /**
867   * @brief Node for registration.
868   *
869   * Used during _Chain_Iterator_initialize() and _Chain_Iterator_destroy().
870   */
871  Chain_Node Registry_node;
872
873  /**
874   * @brief The direction of this iterator.
875   *
876   * Immutable after initialization via _Chain_Iterator_initialize().
877   */
878  Chain_Iterator_direction  direction;
879
880  /**
881   * @brief The current position of this iterator.
882   *
883   * The position is initialized via _Chain_Iterator_initialize().  It must be
884   * explicitly set after one valid iteration step, e.g. in case a next node in
885   * the iterator direction existed.  It is updated through the registration in
886   * case a node is extracted via _Chain_Iterator_registry_update().
887   */
888  Chain_Node *position;
889} Chain_Iterator;
890
891/**
892 * @brief A registry for chain iterators.
893 *
894 * Should be attached to a chain control to enable safe iteration through a
895 * chain in case of concurrent node extractions.
896 */
897typedef struct {
898  Chain_Control Iterators;
899} Chain_Iterator_registry;
900
901/**
902 * @brief Chain iterator registry initializer for static initialization.
903 *
904 * @param name The designator of the chain iterator registry.
905 */
906#define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
907  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
908
909/**
910 * @brief Initializes a chain iterator registry.
911 */
912RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(
913  Chain_Iterator_registry *the_registry
914)
915{
916  _Chain_Initialize_empty( &the_registry->Iterators );
917}
918
919/**
920 * @brief Updates all iterators present in the chain iterator registry in case
921 * of a node extraction.
922 *
923 * Must be called before _Chain_Extract_unprotected().
924 *
925 * @warning This function will look at all registered chain iterators to
926 *   determine if an update is necessary.
927 */
928RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_update(
929  Chain_Iterator_registry *the_registry,
930  Chain_Node              *the_node_to_extract
931)
932{
933  Chain_Node *iter_node;
934  Chain_Node *iter_tail;
935
936  iter_node = _Chain_Head( &the_registry->Iterators );
937  iter_tail = _Chain_Tail( &the_registry->Iterators );
938
939  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
940    Chain_Iterator *iter;
941
942    iter = (Chain_Iterator *) iter_node;
943
944    if ( iter->position == the_node_to_extract ) {
945      if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
946        iter->position = _Chain_Previous( the_node_to_extract );
947      } else {
948        iter->position = _Chain_Next( the_node_to_extract );
949      }
950    }
951  }
952}
953
954/**
955 * @brief Initializes the chain iterator.
956 *
957 * In the following example nodes inserted during the iteration are visited in
958 * case they are inserted after the current position in iteration order.
959 *
960 * @code
961 * #include <rtems/score/chainimpl.h>
962 * #include <rtems/score/isrlock.h>
963 *
964 * typedef struct {
965 *   Chain_Control           Chain;
966 *   Chain_Iterator_registry Iterators;
967 *   ISR_LOCK_MEMBER(        Lock )
968 * } Some_Control;
969 *
970 * void iterate(
971 *   Some_Control   *the_some,
972 *   void         ( *visitor )( Chain_Node * )
973 * )
974 * {
975 *   ISR_lock_Context  lock_context;
976 *   Chain_Iterator    iter;
977 *   Chain_Node       *node;
978 *   const Chain_Node *end;
979 *
980 *   end = _Chain_Immutable_tail( &the_some->Chain );
981 *
982 *   _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
983 *
984 *   _Chain_Iterator_initialize(
985 *     &the_some->Chain,
986 *     &the_some->Iterators,
987 *     &iter,
988 *     CHAIN_ITERATOR_FORWARD
989 *   );
990 *
991 *   while ( ( node = _Chain_Iterator_next( &iter ) ) != end ) {
992 *     _Chain_Iterator_set_position( &iter, node );
993 *     _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
994 *     ( *visitor )( node );
995 *     _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
996 *   }
997 *
998 *   _Chain_Iterator_destroy( &iter );
999 *   _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
1000 * }
1001 * @endcode
1002 *
1003 * @param the_chain The chain to iterate.
1004 * @param the_registry The registry for the chain iterator.
1005 * @param the_iterator The chain iterator to initialize.
1006 * @param direction The iteration direction.
1007 *
1008 * @see _Chain_Iterator_next(), _Chain_Iterator_set_position() and
1009 * Chain_Iterator_destroy().
1010 *
1011 * @warning Think twice before you use a chain iterator.  Its current
1012 *   implementation is unfit for use in performance relevant components, due to
1013 *   the linear time complexity in _Chain_Iterator_registry_update().
1014 */
1015RTEMS_INLINE_ROUTINE void _Chain_Iterator_initialize(
1016  Chain_Control            *the_chain,
1017  Chain_Iterator_registry  *the_registry,
1018  Chain_Iterator           *the_iterator,
1019  Chain_Iterator_direction  direction
1020)
1021{
1022  _Chain_Initialize_node( &the_iterator->Registry_node );
1023  _Chain_Append_unprotected(
1024    &the_registry->Iterators,
1025    &the_iterator->Registry_node
1026  );
1027
1028  the_iterator->direction = direction;
1029
1030  if ( direction == CHAIN_ITERATOR_FORWARD ) {
1031    the_iterator->position = _Chain_Head( the_chain );
1032  } else {
1033    the_iterator->position = _Chain_Tail( the_chain );
1034  }
1035}
1036
1037/**
1038 * @brief Returns the next node in the iterator direction.
1039 *
1040 * In case a next node exists, then the iterator should be updated via
1041 * _Chain_Iterator_set_position() to continue with the next iteration step.
1042 *
1043 * @param the_iterator The chain iterator.
1044 */
1045RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
1046  const Chain_Iterator *the_iterator
1047)
1048{
1049  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
1050    return _Chain_Next( the_iterator->position );
1051  } else {
1052    return _Chain_Previous( the_iterator->position );
1053  }
1054}
1055
1056/**
1057 * @brief Sets the iterator position.
1058 *
1059 * @param the_iterator The chain iterator.
1060 * @param the_node The new iterator position.
1061 */
1062RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(
1063  Chain_Iterator *the_iterator,
1064  Chain_Node     *the_node
1065)
1066{
1067  the_iterator->position = the_node;
1068}
1069
1070/**
1071 * @brief Destroys the iterator.
1072 *
1073 * Removes the iterator from its registry.
1074 *
1075 * @param the_iterator The chain iterator.
1076 */
1077RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(
1078  Chain_Iterator *the_iterator
1079)
1080{
1081  _Chain_Extract_unprotected( &the_iterator->Registry_node );
1082}
1083
1084/** @} */
1085
1086#ifdef __cplusplus
1087}
1088#endif
1089
1090#endif
1091/* end of include file */
Note: See TracBrowser for help on using the repository browser.