<br><br><div class="gmail_quote">2012/5/21 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 Mon, May 21, 2012 at 10:16 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
><br>
><br>
> 2012/5/21 Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>><br>
>> On Mon, May 21, 2012 at 9:30 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
>> > Hi, all.<br>
>> > I'm working on the POSIX key project(here is a introduction of it:[1]).<br>
>> > Since using hash is a good candidate of the solution, I'm trying to do<br>
>> > the<br>
>> Hashing is a good candidate solution for what problem? It is not clear<br>
>> to me what the hash solves, that is why to use a hash at all?<br>
><br>
><br>
> Sorry for the obscure description. Here, we use hash table to dynamicly<br>
> manage POSIX key, then the key can be added and deleted flexibly without<br>
> losing the speed of key query, add, delete operation. While key and it's<br>
> data field is fixed in current implementation, more description of the<br>
> problem of current POSIX implementation is in [1]. This hash approach is an<br>
> alternative to another approach(the rbtree approach), I have decide which is<br>
> better.(Probably, both should be implemented).<br>
><br>
</div>A hash solves the problem of giving you a (unique) key based on some<br>
input data. You then can use that key to map into a searching<br>
structure in order to lookup a value associated with that key.<br></blockquote><div> </div><div>If a proper hash function applied, then all key is well distributed in the hash table,  can I search a value associated with that key by traversing all values? It seems we can't do like that, but I'm not clear about the exact reason.<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">
Regardless of whether you use a hash to create the key or derive it<br>
from some other means, you still need to implement an efficient search<br>
mechanism. I don't know of any structure better than a balanced search<br>
tree to provide bounded worst-case performance times at least for<br>
arbitrary keys.<br>
<br>
I wonder if you need to hash anything, or if you can rely on the<br>
Objects_Id of the Posix_Keys_Control structure itself, or get the key<br>
from the user. Then the map function can just use the Objects_Id as<br>
the search key, or for an score implementation can accept a key as an<br>
argument.<br></blockquote><div>Is hash not necessary? But this wiki page[3] mentioned we need hash. I need help to make it clear.<br><br>links:<br>[3]<a href="http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys">http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys</a><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>
-Gedare<br>
<div><div class="h5"><br>
>> > design using hash. I'm not clear about how to deal with UThash[2] in<br>
>> > RTEMS.<br>
>> > Shall we directly include this lib or reimplemented in RTEMS? If assumed<br>
>> > directly use, I think we can manage all keys in one hash table as like<br>
>> > in<br>
>> > the rbtree approach. Since UThash is able to use structure as it's hash<br>
>> > key,<br>
>> > then the POSIX_Keys_Control can be defined as:<br>
>> ><br>
>> > typedef struct {<br>
>> >     Objects_Control Object;<br>
>> >     void (*destructor) (void *);<br>
>> >     hash_key_t hash_key; /* use struct hash_key_t as a hash key */<br>
>> >     void *value;<br>
>> >     UT_hash_handle hh;<br>
>> > } POSIX_Keys_Control;<br>
>> ><br>
>> > the hash_key_t type is a structure include Object id and pthread_key_t:<br>
>> ><br>
>> > typedef struct {<br>
>> >     Objects_Id thread_id;<br>
>> >     pthread_key_t key;<br>
>> > } hash_key_t;<br>
>> ><br>
>> > Then all the keys' data is managed in one hash table. I've a question<br>
>> > about<br>
>> > this design: is it a waste of memory that every key data holds a<br>
>> > POSIX_Keys_Control structure? If it is, I think we could manage it in a<br>
>> > two<br>
>> > level structure: first level manages all keys by one hash table, and<br>
>> > each<br>
>> > key manages its values in second level by one bash table:<br>
>> ><br>
>> > typedef struct {<br>
>> >     Objects_Control Object;<br>
>> >     Objects_Id Object.id;    /* use Object.id as hash key, I don't know<br>
>> > whether we could directly use Object as a hash key? I know it's no<br>
>> > problem<br>
>> > in UThash  */<br>
>> >     key_node_t * key_node;<br>
>> >     UT_hash_handle hh;<br>
>> > } POSIX_Keys_Control;<br>
>> ><br>
>> > typedef struct {<br>
>> >    Objects_Id thread_id; /* use thread_id as hash key */<br>
>> >    void *value;<br>
>> >    void (*destructor) (void *);<br>
>> >    UT_hash_handle hh;<br>
>> > } key_node_t;<br>
>> ><br>
>> > And as Gedare suggested in my last discuss, the implementation should<br>
>> > consider do actually work in in the supercore layer and shared between<br>
>> > Posix<br>
>> > Keys and Classic Task vars, however, I haven't think about it yet, I'm a<br>
>> > little behind my work.<br>
>> ><br>
>> ><br>
>> > links:<br>
>>   [1]: <a href="http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html" target="_blank">http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html</a><br>
>> > [2]:<a href="http://uthash.sourceforge.net/" target="_blank">http://uthash.sourceforge.net/</a><br>
>> ><br>
>> > --<br>
>> > Best wishes!<br>
>> > zw_yao<br>
>> ><br>
><br>
><br>
><br>
><br>
> --<br>
> Best wishes!<br>
> zw_yao<br>
><br>
><br>
</div></div>> _______________________________________________<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>
><br>
</blockquote></div><br><br clear="all"><br>-- <br>Best wishes!<br>zw_yao<br><br>