List.h部分函数

初始化操作

  • 首先,向函数内部传入链表头节点

  • 在函数中,使头节点的pre以及next指针指向头节点 ,即 next = pre = head

  • 参考代码

    static inline void list_init(ListHead *list) {
    list->prev = list->next = list;
    }
  • 效果图

判断空操作

  • 首先,向函数内部传入链表头节点

  • 在函数中,判断头节点是否与它的其中一个指针分量值相同,若相同,则返回true,否则返回false

  • 参考代码

    static inline boolean list_empty(ListHead *list) {
    return list == list->next;
    }

向头节点后部添加节点操作

  • 首先,向函数内部传入链表头节点以及要插入节点的listhead分量指针

  • 在函数中调用List_add()函数

    • 第一个参数为链表头节点指针
    • 第二参数为链表头节点下一个节点的指针
    • 第三个参数为待插入节点的listhead分量指针
  • 接下来分析List_add()函数

    • 首先判断待插入节点的listhead分量指针是否为空,如果为空,则退出程序,否则,执行以下步骤

    • 在这里 参数 pre = head next = head->next data为待插入节点的listhead分量指针

      (第一次插入 其实质为 next = pre = head , 第i次插入其实质为 pre = head next = 上一个插入节点的listhead分量指针)

    • 首先,待插入节点的listhead分量指针的pre分量设置成pre参数值

    • 待插入节点的listhead分量指针的next分量设置成next参数值

    • 最后,设置参数pre的next等于data,数next的pre等于data

  • 参考代码

    static inline void list_add_after(ListHead *list, ListHead *data) {
    list_add(list, list->next, data);
    }
    static inline void list_add(ListHead *prev, ListHead *next, ListHead *data) {
    assert(data != NULL); //报错&&终止程序!
    data->prev = prev;
    data->next = next;
    if (prev != NULL) prev->next = data;
    if (next != NULL) next->prev = data;
    }
  • 只插一个节点的效果图

  • 插两个节点的过程图

  • 插两个节点的效果图

向头节点前部添加节点操作

  • 在这里,我们只需比较传入List_add()函数参数就可以了

  • 在list_after函数中, pre = 头节点地址 next = 头节点的后继节点地址 data为待插入节点的listhead分量指针

    而在list_before函数中,pre = 头节点的前驱节点地址 next = 头节点地址 data为待插入节点的listhead分量指针

  • 参考代码

    static inline voidlist_add_before(ListHead *list, ListHead *data) {
    list_add(list->prev, list, data);
    }
    static inline void list_add(ListHead *prev, ListHead *next, ListHead *data) {
    assert(data != NULL); //报错&&终止程序!
    data->prev = prev;
    data->next = next;
    if (prev != NULL) prev->next = data;
    if (next != NULL) next->prev = data;
    }
  • 只插一个节点的效果图

  • 插两个节点的过程图

  • 插两个节点的效果图

删除链表中节点操作

  • 我们只需向list_del()函数中传入要删除节点的指针

  • 首先,我们需要判断是否删除的指针为空,如果为空,则直接报错退出,否则,进行下一步

  • 接下来,我们设置两个指针保护要删除节点的前驱节点(pre)地址以及后继节点(next)地址

  • 最后我们先判断pre以及next是否为空,如果为空,无需任何操作,否则,将

    前驱节点(pre)的后继节点指针next设置为后继节点next

    后继节点(next)的前驱节点指针pre设置为前驱节点pre

  • 参考代码

    static inline void list_del(ListHead *data) {
    assert(data != NULL);
    ListHead *prev = data->prev;
    ListHead *next = data->next;
    if (prev != NULL) prev->next = next;
    if (next != NULL) next->prev = prev;
    }
  • 删除节点过程图

  • 删除节点效果图

获取结构体起始指针

  • 0x0地址强制转换为type *类型,然后取type中的成员member地址,因为起始地址为0,得到的member的地址就直接是该成员相对于type对象的偏移地址了。

  • 所以该语句的功能是:得到type类型对象中member成员的地址偏移量。
    先将ptr强制转换为char *类型(因为char *类型进行加减的话,加减量为sizeof(char)*offsetchar占一个字节空间,这样指针加减的步长就是1个字节,实现加一减一。)

  • 整句话的意思就是:得到指向type的指针,已知成员的地址,然后减去这个成员相对于整个结构对象的地址偏移量,得到这个数据对象的地址。

  • 参考代码

    #define list_entry(ptr, type, member) \
    ((type*)((char*)(ptr) - (int)(&((type*)0)->member)))
  • 解析图

