POSIX key structure in rbtree approach
Ashi
ashi08104 at gmail.com
Tue May 8 07:17:04 UTC 2012
2012/5/7 Gedare Bloom <gedare at rtems.org>
> On Mon, May 7, 2012 at 11:16 AM, Ashi <ashi08104 at gmail.com> wrote:
> > I'm terribly sorry for my late reply. I'm off for my weekend.
> >
> Most of us are. :)
>
> > 2012/5/4 Gedare Bloom <gedare at rtems.org>
> >>
> >> On Fri, May 4, 2012 at 3:28 AM, Ashi <ashi08104 at gmail.com> wrote:
> >> > Hi, all. I'm working on the "Use hash or map in POSIX keys" project.
> >> > As Joel said, the first thing to be determined is the problem of what
> >> > data goes with each thread and what goes with each key. I find it's
> >> > difficult to design the interface without some specific approach. And
> >> > since the rbtree api is available in RTEMS, I have tried to do the
> >> > design in the rbtree approach.
> >> >
> >> Good. The rbtree should support an efficient map operation.
> >>
> > Gedare, thanks for your reply!
> >
> >>
> >> > I find 2 data structures need revised(added): POSIX_Keys_Control and
> >> > key_node.
> >> >
> >> > typedef struct {
> >> > Objects_Control Object;
> >> > void (*destructor)( void * );
> >> > key_node * key_node_ptr;
> >> > }POSIX_Keys_Control;
> >> >
> >> > typedef struct{
> >> > rtems_rbtree_node Node;
> >> > Objects_Id thread_id;
> >> > void **value;
> >> > }key_node;
> >> >
> >> > POSIX_Keys_Control is used to manage all keys. And key_node is the
> >> > structure contains key data and rbtree node.
> >> I think you might want an rtems_rbtree_control key_tree field in
> >> POSIX_Keys_Control instead of this key_node* dynamic array. Then your
> >> code can add structs containing an rtems_rbtree_node dynamically to
> >> the key_tree.
> >
> > After read the rbtree.h in score, I find I confused the rtems_rbtree_node
> > and rtems_rbtree_control. It should be the rtems_rbtree_control here.
> >
> >> Also the key_node structure should follow a naming convention of
> >> POSIX_Keys_Key_node or something similar.
> >> API_Package_name_Struct_type_name is the general format for
> >> structures. API_Package_name_Method_name is the general format for
> >> functions. Note the mixture of lower and upper case letters.
> >
> > I see.
> >
> >>
> >> > I'm not quite sure about the Objects_Control member's function in
> >> > current implementation. I find key = Object.id, in which key is
> >> > pthread_key_t type, and _POSIX_Keys_Get(key, &location) is used to
> >> > find key's corresponding the_key, which is POSIX_Keys_Control type.So
> >> > is it the only function of Object member ?
> >> >
> >> Object_Control means the structure embeds an RTEMS Object so that the
> >> structure can be managed by the Object Manager whose responsibilities
> >> include pre-allocating enough objects of a certain type to satisfy
> >> requests to Create those objects.
> >>
> >> It seems to me that the Key (key_node) should be the Object since the
> >> number of keys is the resource being managed. The present solution
> >> uses an array of values (one for each thread) because each thread can
> >> have its own version of a given key. The key is "looked up" by the
> >> Object Id of the Key and then the requesting thread. What we should
> >> prefer is a more scalable solution that does not require
> >> pre-allocating an array of values for all possible threads. Something
> >> like...
> >> typedef struct {
> >> Objects_Control Object;
> >> void (*destructor)( void * );
> >> rtems_rbtree_node Node;
> >> Objects_Id thread_id;
> >> void **value;
> >> } POSIX_Keys_Control;
> >>
> >> And maybe a global:
> >> rtems_rbtree_control POSIX_Keys_Tree;
> >
> >
> > I think this is a new and great idea that I haven't thought before,Does
> it
> > mean a single POSIX_Keys_Tree contains all node in the system?
> yes
>
> > I know a rbtree contains only key data belongs to one specific key in my
> > design above, and I was thinking the idea of manage all keys by a rbtree,
> > then there would be a hiearchy: all keys are in one rbtree, and each
> key's
> > data are in their own rbtrees. But I think this design is a little
> complex,
> > and your idea is more uniform. However, will these two differ much in
> > runtime?
> >
> not sure because i do not quite understand your design. but I get the
> feeling that your design will have a big problem of managing multiple
> rbtrees simultaneously. I have not tried to do that before. Both
> approaches seem like they would have similar (log-time) asymptotic
> behavior.
>
> I mean all keys are managed in one globle rbtree, in which each node has a
member of rtems_rbtree_control, like:
typedef struct {
Objects_Control Object;
void (*destructor)(void*);
rtems_rbtree_node Node;
rtems_rbtree_control key_tree;
}POSIX_Keys_Control;
and for each key, all the key data is managed in each key's rbtree, like:
typedef struct{
rtems_rbtree_node node;
Objects_Id thread_id;
void *value;
}POSIX_Keys_Key_node;
However, this design seems more complex. And I don't know what could lead
to the problem of managing multiple
rbtrees simultaneously, can you give some example?
-zw_yao
> >>
> >> Then you would implement an rbtree_compare function that will combine
> >> the POSIX_Keys_control.Object.id with POSIX_Keys_control.thread_id as
> >> a "key" for the rbtree to use for storing each POSIX_Keys_Control.
> >>
> > I see, I can compare POSIX_Keys_control.Object.id first and if they are
> > equal, then compare the POSIX_Keys_control.thread_id.
> >
> >
> >> all key related operations are described as follow:
> >> - key create:
> >> create POSIX_Keys_Control instance and intialize an empty rbtree, in
> >> which rtems_rbtree_control instance will be created and an rbtree
> >> node's key compare function is also needed. Thread_id is compared in
> >> the compare function. So this approach doesdn't consider allocate same
> >> data for the same thread in the same key, because only different
> >> Thread_id are comparable. But I find something about duplicate node in
> >> the Gedare's rbtree patch, maybe the duplicate feature also can be
> >> added into POSIX key.
> >>
> >>
> >> You still want unique rbtree comparisons so that a thread can
> >> distinguish its own keys, unless it is valid for a thread to allocate
> >> multiple values with the same key?
> >>
> >> Key create should not create the red-black tree; the rbtree should be
> >> created during initialization of the POSIX_Keys manager---which by the
> >> way is improperly named right now as POSIX_Key_Manager_initialization
> >> and should be renamed POSIX_Keys_Manager_initialization with an s on
> >> Keys (or just POSIX_Keys_Initialization).
> >>
> > I didn't notice the POSIX_Key_Manager_initialization before, thanks. BTW
> > I've a question about the _Objects_Initialize_information(), which
> > _POSIX_Key_Manager_initialization calls. I read the code of
> > _Objects_Initialize_information(), but still don't know what the maximum
> > parameter is used for? I think it's not for determining the memory size
> of
> > all objects in one manager and then allocating such size of memory, is
> it?
> >
> maximum determines the total number of that kind of object. it is
> controlled by some CONFIGURE_MAXIMUM_XXX, e.g.
> CONIFIGURE_MAXIMUM_POSIX_KEYS.
>
> -Gedare
>
> >> > - key delete
> >> > delete all the nodes in rbtree by rtems_rbtree_get_min() or
> >> > rtems_rbtree_get_max(), and delete the RBTree_Control,
> >> > POSIX_Keys_Control instance. The key data's deallocation is done by
> >> > user.
> >> >
> >> > - key get specific
> >> > we can use _RBTree_Find() to do the actually work behind
> >> > get_specific(), the runtime is O(log(n))
> >> >
> >> > - key set specific
> >> > after a proper key_node is create, we can use _RBTree_Insert() to do
> >> > the set specific. the runtime is rbtree insert runtime, which is
> >> > O(log(n)).
> >> >
> >> > I'm not sure whether this design is appropriate and this design is
> >> > very simple, need many more work to do. Hope further discussion to
> >> > make it more clear!
> >> >
> >> Simple is good. I think you're on the right track other than my few
> >> comments about organizing the structures. You have the right ideas for
> >> how to implement the Keys functions I believe.
> >> -Gedare
> >
> > Yeah, it remind me the K.I.S.S. principle!
> >
> > -best regards!
> > -zw_yao
> >>
> >>
> >> > --best regards!
> >> > --zw_yao
> >> > _______________________________________________
> >> > rtems-devel mailing list
> >> > rtems-devel at rtems.org
> >> > http://www.rtems.org/mailman/listinfo/rtems-devel
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120508/63ac4e69/attachment.html>
More information about the devel
mailing list