| Commit message (Collapse) | Author | Files | Lines |
|---|
|
Use the BSD <sys/tree.h> implementation since it is faster, more
flexible and uses less storage. See https://github.com/sebhub/rb-bench.
|
|
|
|
|
|
|
|
The user of the red-black tree container must now ensure that at most
one thread at once can access an instance.
|
|
Move implementation specific parts of rbtree.h and rbtree.inl into new
header file rbtreeimpl.h. The rbtree.h contains now only the
application visible API.
|
|
The implementation of RBTree_Next was using an awkward construction to detect
and avoid accessing the false root of the red-black tree. To deal with the
false root, RBTree_Next was comparing node parents with the control node.
Instead the false root can be detected by checking if the grandparent of a
node exists; the grandparent of the tree's true root is NULL by definition
so the root of the tree is found while walking up the tree by checking for
the non-existence of a grandparent.
This change propagates into the predecessor/successor and iterate functions.
|
|
New functions
o _RBTree_Next_unprotected(),
o _RBTree_Next(),
o _RBTree_Successor_unprotected(),
o _RBTree_Predecessor_unprotected(),
o rtems_rbtree_successor_unprotected(), and
o rtems_rbtree_predecessor_unprotected().
Change prototype of
o _RBTree_Successor(),
o _RBTree_Predecessor(),
o rtems_rbtree_successor(), and
o rtems_rbtree_predecessor().
|
