[PATCH] posix: Reimplement POSIX Key manager to use a red-black tree.

[Gedare Bloom]

Now that the free list is committed, can you recreate these patches for review?

On Sat, Jul 6, 2013 at 3:17 AM, Ashi <ashi08104 at gmail.com> wrote:
> Hi all, this patch includes a reimplement of POSIX Key manager and compared
> with first version of this patch, some improvement is added.
>
> *In short*:
> it enable unlimited model in POSIX key manger and have a decent runtime on
> POSIX key searching, adding and deleting operations. Memory overhead is
> lower than current implementation when the size of key and key value becomes
> big.
>
> *Some details*:
> Current POSIX Key manager uses an array to manage POSIX Key value, so it
> can't support POSIX Key unlimited mode. This implementation uses a red-black
> tree(rbtree) to manage Key value. Because rbtree is a dynamic data
> structure, it makes the key manager can support unlimited mode. And the
> runtime of add, delete and search operation is log(n) for rbtree is a kind
> of balance tree.
>
> There is only one rbtree in system. This rbtree contains all key values.
> Each node is like:
>
> typedef struct {
>   Chain_Node ch_node;
>   RBTree_Node rb_node;
>   pthread_key_t key;
>   Objects_Id thread_id;
>   void *value;
>  }  POSIX_Keys_Rbtree_node;
>
> Here, both pthread_key_t key and thread_id are used as rbtree's key.
> RBTree_Node rb_node is necessary for being a rbtree node. Void *value points
> to POSIX Key's value. There is also a ch_node, which is include in every
> thread's key chain. It is used  to keep track of every POSIX thread's key
> value. When thread exits, all key value can be deleted by iterating that
> thread's key chain.
>
> Because it is inefficient that allocating one node each time when new node
> is added under unlimited mode, we employ a freelist structure to be a pool
> of POSIX_Keys_Rbtree_node. The pool's size is initialized to the size
> specified by rtems_resource_unlimited() macro(refer test case psxkey07 for
> concrete example). When pool is empty, freelist structure will expand its
> pool automatically with a size same as initial size.
>
>
> Thanks,
> Zhongwei
>