Linux内核中链表和散列表的达成原理揭秘
发布时间：2021-11-25 20:50:06 所属栏目：教程 来源：互联网
导读：Linux内核的实现，大量使用了数据结构，包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表，简单而高效，使用方法也非常的别具一格。 研究Linux内核的链表和散列表对于看懂Linux内核源代码有重要的意义。本
|
Linux内核的实现，大量使用了数据结构，包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表，简单而高效，使用方法也非常的别具一格。 研究Linux内核的链表和散列表对于看懂Linux内核源代码有重要的意义。本文基于kernel2.6.39版本进行分析。 Linux的链表和散列表定义在include/linux/types.h文件中 structlist_head { 223 struct list_head *next, *prev; 224}; 225 226structhlist_head { 227 struct hlist_node *first; 228}; 229 230structhlist_node { 231 struct hlist_node *next, **pprev; 232}; 233 list_head就是使用最为广泛的双向循环链表。这个数据结构可以说是LinuxKernel的基石，大量内核源代码使用了这个数据结构。 hlist_head和hlist_node常常用于散列表中。 Linux的链表和散列表的操作函数的定义在include/linux/list.h文件中 初始化双向循环链表，只有一个元素的双向循环链表，next和prev指向自身。 staticinline voidINIT_LIST_HEAD(structlist_head *list) 25{ 26list->next = list; 27list->prev = list; 28} 29 初始化散列表的链表。 空的散列表链表的first==NULL。每一个散列表链表的元素初始化时next和pprev指针都是NULL，而不是指向自身。 我们可以看到，散列表链表hlist_node虽然和双向循环链表list_head一样，都有两个指针，但有本质的区别。 散列表链表hlist_node不是循环链表。它有头和尾，是单向的链表。 散列表链表hlist_node之所以有两个指针，是为了提高插入和删除链表的效率。hlist_node的插入，只需要一个相邻的hlist_head或者hlist_node节点即可。它的删除，只需要它本身即可定位其相邻的前后两个元素。 570 571#defineHLIST_HEAD_INIT { .first =NULL } 572#defineHLIST_HEAD(name) struct hlist_headname = { .first =NULL } 573#defineINIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 574staticinline voidINIT_HLIST_NODE(structhlist_node *h) 575{ 576h->next = NULL; 577h->pprev = NULL; 578} 579 脱离链表的元素的状态 staticinline void__list_add(structlist_head *new, 38 struct list_head *prev, 39 struct list_head *next) 40{ 41next->prev = new; 42new->next = next; 43new->prev = prev; 44prev->next = new; 45} 46 /* 80* Delete a list entry by making the prev/next entries 81* point to each other. 82* 83* This is only for internal list manipulation where we know 84* the prev/next entries already! 85*/ 86staticinline void__list_del(structlist_head *prev, structlist_head *next) 87{ 88next->prev = prev; 89prev->next = next; 90} 91 92/** 93* list_del - deletes entry from list. 94* @entry: the element to delete from the list. 95* Note: list_empty() on entry does not return true after this, the entry is 96* in an undefined state. 97*/ 98#ifndefCONFIG_DEBUG_LIST 99staticinline void__list_del_entry(structlist_head *entry) 100{ 101__list_del(entry->prev,entry->next); 102} 103 104staticinline voidlist_del(structlist_head *entry) 105{ 106__list_del(entry->prev,entry->next); 107entry->next = LIST_POISON1; 108entry->prev = LIST_POISON2; 109} 110#else 散列表链表的脱离链表代码： 90staticinline void__hlist_del(structhlist_node *n) 591{ 592 struct hlist_node *next = n->next; 593 struct hlist_node **pprev = n->pprev; 594 *pprev =next; 595 if (next) 596next->pprev = pprev; 597} 598 599staticinline voidhlist_del(structhlist_node *n) 600{ 601__hlist_del(n); 602n->next = LIST_POISON1; 603n->pprev = LIST_POISON2; 604} 605 看看LIST_POISON1和LIST_POISON2是何方神圣。 16 17/* 18* These are non-NULL pointers that will result in page faults 19* under normal circumstances, used to verify that nobody uses 20* non-initialized list entries. 21*/ 22#defineLIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA) 23#defineLIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA) 24 表示链表元素是未初始化的，既不在链表中，也没有经过初始化，不应该使用。  （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
