a simple list

a simple list

[Guffens, Vincent]

[-- Attachment #1: Type: text/plain, Size: 2020 bytes --]

Hi,

I need to use a simple list to register the pci devices, drivers and so on. I notice that there are lists like that already in the code so what would you think about having a list.h file like that ?

/* A very simple list.
 * 
 * If you want a list of struct myitem 
 * you do
 * 
 * struct myitem *item_list;
 * 
 * where myitem MUST have its next pointer as the FIRST field
 * 
 * and you can then add, delete the EL item,
 * grub_add_list (&item_list, el);
 * grub_del_list (&item_list, el);
 *
 * or call HOOK(item) for each element of the list 
 * grub_iterate_list (item_list, hook);
 *
 * This brk version will point el to the list item for which 
 * HOOK(EL) returns a non-null value
 * grub_iterate_list_brk (item_list, hook, el);
 *
 */

struct obj {
  struct obj *next; /* MUST BE FIRST */
};

#define grub_del_list(list, el) _grub_del_list((struct obj**) list, (struct obj*) el) 
#define grub_add_list(list, el) _grub_add_list((struct obj**) list, (struct obj*) el) 
#define grub_find_list(list, el) \
  (typeof(list)) _grub_find_list((struct obj*) list, (struct obj*) el) 
#define grub_iterate_list(list, func) \
  {typeof(list) el = list; while (el) {func(el); el=el->next;}}
#define grub_iterate_list_brk(list, func, it) \
  {typeof(list) el = list; it = 0; \
    while (el) {if (func(el)) {it = el; break;} el=el->next; }}

static inline struct obj*  _grub_find_list (struct obj *list, struct obj *el)
{
  struct obj *it = list;
  for (it = list; it; it=it->next)
  {
    if (it == el) return el;
  }
  return 0;
};

static inline void _grub_add_list (struct obj **list, struct obj *el)
{
  if ( (!el) || (_grub_find_list (*list, el)) )
    return;
  
  el->next = *list;
  *list = el;
};

static inline void _grub_del_list (struct obj **list, struct obj *el)
{
  struct obj **p;
  struct obj *q;

  for (p = list, q = *p; q; p = &(q->next), q = q->next)
    if (q == el)
      {
        *p = q->next;
        break;
      }
};

[-- Attachment #2: Type: text/html, Size: 3046 bytes --]

RE : a simple list

[Eric Salomé]

[-- Attachment #1: Type: text/plain, Size: 4141 bytes --]

Hi,

I didn’t take a good look at current iterate functions in Grub 2, yet.

 

Most iterations needs a “init” (before treatment of first item) and a
“fini” (after treatment of last item).

Further more, one might want to make iteration functions “re-entrant”
(or recursive), or call-back other functions in a generic way.

 

One way to get to such behavior easily cost a bit more than the example
you provided : 

you may just add an argument (let’s call it the context object) to the
call of the iterate function :

 

#define grub_iterate_list(list, func, context) \
  {typeof(list) el = list; while (el) {func(context, el); el=el->next;}
func(context, NULL)}
or

#define grub_iterate_list(list, func) \
  {void * context = NULL; typeof(list) el = list; while (el)
{func(&context, el); el=el->next;} func(&context, NULL)}
but I prefer the first define as it allows transmission of a full
context to the iteration function.

 

my_struct * my_ctxt;

 

my_ctxt = NULL; grub_iterate_list(list, my_func, &my_ctxt);

 

void my_func (my_struct ** ctxt, my_item * item) {

      if (item == NULL) {

          /* End of iteration : Do any cleanup */

          if (*ctxt == NULL) return;

          free (*ctxt) ……

          …..

          return;

      }

      if (*ctxt == NULL) {

           /* First iteration : Do any initialization */

           *ctxt = malloc (sizeof (my_struct)); ….

           …..

}

/* Do the iteration stuff */

…..

return;

}

 

In grub_iterate_list_brk, you can use context to send a patern or model
object to compare each item of the list with.

 

The draw back is it makes iteration function a bit less readable, but a
lot more powerful.

                        

_________________________________________

Eric Salomé – Paris, France

 

-----Message d'origine-----
De : grub-devel-bounces+esalome=ctx.net@gnu.org
[mailto:grub-devel-bounces+esalome=ctx.net@gnu.org] De la part de
Guffens, Vincent
Envoyé : lundi 8 mai 2006 01:14
À : grub-devel@gnu.org
Objet : a simple list

 

Hi,

I need to use a simple list to register the pci devices, drivers and so
on. I notice that there are lists like that already in the code so what
would you think about having a list.h file like that ?

/* A very simple list.
 *
 * If you want a list of struct myitem
 * you do
 *
 * struct myitem *item_list;
 *
 * where myitem MUST have its next pointer as the FIRST field
 *
 * and you can then add, delete the EL item,
 * grub_add_list (&item_list, el);
 * grub_del_list (&item_list, el);
 *
 * or call HOOK(item) for each element of the list
 * grub_iterate_list (item_list, hook);
 *
 * This brk version will point el to the list item for which
 * HOOK(EL) returns a non-null value
 * grub_iterate_list_brk (item_list, hook, el);
 *
 */

struct obj {
  struct obj *next; /* MUST BE FIRST */
};

#define grub_del_list(list, el) _grub_del_list((struct obj**) list,
(struct obj*) el)
#define grub_add_list(list, el) _grub_add_list((struct obj**) list,
(struct obj*) el)
#define grub_find_list(list, el) \
  (typeof(list)) _grub_find_list((struct obj*) list, (struct obj*) el)
#define grub_iterate_list(list, func) \
  {typeof(list) el = list; while (el) {func(el); el=el->next;}}
#define grub_iterate_list_brk(list, func, it) \
  {typeof(list) el = list; it = 0; \
    while (el) {if (func(el)) {it = el; break;} el=el->next; }}

static inline struct obj*  _grub_find_list (struct obj *list, struct obj
*el)
{
  struct obj *it = list;
  for (it = list; it; it=it->next)
  {
    if (it == el) return el;
  }
  return 0;
};

static inline void _grub_add_list (struct obj **list, struct obj *el)
{
  if ( (!el) || (_grub_find_list (*list, el)) )
    return;
 
  el->next = *list;
  *list = el;
};

static inline void _grub_del_list (struct obj **list, struct obj *el)
{
  struct obj **p;
  struct obj *q;

  for (p = list, q = *p; q; p = &(q->next), q = q->next)
    if (q == el)
      {
        *p = q->next;
        break;
      }
};


[-- Attachment #2: Type: text/html, Size: 13334 bytes --]

Re: RE : a simple list

[vincent guffens]

Thank you for this information. Adding the concept of context is indeed
the right idea. I was doing it as follows

void function (grub_device_t dev)
{
 grub_device_t it;
 auto int look_for_dev (grub_device_t);

  int look_for_dev (grub_device_t grub_device_t other_dev)
  {
     return compare (dev, other_dev)
  }

grub_iterate_list_brk (grub_devices, look_for_dev, it);
}

but it has to be compared with something like

void function (grub_device_t dev)
{
  grub_device_t it = grub_devices;

  while (it)
  {
     if ( compare (dev, it) )
       break;
  }
}


which is obviously simpler. Maybe the only two functions that are really
needed are add and del ?

Also, I found out yesterday that
the compiler throws out warning about strict aliasing when using the
iterate function. I had to add -fno-strict-aliasing to get rid of them.



Eric Salomé wrote:
> Hi,
> 
> I didn’t take a good look at current iterate functions in Grub 2, yet.
> 
>  
> 
> Most iterations needs a “init” (before treatment of first item) and a
> “fini” (after treatment of last item).
> 
> Further more, one might want to make iteration functions “re-entrant”
> (or recursive), or call-back other functions in a generic way.
> 
>  
> 
> One way to get to such behavior easily cost a bit more than the example
> you provided : 
> 
> you may just add an argument (let’s call it the context object) to the
> call of the iterate function :
> 
>  
> 
> #define grub_iterate_list(list, func, context) \
>   {typeof(list) el = list; while (el) {func(context, el); el=el->next;}
> func(context, NULL)}
> or
> 
> #define grub_iterate_list(list, func) \
>   {void * context = NULL; typeof(list) el = list; while (el)
> {func(&context, el); el=el->next;} func(&context, NULL)}
> but I prefer the first define as it allows transmission of a full
> context to the iteration function.
> 
>  
> 
> my_struct * my_ctxt;
> 
>  
> 
> my_ctxt = NULL; grub_iterate_list(list, my_func, &my_ctxt);
> 
>  
> 
> void my_func (my_struct ** ctxt, my_item * item) {
> 
>       if (item == NULL) {
> 
>           /* End of iteration : Do any cleanup */
> 
>           if (*ctxt == NULL) return;
> 
>           free (*ctxt) ……
> 
>           …..
> 
>           return;
> 
>       }
> 
>       if (*ctxt == NULL) {
> 
>            /* First iteration : Do any initialization */
> 
>            *ctxt = malloc (sizeof (my_struct)); ….
> 
>            …..
> 
> }
> 
> /* Do the iteration stuff */
> 
> …..
> 
> return;
> 
> }
> 
>  
> 
> In grub_iterate_list_brk, you can use context to send a patern or model
> object to compare each item of the list with.
> 
>  
> 
> The draw back is it makes iteration function a bit less readable, but a
> lot more powerful.
> 
>                         
> 
> _________________________________________
> 
> Eric Salomé – Paris, France
> 
>  
> 
> -----Message d'origine-----
> De : grub-devel-bounces+esalome=ctx.net@gnu.org
> [mailto:grub-devel-bounces+esalome=ctx.net@gnu.org] De la part de
> Guffens, Vincent
> Envoyé : lundi 8 mai 2006 01:14
> À : grub-devel@gnu.org
> Objet : a simple list
> 
>  
> 
> Hi,
> 
> I need to use a simple list to register the pci devices, drivers and so
> on. I notice that there are lists like that already in the code so what
> would you think about having a list.h file like that ?
> 
> /* A very simple list.
>  *
>  * If you want a list of struct myitem
>  * you do
>  *
>  * struct myitem *item_list;
>  *
>  * where myitem MUST have its next pointer as the FIRST field
>  *
>  * and you can then add, delete the EL item,
>  * grub_add_list (&item_list, el);
>  * grub_del_list (&item_list, el);
>  *
>  * or call HOOK(item) for each element of the list
>  * grub_iterate_list (item_list, hook);
>  *
>  * This brk version will point el to the list item for which
>  * HOOK(EL) returns a non-null value
>  * grub_iterate_list_brk (item_list, hook, el);
>  *
>  */
> 
> struct obj {
>   struct obj *next; /* MUST BE FIRST */
> };
> 
> #define grub_del_list(list, el) _grub_del_list((struct obj**) list,
> (struct obj*) el)
> #define grub_add_list(list, el) _grub_add_list((struct obj**) list,
> (struct obj*) el)
> #define grub_find_list(list, el) \
>   (typeof(list)) _grub_find_list((struct obj*) list, (struct obj*) el)
> #define grub_iterate_list(list, func) \
>   {typeof(list) el = list; while (el) {func(el); el=el->next;}}
> #define grub_iterate_list_brk(list, func, it) \
>   {typeof(list) el = list; it = 0; \
>     while (el) {if (func(el)) {it = el; break;} el=el->next; }}
> 
> static inline struct obj*  _grub_find_list (struct obj *list, struct obj
> *el)
> {
>   struct obj *it = list;
>   for (it = list; it; it=it->next)
>   {
>     if (it == el) return el;
>   }
>   return 0;
> };
> 
> static inline void _grub_add_list (struct obj **list, struct obj *el)
> {
>   if ( (!el) || (_grub_find_list (*list, el)) )
>     return;
>  
>   el->next = *list;
>   *list = el;
> };
> 
> static inline void _grub_del_list (struct obj **list, struct obj *el)
> {
>   struct obj **p;
>   struct obj *q;
> 
>   for (p = list, q = *p; q; p = &(q->next), q = q->next)
>     if (q == el)
>       {
>         *p = q->next;
>         break;
>       }
> };
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel


