the hash approach of POSIX key

[Ashi]

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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120522/fc1be309/attachment-0001.html>