posix function (read/write) unusual beavior
Hi, I have a simple loopback program in my board (bsp lpc_176x), It reads
information from a tty and returns it through the same tty (using POSIX
functions), I tested it sending characters with a PC's terminal and I saw
the ECHO on the terminal, I found an unusual behavior with some bsp
configurations, sometimes the first character that I send is returned dirty
(some extra bytes are sent), after this first dirty character the program
works well.
Example:
---
void configureUart(const int fd)
{
struct termios options;
tcgetattr(fd, &options);
//Set raw mode
cfmakeraw(&options);
tcsetattr(fd, TCSANOW, &options);
}
rtems_task Init(
rtems_task_argument ignored
)
{
const int fd = open(TTYSO, O_RDWR);
if (fd >= 0)
{
configureUart(fd);
char buffer[1u];
while (true)
{
if (read(fd, buffer, 1u) == 1u)
{
write(fd, buffer, 1u);
}
}
close(fd);
}
while(1);
}
#define CONFIGURE_APPLICATION_NEEDS_CLOCK_DRIVER
#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
#define CONFIGURE_MAXIMUM_TASKS1
#define CONFIGURE_NUMBER_OF_TERMIOS_PORTS 2
#define CONFIGURE_USE_DEVFS_AS_BASE_FILESYSTEM
#define CONFIGURE_MAXIMUM_DEVICES 5
#define CONFIGURE_LIBIO_MAXIMUM_FILE_DESCRIPTORS 4
#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
#define CONFIGURE_INIT
#define CONFIGURE_STACK_CHECKER_ENABLED
#include
---
In this example, when i press 0123456789 the output looks like:
]�\ B�\^0123456789
I said "with some configurations" because I found that if I define maximum
devices to 4 (#define CONFIGURE_MAXIMUM_DEVICES 4) it works well, but
with #define
CONFIGURE_LIBIO_MAXIMUM_FILE_DESCRIPTORS 4 and if I remove #define
CONFIGURE_STACK_CHECKER_ENABLED the problem appears again.
I don't know if I'm doing something bad or if it is a bug, Can someone help
me with that?
Thanks,
--
Gabriel Alejandro Ibarra
Software Engineer
San Lorenzo 47, 3rd Floor, Office 5
Córdoba, Argentina
Phone: +54 351 4217888
___
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
capture engine use of workspace_allocate
The capture engine currently uses a mixture of malloc and rtems_workspace_allocate. We don't think the workspace accounts for this, and would like to propose changing it so that malloc is used for all memory allocation. Does anyone see any reason this shouldn't be done? --jennifer ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Zynq BSP
On 2014-07-18 18:54, Chris Johns wrote: >> We still use the U-Boot to load it? > I do not use uboot, rather we have a taken the Xilinx FSBL and reworked it. Could you at least share this part? And thanks for this already, I thought that I had to use u-boot. (which I don't mind, it just one more layer of work ;-) ) > I would like to do a write up of the whole process but it is not a > priority for my unfunded work. :( Cheers & Thanks ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: posix function (read/write) unusual beavior
On 07/21/2014 04:42 PM, Gabriel Ibarra wrote: In this example, when i press 0123456789 the output looks like: ]�\ B�\^0123456789 I said "with some configurations" because I found that if I define maximum devices to 4 (#define CONFIGURE_MAXIMUM_DEVICES 4) it works well, but with #define CONFIGURE_LIBIO_MAXIMUM_FILE_DESCRIPTORS 4 and if I remove #define CONFIGURE_STACK_CHECKER_ENABLED the problem appears again. I don't know if I'm doing something bad or if it is a bug, Can someone help me with that? This looks like a bug. I would set a write break point to the UART data register and look who writes what to this register. -- 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
Re: capture engine use of workspace_allocate
Either account for it in workspace sizing or use malloc. On principle, I guess any dynamic allocated memory that isn't mandatory to get RTEMS to work should come from malloc. -Gedare On Mon, Jul 21, 2014 at 10:41 AM, Jennifer Averett < jennifer.aver...@oarcorp.com> wrote: > The capture engine currently uses a mixture of malloc and > > rtems_workspace_allocate. We don’t think the workspace > > accounts for this, and would like to propose changing it > > so that malloc is used for all memory allocation. Does anyone > > see any reason this shouldn’t be done? > > > > --jennifer > > ___ > devel mailing list > devel@rtems.org > http://lists.rtems.org/mailman/listinfo/devel > ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: capture engine use of workspace_allocate
On July 21, 2014 10:44:15 AM CDT, Gedare Bloom wrote: >Either account for it in workspace sizing or use malloc. > >On principle, I guess any dynamic allocated memory that isn't mandatory >to get RTEMS to work should come from malloc. With one malloc and two workspace allocates, I assumed we should use malloc for all three. This is too dynamic for the workspace IMO. > >-Gedare > > >On Mon, Jul 21, 2014 at 10:41 AM, Jennifer Averett > wrote: > >The capture engine currently uses a mixture of malloc and > >rtems_workspace_allocate. We don’t think the workspace > >accounts for this, and would like to propose changing it > >so that malloc is used for all memory allocation. Does anyone > >see any reason this shouldn’t be done? > > > >--jennifer > > >___ >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. ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
[PATCH 3/3] rbtree: Do not set node off-tree in extract
--- cpukit/score/include/rtems/score/rbtree.h | 11 +-- cpukit/score/src/rbtreeextract.c | 3 --- testsuites/sptests/sprbtree01/init.c | 5 + 3 files changed, 14 insertions(+), 5 deletions(-) diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index aa7b86e..54383aa 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -241,9 +241,16 @@ RBTree_Node *_RBTree_Insert( ); /** - * @brief Extracts (removes) @a the_node from @a the_rbtree. + * @brief Extracts (removes) the node from the red-black tree. * - * This routine extracts (removes) @a the_node from @a the_rbtree. + * This function does not set the node off-tree. In case this is desired, then + * call _RBTree_Set_off_rbtree() after the extraction. + * + * In case the node to extract is not a node of the tree, then this function + * yields unpredictable results. + * + * @param[in] the_rbtree The red-black tree control. + * @param[in] the_node The node to extract. */ void _RBTree_Extract( RBTree_Control *the_rbtree, diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 7775b2f..5a64ac4 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -201,9 +201,6 @@ void _RBTree_Extract( } } - /* Wipe the_node */ - _RBTree_Set_off_rbtree( the_node ); - /* set root to black, if it exists */ if ( the_rbtree->root ) the_rbtree->root->color = RBT_BLACK; diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index ca79095..2359fac 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -140,6 +140,9 @@ rtems_task Init( puts( "Init - Initialize rbtree empty" ); rtems_rbtree_initialize_empty( &rbtree1 ); + rtems_rbtree_set_off_rbtree( &node1.Node ); + rtems_assert( rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); + /* verify that the rbtree insert work */ puts( "INIT - Verify rtems_rbtree_insert with two nodes" ); node1.id = 1; @@ -149,6 +152,7 @@ rtems_task Init( rb_insert_unique( &rbtree1, &node1.Node ); rb_insert_unique( &rbtree1, &node2.Node ); + rtems_assert( !rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); _RBTree_Rotate(NULL, RBT_LEFT); i = (node1.Node.parent == &node2.Node); @@ -261,6 +265,7 @@ rtems_task Init( puts( "INIT - rtems_rbtree_extract failed"); rtems_test_exit(0); } + rtems_assert( !rtems_rbtree_is_node_off_rbtree( p ) ); rb_insert_unique(&rbtree1, p); for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; -- 1.8.1.4 ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
[PATCH 2/3] rbtree: Remove superfluous NULL pointer checks
---
cpukit/score/include/rtems/score/rbtree.h | 7 +++
cpukit/score/src/rbtree.c | 3 ---
cpukit/score/src/rbtreeextract.c | 10 --
cpukit/score/src/rbtreeinsert.c | 3 ---
testsuites/sptests/sprbtree01/init.c | 3 ---
5 files changed, 3 insertions(+), 23 deletions(-)
diff --git a/cpukit/score/include/rtems/score/rbtree.h
b/cpukit/score/include/rtems/score/rbtree.h
index a219a6e..aa7b86e 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -229,10 +229,9 @@ RBTree_Node *_RBTree_Find(
* @param[in] is_unique If true, then reject nodes with a duplicate key, else
* otherwise.
*
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
- * in an unique @a the_rbtree.
+ * @retval NULL Successfully inserted.
+ * @retval existing_node This is a unique insert and there exists a node with
+ * an equal key in the tree already.
*/
RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index 2138a81..064cc0c 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -34,9 +34,6 @@ void _RBTree_Initialize(
size_t count;
RBTree_Node *next;
- /* TODO: Error message? */
- if ( !the_rbtree ) return;
-
/* could do sanity checks here */
_RBTree_Initialize_empty( the_rbtree );
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 2638f63..7775b2f 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -11,7 +11,6 @@
#endif
#include
-#include
/** @brief Validate and fix-up tree properties after deleting a node
*
@@ -90,13 +89,6 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node )
the_node->color = RBT_BLACK;
}
-/** @brief Extract a Node (unprotected)
- *
- * This routine extracts (removes) @a the_node from @a the_rbtree.
- *
- * @note It does NOT disable interrupts to ensure the atomicity
- *of the extract operation.
- */
void _RBTree_Extract(
RBTree_Control *the_rbtree,
RBTree_Node*the_node
@@ -106,8 +98,6 @@ void _RBTree_Extract(
RBTree_Color victim_color;
RBTree_Direction dir;
- if ( !the_node ) return;
-
/* check if min needs to be updated */
if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
RBTree_Node *next;
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 369ef26..b31c8e7 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -11,7 +11,6 @@
#endif
#include
-#include
/** @brief Validate and fix-up tree properties for a new insert/colored node
*
@@ -67,8 +66,6 @@ RBTree_Node *_RBTree_Insert(
boolis_unique
)
{
- if ( !the_node ) return (RBTree_Node *) -1;
-
RBTree_Node *iter_node = the_rbtree->root;
if ( !iter_node ) { /* special case: first node inserted */
diff --git a/testsuites/sptests/sprbtree01/init.c
b/testsuites/sptests/sprbtree01/init.c
index acf7f68..ca79095 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -149,9 +149,6 @@ rtems_task Init(
rb_insert_unique( &rbtree1, &node1.Node );
rb_insert_unique( &rbtree1, &node2.Node );
- p = rb_insert_unique( &rbtree1, NULL );
- if (p != (void *)(-1))
-puts( "INIT - FAILED NULL NODE INSERT" );
_RBTree_Rotate(NULL, RBT_LEFT);
i = (node1.Node.parent == &node2.Node);
--
1.8.1.4
___
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
[PATCH 1/3] rbtree: Format
---
cpukit/score/src/rbtree.c| 7 +-
cpukit/score/src/rbtreeextract.c | 152 +--
cpukit/score/src/rbtreefind.c| 7 +-
cpukit/score/src/rbtreeinsert.c | 69 ++
cpukit/score/src/rbtreeiterate.c | 12 ++--
cpukit/score/src/rbtreenext.c| 13 ++--
6 files changed, 143 insertions(+), 117 deletions(-)
diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
index 5e8520d..2138a81 100644
--- a/cpukit/score/src/rbtree.c
+++ b/cpukit/score/src/rbtree.c
@@ -31,17 +31,18 @@ void _RBTree_Initialize(
boolis_unique
)
{
- size_t count;
+ size_t count;
RBTree_Node *next;
/* TODO: Error message? */
- if (!the_rbtree) return;
+ if ( !the_rbtree ) return;
/* could do sanity checks here */
_RBTree_Initialize_empty( the_rbtree );
count = number_nodes;
- next = starting_address;
+ next = starting_address;
+
while ( count-- ) {
_RBTree_Insert( the_rbtree, next, compare, is_unique );
next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 9e87868..2638f63 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -21,45 +21,45 @@
* @note It does NOT disable interrupts to ensure the atomicity
*of the extract operation.
*/
-static void _RBTree_Extract_validate(
-RBTree_Node *the_node
-)
+static void _RBTree_Extract_validate( RBTree_Node *the_node )
{
- RBTree_Node *parent, *sibling;
+ RBTree_Node *parent, *sibling;
RBTree_Direction dir;
parent = the_node->parent;
- if(!parent->parent) return;
- sibling = _RBTree_Sibling(the_node);
+ if ( !parent->parent ) return;
- /* continue to correct tree as long as the_node is black and not the root */
- while (!_RBTree_Is_red(the_node) && parent->parent) {
+ sibling = _RBTree_Sibling( the_node );
+ /* continue to correct tree as long as the_node is black and not the root */
+ while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
/* if sibling is red, switch parent (black) and sibling colors,
* then rotate parent left, making the sibling be the_node's grandparent.
* Now the_node has a black sibling and red parent. After rotation,
* update sibling pointer.
*/
-if (_RBTree_Is_red(sibling)) {
+if ( _RBTree_Is_red( sibling ) ) {
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)];
+ dir = the_node != parent->child[ 0 ];
+ _RBTree_Rotate( parent, dir );
+ sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
}
/* sibling is black, see if both of its children are also black. */
-if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) &&
-!_RBTree_Is_red(sibling->child[RBT_LEFT])) {
-sibling->color = RBT_RED;
-if (_RBTree_Is_red(parent)) {
- parent->color = RBT_BLACK;
- break;
-}
-the_node = parent; /* done if parent is red */
-parent = the_node->parent;
-sibling = _RBTree_Sibling(the_node);
+if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
+ !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
+ sibling->color = RBT_RED;
+
+ if ( _RBTree_Is_red( parent ) ) {
+parent->color = RBT_BLACK;
+break;
+ }
+
+ the_node = parent; /* done if parent is red */
+ parent = the_node->parent;
+ sibling = _RBTree_Sibling( the_node );
} else {
/* at least one of sibling's children is red. we now proceed in two
* cases, either the_node is to the left or the right of the parent.
@@ -67,21 +67,27 @@ static void _RBTree_Extract_validate(
* 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];
- if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) {
+ dir = the_node != parent->child[ 0 ];
+
+ if (
+!_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( 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)];
+sibling->child[ dir ]->color = RBT_BLACK;
+_RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) );
+sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
}
+
sibling->color = parent->color;
parent->color = RBT_BLACK;
- sibling->child[_RBTree_Opposite_direction(dir)]->color = RBT_BLACK;
- _RBTree_Rotate(parent, dir);
+ sibling->child[ _RBTree_Opposite_direction( d
Re: [PATCH 1/3] rbtree: Format
There could be something wrong here but I don't see it on a quick review.
On 7/21/2014 11:31 AM, Sebastian Huber wrote:
> ---
> cpukit/score/src/rbtree.c| 7 +-
> cpukit/score/src/rbtreeextract.c | 152
> +--
> cpukit/score/src/rbtreefind.c| 7 +-
> cpukit/score/src/rbtreeinsert.c | 69 ++
> cpukit/score/src/rbtreeiterate.c | 12 ++--
> cpukit/score/src/rbtreenext.c| 13 ++--
> 6 files changed, 143 insertions(+), 117 deletions(-)
>
> diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> index 5e8520d..2138a81 100644
> --- a/cpukit/score/src/rbtree.c
> +++ b/cpukit/score/src/rbtree.c
> @@ -31,17 +31,18 @@ void _RBTree_Initialize(
>boolis_unique
> )
> {
> - size_t count;
> + size_t count;
>RBTree_Node *next;
>
>/* TODO: Error message? */
> - if (!the_rbtree) return;
> + if ( !the_rbtree ) return;
>
>/* could do sanity checks here */
>_RBTree_Initialize_empty( the_rbtree );
>
>count = number_nodes;
> - next = starting_address;
> + next = starting_address;
> +
>while ( count-- ) {
> _RBTree_Insert( the_rbtree, next, compare, is_unique );
> next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
> diff --git a/cpukit/score/src/rbtreeextract.c
> b/cpukit/score/src/rbtreeextract.c
> index 9e87868..2638f63 100644
> --- a/cpukit/score/src/rbtreeextract.c
> +++ b/cpukit/score/src/rbtreeextract.c
> @@ -21,45 +21,45 @@
> * @note It does NOT disable interrupts to ensure the atomicity
> *of the extract operation.
> */
> -static void _RBTree_Extract_validate(
> -RBTree_Node *the_node
> -)
> +static void _RBTree_Extract_validate( RBTree_Node *the_node )
> {
> - RBTree_Node *parent, *sibling;
> + RBTree_Node *parent, *sibling;
>RBTree_Direction dir;
>
>parent = the_node->parent;
> - if(!parent->parent) return;
>
> - sibling = _RBTree_Sibling(the_node);
> + if ( !parent->parent ) return;
>
> - /* continue to correct tree as long as the_node is black and not the root
> */
> - while (!_RBTree_Is_red(the_node) && parent->parent) {
> + sibling = _RBTree_Sibling( the_node );
>
> + /* continue to correct tree as long as the_node is black and not the root
> */
> + while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
> /* if sibling is red, switch parent (black) and sibling colors,
> * then rotate parent left, making the sibling be the_node's grandparent.
> * Now the_node has a black sibling and red parent. After rotation,
> * update sibling pointer.
> */
> -if (_RBTree_Is_red(sibling)) {
> +if ( _RBTree_Is_red( sibling ) ) {
>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)];
> + dir = the_node != parent->child[ 0 ];
> + _RBTree_Rotate( parent, dir );
> + sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
> }
>
> /* sibling is black, see if both of its children are also black. */
> -if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) &&
> -!_RBTree_Is_red(sibling->child[RBT_LEFT])) {
> -sibling->color = RBT_RED;
> -if (_RBTree_Is_red(parent)) {
> - parent->color = RBT_BLACK;
> - break;
> -}
> -the_node = parent; /* done if parent is red */
> -parent = the_node->parent;
> -sibling = _RBTree_Sibling(the_node);
> +if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
> + !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
> + sibling->color = RBT_RED;
> +
> + if ( _RBTree_Is_red( parent ) ) {
> +parent->color = RBT_BLACK;
> +break;
> + }
> +
> + the_node = parent; /* done if parent is red */
> + parent = the_node->parent;
> + sibling = _RBTree_Sibling( the_node );
> } else {
>/* at least one of sibling's children is red. we now proceed in two
> * cases, either the_node is to the left or the right of the parent.
> @@ -67,21 +67,27 @@ static void _RBTree_Extract_validate(
> * 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];
> - if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) {
> + dir = the_node != parent->child[ 0 ];
> +
> + if (
> +!_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( 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)];
> +sibling->child[ dir ]->color = RBT_BLACK;
> +_RBTree_Rot
Re: [PATCH 2/3] rbtree: Remove superfluous NULL pointer checks
One comment inline.
On 7/21/2014 11:31 AM, Sebastian Huber wrote:
> ---
> cpukit/score/include/rtems/score/rbtree.h | 7 +++
> cpukit/score/src/rbtree.c | 3 ---
> cpukit/score/src/rbtreeextract.c | 10 --
> cpukit/score/src/rbtreeinsert.c | 3 ---
> testsuites/sptests/sprbtree01/init.c | 3 ---
> 5 files changed, 3 insertions(+), 23 deletions(-)
>
> diff --git a/cpukit/score/include/rtems/score/rbtree.h
> b/cpukit/score/include/rtems/score/rbtree.h
> index a219a6e..aa7b86e 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -229,10 +229,9 @@ RBTree_Node *_RBTree_Find(
> * @param[in] is_unique If true, then reject nodes with a duplicate key, else
> * otherwise.
> *
> - * @retval 0 Successfully inserted.
> - * @retval -1 NULL @a the_node.
> - * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
> - * in an unique @a the_rbtree.
> + * @retval NULL Successfully inserted.
> + * @retval existing_node This is a unique insert and there exists a node with
> + * an equal key in the tree already.
> */
> RBTree_Node *_RBTree_Insert(
>RBTree_Control *the_rbtree,
> diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> index 2138a81..064cc0c 100644
> --- a/cpukit/score/src/rbtree.c
> +++ b/cpukit/score/src/rbtree.c
> @@ -34,9 +34,6 @@ void _RBTree_Initialize(
>size_t count;
>RBTree_Node *next;
>
> - /* TODO: Error message? */
> - if ( !the_rbtree ) return;
> -
>/* could do sanity checks here */
>_RBTree_Initialize_empty( the_rbtree );
>
> diff --git a/cpukit/score/src/rbtreeextract.c
> b/cpukit/score/src/rbtreeextract.c
> index 2638f63..7775b2f 100644
> --- a/cpukit/score/src/rbtreeextract.c
> +++ b/cpukit/score/src/rbtreeextract.c
> @@ -11,7 +11,6 @@
> #endif
>
> #include
> -#include
>
> /** @brief Validate and fix-up tree properties after deleting a node
> *
> @@ -90,13 +89,6 @@ static void _RBTree_Extract_validate( RBTree_Node
> *the_node )
> the_node->color = RBT_BLACK;
> }
>
> -/** @brief Extract a Node (unprotected)
> - *
> - * This routine extracts (removes) @a the_node from @a the_rbtree.
> - *
> - * @note It does NOT disable interrupts to ensure the atomicity
> - *of the extract operation.
> - */
Is it assumed that all RBTree operations are unprotected?
If so, should this be in the Doxygen group description. If not, then this
comment is meaningful and should be in the .h.
> void _RBTree_Extract(
>RBTree_Control *the_rbtree,
>RBTree_Node*the_node
> @@ -106,8 +98,6 @@ void _RBTree_Extract(
>RBTree_Color victim_color;
>RBTree_Direction dir;
>
> - if ( !the_node ) return;
> -
>/* check if min needs to be updated */
>if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
> RBTree_Node *next;
> diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
> index 369ef26..b31c8e7 100644
> --- a/cpukit/score/src/rbtreeinsert.c
> +++ b/cpukit/score/src/rbtreeinsert.c
> @@ -11,7 +11,6 @@
> #endif
>
> #include
> -#include
>
> /** @brief Validate and fix-up tree properties for a new insert/colored node
> *
> @@ -67,8 +66,6 @@ RBTree_Node *_RBTree_Insert(
>boolis_unique
> )
> {
> - if ( !the_node ) return (RBTree_Node *) -1;
> -
>RBTree_Node *iter_node = the_rbtree->root;
>
>if ( !iter_node ) { /* special case: first node inserted */
> diff --git a/testsuites/sptests/sprbtree01/init.c
> b/testsuites/sptests/sprbtree01/init.c
> index acf7f68..ca79095 100644
> --- a/testsuites/sptests/sprbtree01/init.c
> +++ b/testsuites/sptests/sprbtree01/init.c
> @@ -149,9 +149,6 @@ rtems_task Init(
>rb_insert_unique( &rbtree1, &node1.Node );
>rb_insert_unique( &rbtree1, &node2.Node );
>
> - p = rb_insert_unique( &rbtree1, NULL );
> - if (p != (void *)(-1))
> -puts( "INIT - FAILED NULL NODE INSERT" );
>
>_RBTree_Rotate(NULL, RBT_LEFT);
>i = (node1.Node.parent == &node2.Node);
--
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
Re: [PATCH 3/3] rbtree: Do not set node off-tree in extract
Unless the chain has changed to have the property of "dangerous to extract if not on", this should be OK. My thinking is that higher level code would be checking a state of some sort and know whether to extract from the underlying chain or rbtree container. Is this true? If so, this looks OK. On 7/21/2014 11:31 AM, Sebastian Huber wrote: > --- > cpukit/score/include/rtems/score/rbtree.h | 11 +-- > cpukit/score/src/rbtreeextract.c | 3 --- > testsuites/sptests/sprbtree01/init.c | 5 + > 3 files changed, 14 insertions(+), 5 deletions(-) > > diff --git a/cpukit/score/include/rtems/score/rbtree.h > b/cpukit/score/include/rtems/score/rbtree.h > index aa7b86e..54383aa 100644 > --- a/cpukit/score/include/rtems/score/rbtree.h > +++ b/cpukit/score/include/rtems/score/rbtree.h > @@ -241,9 +241,16 @@ RBTree_Node *_RBTree_Insert( > ); > > /** > - * @brief Extracts (removes) @a the_node from @a the_rbtree. > + * @brief Extracts (removes) the node from the red-black tree. > * > - * This routine extracts (removes) @a the_node from @a the_rbtree. > + * This function does not set the node off-tree. In case this is desired, > then > + * call _RBTree_Set_off_rbtree() after the extraction. > + * > + * In case the node to extract is not a node of the tree, then this function > + * yields unpredictable results. > + * > + * @param[in] the_rbtree The red-black tree control. > + * @param[in] the_node The node to extract. > */ > void _RBTree_Extract( >RBTree_Control *the_rbtree, > diff --git a/cpukit/score/src/rbtreeextract.c > b/cpukit/score/src/rbtreeextract.c > index 7775b2f..5a64ac4 100644 > --- a/cpukit/score/src/rbtreeextract.c > +++ b/cpukit/score/src/rbtreeextract.c > @@ -201,9 +201,6 @@ void _RBTree_Extract( > } >} > > - /* Wipe the_node */ > - _RBTree_Set_off_rbtree( the_node ); > - >/* set root to black, if it exists */ >if ( the_rbtree->root ) > the_rbtree->root->color = RBT_BLACK; > diff --git a/testsuites/sptests/sprbtree01/init.c > b/testsuites/sptests/sprbtree01/init.c > index ca79095..2359fac 100644 > --- a/testsuites/sptests/sprbtree01/init.c > +++ b/testsuites/sptests/sprbtree01/init.c > @@ -140,6 +140,9 @@ rtems_task Init( >puts( "Init - Initialize rbtree empty" ); >rtems_rbtree_initialize_empty( &rbtree1 ); > > + rtems_rbtree_set_off_rbtree( &node1.Node ); > + rtems_assert( rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); > + >/* verify that the rbtree insert work */ >puts( "INIT - Verify rtems_rbtree_insert with two nodes" ); >node1.id = 1; > @@ -149,6 +152,7 @@ rtems_task Init( >rb_insert_unique( &rbtree1, &node1.Node ); >rb_insert_unique( &rbtree1, &node2.Node ); > > + rtems_assert( !rtems_rbtree_is_node_off_rbtree( &node1.Node ) ); > >_RBTree_Rotate(NULL, RBT_LEFT); >i = (node1.Node.parent == &node2.Node); > @@ -261,6 +265,7 @@ rtems_task Init( > puts( "INIT - rtems_rbtree_extract failed"); > rtems_test_exit(0); >} > + rtems_assert( !rtems_rbtree_is_node_off_rbtree( p ) ); >rb_insert_unique(&rbtree1, p); > >for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; -- 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
Re: [PATCH 2/3] rbtree: Remove superfluous NULL pointer checks
On 07/21/2014 06:59 PM, Joel Sherrill wrote: -/** @brief Extract a Node (unprotected) >- * >- * This routine extracts (removes) @a the_node from @a the_rbtree. >- * >- * @note It does NOT disable interrupts to ensure the atomicity >- *of the extract operation. >- */ Is it assumed that all RBTree operations are unprotected? Yes, all operations are unprotected. -- 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
Re: [PATCH 3/3] rbtree: Do not set node off-tree in extract
On 07/21/2014 07:23 PM, Joel Sherrill wrote: Unless the chain has changed to have the property of "dangerous to extract if not on", this should be OK. My thinking is that higher level code would be checking a state of some sort and know whether to extract from the underlying chain or rbtree container. Is this true? If so, this looks OK. Yes, this is analogous to the chains. The lowest level implementation should not do consistency checks (except via _Assert()). -- 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
Re: [PATCH 2/3] rbtree: Remove superfluous NULL pointer checks
On 7/21/2014 12:52 PM, Sebastian Huber wrote: > On 07/21/2014 06:59 PM, Joel Sherrill wrote: >>> -/** @brief Extract a Node (unprotected) - * - * This routine extracts (removes) @a the_node from @a the_rbtree. - * - * @note It does NOT disable interrupts to ensure the atomicity - *of the extract operation. - */ >> Is it assumed that all RBTree operations are unprotected? > Yes, all operations are unprotected. > Should this be noted in the Doxygen group documentation? I don't know that I care. Just trying to make sure we capture what we should. -- 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
Re: [PATCH 3/3] rbtree: Do not set node off-tree in extract
On 7/21/2014 12:54 PM, Sebastian Huber wrote: > On 07/21/2014 07:23 PM, Joel Sherrill wrote: >> Unless the chain has changed to have the property of >> "dangerous to extract if not on", this should be OK. >> >> My thinking is that higher level code would be checking a state >> of some sort and know whether to extract from the underlying >> chain or rbtree container. >> >> Is this true? If so, this looks OK. > Yes, this is analogous to the chains. The lowest level implementation > should not do consistency checks (except via _Assert()). > Thanks. Then OK. -- 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
[PATCH v2] RTEMS: Add multilibs for ARM
This change is necessary to support Cortex-M4 and Cortex-R based chips in RTEMS. This patch should be applied to GCC 4.8, 4.9 and mainline. I do not have write access, so in case this gets approved, please commit it for me. gcc/ChangeLog 2014-07-21 Sebastian Huber * config/arm/t-rtems-eabi: Add mthumb/march=armv7-r/mfpu=vfpv3-d16/mfloat-abi=hard, mthumb/march=armv7-m/mfpu=fpv4-sp-d16/mfloat-abi=hard, mbig-endian/mthumb/march=armv7-r, and mbig-endian/mthumb/march=armv7-r/mfpu=vfpv3-d16/mfloat-abi=hard multilibs. --- gcc/config/arm/t-rtems-eabi | 124 +++- 1 file changed, 122 insertions(+), 2 deletions(-) diff --git a/gcc/config/arm/t-rtems-eabi b/gcc/config/arm/t-rtems-eabi index d81fbf7..92c4dcb 100644 --- a/gcc/config/arm/t-rtems-eabi +++ b/gcc/config/arm/t-rtems-eabi @@ -1,47 +1,167 @@ # Custom RTEMS EABI multilibs -MULTILIB_OPTIONS = mthumb march=armv6-m/march=armv7-a/march=armv7-r/march=armv7-m mfpu=neon mfloat-abi=hard -MULTILIB_DIRNAMES = thumb armv6-m armv7-a armv7-r armv7-m neon hard +MULTILIB_OPTIONS = mbig-endian mthumb march=armv6-m/march=armv7-a/march=armv7-r/march=armv7-m mfpu=neon/mfpu=vfpv3-d16/mfpu=fpv4-sp-d16 mfloat-abi=hard +MULTILIB_DIRNAMES = eb thumb armv6-m armv7-a armv7-r armv7-m neon vfpv3-d16 fpv4-sp-d16 hard # Enumeration of multilibs MULTILIB_EXCEPTIONS = +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=neon +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv6-m +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=neon +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-a +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=neon +# MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r/mfloat-abi=hard +# MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-r +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=neon +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/march=armv7-m +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=neon +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/mthumb/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/mthumb +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=neon +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=vfpv3-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=vfpv3-d16 +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=fpv4-sp-d16/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfpu=fpv4-sp-d16 +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endian/march=armv6-m +MULTILIB_EXCEPTIONS += mbig-endian/march=armv7-a/mfpu=neon/mfloat-abi=hard +MULTILIB_EXCEPTIONS += mbig-endia
Re: [PATCH 1/3] rbtree: Format
One issue with rbtree formatting is in some places if/while conditional
expressions are put on the same line as the conditional statement. We
should prefer to put them explicitly on separate lines, since that is the
prevailing style of score and I have added such a convention to our style
wiki page.
On Mon, Jul 21, 2014 at 12:57 PM, Joel Sherrill
wrote:
> There could be something wrong here but I don't see it on a quick review.
> On 7/21/2014 11:31 AM, Sebastian Huber wrote:
> > ---
> > cpukit/score/src/rbtree.c| 7 +-
> > cpukit/score/src/rbtreeextract.c | 152
> +--
> > cpukit/score/src/rbtreefind.c| 7 +-
> > cpukit/score/src/rbtreeinsert.c | 69 ++
> > cpukit/score/src/rbtreeiterate.c | 12 ++--
> > cpukit/score/src/rbtreenext.c| 13 ++--
> > 6 files changed, 143 insertions(+), 117 deletions(-)
> >
> > diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> > index 5e8520d..2138a81 100644
> > --- a/cpukit/score/src/rbtree.c
> > +++ b/cpukit/score/src/rbtree.c
> > @@ -31,17 +31,18 @@ void _RBTree_Initialize(
> >boolis_unique
> > )
> > {
> > - size_t count;
> > + size_t count;
> >RBTree_Node *next;
> >
> >/* TODO: Error message? */
> > - if (!the_rbtree) return;
> > + if ( !the_rbtree ) return;
>
Like here.
> >
> >/* could do sanity checks here */
> >_RBTree_Initialize_empty( the_rbtree );
> >
> >count = number_nodes;
> > - next = starting_address;
> > + next = starting_address;
> > +
> >while ( count-- ) {
> > _RBTree_Insert( the_rbtree, next, compare, is_unique );
> > next = (RBTree_Node *) _Addresses_Add_offset( next, node_size );
> > diff --git a/cpukit/score/src/rbtreeextract.c
> b/cpukit/score/src/rbtreeextract.c
> > index 9e87868..2638f63 100644
> > --- a/cpukit/score/src/rbtreeextract.c
> > +++ b/cpukit/score/src/rbtreeextract.c
> > @@ -21,45 +21,45 @@
> > * @note It does NOT disable interrupts to ensure the atomicity
> > *of the extract operation.
> > */
> > -static void _RBTree_Extract_validate(
> > -RBTree_Node *the_node
> > -)
> > +static void _RBTree_Extract_validate( RBTree_Node *the_node )
> > {
> > - RBTree_Node *parent, *sibling;
> > + RBTree_Node *parent, *sibling;
> >RBTree_Direction dir;
> >
> >parent = the_node->parent;
> > - if(!parent->parent) return;
> >
> > - sibling = _RBTree_Sibling(the_node);
> > + if ( !parent->parent ) return;
> >
> > - /* continue to correct tree as long as the_node is black and not the
> root */
> > - while (!_RBTree_Is_red(the_node) && parent->parent) {
> > + sibling = _RBTree_Sibling( the_node );
> >
> > + /* continue to correct tree as long as the_node is black and not the
> root */
> > + while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
> > /* if sibling is red, switch parent (black) and sibling colors,
> > * then rotate parent left, making the sibling be the_node's
> grandparent.
> > * Now the_node has a black sibling and red parent. After rotation,
> > * update sibling pointer.
> > */
> > -if (_RBTree_Is_red(sibling)) {
> > +if ( _RBTree_Is_red( sibling ) ) {
> >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)];
> > + dir = the_node != parent->child[ 0 ];
> > + _RBTree_Rotate( parent, dir );
> > + sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
> > }
> >
> > /* sibling is black, see if both of its children are also black. */
> > -if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) &&
> > -!_RBTree_Is_red(sibling->child[RBT_LEFT])) {
> > -sibling->color = RBT_RED;
> > -if (_RBTree_Is_red(parent)) {
> > - parent->color = RBT_BLACK;
> > - break;
> > -}
> > -the_node = parent; /* done if parent is red */
> > -parent = the_node->parent;
> > -sibling = _RBTree_Sibling(the_node);
> > +if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
> > + !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
> > + sibling->color = RBT_RED;
> > +
> > + if ( _RBTree_Is_red( parent ) ) {
> > +parent->color = RBT_BLACK;
> > +break;
> > + }
> > +
> > + the_node = parent; /* done if parent is red */
> > + parent = the_node->parent;
> > + sibling = _RBTree_Sibling( the_node );
> > } else {
> >/* at least one of sibling's children is red. we now proceed in
> two
> > * cases, either the_node is to the left or the right of the
> parent.
> > @@ -67,21 +67,27 @@ static void _RBTree_Extract_validate(
> > * and if so rotate in the proper direction and update sibling
> pointer.
> > * Then switch the sibling and parent colors, and rotate through
> parent.
>
