<span class="st">I'm terribly sorry for my late reply. I'm off for my weekend.</span><br><br><div class="gmail_quote">2012/5/4 Gedare Bloom <span dir="ltr"><<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Fri, May 4, 2012 at 3:28 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
> Hi, all. I'm working on the "Use hash or map in POSIX keys" project.<br>
> As Joel said, the first thing to be determined is the problem of what<br>
> data goes with each thread and what goes with each key. I find it's<br>
> difficult to design the interface without some specific approach. And<br>
> since the rbtree api is available in RTEMS, I have tried to do the<br>
> design in the rbtree approach.<br>
><br>
</div>Good. The rbtree should support an efficient map operation.<br>
<div class="im"><br></div></blockquote><div>Gedare, thanks for your reply!<br> <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="im">
> I find 2 data structures need revised(added): POSIX_Keys_Control and key_node.<br>
><br>
> typedef struct {<br>
> Objects_Control Object;<br>
> void (*destructor)( void * );<br>
> key_node * key_node_ptr;<br>
> }POSIX_Keys_Control;<br>
><br>
> typedef struct{<br>
> rtems_rbtree_node Node;<br>
> Objects_Id thread_id;<br>
> void **value;<br>
> }key_node;<br>
><br>
> POSIX_Keys_Control is used to manage all keys. And key_node is the<br>
> structure contains key data and rbtree node.<br>
</div>I think you might want an rtems_rbtree_control key_tree field in<br>
POSIX_Keys_Control instead of this key_node* dynamic array. Then your<br>
code can add structs containing an rtems_rbtree_node dynamically to<br>
the key_tree.<br></blockquote><div>After read the rbtree.h in score, I find I confused the rtems_rbtree_node and rtems_rbtree_control. It should be the rtems_rbtree_control here.<br><br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Also the key_node structure should follow a naming convention of<br>
POSIX_Keys_Key_node or something similar.<br>
API_Package_name_Struct_type_name is the general format for<br>
structures. API_Package_name_Method_name is the general format for<br>
functions. Note the mixture of lower and upper case letters. <br></blockquote><div>I see.<br> </div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div class="im">
> I'm not quite sure about the Objects_Control member's function in<br>
> current implementation. I find key = Object.id, in which key is<br>
> pthread_key_t type, and _POSIX_Keys_Get(key, &location) is used to<br>
> find key's corresponding the_key, which is POSIX_Keys_Control type.So<br>
> is it the only function of Object member ?<br>
><br>
</div>Object_Control means the structure embeds an RTEMS Object so that the<br>
structure can be managed by the Object Manager whose responsibilities<br>
include pre-allocating enough objects of a certain type to satisfy<br>
requests to Create those objects.<br>
<br>
It seems to me that the Key (key_node) should be the Object since the<br>
number of keys is the resource being managed. The present solution<br>
uses an array of values (one for each thread) because each thread can<br>
have its own version of a given key. The key is "looked up" by the<br>
Object Id of the Key and then the requesting thread. What we should<br>
prefer is a more scalable solution that does not require<br>
pre-allocating an array of values for all possible threads. Something<br>
like...<br>
<div class="im">typedef struct {<br>
Objects_Control Object;<br>
void (*destructor)( void * );<br>
</div><div class="im"> rtems_rbtree_node Node;<br>
Objects_Id thread_id;<br>
void **value;<br>
</div>} POSIX_Keys_Control;<br>
<br>
And maybe a global:<br>
rtems_rbtree_control POSIX_Keys_Tree;<br></blockquote><div><br>I think this is a new and great idea that I haven't thought before,Does it mean a single
POSIX_Keys_Tree contains all node in the system? <br>
I know a rbtree contains only key data belongs to one specific key in my
design above, and I was thinking the idea of manage all keys by a
rbtree, then there would be a hiearchy: all keys are in one rbtree, and
each key's data are in their own rbtrees. But I think this design is a
little complex, and your idea is more uniform. However, will these two differ much in runtime?<br><br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Then you would implement an rbtree_compare function that will combine<br>
the <a href="http://POSIX_Keys_control.Object.id" target="_blank">POSIX_Keys_control.Object.id</a> with POSIX_Keys_control.thread_id as<br>
a "key" for the rbtree to use for storing each POSIX_Keys_Control.<br>
<div class="im"><br></div></blockquote><div class="im">I see, I can compare <a href="http://POSIX_Keys_control.Object.id">POSIX_Keys_control.Object.id</a> first and if they are equal, then compare the POSIX_Keys_control.thread_id.<br>
<br>> all key related operations are described as follow:<br>
> - key create:<br>
> create POSIX_Keys_Control instance and intialize an empty rbtree, in<br>
> which rtems_rbtree_control instance will be created and an rbtree<br>
> node's key compare function is also needed. Thread_id is compared in<br>
> the compare function. So this approach doesdn't consider allocate same<br>
> data for the same thread in the same key, because only different<br>
> Thread_id are comparable. But I find something about duplicate node in<br>
> the Gedare's rbtree patch, maybe the duplicate feature also can be<br>
> added into POSIX key.<br>
><br>
</div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">You still want unique rbtree comparisons so that a thread can<br>
distinguish its own keys, unless it is valid for a thread to allocate<br>
multiple values with the same key?<br>
<br>
Key create should not create the red-black tree; the rbtree should be<br>
created during initialization of the POSIX_Keys manager---which by the<br>
way is improperly named right now as POSIX_Key_Manager_initialization<br>
and should be renamed POSIX_Keys_Manager_initialization with an s on<br>
Keys (or just POSIX_Keys_Initialization).<br>
<div class="im"><br></div></blockquote><div>I didn't notice the POSIX_Key_Manager_initialization before, thanks. BTW I've a question about the _Objects_Initialize_information(), which _POSIX_Key_Manager_initialization calls. I read the code of _Objects_Initialize_information(), but still don't know what the maximum parameter is used for? I think it's not for determining the memory size of all objects in one manager and then allocating such size of memory, is it?<br>
<br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="im">
> - key delete<br>
> delete all the nodes in rbtree by rtems_rbtree_get_min() or<br>
> rtems_rbtree_get_max(), and delete the RBTree_Control,<br>
> POSIX_Keys_Control instance. The key data's deallocation is done by<br>
> user.<br>
><br>
> - key get specific<br>
> we can use _RBTree_Find() to do the actually work behind<br>
> get_specific(), the runtime is O(log(n))<br>
><br>
> - key set specific<br>
> after a proper key_node is create, we can use _RBTree_Insert() to do<br>
> the set specific. the runtime is rbtree insert runtime, which is<br>
> O(log(n)).<br>
><br>
> I'm not sure whether this design is appropriate and this design is<br>
> very simple, need many more work to do. Hope further discussion to<br>
> make it more clear!<br>
><br>
</div>Simple is good. I think you're on the right track other than my few<br>
comments about organizing the structures. You have the right ideas for<br>
how to implement the Keys functions I believe.<br>
-Gedare<br></blockquote><div>Yeah, it remind me the K.I.S.S. principle!<br><br>-best regards!<br>-zw_yao<br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
> --best regards!<br>
> --zw_yao<br>
> _______________________________________________<br>
> rtems-devel mailing list<br>
> <a href="mailto:rtems-devel@rtems.org">rtems-devel@rtems.org</a><br>
> <a href="http://www.rtems.org/mailman/listinfo/rtems-devel" target="_blank">http://www.rtems.org/mailman/listinfo/rtems-devel</a><br>
</blockquote></div><br>