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
