hello-list.c
C programming language is not very popular nowadays. I don't care. I like the language.
It was very interesting to learn how linked lists are implemented in the Linux kernel. This picture illustrates them nicely:
A custom structure - the type of objects you want to enlist - contains `struct list_head' as its member. This is not a pointer (that's the point) and you can place it anywhere (!) within the structure (i.e., it doesn't have to be the first member).
You use list_head members for list operations (insertion, deletion, iteration, etc.; all the nice stuff defined in linux/list.h). And when you need the rest of your data structure - you use `list_entry' macro. `list_entry' fetches a pointer to the container object from its `struct list_head' member.
This is my "hello world" program (skip down to `struct Char' and `main' function):
#include #include #include /* * List operations are copied from ; * see <http://lxr.linux.no/#linux+v2.6.33/include/linux/list.h>. * * See also <http://www.xml.com/ldd/chapter/book/ch10.html#t5>, * there is a nice picture. */ struct list_head { struct list_head *next, *prev; }; #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { next->prev = new; new->next = next; new->prev = prev; prev->next = new; } /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); } /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. * * NOTE: This definition differs from the one in . */ #define list_entry(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) /** * __list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. * * This variant differs from list_for_each() in that it's the * simplest possible list iteration code, no prefetching is done. * Use this for code that knows the list to be very short (empty * or 1 entry) most of the time. */ #define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) /* ------------------------------------------------------------------ */ /* Custom data type. */ struct Char { char value; struct list_head _; }; static struct Char * new_Char(char c) { struct Char *x = malloc(sizeof(struct Char)); INIT_LIST_HEAD(&x->_); x->value = c; return x; } int main(void) { LIST_HEAD(xs); { /* Populate a list with allocated Chars */ const char *p; for (p = "Hello, world!"; *p != 0; ++p) list_add_tail(&new_Char(*p)->_, &xs); } { /* Print */ const struct list_head *p; __list_for_each(p, &xs) putchar(list_entry(p, struct Char, _)->value); putchar('\n'); } { /* Free allocated memory */ const struct list_head *p = xs.next; while (p != &xs) { void *x = list_entry(p, struct Char, _); p = p->next; free(x); } INIT_LIST_HEAD(&xs); } return 0; }
See also:
- Linux Kernel Linked List Explained
- linux/list.h
- `Linked Lists' section in `Linux Device Drivers' book (that's where the helpful illustration comes from)