Spiegazione della lista concatenata del kernel Linux

Introduzione:

1. Ovvieta' dei Tipi:
   Questa lista puo' essere usata per allineare qualsiasi struttura dati si abbia in mente.
2. Portabile:
   Sebbene non sia stata provata su ogni piattafrma si presume che l'implementazione della lista sia molto portabile. Altrimenti non sarebbe stata inserita nei sorgenti del kernel.
3. Facile da usare:
   Dal momento che la lista ha tipi ovii come le stesse funzioni che sono in uso per inizializzare, accedere, e scorrere qualsiasi elemento disposto nella lista caricato coll'utilizzo dell'implementazione stessa.
4. Leggibile:
   Le macro e le funzioni dell'implementazione della lista fanno il codice risultante molto elegante e leggibile.
5. Risparmia tempo:
   Non reinvetare la ruota. Usando la lista veramente si risparmia molto tempo nell'attivita' di debug e nella ripetitivita' della creazione di liste per ciascuna struttura dati si ha bisogno di collegare.

struct my_list{
	void *myitem;
	struct my_list *next;
	struct my_list *prev;
	};

struct my_cool_list{
	struct list_head list; /* kernel's list structure */
	int my_cool_data;
	void* my_cool_void;
	};

1. La lista e' dentro l'elemento dati che si vuole concatenare.
2. Si puo' inserire struct list_head dovunque nella propria struttura.
3. Si puo' chiamare struct list_head qualsiasi variabile si vuole.
4. Si possono avere liste multiple!

struct todo_tasks{
	char *task_name;
	unsigned int name_len;
	short int status;

	int sub_tasks;

	int subtasks_completed;
	struct list_head completed_subtasks;/* list structure */

	int subtasks_waiting;
	struct list_head waiting_subtasks; 	/* another list of same or different items! */

	struct list_head todo_list;			/* list of todo_tasks */
	};

• include/linux/fs.h:362
• include/linux/fs.h:429

struct list_head{
	struct list_head *next;
	struct list_head *prev;
	}

Usare la Lista:

#include <stdio.h>
#include <stdlib.h>

#include "list.h"


struct kool_list{
	int to;
	struct list_head list;
	int from;
	};

int main(int argc, char **argv){

	struct kool_list *tmp;
	struct list_head *pos, *q;
	unsigned int i;

	struct kool_list mylist;
	INIT_LIST_HEAD(&mylist.list);
	/* or you could have declared this with the following macro
	 * LIST_HEAD(mylist); which declares and initializes the list
	 */

	/* adding elements to mylist */
	for(i=5; i!=0; --i){
		tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
		
		/* INIT_LIST_HEAD(&tmp->list); 
		 *
		 * this initializes a dynamically allocated list_head. we
		 * you can omit this if subsequent call is add_list() or 
		 * anything along that line because the next, prev
		 * fields get initialized in those functions.
		 */
		printf("enter to and from:");
		scanf("%d %d", &tmp->to, &tmp->from);

		/* add the new item 'tmp' to the list of items in mylist */
		list_add(&(tmp->list), &(mylist.list));
		/* you can also use list_add_tail() which adds new items to
		 * the tail end of the list
		 */
	}
	printf("\n");


	/* now you have a circularly linked list of items of type struct kool_list.
	 * now let us go through the items and print them out
	 */


	/* list_for_each() is a macro for a for loop. 
	 * first parameter is used as the counter in for loop. in other words, inside the
	 * loop it points to the current item's list_head.
	 * second parameter is the pointer to the list. it is not manipulated by the macro.
	 */
	printf("traversing the list using list_for_each()\n");
	list_for_each(pos, &mylist.list){

		/* at this point: pos->next points to the next item's 'list' variable and 
		 * pos->prev points to the previous item's 'list' variable. Here item is 
		 * of type struct kool_list. But we need to access the item itself not the 
		 * variable 'list' in the item! macro list_entry() does just that. See "How
		 * does this work?" below for an explanation of how this is done.
		 */
		 tmp= list_entry(pos, struct kool_list, list);

		 /* given a pointer to struct list_head, type of data structure it is part of,
		  * and it's name (struct list_head's name in the data structure) it returns a
		  * pointer to the data structure in which the pointer is part of.
		  * For example, in the above line list_entry() will return a pointer to the
		  * struct kool_list item it is embedded in!
		  */

		 printf("to= %d from= %d\n", tmp->to, tmp->from);

	}
	printf("\n");
	/* since this is a circularly linked list. you can traverse the list in reverse order
	 * as well. all you need to do is replace 'list_for_each' with 'list_for_each_prev'
	 * everything else remain the same!
	 *
	 * Also you can traverse the list using list_for_each_entry() to iterate over a given
	 * type of entries. For example:
	 */
	printf("traversing the list using list_for_each_entry()\n");
	list_for_each_entry(tmp, &mylist.list, list)
		 printf("to= %d from= %d\n", tmp->to, tmp->from);
	printf("\n");
	

	/* now let's be good and free the kool_list items. since we will be removing items
	 * off the list using list_del() we need to use a safer version of the list_for_each() 
	 * macro aptly named list_for_each_safe(). Note that you MUST use this macro if the loop 
	 * involves deletions of items (or moving items from one list to another).
	 */
	printf("deleting the list using list_for_each_safe()\n");
	list_for_each_safe(pos, q, &mylist.list){
		 tmp= list_entry(pos, struct kool_list, list);
		 printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
		 list_del(pos);
		 free(tmp);
	}

	return 0;
}

