数据结构————内核链表

内核链表是Linux内核中广泛使用的一种数据结构，它具有以下特点：
  1.双向循环链表：每个节点包含两个指针，一个指向前驱节点（prev），另一个指向后继节点（next），形成一个闭环。
  2.结构封装：链表节点不直接包含数据。这样的设计使得同一个链表结构可以用于不同类型的数据节点。
  3.通用性：由于链表节点与数据分离，可以方便地将链表结构嵌入到各种数据结构中，提高了代码的复用性和灵活性。

 定义

内核链表是一种线性数据结构，其中每个节点包含了数据元素本身以及指向下一个节点的指针。在Linux内核中，这种链表通常被实现为双向链表或循环链表，以支持更高效的插入、删除和遍历操作。

节点结构

内核链表的节点通常包含至少两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。在某些实现中，还可能包含一个指向数据本身的指针，但在Linux内核的链表中，节点本身并不直接存储用户数据，而是将用户数据保存在包含链表节点的结构体中。

 链表头

链表头是一个特殊的节点，它通常不包含有效数据，但用于标识链表的开始位置。在双向链表中，链表头还可能包含指向链表最后一个节点的指针，以及一个指向链表第一个节点的指针。

单向链表	单向链表是最基本的链表结构，每个节点包含数据域和一个指向下一个节点的指针。它只能向前遍历，不能直接访问链表中的任意元素，需要从头开始遍历找到指定位置的节点。插入和删除操作的时间复杂度为 O(1)，但由于不能直接访问链表中的任意元素，因此在需要频繁访问链表中间节点的场景中效率较低。
双向链表	双向链表是每个节点包含数据域、一个指向前一个节点的指针和一个指向下一个节点的指针的链表。它可以向前和向后遍历，因此查找操作的时间复杂度为 O(1)。但是，双向链表的插入和删除操作需要更多的指针操作，时间复杂度较高。由于双向链表需要更多的存储空间来存储额外的指针，因此空间复杂度也较高。
内核链表	内核链表的链表节点不直接包含数据。这样的设计使得同一个链表结构可以用于不同类型的数据节点。 由于链表节点与数据分离，可以方便地将链表结构嵌入到各种数据结构中，提高了代码的复用性和灵活性。

 

内核链表的操作
1. 初始化

        在创建链表之前，需要先对链表头进行初始化。这通常包括设置链表头的指针为NULL（对于

单向链表）或指向自身（对于双向循环链表）。

typedef struct knode
{struct knode *ppre;struct knode *pnext;}Knode_t;typedef struct klink
{Knode_t *phead;int clen;pthread_mutex_t mutex;
}Klink_t;

2. 插入节点

        在链表中插入节点时，需要找到插入位置的前一个节点，并修改该节点和待插入节点的指

针。对于双向链表，还需要更新待插入节点的前驱指针。

int push_klink_head(Klink_t *pklink, void *p)
{Knode_t *pnode = (Knode_t *)p;pnode->pnext = NULL;pnode->ppre = NULL;pnode->pnext = pklink->phead;if (pklink->phead != NULL){pklink->phead->ppre = pnode;}pklink->phead = pnode;pklink->clen++;return 0;
}
int push_klink_tail(Klink_t *pklink,void *p)
{Knode_t *pnode = (Knode_t *)p;pnode->pnext =NULL;pnode->ppre =NULL;if(pklink->phead!=NULL){Knode_t *p = pklink->phead;while(p->pnext!=NULL){p=p->pnext;}p->pnext=pnode;pnode->ppre=p;}else if(pklink->phead==NULL){pklink->phead = pnode;}pklink->clen++;return 0;
}

3. 删除节点

        删除链表中的节点时，需要找到该节点的前一个节点和后一个节点，并修改它们的指针以绕

过被删除的节点。对于双向链表，还需要更新被删除节点的前驱指针的指向。

int pop_klink_head(Klink_t *pklink)
{if(pklink->phead ==NULL){return 0;}Knode_t *p = pklink->phead;pklink->phead = p->pnext;p->ppre = NULL;free(p);if(pklink->phead !=NULL){pklink->phead->ppre=NULL;}pklink->clen--;return 0;
}
int pop_klink_tail(Klink_t *pklink)
{if(pklink->phead==NULL){return 0;}Knode_t *p = pklink->phead;while(p->pnext != NULL){p=p->pnext;}if(p->ppre!= NULL){p->ppre->pnext=NULL;}else{pklink->phead = NULL;}free(p);pklink->clen--;return 0;
}

4. 遍历链表

        遍历链表通常从链表头开始，依次访问每个节点直到链表末尾。在双向链表中，可以从链表

头或链表尾开始遍历。

void klink_for_each(Klink_t *pklink, void (*pfun)(void *))
{Knode_t *pnode = pklink->phead;while (pnode != NULL){pfun(pnode);pnode = pnode->pnext;}printf("\n");
}

5.查找

KNode_t *find_klink(KLink_t *pklink, void *t, CMP_t pfun)
{KNode_t *pnode = pklink->phead;while (pnode != NULL){if (pfun(t, pnode)){return pnode;}pnode = pnode->pnext;}return NULL;
}

6.销毁

int is_empty_klink(KLink_t *pklink)
{return NULL == pklink->phead;
}
void destroy_klink(KLink_t *pklink)
{while (!is_empty_klink(pklink)){pop_klink_head(pklink);}free(pklink);
}