[PATCH] add freelist data structure to score
Sebastian Huber
sebastian.huber at embedded-brains.de
Tue Jul 9 15:24:38 UTC 2013
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
);
}
[...]
--
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.
More information about the devel
mailing list