函数测试

说明:构造一个基于list.h的链表模拟进程切换程序

解析

  • 首先初始化链表
  • 之后依次向链表插入三个节点(进程的linklist指针)
  • 接下来模拟进程的切换,边切换进程同时对链表进行节点删除以及节点前插

示意图

  • 首先初始化链表,之后依次向链表插入三个节点(进程的linklist指针)

  • 边切换进程同时对链表进行节点删除以及节点前插

参考代码

  • list.h

    #ifndef __LIST_H__
    #define __LIST_H__
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<unistd.h>
    #include<assert.h>
    typedef enum { true=0, false} boolean;
    struct ListHead {
    struct ListHead *prev, *next;
    };
    typedef struct ListHead ListHead;

    #define list_entry(ptr, type, member) \
    ((type*)((char*)(ptr) - (int)(&((type*)0)->member)))

    static inline void
    list_add(ListHead *prev, ListHead *next, ListHead *data) {
    assert(data != NULL);
    data->prev = prev;
    data->next = next;
    if (prev != NULL) prev->next = data;
    if (next != NULL) next->prev = data;
    }

    static inline void
    list_add_before(ListHead *list, ListHead *data) {
    list_add(list->prev, list, data);
    }

    static inline void
    list_add_after(ListHead *list, ListHead *data) {
    list_add(list, list->next, data);
    }

    static inline void
    list_del(ListHead *data) {
    assert(data != NULL);
    ListHead *prev = data->prev;
    ListHead *next = data->next;
    if (prev != NULL) prev->next = next;
    if (next != NULL) next->prev = prev;
    }

    static inline void
    list_init(ListHead *list) {
    list->prev = list->next = list;
    }

    static inline boolean
    list_empty(ListHead *list) {
    return list == list->next;
    }

    #define list_foreach(ptr, head) \
    for ((ptr) = (head)->next; (ptr) != (head); (ptr) = (ptr)->next)

    #endif
  • test.h

    #include "list.h"
    #define KSTACKSIZE 1024
    #define NR_PROC 64
    enum proc_state{UNUSED=0,RUNNABLE,RUNNING,BLOCKED,STOPED};
    struct task_struct{
    pid_t pid;
    char name[20];
    enum proc_state state;
    ListHead linklist;
    };
    void meun();
  • main.c

     #include "test.h"
    void meun(void){
    printf("1.初始化就绪队列\n");
    printf("2.插入进程\n");
    printf("3.循环遍历进程\n");
    printf("4.结束程序\n");
    }
    int main(void){
    int nextpid = 0 , order = 0 , flag = 1;
    ListHead RunableList; //就绪队列
    struct task_struct task[NR_PROC];//进程表
    struct task_struct *current;
    while(flag){
    //input
    while(1){
    meun();
    int r = scanf("%d",&order);
    if(!r || order < 1 || order > 4) {printf("please input again\n");}
    else {break;}
    }
    switch(order){
    case 1 : {
    int i = 0;
    list_init(&RunableList);
    for(i = 0 ; i < NR_PROC ; ++i) {task[i].state = UNUSED;}
    current = &task[0];
    current->pid = nextpid++;
    current->state = RUNNING;
    strcpy(current->name,"idle");
    break;
    }
    case 2 : {
    struct task_struct *data ;
    int i = 1 ;
    for(i=1; i < NR_PROC;i++){
    if(task[i].state == 0) {data = &task[i]; break;} }
    printf("输入进程名\n");
    scanf("%s",data->name);
    data->pid = nextpid++;
    data->state = RUNNABLE;
    list_add_after(&RunableList, &data->linklist);
    break;
    }

    case 3 : {
    int cnt = 0 ;
    while(1){
    struct task_struct *p;
    if(current->pid != 0){current->state = RUNNABLE; list_add_before(&RunableList,&current->linklist);}
    p=list_entry (RunableList.next,struct task_struct,linklist);
    p->state = RUNNABLE;
    printf("%d..%s..",p->pid,p->name);
    list_del(&p->linklist);
    current =p;
    ++cnt;
    if(cnt == 15) {break;}
    }
    printf("\n");
    break;
    }
    case 4 : {
    printf("the program is stoping...");
    flag = 0;
    sleep(1);
    break;
    }
    }
    }
    return 0 ;
    }

运行截图

谢谢访问