Use Hash or Map in POSIX Key

current implementation's problem

There are 2 problems in current implementation of POSIX Key(more details are described next section). #The POSIX key area is not properly extended when the number of threads is increased(dynamically created) if POSIX threads are configured as "unlimited", which is a known bug. #Extra memory is reserved in keys for each thread or task in current implementation, which can be heavy memory overhead when keys increase.= several design approaches =

current implementation

current implementation allocates an array when key creates, which holds all of the threads' or tasks' key value. The pre-allocated array's size is as big as the number of threads in system. It is a waste of memory that allocates key value slot for thread which would not use POSIX key at all. And other problems of current implementation is as current implementation's problem? describes.= one rbtree approach =

In this approach, there is only one rbtree which is used to manage all POSIX Keys' data. If there are m POSIX Keys and t POSIX Threads, and each Thread has m Key values, then there is n(n = m x t) nodes in the global rbtree. A comparison between this approach and one rbtree per thread approach is provided in one rbtree per thread approach?.= one rbtree per thread approach =

Suppose there are also m POSIX Keys and t POSIX Threads in the system, then each thread maintains one rbtree, all key data of specific thread is in that rbtree. For example, say if each thread has m Key values, then there are m nodes in each thread's rbtree. Here is a comparison between one-rbtree approach and this approach: Runtime_and_space_comparison_between_one-rbtree_and_one-rbtree_per-thread_approach?[comparison runtime and space comparison between one-rbtree and one-rbtree per-thread approach][comparison].= hash approach =

there is also a hash approach discussed beforehttp://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html[(links) runtime and space comparison between one-rbtree and one-rbtree per-thread approach][comparison]. However, it's worst-case runtime is O(n). And it's unacceptable to RTEMS. Another reason that this approach is not desirable is that we would have to add hash code to RTEMS score which is not there now. The other approaches reuse a score object(the rbtree api).