Opened on Jul 28, 2010 at 3:01:26 PM

Closed on Apr 4, 2011 at 5:49:05 PM

#1641 closed defect (fixed)

Red Black Tree data structure

Reported by: Gedare Bloom Owned by: Joel Sherrill
Priority: normal Milestone: 4.11
Component: score Version: 4.11
Severity: normal Keywords:
Cc: chrisj@…, sebastian.huber@… Blocked By:
Blocking:

Description

This PR introduces a red-black tree to the supercore. The red-black tree also has a public interface exported via sapi, similar to the chain data structure.

A new sptest is provided that uses the red-black tree. I have not verified that the test case covers the implementation.

The red-black tree will be used in an upcoming implementation of earliest deadline first scheduling.

Attachments (6)

rtems-cvs.diff​ (7.4 KB) - added by Gedare Bloom on Jul 28, 2010 at 3:02:42 PM.
Patch for red black tree.
rtems.tgz​ (12.1 KB) - added by Gedare Bloom on Jul 28, 2010 at 3:03:44 PM.
New files.
ChangeLog​ (516 bytes) - added by Gedare Bloom on Jul 28, 2010 at 3:04:05 PM.
cpukit/ChangeLog
ChangeLog_v1​ (242 bytes) - added by Gedare Bloom on Jul 28, 2010 at 3:06:45 PM.
testsuites/sptests/ChangeLog
rtems_v1.tgz​ (12.0 KB) - added by Gedare Bloom on Sep 21, 2010 at 5:48:56 PM.
New files.
rtems-cvs_v1.diff​ (7.3 KB) - added by Gedare Bloom on Dec 9, 2010 at 1:37:51 AM.
Patch for red black tree.

Download all attachments as: .zip

Change History (12)

Changed on Jul 28, 2010 at 3:02:42 PM by Gedare Bloom

Attachment: rtems-cvs.diff​ added

Patch for red black tree.

Changed on Jul 28, 2010 at 3:03:44 PM by Gedare Bloom

Attachment: rtems.tgz​ added

New files.

Changed on Jul 28, 2010 at 3:04:05 PM by Gedare Bloom

Attachment: ChangeLog​ added

cpukit/ChangeLog

Changed on Jul 28, 2010 at 3:06:45 PM by Gedare Bloom

Attachment: ChangeLog_v1​ added

testsuites/sptests/ChangeLog

comment:1 Changed on Jul 29, 2010 at 10:09:36 AM by Sebastian Huber

Cc: Sebastian Huber added

comment:2 Changed on Jul 30, 2010 at 12:55:25 AM by Chris Johns

Cc: Chris Johns added

Changed on Sep 21, 2010 at 5:48:56 PM by Gedare Bloom

Attachment: rtems_v1.tgz​ added

New files.

comment:3 Changed on Sep 21, 2010 at 5:48:56 PM by Gedare Bloom

attachments.isobsolete: 0 → 1

Changed on Dec 9, 2010 at 1:37:51 AM by Gedare Bloom

Attachment: rtems-cvs_v1.diff​ added

Patch for red black tree.

comment:4 Changed on Dec 12, 2010 at 7:02:43 PM by Gedare Bloom

attachments.isobsolete: 0 → 1

comment:5 Changed on Apr 4, 2011 at 5:49:05 PM by Joel Sherrill

Resolution: → fixed
Status: new → closed

Patch committed to head. All tests passed. Please update the 4.11 release notes in the wiki to reflect the addition.

comment:6 Changed on Nov 24, 2014 at 6:58:28 PM by Gedare Bloom

Version: HEAD → 4.11

Replace Version=HEAD with Version=4.11 for the tickets with Milestone >= 4.11

Note: See TracTickets for help on using tickets.