#2354 closed enhancement (fixed)

Replace red-black tree implementation, change API

Reported by: Sebastian Huber Owned by:
Priority: normal Milestone: 5.1
Component: unspecified Version:
Severity: normal Keywords:
Cc: Blocked By:
Blocking:

Description

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.

Change History (3)

comment:1 Changed on Aug 14, 2017 at 12:05:18 AM by Chris Johns

Milestone: 5.0Indefinite
Version: 4.11

comment:2 Changed on Aug 21, 2017 at 5:21:29 AM by Sebastian Huber

Milestone: Indefinite4.12.0
Resolution: fixed
Status: newclosed

comment:3 Changed on Nov 9, 2017 at 6:27:14 AM by Sebastian Huber

Milestone: 4.12.05.1

Milestone renamed

Note: See TracTickets for help on using tickets.