RTEMS  5.0.0
chainimpl.h
Go to the documentation of this file.
1 
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/assert.h>
23 
24 #ifdef __cplusplus
25 extern "C" {
26 #endif
27 
36 #define CHAIN_INITIALIZER_EMPTY(name) \
37  { { { &(name).Tail.Node, NULL }, &(name).Head.Node } }
38 
44 #define CHAIN_INITIALIZER_ONE_NODE( node ) \
45  { { { (node), NULL }, (node) } }
46 
52 #define CHAIN_NODE_INITIALIZER_ONE_NODE_CHAIN( chain ) \
53  { &(chain)->Tail.Node, &(chain)->Head.Node }
54 
58 #define CHAIN_DEFINE_EMPTY(name) \
59  Chain_Control name = CHAIN_INITIALIZER_EMPTY(name)
60 
75  Chain_Control *the_chain,
76  void *starting_address,
77  size_t number_nodes,
78  size_t node_size
79 );
80 
91 size_t _Chain_Node_count_unprotected( const Chain_Control *chain );
92 
102  Chain_Node *node
103 )
104 {
105  node->next = NULL;
106 #if defined(RTEMS_DEBUG)
107  node->previous = NULL;
108 #endif
109 }
110 
120 {
121 #if defined(RTEMS_DEBUG)
122  _Chain_Set_off_chain( the_node );
123 #else
124  (void) the_node;
125 #endif
126 }
127 
140  const Chain_Node *node
141 )
142 {
143  return node->next == NULL;
144 }
145 
159  const Chain_Node *left,
160  const Chain_Node *right
161 )
162 {
163  return left == right;
164 }
165 
177  const Chain_Node *the_node
178 )
179 {
180  return (the_node == NULL);
181 }
182 
193  Chain_Control *the_chain
194 )
195 {
196  return &the_chain->Head.Node;
197 }
198 
209  const Chain_Control *the_chain
210 )
211 {
212  return &the_chain->Head.Node;
213 }
214 
225  Chain_Control *the_chain
226 )
227 {
228  return &the_chain->Tail.Node;
229 }
230 
241  const Chain_Control *the_chain
242 )
243 {
244  return &the_chain->Tail.Node;
245 }
246 
258  const Chain_Control *the_chain
259 )
260 {
261  return _Chain_Immutable_head( the_chain )->next;
262 }
263 
275  const Chain_Control *the_chain
276 )
277 {
278  return _Chain_Immutable_head( the_chain )->next;
279 }
280 
292  const Chain_Control *the_chain
293 )
294 {
295  return _Chain_Immutable_tail( the_chain )->previous;
296 }
297 
309  const Chain_Control *the_chain
310 )
311 {
312  return _Chain_Immutable_tail( the_chain )->previous;
313 }
314 
325  const Chain_Node *the_node
326 )
327 {
328  return the_node->next;
329 }
330 
341  const Chain_Node *the_node
342 )
343 {
344  return the_node->next;
345 }
346 
357  const Chain_Node *the_node
358 )
359 {
360  return the_node->previous;
361 }
362 
373  const Chain_Node *the_node
374 )
375 {
376  return the_node->previous;
377 }
378 
391  const Chain_Control *the_chain
392 )
393 {
394  return _Chain_Immutable_first( the_chain )
395  == _Chain_Immutable_tail( the_chain );
396 }
397 
411  const Chain_Node *the_node
412 )
413 {
414  return (the_node->previous->previous == NULL);
415 }
416 
429  const Chain_Node *the_node
430 )
431 {
432  return (the_node->next->next == NULL);
433 }
434 
450  const Chain_Control *the_chain
451 )
452 {
453  return _Chain_Immutable_first( the_chain )
454  == _Chain_Immutable_last( the_chain );
455 }
456 
470  const Chain_Control *the_chain,
471  const Chain_Node *the_node
472 )
473 {
474  return (the_node == _Chain_Immutable_head( the_chain ));
475 }
476 
490  const Chain_Control *the_chain,
491  const Chain_Node *the_node
492 )
493 {
494  return (the_node == _Chain_Immutable_tail( the_chain ));
495 }
496 
505  Chain_Control *the_chain
506 )
507 {
508  Chain_Node *head;
509  Chain_Node *tail;
510 
511  _Assert( the_chain != NULL );
512 
513  head = _Chain_Head( the_chain );
514  tail = _Chain_Tail( the_chain );
515 
516  head->next = tail;
517  head->previous = NULL;
518  tail->previous = head;
519 }
520 
528  Chain_Control *the_chain,
529  Chain_Node *the_node
530 )
531 {
532  Chain_Node *head;
533  Chain_Node *tail;
534 
535  _Assert( _Chain_Is_node_off_chain( the_node ) );
536 
537  head = _Chain_Head( the_chain );
538  tail = _Chain_Tail( the_chain );
539 
540  the_node->next = tail;
541  the_node->previous = head;
542 
543  head->next = the_node;
544  head->previous = NULL;
545  tail->previous = the_node;
546 }
547 
558  Chain_Node *the_node
559 )
560 {
561  Chain_Node *next;
562  Chain_Node *previous;
563 
564  _Assert( !_Chain_Is_node_off_chain( the_node ) );
565 
566  next = the_node->next;
567  previous = the_node->previous;
568  next->previous = previous;
569  previous->next = next;
570 
571 #if defined(RTEMS_DEBUG)
572  _Chain_Set_off_chain( the_node );
573 #endif
574 }
575 
592  Chain_Control *the_chain
593 )
594 {
595  Chain_Node *head;
596  Chain_Node *old_first;
597  Chain_Node *new_first;
598 
599  _Assert( !_Chain_Is_empty( the_chain ) );
600 
601  head = _Chain_Head( the_chain );
602  old_first = head->next;
603  new_first = old_first->next;
604 
605  head->next = new_first;
606  new_first->previous = head;
607 
608 #if defined(RTEMS_DEBUG)
609  _Chain_Set_off_chain( old_first );
610 #endif
611 
612  return old_first;
613 }
614 
630  Chain_Control *the_chain
631 )
632 {
633  if ( !_Chain_Is_empty(the_chain))
634  return _Chain_Get_first_unprotected(the_chain);
635  else
636  return NULL;
637 }
638 
653  Chain_Node *after_node,
654  Chain_Node *the_node
655 )
656 {
657  Chain_Node *before_node;
658 
659  _Assert( _Chain_Is_node_off_chain( the_node ) );
660 
661  the_node->previous = after_node;
662  before_node = after_node->next;
663  after_node->next = the_node;
664  the_node->next = before_node;
665  before_node->previous = the_node;
666 }
667 
680  Chain_Control *the_chain,
681  Chain_Node *the_node
682 )
683 {
684  Chain_Node *tail;
685  Chain_Node *old_last;
686 
687  _Assert( _Chain_Is_node_off_chain( the_node ) );
688 
689  tail = _Chain_Tail( the_chain );
690  old_last = tail->previous;
691 
692  the_node->next = tail;
693  tail->previous = the_node;
694  old_last->next = the_node;
695  the_node->previous = old_last;
696 }
697 
708  Chain_Control *the_chain,
709  Chain_Node *the_node
710 )
711 {
712  if ( _Chain_Is_node_off_chain( the_node ) ) {
713  _Chain_Append_unprotected( the_chain, the_node );
714  }
715 }
716 
729  Chain_Control *the_chain,
730  Chain_Node *the_node
731 )
732 {
733  _Chain_Insert_unprotected(_Chain_Head(the_chain), the_node);
734 }
735 
751  Chain_Control *the_chain,
752  Chain_Node *the_node
753 )
754 {
755  bool was_empty = _Chain_Is_empty( the_chain );
756 
757  _Chain_Append_unprotected( the_chain, the_node );
758 
759  return was_empty;
760 }
761 
777  Chain_Control *the_chain,
778  Chain_Node *the_node
779 )
780 {
781  bool was_empty = _Chain_Is_empty( the_chain );
782 
783  _Chain_Prepend_unprotected( the_chain, the_node );
784 
785  return was_empty;
786 }
787 
807  Chain_Control *the_chain,
808  Chain_Node **the_node
809 )
810 {
811  bool is_empty_now = true;
812  Chain_Node *head = _Chain_Head( the_chain );
813  Chain_Node *tail = _Chain_Tail( the_chain );
814  Chain_Node *old_first = head->next;
815 
816  if ( old_first != tail ) {
817  Chain_Node *new_first = old_first->next;
818 
819  head->next = new_first;
820  new_first->previous = head;
821 
822  *the_node = old_first;
823 
824  is_empty_now = new_first == tail;
825  } else
826  *the_node = NULL;
827 
828  return is_empty_now;
829 }
830 
840 typedef bool ( *Chain_Node_order )(
841  const void *left,
842  const Chain_Node *right
843 );
844 
861  Chain_Control *the_chain,
862  Chain_Node *to_insert,
863  const void *left,
864  Chain_Node_order order
865 )
866 {
867  const Chain_Node *tail = _Chain_Immutable_tail( the_chain );
868  Chain_Node *next = _Chain_First( the_chain );
869 
870  while ( next != tail && !( *order )( left, next ) ) {
871  next = _Chain_Next( next );
872  }
873 
874  _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
875 }
876 
880 typedef enum {
885 
891 
898 typedef struct {
905 
911  Chain_Iterator_direction direction;
912 
923 
930 typedef struct {
931  Chain_Control Iterators;
933 
939 #define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
940  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
941 
946  Chain_Iterator_registry *the_registry
947 )
948 {
949  _Chain_Initialize_empty( &the_registry->Iterators );
950 }
951 
962  Chain_Iterator_registry *the_registry,
963  Chain_Node *the_node_to_extract
964 )
965 {
966  Chain_Node *iter_node;
967  Chain_Node *iter_tail;
968 
969  iter_node = _Chain_Head( &the_registry->Iterators );
970  iter_tail = _Chain_Tail( &the_registry->Iterators );
971 
972  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
973  Chain_Iterator *iter;
974 
975  iter = (Chain_Iterator *) iter_node;
976 
977  if ( iter->position == the_node_to_extract ) {
978  if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
979  iter->position = _Chain_Previous( the_node_to_extract );
980  } else {
981  iter->position = _Chain_Next( the_node_to_extract );
982  }
983  }
984  }
985 }
986 
1049  Chain_Control *the_chain,
1050  Chain_Iterator_registry *the_registry,
1051  Chain_Iterator *the_iterator,
1052  Chain_Iterator_direction direction
1053 )
1054 {
1055  _Chain_Initialize_node( &the_iterator->Registry_node );
1057  &the_registry->Iterators,
1058  &the_iterator->Registry_node
1059  );
1060 
1061  the_iterator->direction = direction;
1062 
1063  if ( direction == CHAIN_ITERATOR_FORWARD ) {
1064  the_iterator->position = _Chain_Head( the_chain );
1065  } else {
1066  the_iterator->position = _Chain_Tail( the_chain );
1067  }
1068 }
1069 
1079  const Chain_Iterator *the_iterator
1080 )
1081 {
1082  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
1083  return _Chain_Next( the_iterator->position );
1084  } else {
1085  return _Chain_Previous( the_iterator->position );
1086  }
1087 }
1088 
1096  Chain_Iterator *the_iterator,
1097  Chain_Node *the_node
1098 )
1099 {
1100  the_iterator->position = the_node;
1101 }
1102 
1111  Chain_Iterator *the_iterator
1112 )
1113 {
1114  _Chain_Extract_unprotected( &the_iterator->Registry_node );
1115 }
1116 
1119 #ifdef __cplusplus
1120 }
1121 #endif
1122 
1123 #endif
1124 /* end of include file */
RTEMS_INLINE_ROUTINE void _Chain_Append_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Append a node (unprotected).
Definition: chainimpl.h:679
Definition: chain.h:65
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Head(Chain_Control *the_chain)
Return pointer to chain head.
Definition: chainimpl.h:192
Chain_Node * previous
Definition: chain.h:69
RTEMS_INLINE_ROUTINE 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:860
RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(Chain_Iterator *the_iterator, Chain_Node *the_node)
Sets the iterator position.
Definition: chainimpl.h:1095
Chain_Node Registry_node
Node for registration.
Definition: chainimpl.h:904
A chain iterator which is updated during node extraction if it is properly registered.
Definition: chainimpl.h:898
void _Chain_Initialize(Chain_Control *the_chain, void *starting_address, size_t number_nodes, size_t node_size)
Initialize a chain header.
Definition: chain.c:26
RTEMS_INLINE_ROUTINE bool _Chain_Prepend_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Prepend a node and check if the chain was empty before (unprotected).
Definition: chainimpl.h:776
#define RTEMS_INLINE_ROUTINE
Definition: basedefs.h:65
RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(Chain_Iterator *the_iterator)
Destroys the iterator.
Definition: chainimpl.h:1110
RTEMS_INLINE_ROUTINE 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:1048
Definition: chain.h:83
RTEMS_INLINE_ROUTINE bool _Chain_Are_nodes_equal(const Chain_Node *left, const Chain_Node *right)
Are two nodes equal.
Definition: chainimpl.h:158
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_head(const Chain_Control *the_chain)
Return pointer to immutable chain head.
Definition: chainimpl.h:208
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Iterator_next(const Chain_Iterator *the_iterator)
Returns the next node in the iterator direction.
Definition: chainimpl.h:1078
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Next(const Chain_Node *the_node)
Return pointer the next node from this node.
Definition: chainimpl.h:324
RTEMS_INLINE_ROUTINE bool _Chain_Is_node_off_chain(const Chain_Node *node)
Is the node off chain.
Definition: chainimpl.h:139
RTEMS_INLINE_ROUTINE void _Chain_Extract_unprotected(Chain_Node *the_node)
Extract this node (unprotected).
Definition: chainimpl.h:557
RTEMS_INLINE_ROUTINE void _Chain_Initialize_empty(Chain_Control *the_chain)
Initialize this chain as empty.
Definition: chainimpl.h:504
RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(Chain_Iterator_registry *the_registry)
Initializes a chain iterator registry.
Definition: chainimpl.h:945
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_previous(const Chain_Node *the_node)
Return pointer the immutable previous node from this node.
Definition: chainimpl.h:372
RTEMS_INLINE_ROUTINE bool _Chain_Is_empty(const Chain_Control *the_chain)
Is the chain empty.
Definition: chainimpl.h:390
Chain_Node * next
Definition: chain.h:67
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_First(const Chain_Control *the_chain)
Return pointer to chain&#39;s first node.
Definition: chainimpl.h:257
RTEMS_INLINE_ROUTINE bool _Chain_Has_only_one_node(const Chain_Control *the_chain)
Does this chain have only one node.
Definition: chainimpl.h:449
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Get_unprotected(Chain_Control *the_chain)
Get the first node (unprotected).
Definition: chainimpl.h:629
RTEMS_INLINE_ROUTINE bool _Chain_Get_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node **the_node)
Get the first node and check if the chain is empty afterwards (unprotected).
Definition: chainimpl.h:806
RTEMS_INLINE_ROUTINE bool _Chain_Append_with_empty_check_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Append a node and check if the chain was empty before (unprotected).
Definition: chainimpl.h:750
size_t _Chain_Node_count_unprotected(const Chain_Control *chain)
Returns the node count of the chain.
Definition: chainnodecount.c:21
RTEMS_INLINE_ROUTINE bool _Chain_Is_last(const Chain_Node *the_node)
Is this the last node on the chain.
Definition: chainimpl.h:428
Iteration from head to tail.
Definition: chainimpl.h:884
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_first(const Chain_Control *the_chain)
Return pointer to immutable chain&#39;s first node.
Definition: chainimpl.h:274
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Tail(Chain_Control *the_chain)
Return pointer to chain tail.
Definition: chainimpl.h:224
bool(* Chain_Node_order)(const void *left, const Chain_Node *right)
Chain node order.
Definition: chainimpl.h:840
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_next(const Chain_Node *the_node)
Return pointer the immutable next node from this node.
Definition: chainimpl.h:340
RTEMS_INLINE_ROUTINE void _Chain_Initialize_node(Chain_Node *the_node)
Initializes a chain node.
Definition: chainimpl.h:119
RTEMS_INLINE_ROUTINE void _Chain_Insert_unprotected(Chain_Node *after_node, Chain_Node *the_node)
Insert a node (unprotected).
Definition: chainimpl.h:652
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Previous(const Chain_Node *the_node)
Return pointer the previous node from this node.
Definition: chainimpl.h:356
Chain Handler API.
RTEMS_INLINE_ROUTINE bool _Chain_Is_tail(const Chain_Control *the_chain, const Chain_Node *the_node)
Is this node the chail tail.
Definition: chainimpl.h:489
RTEMS_INLINE_ROUTINE bool _Chain_Is_first(const Chain_Node *the_node)
Is this the first node on the chain.
Definition: chainimpl.h:410
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Get_first_unprotected(Chain_Control *the_chain)
Get the first node (unprotected).
Definition: chainimpl.h:591
RTEMS_INLINE_ROUTINE void _Chain_Set_off_chain(Chain_Node *node)
Set off chain.
Definition: chainimpl.h:101
Chain_Iterator_direction
The chain iterator direction.
Definition: chainimpl.h:880
RTEMS_INLINE_ROUTINE bool _Chain_Is_null_node(const Chain_Node *the_node)
Is the chain node pointer NULL.
Definition: chainimpl.h:176
Iteration from tail to head.
Definition: chainimpl.h:889
Chain_Iterator_direction direction
The direction of this iterator.
Definition: chainimpl.h:911
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_tail(const Chain_Control *the_chain)
Return pointer to immutable chain tail.
Definition: chainimpl.h:240
RTEMS_INLINE_ROUTINE 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:961
RTEMS_INLINE_ROUTINE bool _Chain_Is_head(const Chain_Control *the_chain, const Chain_Node *the_node)
Is this node the chain head.
Definition: chainimpl.h:469
RTEMS_INLINE_ROUTINE const Chain_Node * _Chain_Immutable_last(const Chain_Control *the_chain)
Return pointer to immutable chain&#39;s last node.
Definition: chainimpl.h:308
RTEMS_INLINE_ROUTINE Chain_Node * _Chain_Last(const Chain_Control *the_chain)
Return pointer to chain&#39;s last node.
Definition: chainimpl.h:291
RTEMS_INLINE_ROUTINE void _Chain_Append_if_is_off_chain_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Append a node on the end of a chain if the node is in the off chain state (unprotected).
Definition: chainimpl.h:707
RTEMS_INLINE_ROUTINE void _Chain_Prepend_unprotected(Chain_Control *the_chain, Chain_Node *the_node)
Prepend a node (unprotected).
Definition: chainimpl.h:728
Chain_Node * position
The current position of this iterator.
Definition: chainimpl.h:921
RTEMS_INLINE_ROUTINE void _Chain_Initialize_one(Chain_Control *the_chain, Chain_Node *the_node)
Initializes this chain to contain exactly the specified node.
Definition: chainimpl.h:527
A registry for chain iterators.
Definition: chainimpl.h:930
#define NULL
Requests a GPIO pin group configuration.
Definition: bestcomm_api.h:77