the hash approach of POSIX key

[Ashi]

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).

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