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.hu...@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/
_______________________________________________
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
