the hash approach of POSIX key

[Gedare Bloom]

On Mon, May 21, 2012 at 10:16 AM, Ashi <ashi08104 at gmail.com> wrote:
>
>
> 2012/5/21 Gedare Bloom <gedare at rtems.org>
>>
>> On Mon, May 21, 2012 at 9:30 AM, Ashi <ashi08104 at gmail.com> wrote:
>> > Hi, all.
>> > I'm working on the POSIX key project(here is a introduction of it:[1]).
>> > Since using hash is a good candidate of the solution, I'm trying to do
>> > the
>> Hashing is a good candidate solution for what problem? It is not clear
>> to me what the hash solves, that is why to use a hash at all?
>
>
> Sorry for the obscure description. Here, we use hash table to dynamicly
> manage POSIX key, then the key can be added and deleted flexibly without
> losing the speed of key query, add, delete operation. While key and it's
> data field is fixed in current implementation, more description of the
> problem of current POSIX implementation is in [1]. This hash approach is an
> alternative to another approach(the rbtree approach), I have decide which is
> better.(Probably, both should be implemented).
>
A hash solves the problem of giving you a (unique) key based on some
input data. You then can use that key to map into a searching
structure in order to lookup a value associated with that key.
Regardless of whether you use a hash to create the key or derive it
from some other means, you still need to implement an efficient search
mechanism. I don't know of any structure better than a balanced search
tree to provide bounded worst-case performance times at least for
arbitrary keys.

I wonder if you need to hash anything, or if you can rely on the
Objects_Id of the Posix_Keys_Control structure itself, or get the key
from the user. Then the map function can just use the Objects_Id as
the search key, or for an score implementation can accept a key as an
argument.

-Gedare

>> > design using hash. I'm not clear about how to deal with UThash[2] in
>> > RTEMS.
>> > Shall we directly include this lib or reimplemented in RTEMS? If assumed
>> > directly use, I think we can manage all keys in one hash table as like
>> > in
>> > the rbtree approach. Since UThash is able to use structure as it's hash
>> > key,
>> > then the POSIX_Keys_Control can be defined as:
>> >
>> > typedef struct {
>> >     Objects_Control Object;
>> >     void (*destructor) (void *);
>> >     hash_key_t hash_key; /* use struct hash_key_t as a hash key */
>> >     void *value;
>> >     UT_hash_handle hh;
>> > } POSIX_Keys_Control;
>> >
>> > the hash_key_t type is a structure include Object id and pthread_key_t:
>> >
>> > typedef struct {
>> >     Objects_Id thread_id;
>> >     pthread_key_t key;
>> > } hash_key_t;
>> >
>> > Then all the keys' data is managed in one hash table. I've a question
>> > about
>> > this design: is it a waste of memory that every key data holds a
>> > POSIX_Keys_Control structure? If it is, I think we could manage it in a
>> > two
>> > level structure: first level manages all keys by one hash table, and
>> > each
>> > key manages its values in second level by one bash table:
>> >
>> > typedef struct {
>> >     Objects_Control Object;
>> >     Objects_Id Object.id;    /* use Object.id as hash key, I don't know
>> > whether we could directly use Object as a hash key? I know it's no
>> > problem
>> > in UThash  */
>> >     key_node_t * key_node;
>> >     UT_hash_handle hh;
>> > } POSIX_Keys_Control;
>> >
>> > typedef struct {
>> >    Objects_Id thread_id; /* use thread_id as hash key */
>> >    void *value;
>> >    void (*destructor) (void *);
>> >    UT_hash_handle hh;
>> > } key_node_t;
>> >
>> > And as Gedare suggested in my last discuss, the implementation should
>> > consider do actually work in in the supercore layer and shared between
>> > Posix
>> > Keys and Classic Task vars, however, I haven't think about it yet, I'm a
>> > little behind my work.
>> >
>> >
>> > links:
>>   [1]: http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html
>> > [2]:http://uthash.sourceforge.net/
>> >
>> > --
>> > Best wishes!
>> > zw_yao
>> >
>
>
>
>
> --
> Best wishes!
> zw_yao
>
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
>