[PATCH] add freelist data structure to score

[Gedare Bloom]

You would call extend instead of calling bump, or as part of bumping.

On Wed, Jul 10, 2013 at 2:30 AM, Ashi <ashi08104 at gmail.com> wrote:
> 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
>>> <mailto: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
>> PGP     : Public key available on request.
>>
>> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>
>
> Cheers,
> Zhongwei
>