diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2018-06-29 20:00:28 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2018-07-16 07:22:06 +0200 |
commit | 6539beab824d4b9718fc0ea841791caacb8ac02f (patch) | |
tree | ce0b51e7146fc7ebfd0ee1d983fa59f8f240b6a7 /cpukit/score | |
parent | x86_64/console: Add NS16550 polled console driver (diff) | |
download | rtems-6539beab824d4b9718fc0ea841791caacb8ac02f.tar.bz2 |
score: Add postorder tree iteration support
Update #3465.
Diffstat (limited to '')
-rw-r--r-- | cpukit/score/Makefile.am | 1 | ||||
-rw-r--r-- | cpukit/score/src/rbtreepostorder.c | 81 |
2 files changed, 82 insertions, 0 deletions
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index b7ce16c299..e345f77daa 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -157,6 +157,7 @@ libscore_a_SOURCES += src/freechain.c libscore_a_SOURCES += \ src/rbtreeextract.c \ src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c +libscore_a_SOURCES += src/rbtreepostorder.c libscore_a_SOURCES += src/rbtreereplace.c ## THREAD_C_FILES diff --git a/cpukit/score/src/rbtreepostorder.c b/cpukit/score/src/rbtreepostorder.c new file mode 100644 index 0000000000..26555c8848 --- /dev/null +++ b/cpukit/score/src/rbtreepostorder.c @@ -0,0 +1,81 @@ +/** + * @file + * + * @ingroup ScoreRBTree + * + * @brief _RBTree_Postorder_first() and _RBTree_Postorder_next() + * implementation. + */ + +/* + * Copyright (c) 2018 embedded brains GmbH. All rights reserved. + * + * embedded brains GmbH + * Dornierstr. 4 + * 82178 Puchheim + * Germany + * <rtems@embedded-brains.de> + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. + */ + +#if HAVE_CONFIG_H +#include "config.h" +#endif + +#include <rtems/score/rbtree.h> + +static void *_RBTree_Postorder_dive_left( + const RBTree_Node *the_node, + size_t offset +) +{ + while ( true ) { + if ( _RBTree_Left( the_node ) != NULL ) { + the_node = _RBTree_Left( the_node ); + } else if ( _RBTree_Right( the_node ) != NULL ) { + the_node = _RBTree_Right( the_node ); + } else { + return (void *) ( (uintptr_t) the_node - offset ); + } + } +} + +void *_RBTree_Postorder_next( + const RBTree_Node *the_node, + size_t offset +) +{ + const RBTree_Node *parent; + + parent = _RBTree_Parent( the_node ); + if ( parent == NULL ) { + return NULL; + } + + if ( + the_node == _RBTree_Left( parent ) + && _RBTree_Right( parent ) != NULL + ) { + return _RBTree_Postorder_dive_left( _RBTree_Right( parent ), offset ); + } + + return (void *) ( (uintptr_t) parent - offset ); +} + +void *_RBTree_Postorder_first( + const RBTree_Control *the_rbtree, + size_t offset +) +{ + const RBTree_Node *the_node; + + the_node = _RBTree_Root( the_rbtree ); + if ( the_node == NULL ) { + return NULL; + } + + return _RBTree_Postorder_dive_left( the_node, offset ); +} |