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

[Ashi]

Sure, I'll update this patch shortly.


On Fri, Jul 26, 2013 at 9:01 PM, Gedare Bloom <gedare at rtems.org> wrote:

> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130727/39e966b8/attachment.html>