Changeset 8f6c295b in rtems


Ignore:
Timestamp:
Apr 11, 2016, 3:03:05 PM (4 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
36272279
Parents:
b752f945
git-author:
Sebastian Huber <sebastian.huber@…> (04/11/16 15:03:05)
git-committer:
Sebastian Huber <sebastian.huber@…> (04/18/16 06:17:46)
Message:

score: Add Chain_Iterator

Add a chain iterator for safe iteration of chains with concurrent node
extraction.

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • cpukit/score/include/rtems/score/chainimpl.h

    rb752f945 r8f6c295b  
    801801}
    802802
     803/**
     804 * @brief The chain iterator direction.
     805 */
     806typedef enum {
     807  /**
     808   * @brief Iteration from head to tail.
     809   */
     810  CHAIN_ITERATOR_FORWARD,
     811
     812  /**
     813   * @brief Iteration from tail to head.
     814   */
     815  CHAIN_ITERATOR_BACKWARD
     816} Chain_Iterator_direction;
     817
     818/**
     819 * @brief A chain iterator which is updated during node extraction if it is
     820 * properly registered.
     821 *
     822 * @see _Chain_Iterator_initialize().
     823 */
     824typedef struct {
     825  /**
     826   * @brief Node for registration.
     827   *
     828   * Used during _Chain_Iterator_initialize() and _Chain_Iterator_destroy().
     829   */
     830  Chain_Node Registry_node;
     831
     832  /**
     833   * @brief The direction of this iterator.
     834   *
     835   * Immutable after initialization via _Chain_Iterator_initialize().
     836   */
     837  Chain_Iterator_direction  direction;
     838
     839  /**
     840   * @brief The current position of this iterator.
     841   *
     842   * The position is initialized via _Chain_Iterator_initialize().  It must be
     843   * explicitly set after one valid iteration step, e.g. in case a next node in
     844   * the iterator direction existed.  It is updated through the registration in
     845   * case a node is extracted via _Chain_Iterator_registry_update().
     846   */
     847  Chain_Node *position;
     848} Chain_Iterator;
     849
     850/**
     851 * @brief A registry for chain iterators.
     852 *
     853 * Should be attached to a chain control to enable safe iteration through a
     854 * chain in case of concurrent node extractions.
     855 */
     856typedef struct {
     857  Chain_Control Iterators;
     858} Chain_Iterator_registry;
     859
     860/**
     861 * @brief Chain iterator registry initializer for static initialization.
     862 *
     863 * @param name The designator of the chain iterator registry.
     864 */
     865#define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
     866  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
     867
     868/**
     869 * @brief Initializes a chain iterator registry.
     870 */
     871RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(
     872  Chain_Iterator_registry *the_registry
     873)
     874{
     875  _Chain_Initialize_empty( &the_registry->Iterators );
     876}
     877
     878/**
     879 * @brief Updates all iterators present in the chain iterator registry in case
     880 * of a node extraction.
     881 *
     882 * Must be called before _Chain_Extract_unprotected().
     883 *
     884 * @warning This function will look at all registered chain iterators to
     885 *   determine if an update is necessary.
     886 */
     887RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_update(
     888  Chain_Iterator_registry *the_registry,
     889  Chain_Node              *the_node_to_extract
     890)
     891{
     892  Chain_Node *iter_node;
     893  Chain_Node *iter_tail;
     894
     895  iter_node = _Chain_Head( &the_registry->Iterators );
     896  iter_tail = _Chain_Tail( &the_registry->Iterators );
     897
     898  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
     899    Chain_Iterator *iter;
     900
     901    iter = (Chain_Iterator *) iter_node;
     902
     903    if ( iter->position == the_node_to_extract ) {
     904      if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
     905        iter->position = _Chain_Previous( the_node_to_extract );
     906      } else {
     907        iter->position = _Chain_Next( the_node_to_extract );
     908      }
     909    }
     910  }
     911}
     912
     913/**
     914 * @brief Initializes the chain iterator.
     915 *
     916 * In the following example nodes inserted during the iteration are visited in
     917 * case they are inserted after the current position in iteration order.
     918 *
     919 * @code
     920 * #include <rtems/score/chainimpl.h>
     921 * #include <rtems/score/isrlock.h>
     922 *
     923 * typedef struct {
     924 *   Chain_Control           Chain;
     925 *   Chain_Iterator_registry Iterators;
     926 *   ISR_LOCK_MEMBER(        Lock )
     927 * } Some_Control;
     928 *
     929 * void iterate(
     930 *   Some_Control   *the_some,
     931 *   void         ( *visitor )( Chain_Node * )
     932 * )
     933 * {
     934 *   ISR_lock_Context  lock_context;
     935 *   Chain_Iterator    iter;
     936 *   Chain_Node       *node;
     937 *   const Chain_Node *end;
     938 *
     939 *   end = _Chain_Immutable_tail( &the_some->Chain );
     940 *
     941 *   _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
     942 *
     943 *   _Chain_Iterator_initialize(
     944 *     &the_some->Chain,
     945 *     &the_some->Iterators,
     946 *     &iter,
     947 *     CHAIN_ITERATOR_FORWARD
     948 *   );
     949 *
     950 *   while ( ( node = _Chain_Iterator_next( &iter ) ) != end ) {
     951 *     _Chain_Iterator_set_position( &iter, node );
     952 *     _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
     953 *     ( *visitor )( node );
     954 *     _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
     955 *   }
     956 *
     957 *   _Chain_Iterator_destroy( &iter );
     958 *   _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
     959 * }
     960 * @endcode
     961 *
     962 * @param the_chain The chain to iterate.
     963 * @param the_registry The registry for the chain iterator.
     964 * @param the_iterator The chain iterator to initialize.
     965 * @param direction The iteration direction.
     966 *
     967 * @see _Chain_Iterator_next(), _Chain_Iterator_set_position() and
     968 * Chain_Iterator_destroy().
     969 *
     970 * @warning Think twice before you use a chain iterator.  Its current
     971 *   implementation is unfit for use in performance relevant components, due to
     972 *   the linear time complexity in _Chain_Iterator_registry_update().
     973 */
     974RTEMS_INLINE_ROUTINE void _Chain_Iterator_initialize(
     975  Chain_Control            *the_chain,
     976  Chain_Iterator_registry  *the_registry,
     977  Chain_Iterator           *the_iterator,
     978  Chain_Iterator_direction  direction
     979)
     980{
     981  _Chain_Append_unprotected(
     982    &the_registry->Iterators,
     983    &the_iterator->Registry_node
     984  );
     985
     986  the_iterator->direction = direction;
     987
     988  if ( direction == CHAIN_ITERATOR_FORWARD ) {
     989    the_iterator->position = _Chain_Head( the_chain );
     990  } else {
     991    the_iterator->position = _Chain_Tail( the_chain );
     992  }
     993}
     994
     995/**
     996 * @brief Returns the next node in the iterator direction.
     997 *
     998 * In case a next node exists, then the iterator should be updated via
     999 * _Chain_Iterator_set_position() to continue with the next iteration step.
     1000 *
     1001 * @param the_iterator The chain iterator.
     1002 */
     1003RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
     1004  const Chain_Iterator *the_iterator
     1005)
     1006{
     1007  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
     1008    return _Chain_Next( the_iterator->position );
     1009  } else {
     1010    return _Chain_Previous( the_iterator->position );
     1011  }
     1012}
     1013
     1014/**
     1015 * @brief Sets the iterator position.
     1016 *
     1017 * @param the_iterator The chain iterator.
     1018 * @param the_node The new iterator position.
     1019 */
     1020RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(
     1021  Chain_Iterator *the_iterator,
     1022  Chain_Node     *the_node
     1023)
     1024{
     1025  the_iterator->position = the_node;
     1026}
     1027
     1028/**
     1029 * @brief Destroys the iterator.
     1030 *
     1031 * Removes the iterator from its registry.
     1032 *
     1033 * @param the_iterator The chain iterator.
     1034 */
     1035RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(
     1036  Chain_Iterator *the_iterator
     1037)
     1038{
     1039  _Chain_Extract_unprotected( &the_iterator->Registry_node );
     1040}
     1041
    8031042/** @} */
    8041043
  • testsuites/sptests/spchain/init.c

    rb752f945 r8f6c295b  
    1616
    1717const char rtems_test_name[] = "SPCHAIN";
     18
     19static void update_registry_and_extract(
     20  Chain_Iterator_registry *reg,
     21  Chain_Node *n
     22)
     23{
     24  _Chain_Iterator_registry_update( reg, n );
     25  _Chain_Extract_unprotected( n );
     26}
     27
     28static Chain_Iterator_registry static_reg =
     29  CHAIN_ITERATOR_REGISTRY_INITIALIZER( static_reg );
     30
     31static void test_chain_iterator( void )
     32{
     33  Chain_Control chain;
     34  Chain_Iterator_registry reg;
     35  Chain_Iterator fit;
     36  Chain_Iterator bit;
     37  Chain_Node a;
     38  Chain_Node b;
     39  Chain_Node c;
     40
     41  puts( "INIT - Verify Chain_Iterator" );
     42
     43  rtems_test_assert( _Chain_Is_empty( &static_reg.Iterators ));
     44
     45  _Chain_Initialize_empty( &chain );
     46  _Chain_Iterator_registry_initialize( &reg );
     47  _Chain_Iterator_initialize( &chain, &reg, &fit, CHAIN_ITERATOR_FORWARD );
     48  _Chain_Iterator_initialize( &chain, &reg, &bit, CHAIN_ITERATOR_BACKWARD );
     49
     50  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
     51  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
     52
     53  _Chain_Iterator_set_position( &fit, _Chain_Head( &chain ) );
     54  _Chain_Iterator_set_position( &bit, _Chain_Tail( &chain ) );
     55  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
     56  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
     57
     58  _Chain_Append_unprotected( &chain, &a );
     59  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     60  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
     61
     62  _Chain_Append_unprotected( &chain, &b );
     63  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     64  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
     65
     66  _Chain_Append_unprotected( &chain, &c );
     67  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     68  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     69
     70  update_registry_and_extract( &reg, &b );
     71  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     72  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     73
     74  _Chain_Insert_unprotected( &a, &b );
     75  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     76  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     77
     78  update_registry_and_extract( &reg, &c );
     79  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     80  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
     81
     82  _Chain_Append_unprotected( &chain, &c );
     83  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     84  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     85
     86  update_registry_and_extract( &reg, &a );
     87  rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
     88  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     89
     90  _Chain_Prepend_unprotected( &chain, &a );
     91  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     92  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     93
     94  update_registry_and_extract( &reg, &a );
     95  rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
     96  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     97
     98  update_registry_and_extract( &reg, &b );
     99  rtems_test_assert( _Chain_Iterator_next( &fit ) == &c );
     100  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     101
     102  update_registry_and_extract( &reg, &c );
     103  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
     104  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
     105
     106  _Chain_Append_unprotected( &chain, &a );
     107  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     108  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
     109
     110  _Chain_Append_unprotected( &chain, &b );
     111  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     112  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
     113
     114  _Chain_Append_unprotected( &chain, &c );
     115  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     116  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
     117
     118  update_registry_and_extract( &reg, &c );
     119  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     120  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
     121
     122  update_registry_and_extract( &reg, &b );
     123  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
     124  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
     125
     126  update_registry_and_extract( &reg, &a );
     127  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
     128  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
     129
     130  rtems_test_assert( !_Chain_Is_empty( &reg.Iterators ));
     131  _Chain_Iterator_destroy( &fit );
     132  rtems_test_assert( !_Chain_Is_empty( &reg.Iterators ));
     133  _Chain_Iterator_destroy( &bit );
     134  rtems_test_assert( _Chain_Is_empty( &reg.Iterators ));
     135}
    18136
    19137/* forward declarations to avoid warnings */
     
    342460  test_chain_node_count();
    343461  test_chain_insert_ordered();
     462  test_chain_iterator();
    344463
    345464  TEST_END();
  • testsuites/sptests/spchain/spchain.scn

    rb752f945 r8f6c295b  
    1 *** TEST OF RTEMS CHAIN API ***
     1*** BEGIN OF TEST SPCHAIN ***
    22Init - Initialize chain empty
    33INIT - Verify rtems_chain_insert
     
    1515INIT - Verify rtems_chain_node_count_unprotected
    1616INIT - Verify _Chain_Insert_ordered_unprotected
    17 *** END OF RTEMS CHAIN API TEST ***
     17INIT - Verify Chain_Iterator
     18*** END OF TEST SPCHAIN ***
Note: See TracChangeset for help on using the changeset viewer.