[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