顯示具有 Linux - kernel - DS 標籤的文章。 顯示所有文章
顯示具有 Linux - kernel - DS 標籤的文章。 顯示所有文章

2009年9月27日 星期日

linux - hlist


一樣在include/linux/list.h中,開宗明義的說Mostly useful for hash tables where the two pointer list head is too wastful,點出hlist為啥要有hlist_head和hlist_node了。
/* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is * too wasteful. * You lose the ability to access the tail in O(1). */ struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; #define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; } HLIST_HEAD_INIT()和HLIST_HEAD()用於未定義的變數,INIT_HLIST_HEAD()用於以定義的變數。

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; if (first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; } /* next must be != NULL */ static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next) { n->pprev = next->pprev; n->next = next; next->pprev = &n->next; *(n->pprev) = n; } static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *next) { next->next = n->next; n->next = next; next->pprev = &n->next; if(next->next) next->next->pprev = &next->next; } hlist_add_head()就很是很簡單的將n加到h的第一個node上。

hlist_add_after()是將next加到n的後面去,這裡新加入的node是next

hlist_add_before()是將n加到next的前面去,這裡新加入的node則是n


static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; } __hlist_del()就像__list_del()一樣,把要del的node的前後串起來。



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並沒有真的是放記憶體唷。