POSIX key structure in rbtree approach

Ashi ashi08104 at gmail.com
Fri May 4 07:28:08 UTC 2012

Hi, all. I'm working on the "Use hash or map in POSIX keys" project.
As Joel said, the first thing to be determined is the problem of what
data goes with each thread and what goes with each key. I find it's
difficult to design the interface without some specific approach. And
since the rbtree api is available in RTEMS, I have tried to do the
design in the rbtree approach.

I find 2 data structures need revised(added): POSIX_Keys_Control and key_node.

typedef struct {
            Objects_Control     Object;
            void     (*destructor)( void * );
            key_node * key_node_ptr;

typedef struct{
	  rtems_rbtree_node Node;
	  Objects_Id thread_id;
	  void **value;

POSIX_Keys_Control is used to manage all keys. And key_node is the
structure contains key data and rbtree node.
I'm not quite sure about the Objects_Control member's function in
current implementation. I find key = Object.id, in which key is
pthread_key_t type, and  _POSIX_Keys_Get(key, &location) is used to
find key's corresponding the_key, which is POSIX_Keys_Control type.So
is it the only function of Object member ?

all key related operations are described as follow:
- key create:
create POSIX_Keys_Control instance and intialize an empty rbtree, in
which rtems_rbtree_control instance will be created and an rbtree
node's key compare function is also needed. Thread_id is compared in
the compare function. So this approach doesdn't consider allocate same
data for the same thread in the same key, because only different
Thread_id are comparable. But I find something about duplicate node in
the Gedare's rbtree patch, maybe the duplicate feature also can be
added into POSIX key.

- key delete
delete all the nodes in rbtree by rtems_rbtree_get_min() or
rtems_rbtree_get_max(), and delete the RBTree_Control,
POSIX_Keys_Control instance. The key data's deallocation is done by

- key get specific
we can use _RBTree_Find() to do the actually work behind
get_specific(),  the runtime is O(log(n))

- key set specific
after a proper key_node is create, we can use _RBTree_Insert() to do
the set specific. the runtime is rbtree insert runtime, which is

I'm not sure whether this design is appropriate and this design is
very simple, need many more work to do. Hope further discussion to
make it more clear!

--best regards!

More information about the devel mailing list