[PATCH 1/4] score: Add Chain_Iterator

Sebastian Huber sebastian.huber at embedded-brains.de
Fri Apr 15 09:16:05 UTC 2016


Add a chain iterator for safe iteration of chains with concurrent node
extraction.
---
 cpukit/score/include/rtems/score/chainimpl.h | 186 +++++++++++++++++++++++++++
 testsuites/sptests/spchain/init.c            | 119 +++++++++++++++++
 testsuites/sptests/spchain/spchain.doc       |   6 +
 testsuites/sptests/spchain/spchain.scn       |   5 +-
 4 files changed, 314 insertions(+), 2 deletions(-)

diff --git a/cpukit/score/include/rtems/score/chainimpl.h b/cpukit/score/include/rtems/score/chainimpl.h
index ff66d46..6210ea5 100644
--- a/cpukit/score/include/rtems/score/chainimpl.h
+++ b/cpukit/score/include/rtems/score/chainimpl.h
@@ -800,6 +800,192 @@ RTEMS_INLINE_ROUTINE void _Chain_Insert_ordered_unprotected(
   _Chain_Insert_unprotected( _Chain_Previous( next ), to_insert );
 }
 
+/**
+ * @brief The chain iterator direction.
+ */
+typedef enum {
+  /**
+   * @brief Iteration from head to tail.
+   */
+  CHAIN_ITERATOR_FORWARD,
+
+  /**
+   * @brief Iteration from tail to head.
+   */
+  CHAIN_ITERATOR_BACKWARD
+} Chain_Iterator_direction;
+
+/**
+ * @brief A chain iterator which is updated during node extraction if it is
+ * properly registered.
+ *
+ * @see _Chain_Iterator_initialize().
+ */
+typedef struct {
+  /**
+   * @brief Node for registration.
+   *
+   * Used during _Chain_Iterator_initialize() and _Chain_Iterator_destroy().
+   */
+  Chain_Node Registry_node;
+
+  /**
+   * @brief The direction of this iterator.
+   *
+   * Immutable after initialization via _Chain_Iterator_initialize().
+   */
+  Chain_Iterator_direction  direction;
+
+  /**
+   * @brief The current position of this iterator.
+   *
+   * The position is initialized via _Chain_Iterator_initialize().  It must be
+   * explicitly set after one valid iteration step, e.g. in case a next node in
+   * the iterator direction existed.  It is updated through the registration in
+   * case a node is extracted via _Chain_Iterator_registry_update().
+   */
+  Chain_Node *position;
+} Chain_Iterator;
+
+/**
+ * @brief A registry for chain iterators.
+ *
+ * Should be attached to a chain control to enable safe iteration through a
+ * chain in case of concurrent node extractions.
+ */
+typedef struct {
+  Chain_Control Iterators;
+} Chain_Iterator_registry;
+
+/**
+ * @brief Chain iterator registry initializer for static initialization.
+ *
+ * @param name The designator of the chain iterator registry.
+ */
+#define CHAIN_ITERATOR_REGISTRY_INITIALIZER( name ) \
+  { CHAIN_INITIALIZER_EMPTY( name.Iterators ) }
+
+/**
+ * @brief Initializes a chain iterator registry.
+ */
+RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_initialize(
+  Chain_Iterator_registry *the_registry
+)
+{
+  _Chain_Initialize_empty( &the_registry->Iterators );
+}
+
+/**
+ * @brief Updates all iterators present in the chain iterator registry in case
+ * of a node extraction.
+ *
+ * Must be called before _Chain_Extract_unprotected().
+ */
+RTEMS_INLINE_ROUTINE void _Chain_Iterator_registry_update(
+  Chain_Iterator_registry *the_registry,
+  Chain_Node              *the_node_to_extract
+)
+{
+  Chain_Node *iter_node;
+  Chain_Node *iter_tail;
+
+  iter_node = _Chain_Head( &the_registry->Iterators );
+  iter_tail = _Chain_Tail( &the_registry->Iterators );
+
+  while ( ( iter_node = _Chain_Next( iter_node ) ) != iter_tail ) {
+    Chain_Iterator *iter;
+
+    iter = (Chain_Iterator *) iter_node;
+
+    if ( iter->position == the_node_to_extract ) {
+      if ( iter->direction == CHAIN_ITERATOR_FORWARD ) {
+        iter->position = _Chain_Previous( the_node_to_extract );
+      } else {
+        iter->position = _Chain_Next( the_node_to_extract );
+      }
+    }
+  }
+}
+
+/**
+ * @brief Initializes the chain iterator.
+ *
+ * @param the_chain The chain to iterate.
+ * @param the_registry The registry for the chain iterator.
+ * @param the_iterator The chain iterator to initialize.
+ * @param direction The iteration direction.
+ *
+ * @see _Chain_Iterator_next(), _Chain_Iterator_set_position() and
+ * Chain_Iterator_destroy().
+ */
+RTEMS_INLINE_ROUTINE void _Chain_Iterator_initialize(
+  Chain_Control            *the_chain,
+  Chain_Iterator_registry  *the_registry,
+  Chain_Iterator           *the_iterator,
+  Chain_Iterator_direction  direction
+)
+{
+  _Chain_Append_unprotected(
+    &the_registry->Iterators,
+    &the_iterator->Registry_node
+  );
+
+  the_iterator->direction = direction;
+
+  if ( direction == CHAIN_ITERATOR_FORWARD ) {
+    the_iterator->position = _Chain_Head( the_chain );
+  } else {
+    the_iterator->position = _Chain_Tail( the_chain );
+  }
+}
+
+/**
+ * @brief Returns the next node in the iterator direction.
+ *
+ * In case a next node exits, then the iterator should be updated via
+ * _Chain_Iterator_set_position() to start the next iteration step.
+ *
+ * @param the_iterator The chain iterator.
+ */
+RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
+  Chain_Iterator *the_iterator
+)
+{
+  if ( the_iterator->direction == CHAIN_ITERATOR_FORWARD ) {
+    return _Chain_Next( the_iterator->position );
+  } else {
+    return _Chain_Previous( the_iterator->position );
+  }
+}
+
+/**
+ * @brief Sets the iterator position.
+ *
+ * @param the_iterator The chain iterator.
+ * @param the_node The new iterator position.
+ */
+RTEMS_INLINE_ROUTINE void _Chain_Iterator_set_position(
+  Chain_Iterator *the_iterator,
+  Chain_Node     *the_node
+)
+{
+  the_iterator->position = the_node;
+}
+
+/**
+ * @brief Destroys the iterator.
+ *
+ * Removes the iterator from its registry.
+ *
+ * @param the_iterator The chain iterator.
+ */
+RTEMS_INLINE_ROUTINE void _Chain_Iterator_destroy(
+  Chain_Iterator *the_iterator
+)
+{
+  _Chain_Extract_unprotected( &the_iterator->Registry_node );
+}
+
 /** @} */
 
 #ifdef __cplusplus
