2009年9月21日 星期一

linux之link list


linux的code算是經過高手中的高手淬煉過的精華,應該是每一個programmer朝聖取經的對象才是,所以,近日想由簡單的一些header file著手,先挑了link-list(linux/list.h)開始看起。list.h開頭就說明了這個檔案是Simple doubly linked list implementation。 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; } struct list_head宣告兩個指向struct list_head的指標,這樣可以很general的對任何struct做link-list的動作,而list.h所提供的api也都是對struct list_head進行操作。 LIST_HEAD_INIT(name)是用於還沒有宣告的做init的動作,主要是將prev和next都指向自己。LIST_HEAD(name)其實和LIST_HEAD_INIT(name)差不多,也都是用來init link_head的。已經宣告過的則要使用INIT_LIST_HEAD(struct list_head *list)做init。 在list.h中有使用到一個重要的macro,container_of(ptr, type, member), /** * container_of cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) 而offsetof在C99的offsetof macro中有提到。所以container_of()就可以看出先宣告__mptr,其型態為傳進來的member,其值為傳進來的ptr,接著再扣除member所在的offset,就可以找到原本的頭了。 /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ 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 - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */ static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } /** * 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); } /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add_rcu(struct list_head * new, struct list_head * prev, struct list_head * next) { new->next = next; new->prev = prev; smp_wmb(); next->prev = new; prev->next = new; } /** * list_add_rcu - add a new entry to rcu-protected list * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. * * The caller must take whatever precautions are necessary * (such as holding appropriate locks) to avoid racing * with another list-mutation primitive, such as list_add_rcu() * or list_del_rcu(), running on this same list. * However, it is perfectly legal to run concurrently with * the _rcu list-traversal primitives, such as * list_for_each_entry_rcu(). */ static inline void list_add_rcu(struct list_head *new, struct list_head *head) { __list_add_rcu(new, head, head->next); } /** * list_add_tail_rcu - add a new entry to rcu-protected list * @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. * * The caller must take whatever precautions are necessary * (such as holding appropriate locks) to avoid racing * with another list-mutation primitive, such as list_add_tail_rcu() * or list_del_rcu(), running on this same list. * However, it is perfectly legal to run concurrently with * the _rcu list-traversal primitives, such as * list_for_each_entry_rcu(). */ static inline void list_add_tail_rcu(struct list_head *new, struct list_head *head) { __list_add_rcu(new, head->prev, head); } list_add_tail()可以想像把新的加到head的前面,就等於加到最後面了(因為是doubly linked list)。 /* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } /** * list_del - deletes entry from list. * @entry: the element to delete from the list. * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */ static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } 看到後面的delete就簡單了,先把自己的前後node接起來,接著再把自己的指標指向特殊位置(我的認知應該是給kernel debug用的特別位置),這樣就完成了delete的動作,所謂的delete並沒有真的是放記憶體唷。

沒有留言:

張貼留言

熱門文章