Red-Black-Tree for Priority Queues

[Sebastian Huber]

Hello,

I consider to replace the current priority queue implementation used for thread 
queues (not the scheduler ready queue) with red-black trees.  Currently we use 
four chains and linear operations in the corresponding priority subset.  A 
red-black tree root can be reduced to at most four pointers.  The four chain 
controls need twelve pointers in contrast.  It helps also to simplify complex 
functions like _Thread_queue_Enqueue_priority() which use _ISR_Flash().  Usage 
of _ISR_Flash() will be highly problematic in case we introduce fine grained 
locking for SMP.

I have a question regarding the current red-black tree implementation.  In case 
the key to insert is already present (multiple) times in the tree, are there 
ordering guarantees with respect to the nodes with the same key?  Can I for 
example insert a key so that the new node is minimal/maximal with respect to 
the existing nodes with the same key value?

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.