RTEMS
chainimpl.h
Go to the documentation of this file.
1 
9 /*
10  * Copyright (c) 2010 embedded brains GmbH.
11  *
12  * COPYRIGHT (c) 1989-2014.
13  * On-Line Applications Research Corporation (OAR).
14  *
15  * The license and distribution terms for this file may be
16  * found in the file LICENSE in this distribution or at
17  * http://www.rtems.org/license/LICENSE.
18  */
19 
20 #ifndef _RTEMS_SCORE_CHAINIMPL_H
21 #define _RTEMS_SCORE_CHAINIMPL_H
22 
23 #include <rtems/score/chain.h>
24 #include <rtems/score/assert.h>
25 
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29 
39 #define CHAIN_INITIALIZER_EMPTY(name) \
40  { { { &(name).Tail.Node, NULL }, &(name).Head.Node } }
41 
47 #define CHAIN_INITIALIZER_ONE_NODE( node ) \
48  { { { (node), NULL }, (node) } }
49 
55 #define CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN( chain ) \
56  { &(chain)->Tail.Node, &(chain)->Head.Node }
57 
61 #define CHAIN_DEFINE_EMPTY(name) \
62  Chain_Control name = CHAIN_INITIALIZER_EMPTY(name)
63 
78  Chain_Control *the_chain,
79  void *starting_address,
80  size_t number_nodes,
81  size_t node_size
82 );
83 
94 size_t _Chain_Node_count_unprotected( const Chain_Control *chain );
95 
105  Chain_Node *node
106 )
107 {
108  node->next = NULL;
109 #if defined(RTEMS_DEBUG)
110  node->previous = NULL;
111 #endif
112 }
113 
123 {
124 #if defined(RTEMS_DEBUG)
125  _Chain_Set_off_chain( the_node );
126 #else
127  (void) the_node;
128 #endif
129 }
130 
143  const Chain_Node *node
144 )
145 {
146  return node->next == NULL;
147 }
148 
162  const Chain_Node *left,
163  const Chain_Node *right
164 )
165 {
166  return left == right;
167 }
168 
180  const Chain_Node *the_node
181 )
182 {
183  return (the_node == NULL);
184 }
185 
196  Chain_Control *the_chain
197 )
198 {
199  return &the_chain->Head.Node;
200 }
201 
212  const Chain_Control *the_chain
213 )
214 {
215  return &the_chain->Head.Node;
216 }
217 
228  Chain_Control *the_chain
229 )
230 {
231  return &the_chain->Tail.Node;
232 }
233 
244  const Chain_Control *the_chain
245 )
246 {
247  return &the_chain->Tail.Node;
248 }
249 
261  const Chain_Control *the_chain
262 )
263 {
264  return _Chain_Immutable_head( the_chain )->next;
265 }
266 
278  const Chain_Control *the_chain
279 )
280 {
281  return _Chain_Immutable_head( the_chain )->next;
282 }
283 
295  const Chain_Control *the_chain
296 )
297 {
298  return _Chain_Immutable_tail( the_chain )->previous;
299 }
300 
312  const Chain_Control *the_chain
313 )
314 {
315  return _Chain_Immutable_tail( the_chain )->previous;
316 }
317 
328  const Chain_Node *the_node
329 )
330 {
331  return the_node->next;
332 }
333 
344  const Chain_Node *the_node
345 )
346 {
347  return the_node->next;
348 }
349 
360  const Chain_Node *the_node
361 )
362 {
363  return the_node->previous;
364 }
365 
376  const Chain_Node *the_node
377 )
378 {
379  return the_node->previous;
380 }
381 
394  const Chain_Control *the_chain
395 )
396 {
397  return _Chain_Immutable_first( the_chain )
398  == _Chain_Immutable_tail( the_chain );
399 }
400 
414  const Chain_Node *the_node
415 )
416 {
417  return (the_node->previous->previous == NULL);
418 }
419 
433  const Chain_Node *the_node
434 )
435 {
436  return (the_node->next->next == NULL);
437 }
438 
451  const Chain_Control *the_chain
452 )
453 {
454  return _Chain_Immutable_first( the_chain )
455  == _Chain_Immutable_last( the_chain );
456 }
457 
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 
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 
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 
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 
559  Chain_Node *the_node
560 )
561 {
562  Chain_Node *next;
563  Chain_Node *previous;
564 
565  _Assert( !_Chain_Is_node_off_chain( the_node ) );
566 
567  next = the_node->next;
568  previous = the_node->previous;
569  next->previous = previous;
570  previous->next = next;
571 
572 #if defined(RTEMS_DEBUG)
573  _Chain_Set_off_chain( the_node );
574 #endif
575 }
576 
593  Chain_Control *the_chain
594 )
595 {
596  Chain_Node *head;
597  Chain_Node *old_first;
598  Chain_Node *new_first;
599 
600  _Assert( !_Chain_Is_empty( the_chain ) );
601 
602  head = _Chain_Head( the_chain );
603  old_first = head->next;
604  new_first = old_first->next;
605 
606  head->next = new_first;
607  new_first->previous = head;
608 
609 #if defined(RTEMS_DEBUG)
610  _Chain_Set_off_chain( old_first );
611 #endif
612 
613  return old_first;
614 }
615 
631  Chain_Control *the_chain
632 )
633 {
634  if ( !_Chain_Is_empty(the_chain))
635  return _Chain_Get_first_unprotected(the_chain);
636  else
637  return NULL;
638 }
639 
654  Chain_Node *after_node,
655  Chain_Node *the_node
656 )
657 {
658  Chain_Node *before_node;
659 
660  _Assert( _Chain_Is_node_off_chain( the_node ) );
661 
662  the_node->previous = after_node;
663  before_node = after_node->next;
664  after_node->next = the_node;
665  the_node->next = before_node;
666  before_node->previous = the_node;
667 }
668 
681  Chain_Control *the_chain,
682  Chain_Node *the_node
683 )
684 {
685  Chain_Node *tail;
686  Chain_Node *old_last;
687 
688  _Assert( _Chain_Is_node_off_chain( the_node ) );
689 
690  tail = _Chain_Tail( the_chain );
691  old_last = tail->previous;
692 
693  the_node->next = tail;
694  tail->previous = the_node;
695  old_last->next = the_node;
696  the_node->previous = old_last;
697 }
698 
712  Chain_Control *the_chain,
713  Chain_Node *the_node
714 )
715 {
716  if ( _Chain_Is_node_off_chain( the_node ) ) {
717  _Chain_Append_unprotected( the_chain, the_node );
718  }
719 }
720 
733  Chain_Control *the_chain,
734  Chain_Node *the_node
735 )
736 {
737  _Chain_Insert_unprotected(_Chain_Head(the_chain), the_node);
738 }
739 
755  Chain_Control *the_chain,
756  Chain_Node *the_node
757 )
758 {
759  bool was_empty = _Chain_Is_empty( the_chain );
760 
761  _Chain_Append_unprotected( the_chain, the_node );
762 
763  return was_empty;
764 }
765 
781  Chain_Control *the_chain,
782  Chain_Node *the_node
783 )
784 {
785  bool was_empty = _Chain_Is_empty( the_chain );
786 
787  _Chain_Prepend_unprotected( the_chain, the_node );
788 
789  return was_empty;
790 }
791 
811  Chain_Control *the_chain,
812  Chain_Node **the_node
813 )
814 {
815  bool is_empty_now = true;
816  Chain_Node *head = _Chain_Head( the_chain );
817  Chain_Node *tail = _Chain_Tail( the_chain );
818  Chain_Node *old_first = head->next;
819 
820  if ( old_first != tail ) {
821  Chain_Node *new_first = old_first->next;
822 
823  head->next = new_first;
824  new_first->previous = head;
825 
826  *the_node = old_first;
827 
828  is_empty_now = new_first == tail;
829  } else
830  *the_node = NULL;
831 
832  return is_empty_now;
833 }
834 
844 typedef bool ( *Chain_Node_order )(
845  const void *left,
846  const Chain_Node *right
847 );
848 
865  Chain_Control *the_chain,
866  Chain_Node *to_insert,
867  const void *left,
868  Chain_Node_order order
869 )
870 {
871  const Chain_Node *tail = _Chain_Immutable_tail( the_chain );
872  Chain_Node *next = _Chain_First( the_chain );
873 
874  while ( next != tail && !( *order )( left, next ) ) {
875  next = _Chain_Next( next );
876  }
877 
878  _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
879 }
880 
884 typedef enum {
889 
895 
902 typedef struct {
909 
916 
927 
934 typedef struct {
935  Chain_Control Iterators;
937 
943 #define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
944  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
945 
952  Chain_Iterator_registry *the_registry
953 )
954 {
955  _Chain_Initialize_empty( &the_registry->Iterators );
956 }
957 
971  Chain_Iterator_registry *the_registry,
972  Chain_Node *the_node_to_extract
973 )
974 {
975  Chain_Node *iter_node;
976  Chain_Node *iter_tail;
977 
978  iter_node = _Chain_Head( &the_registry->Iterators );
979  iter_tail = _Chain_Tail( &the_registry->Iterators );
980 
981  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
982  Chain_Iterator *iter;
983 
984  iter = (Chain_Iterator *) iter_node;
985 
986  if ( iter->position == the_node_to_extract ) {
987  if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
988  iter->position = _Chain_Previous( the_node_to_extract );
989  } else {
990  iter->position = _Chain_Next( the_node_to_extract );
991  }
992  }
993  }
994 }
995 
1058  Chain_Control *the_chain,
1059  Chain_Iterator_registry *the_registry,
1060  Chain_Iterator *the_iterator,
1061  Chain_Iterator_direction direction
1062 )
1063 {
1064  _Chain_Initialize_node( &the_iterator->Registry_node );
1066  &the_registry->Iterators,
1067  &the_iterator->Registry_node
1068  );
1069 
1070  the_iterator->direction = direction;
1071 
1072  if ( direction == CHAIN_ITERATOR_FORWARD ) {
1073  the_iterator->position = _Chain_Head( the_chain );
1074  } else {
1075  the_iterator->position = _Chain_Tail( the_chain );
1076  }
1077 }
1078 
1090  const Chain_Iterator *the_iterator
1091 )
1092 {
1093  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
1094  return _Chain_Next( the_iterator->position );
1095  } else {
1096  return _Chain_Previous( the_iterator->position );
1097  }
1098 }
1099 
1107  Chain_Iterator *the_iterator,
1108  Chain_Node *the_node
1109 )
1110 {
1111  the_iterator->position = the_node;
1112 }
1113 
1122  Chain_Iterator *the_iterator
1123 )
1124 {
1125  _Chain_Extract_unprotected( &the_iterator->Registry_node );
1126 }
1127 
1130 #ifdef __cplusplus
1131 }
1132 #endif
1133 
1134 #endif
1135 /* end of include file */
static __inline__ void _Chain_Iterator_destroy(Chain_Iterator *the_iterator)
Destroys the iterator.
Definition: chainimpl.h:1121
static __inline__ bool _Chain_Append_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Appends a node and checks if the chain was empty before (unprotected).
Definition: chainimpl.h:754
bool(* Chain_Node_order)(const void *left, const Chain_Node *right)
Chain node order.
Definition: chainimpl.h:844
static __inline__ Chain_Node * _Chain_First(const Chain_Control *the_chain)
Returns pointer to chain&#39;s first node.
Definition: chainimpl.h:260
static __inline__ bool _Chain_Is_first(const Chain_Node *the_node)
Checks if this is the first node on the chain.
Definition: chainimpl.h:413
Chain_Node * previous
Definition: chain.h:72
static __inline__ void _Chain_Iterator_set_position(Chain_Iterator *the_iterator, Chain_Node *the_node)
Sets the iterator position.
Definition: chainimpl.h:1106
static __inline__ bool _Chain_Are_nodes_equal(const Chain_Node *left, const Chain_Node *right)
Checks if two nodes are equal.
Definition: chainimpl.h:161
Chain_Node Registry_node
Node for registration.
Definition: chainimpl.h:908
A chain iterator which is updated during node extraction if it is properly registered.
Definition: chainimpl.h:902
static __inline__ void _Chain_Iterator_registry_update(Chain_Iterator_registry *the_registry, Chain_Node *the_node_to_extract)
Updates all iterators present in the chain iterator registry in case of a node extraction.
Definition: chainimpl.h:970
static __inline__ bool _Chain_Is_node_off_chain(const Chain_Node *node)
Checks if the node is off chain.
Definition: chainimpl.h:142
static __inline__ bool _Chain_Is_last(const Chain_Node *the_node)
Checks if this is the last node on the chain.
Definition: chainimpl.h:432
static __inline__ void _Chain_Initialize_node(Chain_Node *the_node)
Initializes a chain node.
Definition: chainimpl.h:122
static __inline__ bool _Chain_Get_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node **the_node)
Gets the first node and checks if the chain is empty afterwards (unprotected).
Definition: chainimpl.h:810
static __inline__ const Chain_Node * _Chain_Immutable_previous(const Chain_Node *the_node)
Returns pointer to the immutable previous node from this node.
Definition: chainimpl.h:375
static __inline__ void _Chain_Iterator_registry_initialize(Chain_Iterator_registry *the_registry)
Initializes a chain iterator registry.
Definition: chainimpl.h:951
static __inline__ Chain_Node * _Chain_Get_first_unprotected(Chain_Control *the_chain)
Gets the first node (unprotected).
Definition: chainimpl.h:592
void _Chain_Initialize(Chain_Control *the_chain, void *starting_address, size_t number_nodes, size_t node_size)
Initializes a chain header.
Definition: chain.c:26
size_t _Chain_Node_count_unprotected(const Chain_Control *chain)
Returns the node count of the chain.
static __inline__ bool _Chain_Is_head(const Chain_Control *the_chain, const Chain_Node *the_node)
Checks if this node is the chain head.
Definition: chainimpl.h:470
static __inline__ void _Chain_Insert_unprotected(Chain_Node *after_node, Chain_Node *the_node)
Inserts a node (unprotected).
Definition: chainimpl.h:653
Information for the Assert Handler.
static __inline__ void _Chain_Append_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Appends a node (unprotected).
Definition: chainimpl.h:680
Chain_Node * next
Definition: chain.h:70
static __inline__ void _Chain_Prepend_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Prepends a node (unprotected).
Definition: chainimpl.h:732
static __inline__ bool _Chain_Is_null_node(const Chain_Node *the_node)
Checks if the chain node pointer is NULL.
Definition: chainimpl.h:179
static __inline__ Chain_Node * _Chain_Next(const Chain_Node *the_node)
Returns pointer to the next node from this node.
Definition: chainimpl.h:327
static __inline__ Chain_Node * _Chain_Head(Chain_Control *the_chain)
Returns pointer to chain head.
Definition: chainimpl.h:195
static __inline__ bool _Chain_Has_only_one_node(const Chain_Control *the_chain)
Checks if this chain has only one node.
Definition: chainimpl.h:450
static __inline__ void _Chain_Extract_unprotected(Chain_Node *the_node)
Extracts this node (unprotected).
Definition: chainimpl.h:558
static __inline__ const Chain_Node * _Chain_Immutable_next(const Chain_Node *the_node)
Returns pointer to the immutable next node from this node.
Definition: chainimpl.h:343
static __inline__ Chain_Node * _Chain_Iterator_next(const Chain_Iterator *the_iterator)
Returns the next node in the iterator direction.
Definition: chainimpl.h:1089
static __inline__ void _Chain_Initialize_one(Chain_Control *the_chain, Chain_Node *the_node)
Initializes this chain to contain exactly the specified node.
Definition: chainimpl.h:528
static __inline__ void _Chain_Initialize_empty(Chain_Control *the_chain)
Initializes this chain as empty.
Definition: chainimpl.h:505
static __inline__ const Chain_Node * _Chain_Immutable_first(const Chain_Control *the_chain)
Returns pointer to immutable chain&#39;s first node.
Definition: chainimpl.h:277
Iteration from head to tail.
Definition: chainimpl.h:888
Chain Handler API.
static __inline__ Chain_Node * _Chain_Last(const Chain_Control *the_chain)
Returns pointer to chain&#39;s last node.
Definition: chainimpl.h:294
static __inline__ Chain_Node * _Chain_Previous(const Chain_Node *the_node)
Returns pointer to the previous node from this node.
Definition: chainimpl.h:359
static __inline__ void _Chain_Set_off_chain(Chain_Node *node)
Sets off chain.
Definition: chainimpl.h:104
static __inline__ const Chain_Node * _Chain_Immutable_head(const Chain_Control *the_chain)
Returns pointer to immutable chain head.
Definition: chainimpl.h:211
static __inline__ const Chain_Node * _Chain_Immutable_last(const Chain_Control *the_chain)
Returns pointer to immutable chain&#39;s last node.
Definition: chainimpl.h:311
Chain_Iterator_direction
The chain iterator direction.
Definition: chainimpl.h:884
#define RTEMS_INLINE_ROUTINE
Gives a hint to the compiler in a function declaration to inline this function.
Definition: basedefs.h:683
static __inline__ void _Chain_Insert_ordered_unprotected(Chain_Control *the_chain, Chain_Node *to_insert, const void *left, Chain_Node_order order)
Inserts a node into the chain according to the order relation.
Definition: chainimpl.h:864
Chain_Iterator_direction direction
The direction of this iterator.
Definition: chainimpl.h:915
static __inline__ void _Chain_Iterator_initialize(Chain_Control *the_chain, Chain_Iterator_registry *the_registry, Chain_Iterator *the_iterator, Chain_Iterator_direction direction)
Initializes the chain iterator.
Definition: chainimpl.h:1057
Iteration from tail to head.
Definition: chainimpl.h:893
static __inline__ bool _Chain_Prepend_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Prepends a node and checks if the chain was empty before (unprotected).
Definition: chainimpl.h:780
static __inline__ bool _Chain_Is_empty(const Chain_Control *the_chain)
Checks if the chain is empty.
Definition: chainimpl.h:393
static __inline__ void _Chain_Append_if_is_off_chain_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Appends a node on the end of a chain if the node is in the off chain state (unprotected).
Definition: chainimpl.h:711
Chain_Node * position
The current position of this iterator.
Definition: chainimpl.h:925
static __inline__ Chain_Node * _Chain_Tail(Chain_Control *the_chain)
Returns pointer to chain tail.
Definition: chainimpl.h:227
static __inline__ bool _Chain_Is_tail(const Chain_Control *the_chain, const Chain_Node *the_node)
Checks if this node is the chain tail.
Definition: chainimpl.h:490
static __inline__ const Chain_Node * _Chain_Immutable_tail(const Chain_Control *the_chain)
Returns pointer to immutable chain tail.
Definition: chainimpl.h:243
#define _Assert(_e)
Assertion similar to assert() controlled via RTEMS_DEBUG instead of NDEBUG.
Definition: assert.h:100
A registry for chain iterators.
Definition: chainimpl.h:934
static __inline__ Chain_Node * _Chain_Get_unprotected(Chain_Control *the_chain)
Gets the first node (unprotected).
Definition: chainimpl.h:630