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

[Ashi]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130706/5c9ac083/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: improve-POSIX-Key-manager-cpukit.patch
Type: application/octet-stream
Size: 28775 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130706/5c9ac083/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: improve-POSIX-Key-manager-testcases.patch
Type: application/octet-stream
Size: 45312 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130706/5c9ac083/attachment-0001.obj>