Now that the free list is committed, can you recreate these patches for review?
On Sat, Jul 6, 2013 at 3:17 AM, Ashi <[email protected]> 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 > _______________________________________________ rtems-devel mailing list [email protected] http://www.rtems.org/mailman/listinfo/rtems-devel
