Red-Black-Tree for Priority Queues

[Joel Sherrill]

The current implementation has a bounded maximum
execution time. Does the Red-Black Tree have that
guarantee?

Technically the code to unroll the loop could be
deleted. In either case, how long would interrupts
have to be disabled?

On 11/15/2013 11:00 AM, Sebastian Huber wrote:
> 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?
> 



-- 
Joel Sherrill, Ph.D.             Director of Research & Development
joel.sherrill at OARcorp.com        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
Support Available                (256) 722-9985