POSIX key structure in rbtree approach

[Gedare Bloom]

also is it void** value or void* value?

I think the latter...

-Gedare

On Fri, May 4, 2012 at 11:57 AM, Gedare Bloom <gedare at rtems.org> wrote:
> 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