[PATCH] add freelist data structure to score

[Ashi]

Thanks for all good explanation.


On Tue, Jul 9, 2013 at 11:24 PM, Sebastian Huber <
sebastian.huber at embedded-brains.de> wrote:

> On 07/09/2013 05:29 AM, Ashi wrote:
>
>> Hi, Sebastian, thanks for your review!
>>
>> 在 2013-7-7 下午9:49，"Sebastian Huber" <sebastian.huber at embedded-**brains.de<sebastian.huber at embedded-brains.de>
>> <mailto:sebastian.huber@**embedded-brains.de<sebastian.huber at embedded-brains.de>
>> >>写道：
>>
>>  >
>>  > Hello Ashi,
>>  >
>>  >
>>  > On 06/07/13 09:17, Ashi wrote:
>>  >>
>>  >> Hi all,
>>  >>
>>  >> this patch adds a data structure called freelist to score, there are
>> no
>>  >> test cases yet and should be added later.
>>  >
>>  >
>>  > I would appreciate to have the test for this new stuff included in the
>> patch.
>>
>>
>> sure, I will update the patch with test cases.
>>  >
>>  >
>>  >>
>>  >> Freelist is a structure, which contains a chain of nodes. It supports
>> 2
>>  >> operation:
>>  >> - get node from freelist
>>  >> - put node to freelist.
>>  >> And when there is no enough node in freelist, it will automatically
>>  >> increase itself's size by allocate more nodes from heap or
>> workspace(which
>>  >> is specified by user).
>>  >
>>  >
>>  > What can I do if I like to get the nodes from a magic space?
>>
>>
>> sorry for the unclear, you can get nodes from freelist by 'get'
>> operation. And
>> if you mean get nodes from heap or workspace, it's done by
>> _Freelist_Get_node(), which calls _Freelist_Bump() when there is no free
>> node left.
>>
>
> Yes, the problem is that you limit your Freelist to the heap and
> workspace.  If you use a handler function (or virtual method if you like)
> then you can avoid this limitation.
>
> [...]
>
>   >> +/**
>>  >> + * @typedef freelist_callout
>>  >> + */
>>  >> +typedef void (*freelist_callout)(
>>  >> +  Freelist_Control *fc,
>>  >> +  void *nodes
>>  >> +);
>>  >> +
>>  >> +/**
>>  >> + * @typedef Freelist_Control_struct
>>  >> + *
>>  >> + * This is used to manage each element.
>>  >> + */
>>  >> +struct Freelist_Control_struct {
>>  >> +  Chain_Control     Freelist;
>>  >> +  size_t            free_count;
>>  >
>>  >
>>  > Why do we need the free_count?
>>
>> free_count is used to keep track how many nodes there is in freelist. And
>> if
>> free_count is 0 when you try to get node from freelist by call
>> _Freelist_Get_node(), _Freelist_Get_node() will call _Freelist_Bump() to
>> allocate more node from heap or workspace.
>>
>
> The list knows if it is empty.  There is not need to store this
> information in two ways.
>
>
>   >
>>  >> +  size_t            bump_count;
>>  >> +  size_t            node_size;
>>  >
>>  >
>>  >> +  freelist_callout  callout;
>>  >> +  bool              use_workspace;
>>  >> +};
>>  >
>>  >
>>  > I would replace this with an extend handler.
>>  >
>>  > /**
>>  >  * @brief Extends the freelist.
>>  >  *
>>  >  * @param[in] freelist The freelist control.
>>  >  *
>>  >  * @return The count of new nodes.
>>  >  */
>>  > typedef size_t ( *Freelist_Extend )( Freelist_Control *freelist );
>>  >
>>  > This is much more flexible since you only specify the interface and
>> don't
>> limit this to heap/workspace.
>>  >
>>  > You can provide a _Freelist_Extend_with_nothing(**) which simply
>> returns 0.
>>
>> Yeah, this Freelist_Extend is very flexible, but I feel the
>> Freelist_Extend is
>> a little complex. As it shows in _Freelist_Bump(), if users provides
>> their own
>> extension function, they have to append there new nodes to freelist's
>> internal
>> chain and call their callout function on new nodes. And since
>> _Freelist_Initialize() also would call Freelist_Extend(), if we provided
>> _Freelist_Extend_with_nothing(**), the initialization may fail.
>>
>
> Since the Freelist_Extend gets the Freelist as a first argument it can set
> the extend handler to _Freelist_Extend_with_nothing(**) after the first
> invocation.
>
> Example:
>
>
> /**
>  * @brief Extends the freelist.
>  *
>  * @param[in] freelist The freelist control.
>  */
> typedef void ( *Freelist_Extend )( Freelist_Control *freelist );
>
> typedef struct {
>   Objects_Control obj;
>   int x;
> } my_obj;
>
> void my_extend( Freelist_Control *freelist )
> {
>   size_t bump_count = freelist->bump_count;
>   size_t size = bump_count * sizeof(my_obj);
>   my_obj *objs = malloc(size);
>
>   _Freelist_Set_extend_handler( freelist, _Freelist_Extend_with_nothing );
>   _Chain_Initialize(
>     _Freelist_Get_list( freelist ),
>     objs,
>     bump_count,
>     size
>   );
>
> }
>
I'm a little confused by my_extend() function, is it only called after
calling _Freelist_Initialize() by user?

>
> [...]
>
> --
> Sebastian Huber, embedded brains GmbH
>
> Address : Dornierstr. 4, D-82178 Puchheim, Germany
> Phone   : +49 89 189 47 41-16
> Fax     : +49 89 189 47 41-09
> E-Mail  : sebastian.huber at embedded-**brains.de<sebastian.huber at embedded-brains.de>
> PGP     : Public key available on request.
>
> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>

Cheers,
Zhongwei
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130710/76cf7361/attachment-0001.html>