UseHashOrMapInNotepadsAndKeys

Status: This project has been done as one of GSOC2012 project. Here is the document about this project:Use Hash or Map in POSIX Key

Reimplement Classic API notepads and POSIX keys using code like std::map but in C. The current implementation requires that enough memory be reserved for every task to have memory for all notepads and every key whether they use them or not. This results in simple and fast array lookups to access individual values but is obviously heavy on memory. It is hoped that a hash/map algorithm can be found or designed which reduces the memory overhead without adding excessive lookup overhead or heavy handed O(n) algorithms for management of the entries. This is particularly important because tasks and keys can be dynamically created and deleted.

This is needed on POSIX Keys because when POSIX threads are configured as "unlimited", the key area is not extended when the number of threads is increased. This is a known bug.

JoelSherrill and PavelPisa are good resources for this. Joel can answer questions about the rationale driving this need and help evaluate algorithms. The run-time behaviour of the algorithm is very important because RTEMS strives to be as predictable in run-time execution times and memory usage as possible. Pavel is very knowledgeable about hash algorithms.

The uthash code should be evaluated for use. Factors to consider are memory usage, algorithmic order, and ability for us to do complete code coverage on the code.

Other map/hash implementations may be considered.

A standard map/hash implementation for C in RTEMS could be promoted for use by other components including the device driver interface and shell command lookup.