diff --git a/testsuites/sptests/spchain/init.c b/testsuites/sptests/spchain/init.c
index 476629b..dd46d68 100644
--- a/testsuites/sptests/spchain/init.c
+++ b/testsuites/sptests/spchain/init.c
@@ -16,6 +16,124 @@
 
 const char rtems_test_name[] = "SPCHAIN";
 
+static void update_registry_and_extract(
+  Chain_Iterator_registry *reg,
+  Chain_Node *n
+)
+{
+  _Chain_Iterator_registry_update( reg, n );
+  _Chain_Extract_unprotected( n );
+}
+
+static Chain_Iterator_registry static_reg =
+  CHAIN_ITERATOR_REGISTRY_INITIALIZER( static_reg );
+
+static void test_chain_iterator( void )
+{
+  Chain_Control chain;
+  Chain_Iterator_registry reg;
+  Chain_Iterator fit;
+  Chain_Iterator bit;
+  Chain_Node a;
+  Chain_Node b;
+  Chain_Node c;
+
+  puts( "INIT - Verify Chain_Iterator" );
+
+  rtems_test_assert( _Chain_Is_empty( &static_reg.Iterators ));
+
+  _Chain_Initialize_empty( &chain );
+  _Chain_Iterator_registry_initialize( &reg );
+  _Chain_Iterator_initialize( &chain, &reg, &fit, CHAIN_ITERATOR_FORWARD );
+  _Chain_Iterator_initialize( &chain, &reg, &bit, CHAIN_ITERATOR_BACKWARD );
+
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
+
+  _Chain_Iterator_set_position( &fit, _Chain_Head( &chain ) );
+  _Chain_Iterator_set_position( &bit, _Chain_Tail( &chain ) );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
+
+  _Chain_Append_unprotected( &chain, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
+
+  _Chain_Append_unprotected( &chain, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
+
+  _Chain_Append_unprotected( &chain, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  _Chain_Insert_unprotected( &a, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
+
+  _Chain_Append_unprotected( &chain, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  _Chain_Prepend_unprotected( &chain, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &c );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
+
+  _Chain_Append_unprotected( &chain, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
+
+  _Chain_Append_unprotected( &chain, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
+
+  _Chain_Append_unprotected( &chain, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+  update_registry_and_extract( &reg, &c );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
+
+  update_registry_and_extract( &reg, &b );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
+
+  update_registry_and_extract( &reg, &a );
+  rtems_test_assert( _Chain_Iterator_next( &fit ) == _Chain_Tail( &chain ));
+  rtems_test_assert( _Chain_Iterator_next( &bit ) == _Chain_Head( &chain ));
+
+  rtems_test_assert( !_Chain_Is_empty( &reg.Iterators ));
+  _Chain_Iterator_destroy( &fit );
+  rtems_test_assert( !_Chain_Is_empty( &reg.Iterators ));
+  _Chain_Iterator_destroy( &bit );
+  rtems_test_assert( _Chain_Is_empty( &reg.Iterators ));
+}
+
 /* forward declarations to avoid warnings */
 rtems_task Init(rtems_task_argument argument);
 
@@ -341,6 +459,7 @@ rtems_task Init(
   test_chain_control_initializer();
   test_chain_node_count();
   test_chain_insert_ordered();
+  test_chain_iterator();
 
   TEST_END();
   rtems_test_exit(0);
diff --git a/testsuites/sptests/spchain/spchain.doc b/testsuites/sptests/spchain/spchain.doc
index 511e0b5..4962426 100644
--- a/testsuites/sptests/spchain/spchain.doc
+++ b/testsuites/sptests/spchain/spchain.doc
@@ -25,6 +25,12 @@ directives:
   rtems_chain_get_with_wait
   rtems_chain_node_count_unprotected
   _Chain_Insert_ordered_unprotected
+  _Chain_Iterator_registry_initialize
+  _Chain_Iterator_registry_update
+  _Chain_Iterator_initialize
+  _Chain_Iterator_next
+  _Chain_Iterator_set_position
+  _Chain_Iterator_destroy
 
 concepts:
 
diff --git a/testsuites/sptests/spchain/spchain.scn b/testsuites/sptests/spchain/spchain.scn
index 39f3795..4aff306 100644
--- a/testsuites/sptests/spchain/spchain.scn
+++ b/testsuites/sptests/spchain/spchain.scn
@@ -1,4 +1,4 @@
-*** TEST OF RTEMS CHAIN API ***
+*** BEGIN OF TEST SPCHAIN ***
 Init - Initialize chain empty
 INIT - Verify rtems_chain_insert
 INIT - Verify rtems_chain_is_first
@@ -14,4 +14,5 @@ INIT - Verify rtems_chain_control layout
 INIT - Verify rtems_chain_control initializer
 INIT - Verify rtems_chain_node_count_unprotected
 INIT - Verify _Chain_Insert_ordered_unprotected
-*** END OF RTEMS CHAIN API TEST ***
+INIT - Verify Chain_Iterator
+*** END OF TEST SPCHAIN ***
-- 
1.8.4.5



More information about the devel mailing list