-- 
		Vincent Guffens
		Intelligent Systems & Networks Group
		Research associate, Imperial College

RE : a simple list

[Eric Salomé]

Hi Vincent,

I picked up your email from the archive as I didn't received it yet.

As you see, it's very easy with a simple #define to create simple code
for simple cases and yet be powerful for more complex cases :
#define grub_iterate_list_brk(list, func, context, it) \
  {typeof(list) el = list; it = 0; \
    while (el) {if (func(context, el)) {it = el; break;} el=el->next; }}

that you can call with 

grub_iterate_list_brk(grub_devices, compare, dev, it);

with the simpliest compare function between two devices, and you get
in-line functions nearly as simpler as the one you wrote.

But let's try this :

item * grub_iterate_list_brk (item * start, 
		void * (*fct) (void * a, void * b), void * search) {
	while (start && fct(search, (void *) start)) start =
start->next;
	return start ? start : (item *) fct(search, NULL);
}

that you can call with :

it = (dev *) grub_iterate_list_brk((item *) grub_devices, 
				devcompare, device);

You are not in-lining functions (that makes the code smaller) and this
is a simple devcompare function to see how it works :

void * devcompare (dev * a, dev * b) {
	if (b == NULL) return NULL;
	if (a == NULL) return NULL;
	return (void *) strcmp (a->name, b->name);
}

Which is 3 line long but still is readable ... and yet powerful :

If (b == NULL) return NULL;
You have ended the list and didn't find a match ? grub_iterate_list_brk
let the compare function choose what it likes to return as a result :
Can be NULL (not found)
Can be a default value
Can be the "best" item picked out of the iteration process that matches
best the criteria; as you like :-)

If (a == NULL) return NULL;
What happens then ? if you call grub_iterate_list_brk with no criteria
(device == NULL), than it assumes you want any item and returns the
first item in the list. That's good behaviour and only a small overhead
in devcompare.

Return (void *) strcmp (a->name, b->name); 
Grub_iterate_list_brk return the item for which the compare function
returns 0 (or NULL), so that you can easily write :
Return (void *) (
	a->id - b->id
   || a->magic - b-> magic
   || strcmp(a->name, b->name) );

  
Is that what you were looking for ?

PS: Sorry folks for my previous emails sent in html : it sent lots of
useless blank lines for nothing.
________________________________________
Eric Salomé – Paris, France

From: 
vincent guffens
Subject: 
Re: RE : a simple list
Date: 
Tue, 09 May 2006 10:08:24 +0100
User-agent: 
Debian Thunderbird 1.0.7 (X11/20051017)

Thank you for this information. Adding the concept of context is indeed
the right idea. I was doing it as follows

void function (grub_device_t dev)
{
 grub_device_t it;
 auto int look_for_dev (grub_device_t);

  int look_for_dev (grub_device_t grub_device_t other_dev)
  {
     return compare (dev, other_dev)
  }

grub_iterate_list_brk (grub_devices, look_for_dev, it);
}

but it has to be compared with something like

void function (grub_device_t dev)
{
  grub_device_t it = grub_devices;

  while (it)
  {
     if ( compare (dev, it) )
       break;
  }
}


which is obviously simpler. Maybe the only two functions that are really
needed are add and del ?

Re: RE : a simple list

[vincent guffens]

Eric Salomé wrote:
> Hi Vincent,
> 
> I picked up your email from the archive as I didn't received it yet.
> 
> As you see, it's very easy with a simple #define to create simple code
> for simple cases and yet be powerful for more complex cases :
> #define grub_iterate_list_brk(list, func, context, it) \
>   {typeof(list) el = list; it = 0; \
>     while (el) {if (func(context, el)) {it = el; break;} el=el->next; }}
> 
> that you can call with 
> 
> grub_iterate_list_brk(grub_devices, compare, dev, it);
> 
> with the simpliest compare function between two devices, and you get
> in-line functions nearly as simpler as the one you wrote.
> 
> But let's try this :
> 
> item * grub_iterate_list_brk (item * start, 
> 		void * (*fct) (void * a, void * b), void * search) {
> 	while (start && fct(search, (void *) start)) start =
> start->next;
> 	return start ? start : (item *) fct(search, NULL);
> }
> 
> that you can call with :
> 
> it = (dev *) grub_iterate_list_brk((item *) grub_devices, 
> 				devcompare, device);

Thank you very, this is definitely interesting although I don't like
these explicit castings in the code, especially not the one to (item *).
But at the end of the day I think this is overkilled and the while (dev)
seems more appropriate for simple tasks like the one I need.