Come funziona?

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

	((struct kool_list *)((char *)(pos) - (unsigned long)(&((struct kool_list *)0)->list)))

(unsigned long)(&((struct foo_bar *)0)->boo)

#include <stdio.h>
#include <stdlib.h>

struct foobar{
	unsigned int foo;
	char bar;
	char boo;
};

int main(int argc, char** argv){

	struct foobar tmp;

	printf("address of &tmp is= %p\n\n", &tmp);
	printf("address of tmp->foo= %p \t offset of tmp->foo= %lu\n", &tmp.foo, (unsigned long) &((struct foobar *)0)->foo);
	printf("address of tmp->bar= %p \t offset of tmp->bar= %lu\n", &tmp.bar, (unsigned long) &((struct foobar *)0)->bar);
	printf("address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n", &tmp.boo, (unsigned long) &((struct foobar *)0)->boo);

	printf("computed address of &tmp using:\n");
	printf("\taddress and offset of tmp->foo= %p\n",
	      (struct foobar *) (((char *) &tmp.foo) - ((unsigned long) &((struct foobar *)0)->foo)));
	printf("\taddress and offset of tmp->bar= %p\n",
	      (struct foobar *) (((char *) &tmp.bar) - ((unsigned long) &((struct foobar *)0)->bar)));
	printf("\taddress and offset of tmp->boo= %p\n",
	      (struct foobar *) (((char *) &tmp.boo) - ((unsigned long) &((struct foobar *)0)->boo)));

	return 0;
}

address of &tmp is= 0xbfffed00

address of tmp->foo= 0xbfffed00   offset of tmp->foo= 0
address of tmp->bar= 0xbfffed04   offset of tmp->bar= 4
address of tmp->boo= 0xbfffed05   offset of tmp->boo= 5

indirizzo calcolato di &tmp using:
address and offset of tmp->foo= 0xbfffed00
address and offset of tmp->bar= 0xbfffed00
address and offset of tmp->boo= 0xbfffed00

Vedere anche

• Si prega di dare un'occhiata alla tabella hash che usa la lista concatenata.
• /sutff/src/ per il codice sorgente

TODO

• Figura per spiegare list_entry() meglio
• Consegnare la C Data Structures Library (CDSL) che contiene le hashtable, map ecc. per le recenzioni dei colleghi. Pensarla come l'equivalente C di Java.Util. Sintassi pulita, strutture dati preimpacchetate per rendere la propria vita col C piu' semplice!