[RTEMS Project] #2354: Replace red-black tree implementation, change API

RTEMS trac trac at rtems.org
Thu May 28 09:39:15 UTC 2015


#2354: Replace red-black tree implementation, change API
-----------------------------+------------------
 Reporter:  sebastian.huber  |      Owner:
     Type:  enhancement      |     Status:  new
 Priority:  normal           |  Milestone:  5.0
Component:  General          |    Version:  4.11
 Severity:  normal           |   Keywords:
-----------------------------+------------------
 The RTEMS red-black tree implementation is not as good as the BSD
 implementation which performs quite well in a benchmark:

 https://github.com/sebhub/rb-bench

 Proposal:

 https://github.com/sebhub/rb-bench/blob/master/test-rbtree-bsd-for-rtems.c

 One benefit is that the search/insert is done inline and the red-black
 tree fixup is done in a general purpose _BSD_RBTree_Insert_color()
 function (similar to the Linux red-black tree API).

 This makes it possible to get rid of the red-black tree implementation
 used by the JFFS2 support.

--
Ticket URL: <http://devel.rtems.org/ticket/2354>
RTEMS Project <http://www.rtems.org/>
RTEMS Project


More information about the bugs mailing list