POSIX key structure in rbtree approach

[Gedare Bloom]

On Fri, May 4, 2012 at 3:28 AM, Ashi <ashi08104 at gmail.com> wrote:
> 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.
>
Good. The rbtree should support an efficient map operation.

> 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;
> }POSIX_Keys_Control;
>
> typedef struct{
>          rtems_rbtree_node Node;
>          Objects_Id thread_id;
>          void **value;
> }key_node;
>
> POSIX_Keys_Control is used to manage all keys. And key_node is the
> structure contains key data and rbtree node.
I think you might want an rtems_rbtree_control key_tree field in
POSIX_Keys_Control instead of this key_node* dynamic array.  Then your
code can add structs containing an rtems_rbtree_node dynamically to
the key_tree.

Also the key_node structure should follow a naming convention of
POSIX_Keys_Key_node or something similar.
API_Package_name_Struct_type_name is the general format for
structures. API_Package_name_Method_name is the general format for
functions. Note the mixture of lower and upper case letters.

> 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 ?
>
Object_Control means the structure embeds an RTEMS Object so that the
structure can be managed by the Object Manager whose responsibilities
include pre-allocating enough objects of a certain type to satisfy
requests to Create those objects.

It seems to me that the Key (key_node) should be the Object since the
number of keys is the resource being managed. The present solution
uses an array of values (one for each thread) because each thread can
have its own version of a given key. The key is "looked up" by the
Object Id of the Key and then the requesting thread.  What we should
prefer is a more scalable solution that does not require
pre-allocating an array of values for all possible threads.  Something
like...
typedef struct {
           Objects_Control     Object;
           void     (*destructor)( void * );
          rtems_rbtree_node Node;
          Objects_Id thread_id;
          void **value;
} POSIX_Keys_Control;

And maybe a global:
rtems_rbtree_control POSIX_Keys_Tree;

Then you would implement an rbtree_compare function that will combine
the POSIX_Keys_control.Object.id with POSIX_Keys_control.thread_id as
a "key" for the rbtree to use for storing each POSIX_Keys_Control.

> 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.
>
You still want unique rbtree comparisons so that a thread can
distinguish its own keys, unless it is valid for a thread to allocate
multiple values with the same key?

Key create should not create the red-black tree; the rbtree should be
created during initialization of the POSIX_Keys manager---which by the
way is improperly named right now as POSIX_Key_Manager_initialization
and should be renamed POSIX_Keys_Manager_initialization with an s on
Keys (or just POSIX_Keys_Initialization).

> - 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
> user.
>
> - 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
> O(log(n)).
>
> 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!
>
Simple is good. I think you're on the right track other than my few
comments about organizing the structures. You have the right ideas for
how to implement the Keys functions I believe.
-Gedare

> --best regards!
> --zw_yao
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel