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.hu...@embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
rtems-devel mailing list
rtems-devel@rtems.org
http://www.rtems.org/mailman/listinfo/rtems-devel

Reply via email to