the hash approach of POSIX key

Gedare Bloom gedare at rtems.org
Tue May 22 02:11:32 UTC 2012 

On Mon, May 21, 2012 at 9:17 PM, Ashi <ashi08104 at gmail.com> wrote:
>
>
> 2012/5/21 Gedare Bloom <gedare at rtems.org>
>>
>> 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.
>
>
> 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.
>
>>
>> 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.
>
> Is hash not necessary? But this wiki page[3] mentioned we need hash. I need
> help to make it clear.
>
I don't think a hash is necessary. It's not even clear to me what
would be hashed. The pthread_key_t *key is opaque to the application,
so the POSIX_Keys Manager can create any arbitrary key: the trick is
to create a unique key that can be used to access the stored value
efficiently.

If you embed an Objects_Control in each POSIX_Keys_Control then you
can use the objects_id field as a key directly. Since every
Keys_Control would have a unique object_id, you satisfy one
requirement of the key. The next requirement is efficient searching. I
wonder if you could just use the Object Manager directly. It already
implements a way to "get" an object given its id. So if the user is
given a pthread_key_t that is just a copy of an objects_id, then you
can rely on the Object Manager to handle storing/retrieving the
POSIX_Keys_Control for that key (objects_id). This should work fine
for posix keys; I'm not sure about notepads.

-Gedare

> links:
> [3]http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys
>>
>>
>> -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
>> >
>
>
>
>
> --
> Best wishes!
> zw_yao
>

More information about the devel mailing list