[PATCH 02/27] score: Add red-black tree append/prepend

[Sebastian Huber]

On 20/11/2021 19:36, Gedare Bloom wrote:
>> +void _RBTree_Append( RBTree_Control *the_rbtree, RBTree_Node *the_node )
>> +{
>> +  RBTree_Node **link;
>> +  RBTree_Node  *parent;
>> +
>> +  link = _RBTree_Root_reference( the_rbtree );
>> +  parent = NULL;
>> +
>> +  while ( *link != NULL ) {
>> +    parent = *link;
>> +    link = _RBTree_Right_reference( parent );
>> +  }
>> +
>> +  _RBTree_Add_child( the_node, parent, link );
>> +  _RBTree_Insert_color( the_rbtree, the_node );
>> +}
> Can this be simplified?
> RBTree_Node *p = _RBTree_Maximum( the_rbtree );
> RBTree_Insert_with_parent( the_rbtree, the_node, p,
> _RBTree_Right_reference( p ) );

 From a high level point of view, yes. However, the _RBTree_Maximum() 
needs a function call and the proposed approach allows a tail call 
optimization. For example on ARM we have:

         .type   _RBTree_Append, %function
_RBTree_Append:
         @ args = 0, pretend = 0, frame = 0
         @ frame_needed = 0, uses_anonymous_args = 0
         @ link register save eliminated.
         ldr     r3, [r0]
         cbz     r3, .L2
.L3:
         mov     r2, r3
         ldr     r3, [r3, #4]
         cmp     r3, #0
         bne     .L3
         add     ip, r2, #4
.L4:
         movs    r3, #0
         strd    r3, r2, [r1, #4]
         str     r3, [r1]
         movs    r3, #1
         str     r3, [r1, #12]
         str     r1, [ip]
         b       _RBTree_Insert_color
.L2:
         mov     ip, r0
         mov     r2, r3
         b       .L4
         .size   _RBTree_Append, .-_RBTree_Append
         .ident  "GCC: (GNU) 10.3.1 20210409 (RTEMS 6, RSB 
a1f7b3b60e5c532a46e728c8606d2fe5bcb3a562, Newlib 4f81149)"


-- 
embedded brains GmbH
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: sebastian.huber at embedded-brains.de
phone: +49-89-18 94 741 - 16
fax:   +49-89-18 94 741 - 08

Registergericht: Amtsgericht München
Registernummer: HRB 157899
Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
Unsere Datenschutzerklärung finden Sie hier:
https://embedded-brains.de/datenschutzerklaerung/