当前位置：首页 > news >正文

内核链表

news 来源：原创 2024/9/19 10:03:12

一、特性

内核链表：双向循环有头链表

组成：将链表的结点作为结构体成员存在，只放指向前驱结点和后继结点的指针

offsetof 获取结构体中的成员到结构体开头中的偏移量

container_of通过偏移量获取结构体首地址

但应用层不能使用上述两个宏，处理方法：将节点作为结构体第一个成员（结构体第一个成员首地址为结构体的地址）

注：结点将作为结点保存在结构体中，不能定义为指针。

二、内核链表使用示例：

klink.h

#ifndef __KLINK_H__
#define __KLINK_H__#include <pthread.h>typedef int (*CMP_t)(void *, void *);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;extern int push_klink_head(KLink_t *pklink, void *p);
extern KLink_t *create_klink();
extern void klink_for_each(KLink_t *pklink, void (*pfun)(void *));
extern KNode_t *find_klink(KLink_t *pklink, void * t, CMP_t pfun);
extern int pop_klink_head(KLink_t *pklink);
extern int is_empty_klink(KLink_t *pklink);
extern void destroy_klink(KLink_t *pklink);#endif

link.c

#include "klink.h"
#include <stdio.h>
#include <stdlib.h>KLink_t *create_klink()
{KLink_t *pklink = malloc(sizeof(KLink_t));if (NULL == pklink){perror("fail malloc");return NULL;}pklink->phead = NULL;pklink->clen = 0;pthread_mutex_init(&(pklink->mutex), NULL);return pklink;
}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;
}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");
}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;
}int is_empty_klink(KLink_t *pklink)
{return NULL == pklink->phead;
}int pop_klink_head(KLink_t *pklink)
{if (is_empty_klink(pklink))return 0;KNode_t *pdel = pklink->phead;pklink->phead = pdel->pnext;if (pklink->phead != NULL){pklink->phead->ppre = NULL;}free(pdel);pklink->clen--;return 1;
}void destroy_klink(KLink_t *pklink)
{while (!is_empty_klink(pklink)){pop_klink_head(pklink);}free(pklink);
}

flight.c

#include "flight.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct passager *create_passager(char *name, int flt_num, int sit_num, char card)
{struct passager *p = malloc(sizeof(struct passager));if (NULL == p){perror("fail malloc");return NULL;}strcpy(p->name, name);p->flt_num = flt_num;p->sit_num = sit_num;p->card = card;return p;
}void print_passager(void *pnode)
{struct passager *p = (struct passager *)pnode;printf("%s %d %d %c\n", p->name, p->flt_num, p->sit_num, p->card);
}struct flight *create_flight(int flt_num, char *src, char *dst)
{struct flight *f = malloc(sizeof(struct flight));if (NULL == f){perror("fail malloc");return NULL;}f->flt_num = flt_num;strcpy(f->src, src);strcpy(f->dst, dst);return f;
}void print_flight(void *pnode)
{struct flight *f = (struct flight *)pnode;printf("%d %s %s\n", f->flt_num, f->src, f->dst);
}int compare_by_card(void *t, void *pnode)
{struct passager *p = (struct passager *)pnode;if (p->card == *((char *)t)){return 1;}return 0;
}

flight.h

#ifndef __FLIGHT_H__
#define __FLIGHT_H__#include "klink.h"struct passager
{KNode_t node;char name[64];int flt_num;int sit_num;char card;
};struct flight
{KNode_t node;int flt_num;char src[64];char dst[32];
};extern struct passager *create_passager(char *name, int flt_num, int sit_num, char card);
extern void print_passager(void *pnode);
extern struct flight *create_flight(int flt_num, char *src, char *dst);
extern void print_flight(void *pnode);
extern int compare_by_card(void *t, void *pnode);#endif

main.c

#include "klink.h"
#include "flight.h"
#include <stdio.h>int main(int argc, const char *argv[])
{KLink_t *ppasslink = create_klink();	if (NULL == ppasslink){return -1;}struct passager *ppass = create_passager("zhangsan", 2024, 1, 'r');push_klink_head(ppasslink, ppass);ppass = create_passager("lisi", 2024, 2, 'g');push_klink_head(ppasslink, ppass);ppass = create_passager("wanger", 2024, 3, 'y');push_klink_head(ppasslink, ppass);klink_for_each(ppasslink, print_passager);char card = 'r';KNode_t *ptmp = find_klink(ppasslink, &card, compare_by_card);if (ptmp != NULL){print_passager(ptmp);}KLink_t *pfltlink = create_klink();if (NULL == pfltlink){return -1;}