Re: [PATCH 1/3] Add and use RTEMS_CONTAINER_OF()
On 08/04/2014 03:59 PM, Gedare Bloom wrote:
>diff --git a/cpukit/libblock/src/bdbuf.c b/cpukit/libblock/src/bdbuf.c
>index 31dd289..f215911 100644
>--- a/cpukit/libblock/src/bdbuf.c
>+++ b/cpukit/libblock/src/bdbuf.c
>@@ -3178,8 +3178,8 @@ rtems_bdbuf_read_ahead_task (rtems_task_argument arg)
>
> while ((node = rtems_chain_get_unprotected (chain)) != NULL)
> {
>- rtems_disk_device *dd = (rtems_disk_device *)
>-((char *) node - offsetof (rtems_disk_device, read_ahead.node));
>+ rtems_disk_device *dd =
>+RTEMS_CONTAINER_OF (node, rtems_disk_device, read_ahead.node);
Delete the extra space between OF and (.
This file has its own style.
--
Sebastian Huber, embedded brains GmbH
Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone : +49 89 189 47 41-16
Fax : +49 89 189 47 41-09
E-Mail : sebastian.hu...@embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
___
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
[PATCH 1/3] rbtree: Simplify insert and extract
Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().
---
cpukit/sapi/include/rtems/rbtree.h| 12 ++
cpukit/score/include/rtems/score/rbtree.h | 44 +++---
cpukit/score/include/rtems/score/rbtreeimpl.h | 53 +--
cpukit/score/src/rbtreeextract.c | 7 ++--
cpukit/score/src/rbtreeinsert.c | 44 --
testsuites/sptests/sprbtree01/init.c | 14 ++-
6 files changed, 76 insertions(+), 98 deletions(-)
diff --git a/cpukit/sapi/include/rtems/rbtree.h
b/cpukit/sapi/include/rtems/rbtree.h
index 0e2ea2c..900506f 100644
--- a/cpukit/sapi/include/rtems/rbtree.h
+++ b/cpukit/sapi/include/rtems/rbtree.h
@@ -195,9 +195,7 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
}
/**
- * @brief Return pointer to the parent child node from this node.
- *
- * This function returns a pointer to the parent node of @a the_node.
+ * @copydoc _RBTree_Parent()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
const rtems_rbtree_node *the_node
@@ -248,17 +246,13 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
}
/**
- * @brief Is this node the RBTree root.
- *
- * This function returns true if @a the_node is the root of @a the_rbtree and
- * false otherwise.
+ * @copydoc _RBTree_Is_root()
*/
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
- const rtems_rbtree_control *the_rbtree,
const rtems_rbtree_node *the_node
)
{
- return _RBTree_Is_root( the_rbtree, the_node );
+ return _RBTree_Is_root( the_node );
}
/**
diff --git a/cpukit/score/include/rtems/score/rbtree.h
b/cpukit/score/include/rtems/score/rbtree.h
index aa84558..299b75a 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -300,9 +300,16 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
}
/**
- * @brief Return pointer to RBTree's root node.
+ * @brief Returns a pointer to root node of the red-black tree.
*
- * This function returns a pointer to the root node of @a the_rbtree.
+ * The root node may change after insert or extract operations.
+ *
+ * @param[in] the_rbtree The red-black tree control.
+ *
+ * @retval NULL The tree is empty.
+ * @retval root The root node.
+ *
+ * @see _RBTree_Is_root().
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
const RBTree_Control *the_rbtree
@@ -326,15 +333,21 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
}
/**
- * @brief Return pointer to the parent of this node.
+ * @brief Returns a pointer to the parent of this node.
+ *
+ * The node must have a parent, thus it is invalid to use this function for the
+ * root node or a node that is not part of a tree. To test for the root node
+ * compare with _RBTree_Root() or use _RBTree_Is_root().
+ *
+ * @param[in] the_node The node of interest.
*
- * This function returns a pointer to the parent node of @a the_node.
+ * @retval parent The parent of this node.
+ * @retval undefined The node is the root node or not part of a tree.
*/
RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
const RBTree_Node *the_node
)
{
- if (!the_node->parent->parent) return NULL;
return the_node->parent;
}
@@ -409,20 +422,25 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
}
/**
- * @brief Is this node the RBTree root.
- *
- * This function returns true if @a the_node is the root of @a the_rbtree and
+ * @brief Returns true if this node is the root node of a red-black tree, and
* false otherwise.
*
- * @retval true @a the_node is the root of @a the_rbtree.
- * @retval false @a the_node is not the root of @a the_rbtree.
+ * The root node may change after insert or extract operations. In case the
+ * node is not a node of a tree, then this function yields unpredictable
+ * results.
+ *
+ * @param[in] the_node The node of interest.
+ *
+ * @retval true The node is the root node.
+ * @retval false Otherwise.
+ *
+ * @see _RBTree_Root().
*/
RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
- const RBTree_Control *the_rbtree,
- const RBTree_Node*the_node
+ const RBTree_Node *the_node
)
{
- return (the_node == _RBTree_Root(the_rbtree));
+ return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
}
/**
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h
b/cpukit/score/include/rtems/score/rbtreeimpl.h
index 451b5f4..e7d5630 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -92,56 +92,23 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_red(
}
/**
- * @brief Return a pointer to node's grandparent.
+ * @brief Returns the sibling of the node.
*
- * This function returns a pointer to the grandparent of @a the_node if it
- * exists, and NULL if not.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_
[PATCH 3/3] rbtree: Simplify _RBTree_Extract()
---
cpukit/score/src/rbtreeextract.c | 18 ++
1 file changed, 10 insertions(+), 8 deletions(-)
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index f3a7328..2be6a23 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -23,7 +23,6 @@
static void _RBTree_Extract_validate( RBTree_Node *the_node )
{
RBTree_Node *parent;
- RBTree_Direction dir;
parent = the_node->parent;
@@ -40,11 +39,13 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node
)
* update sibling pointer.
*/
if ( _RBTree_Is_red( sibling ) ) {
+ RBTree_Direction dir = the_node != parent->child[ 0 ];
+ RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
+
parent->color = RBT_RED;
sibling->color = RBT_BLACK;
- dir = the_node != parent->child[ 0 ];
_RBTree_Rotate( parent, dir );
- sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
+ sibling = parent->child[ opp_dir ];
}
/* sibling is black, see if both of its children are also black. */
@@ -66,20 +67,21 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node
)
* and if so rotate in the proper direction and update sibling pointer.
* Then switch the sibling and parent colors, and rotate through parent.
*/
- dir = the_node != parent->child[ 0 ];
+ RBTree_Direction dir = the_node != parent->child[ 0 ];
+ RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
if (
-!_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( dir ) ] )
+!_RBTree_Is_red( sibling->child[ opp_dir ] )
) {
sibling->color = RBT_RED;
sibling->child[ dir ]->color = RBT_BLACK;
-_RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) );
-sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
+_RBTree_Rotate( sibling, opp_dir );
+sibling = parent->child[ opp_dir ];
}
sibling->color = parent->color;
parent->color = RBT_BLACK;
- sibling->child[ _RBTree_Opposite_direction( dir ) ]->color = RBT_BLACK;
+ sibling->child[ opp_dir ]->color = RBT_BLACK;
_RBTree_Rotate( parent, dir );
break; /* done */
}
--
1.8.1.4
___
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
[PATCH 2/3] rbtree: Simplify _RBTree_Rotate()
---
cpukit/score/include/rtems/score/rbtreeimpl.h | 39 ---
testsuites/sptests/sprbtree01/init.c | 1 -
2 files changed, 24 insertions(+), 16 deletions(-)
diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h
b/cpukit/score/include/rtems/score/rbtreeimpl.h
index e7d5630..09e4212 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -133,32 +133,41 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
}
/**
- * @brief Rotate the_node in the direction passed as second argument.
+ * @brief Rotates the node in the specified direction.
*
* This routine rotates @a the_node to the direction @a dir, swapping
* @a the_node with its child\[@a dir\].
+ *
+ * @param[in] the_node The node to rotate.
+ * @param[in] dir The rotation direction.
*/
RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
-RBTree_Node *the_node,
-RBTree_Direction dir
-)
+ RBTree_Node *the_node,
+ RBTree_Direction dir
+)
{
- RBTree_Node *c;
- if (the_node == NULL) return;
- if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
+ RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
+ RBTree_Node *child = the_node->child[ opp_dir ];
+ RBTree_Node *grandchild;
+ RBTree_Node *parent;
+
+ if ( child == NULL)
+return;
- c = the_node->child[_RBTree_Opposite_direction(dir)];
- the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
+ grandchild = child->child[ dir ];
+ the_node->child[ opp_dir ] = grandchild;
- if (c->child[dir])
-c->child[dir]->parent = the_node;
+ if ( grandchild != NULL )
+grandchild->parent = the_node;
- c->child[dir] = the_node;
+ child->child[ dir ] = the_node;
- the_node->parent->child[the_node != the_node->parent->child[0]] = c;
+ parent = _RBTree_Parent( the_node );
+ parent->child[ the_node == parent->child[ RBT_LEFT ] ? RBT_LEFT : RBT_RIGHT ]
+= child;
- c->parent = the_node->parent;
- the_node->parent = c;
+ child->parent = parent;
+ the_node->parent = child;
}
/** @} */
diff --git a/testsuites/sptests/sprbtree01/init.c
b/testsuites/sptests/sprbtree01/init.c
index 89abdd3..6a02a53 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -858,7 +858,6 @@ rtems_task Init( rtems_task_argument ignored )
rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
- _RBTree_Rotate(NULL, RBT_LEFT);
i = (node1.Node.parent == &node2.Node);
_RBTree_Rotate( &node1.Node,
!node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT
--
1.8.1.4
___
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
Re: [GSoC] OpenRISC port | ISR_Enable/Disable and isr_level
On 7/31/2014 9:31 AM, Hesham Moustafa wrote: > On Thu, Jul 31, 2014 at 4:17 PM, Joel Sherrill > wrote: >> >> On July 31, 2014 8:54:29 AM CDT, Hesham Moustafa >> wrote: >>> Hi all, >>> >>> I was trying to figure out where to increment ISR level related >>> variables. First, I wanna indicate that the current OpenRISC port only >>> has two level of interrupts: disable/enable. Given that, does this >>> mean that the maximum interrupt level is 1? >>> >>> I noticed that there is some architectures have its own (static) >>> variable to contain isr_level, other RTEMS portable structures like >>> per_cpu structure has its own isr_level variable, and some have this >>> embedded in Context_Control. Maybe one of the previous variables are >>> just reading from an original one? If so, where it's? I assume it's >>> all read from one global/static variable which we can get directly >> >from a call to _CPU_ISR_Disable down to the architecture specific >>> function (at cpu.h?). If that's right, should _CPU_ISR_Disable (in >>> case of OpenRISC) just did the magic to disable interrupts in HW, and >>> always return 1 (or increment a static variable if interrupts are >>> already disable and do nothing in HW?) >>> _CPU_ISR_Enable in turn, should check on this level, decrements it, >>> and only do the HW magic to enable interrupts when level = 1? Please >>> correct me if I am getting this wrong. >> ISR disable and enable should not need to touch any global data or per >> thread/CPU data. They disable maskable interrupts at the CPU level. This >> usually involves a single special status register. Return the value of this >> register before disable to the caller. That value is passed to enable and >> flash. >> > So, for or1k port, should or1k_interrupt_disable (at cpu.h) just > return the value of sr (supervision/status register) before I do > disable interrupts in HW? Yes. The level returned is simply the value from the sr and is simply put back in the sr to restore the previous level. This nests nicely although we do not intend that it ever does. >>> Another question is, where/when should this variable be >>> incremented/decremented? Currently I did that from or1k/cpu.h from the >>> HW disable/enable interrupts function (which is called from >>> _ISR_[Disable|Enable]. Also, there are some architectures (like nios2) >>> increment/decrement it from the _ISR_Handler sometimes hard-coded in >>> assembly code. And of course, which variable exactly to be incremented >>> (the static one, the one at per_cpu and using macros for calculating >>> its address/offset, or where?) >>> I see also some high-level variable always incremented before every >>> call to _ISR_Enable, and decremented before _ISR_Disable. >> I think you have confused isr disable level and isr nest level. Nest level >> is part of the asm code for irqs. >> > Now I know that isr_disable_level should hold the content of the sr > register (before disabling interrupts in HW) to be used when calling > _ISR_Enable again. > So, where is isr_nest_level should be defined and touched (in > _ISR_Handler)? And for or1k, should this hold maximum value of 1 at a > given time? It is in the per cpu information structure. If you do not have interrupt levels in hardware or a driver reenables interrupts, in practice, it will always be 0 when a task is executing and always 1 when in an ISR. But that is not the general case. If interrupts are reenabled in the ISR handler or there are multiple IRQ sources and the CPU/PIC prioritizes them, then nesting IRQs is fairly routine. >>> Thanks in advance, >>> Hesham >>> ___ >>> devel mailing list >>> devel@rtems.org >>> http://lists.rtems.org/mailman/listinfo/devel >> -- >> Sent from my Android device with K-9 Mail. Please excuse my brevity. -- Joel Sherrill, Ph.D. Director of Research & Development joel.sherr...@oarcorp.comOn-Line Applications Research Ask me about RTEMS: a free RTOS Huntsville AL 35805 Support Available(256) 722-9985 ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
