[rtems commit] score: Add Chain_Iterator
Sebastian Huber
sebh at rtems.org
Tue Apr 19 05:22:42 UTC 2016
Module: rtems
Branch: master
Commit: 8f6c295b94c5a25c70dce2adac1a89366ca31f0a
Changeset: http://git.rtems.org/rtems/commit/?id=8f6c295b94c5a25c70dce2adac1a89366ca31f0a
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Mon Apr 11 17:03:05 2016 +0200
score: Add Chain_Iterator
Add a chain iterator for safe iteration of chains with concurrent node
extraction.
---
cpukit/score/include/rtems/score/chainimpl.h | 239 +++++++++++++++++++++++++++
testsuites/sptests/spchain/init.c | 119 +++++++++++++
testsuites/sptests/spchain/spchain.doc | 6 +
testsuites/sptests/spchain/spchain.scn | 5 +-
4 files changed, 367 insertions(+), 2 deletions(-)
diff --git a/cpukit/score/include/rtems/score/chainimpl.h b/cpukit/score/include/rtems/score/chainimpl.h
index ff66d46..f78f2d6 100644
--- a/cpukit/score/include/rtems/score/chainimpl.h
+++ b/cpukit/score/include/rtems/score/chainimpl.h
@@ -800,6 +800,245 @@ 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().
+ *
+ * @warning This function will look at all registered chain iterators to
+ * determine if an update is necessary.
+ */
+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.
+ *
+ * In the following example nodes inserted during the iteration are visited in
+ * case they are inserted after the current position in iteration order.
+ *
+ * @code
+ * #include <rtems/score/chainimpl.h>
+ * #include <rtems/score/isrlock.h>
+ *
+ * typedef struct {
+ * Chain_Control Chain;
+ * Chain_Iterator_registry Iterators;
+ * ISR_LOCK_MEMBER( Lock )
+ * } Some_Control;
+ *
+ * void iterate(
+ * Some_Control *the_some,
+ * void ( *visitor )( Chain_Node * )
+ * )
+ * {
+ * ISR_lock_Context lock_context;
+ * Chain_Iterator iter;
+ * Chain_Node *node;
+ * const Chain_Node *end;
+ *
+ * end = _Chain_Immutable_tail( &the_some->Chain );
+ *
+ * _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
+ *
+ * _Chain_Iterator_initialize(
+ * &the_some->Chain,
+ * &the_some->Iterators,
+ * &iter,
+ * CHAIN_ITERATOR_FORWARD
+ * );
+ *
+ * while ( ( node = _Chain_Iterator_next( &iter ) ) != end ) {
+ * _Chain_Iterator_set_position( &iter, node );
+ * _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
+ * ( *visitor )( node );
+ * _ISR_lock_ISR_disable_and_acquire( &the_some->Lock, &lock_context );
+ * }
+ *
+ * _Chain_Iterator_destroy( &iter );
+ * _ISR_lock_Release_and_ISR_enable( &the_some->Lock, &lock_context );
+ * }
+ * @endcode
+ *
+ * @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().
+ *
+ * @warning Think twice before you use a chain iterator. Its current
+ * implementation is unfit for use in performance relevant components, due to
+ * the linear time complexity in _Chain_Iterator_registry_update().
+ */
+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 exists, then the iterator should be updated via
+ * _Chain_Iterator_set_position() to continue with the next iteration step.
+ *
+ * @param the_iterator The chain iterator.
+ */
+RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Iterator_next(
+ const 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( ® );
+ _Chain_Iterator_initialize( &chain, ®, &fit, CHAIN_ITERATOR_FORWARD );
+ _Chain_Iterator_initialize( &chain, ®, &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( ®, &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( ®, &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( ®, &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( ®, &a );
+ rtems_test_assert( _Chain_Iterator_next( &fit ) == &b );
+ rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+ update_registry_and_extract( ®, &b );
+ rtems_test_assert( _Chain_Iterator_next( &fit ) == &c );
+ rtems_test_assert( _Chain_Iterator_next( &bit ) == &c );
+
+ update_registry_and_extract( ®, &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( ®, &c );
+ rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+ rtems_test_assert( _Chain_Iterator_next( &bit ) == &b );
+
+ update_registry_and_extract( ®, &b );
+ rtems_test_assert( _Chain_Iterator_next( &fit ) == &a );
+ rtems_test_assert( _Chain_Iterator_next( &bit ) == &a );
+
+ update_registry_and_extract( ®, &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( ®.Iterators ));
+ _Chain_Iterator_destroy( &fit );
+ rtems_test_assert( !_Chain_Is_empty( ®.Iterators ));
+ _Chain_Iterator_destroy( &bit );
+ rtems_test_assert( _Chain_Is_empty( ®.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 ***
More information about the vc
mailing list