GeekOS学习(8)链表操作宏

柔情只为你懂 2022-06-13 12:50 135阅读 0赞

这种手法，第一次见到。

一个宏里面定义了多个内联函数。。不知如何称呼。

不过宏只不过是原样替代。其实就是定义了很多个内联函数，但是两函数之间没有打回车，所有函数都在一行上完成。

把代码贴上，注释都在代码上了，看一下就懂了。

位于./include/geekos/list.h

/*
     * Generic list data type
     * Copyright (c) 2001,2004 David H. Hovemeyer <daveho@cs.umd.edu>
     * $Revision: 1.16 $
     * 
     * This is free software.  You are permitted to use,
     * redistribute, and modify it as specified in the file "COPYING".
     */
    
    #ifndef GEEKOS_LIST_H//避免重复定义
    #define GEEKOS_LIST_H
    
    #include <geekos/ktypes.h>
    #include <geekos/kassert.h>
    
    /*
     * Define a list type.定义一个list表类型，list类型包含2个节点node类型的指针
     */
    #define DEFINE_LIST(listTypeName, nodeTypeName)		\
    struct listTypeName {					\
        struct nodeTypeName *head, *tail;			\
    }
    
    /*
     * Define members of a struct to be used as link fields for
     * membership in given list type.定义两个node类型的指针，用于链接。
     */
    #define DEFINE_LINK(listTypeName, nodeTypeName) \
        struct nodeTypeName * prev##listTypeName, * next##listTypeName
    
    /*
     * Define inline list manipulation and access functions.
     */
    #define IMPLEMENT_LIST(LType, NType)								\
    static __inline__ void Clear_##LType(struct LType *listPtr) {					\
        listPtr->head = listPtr->tail = 0;								\
    }清空list											\
    static __inline__ bool Is_Member_Of_##LType(struct LType *listPtr, struct NType *nodePtr) {	\
        struct NType *cur = listPtr->head;								\
        while (cur != 0) {链表最后一个节点的next指针是0							\
    	if (cur == nodePtr)									\
    	    return true;									\
    	cur = cur->next##LType;									\
        }												\
        return false;										\
    }从链表头开始搜索节点node是否存在，存在返回true，不存在返回false						\
    static __inline__ struct NType * Get_Front_Of_##LType(struct LType *listPtr) {			\
        return listPtr->head;									\
    }返回链表的第一个元素的指针										\
    static __inline__ struct NType * Get_Back_Of_##LType(struct LType *listPtr) {			\
        return listPtr->tail;									\
    }返回链表的最后一个元素的指针									\
    static __inline__ struct NType * Get_Next_In_##LType(struct NType *nodePtr) {			\
        return nodePtr->next##LType;								\
    }返回节点的next值										\
    static __inline__ void Set_Next_In_##LType(struct NType *nodePtr, struct NType *value) {	\
        nodePtr->next##LType = value;								\
    }设置节点next的值											\
    static __inline__ struct NType * Get_Prev_In_##LType(struct NType *nodePtr) {			\
        return nodePtr->prev##LType;								\
    }返回节点prev的值											\
    static __inline__ void Set_Prev_In_##LType(struct NType *nodePtr, struct NType *value) {	\
        nodePtr->prev##LType = value;								\
    }设置节点prev的值											\
    static __inline__ void Add_To_Front_Of_##LType(struct LType *listPtr, struct NType *nodePtr) {	\
        KASSERT(!Is_Member_Of_##LType(listPtr, nodePtr));节点必须是一个新的节点，不能重复添加		\
        nodePtr->prev##LType = 0;首节点无先驱节点							\
        if (listPtr->head == 0) {链表为空								\
    	listPtr->head = listPtr->tail = nodePtr;						\
    	nodePtr->next##LType = 0;								\
        } else {成为首节点										\
    	listPtr->head->prev##LType = nodePtr;							\
    	nodePtr->next##LType = listPtr->head;							\
    	listPtr->head = nodePtr;								\
        }												\
    }令节点node成为链表的头节点										\
    static __inline__ void Add_To_Back_Of_##LType(struct LType *listPtr, struct NType *nodePtr) {	\
        KASSERT(!Is_Member_Of_##LType(listPtr, nodePtr));						\
        nodePtr->next##LType = 0;尾节点无后继节点							\
        if (listPtr->tail == 0) {									\
    	listPtr->head = listPtr->tail = nodePtr;						\
    	nodePtr->prev##LType = 0;								\
        }												\
        else {											\
    	listPtr->tail->next##LType = nodePtr;							\
    	nodePtr->prev##LType = listPtr->tail;							\
    	listPtr->tail = nodePtr;								\
        }												\
    }将节点node加到链表的尾部										\
    static __inline__ void Append_##LType(struct LType *listToModify, struct LType *listToAppend) {	\
        if (listToAppend->head != 0) {listToAppend链表不空						\
    	if (listToModify->head == 0) {								\
    	    listToModify->head = listToAppend->head;						\
    	    listToModify->tail = listToAppend->tail;						\
    	} else {										\
    	    KASSERT(listToAppend->head != 0);							\
    	    KASSERT(listToModify->tail != 0);							\
    	    listToAppend->head->prev##LType = listToModify->tail;				\
    	    listToModify->tail->next##LType = listToAppend->head;				\
    	    listToModify->tail = listToAppend->tail;						\
    	}											\
        }												\
        listToAppend->head = listToAppend->tail = 0;						\
    }将listToAppend链表链接到listToModify的末尾												\
    static __inline__ struct NType * Remove_From_Front_Of_##LType(struct LType *listPtr) {		\
        struct NType *nodePtr;									\
        nodePtr = listPtr->head;									\
        KASSERT(nodePtr != 0);									\
        listPtr->head = listPtr->head->next##LType;							\
        if (listPtr->head == 0)									\
    	listPtr->tail = 0;									\
        else											\
    	listPtr->head->prev##LType = 0;								\
        return nodePtr;										\
    }使链表中的首节点脱离链表												\
    static __inline__ void Remove_From_##LType(struct LType *listPtr, struct NType *nodePtr) {	\
        KASSERT(Is_Member_Of_##LType(listPtr, nodePtr));						\
        if (nodePtr->prev##LType != 0)								\
    	nodePtr->prev##LType->next##LType = nodePtr->next##LType;				\
        else											\
    	listPtr->head = nodePtr->next##LType;							\
        if (nodePtr->next##LType != 0)								\
    	nodePtr->next##LType->prev##LType = nodePtr->prev##LType;				\
        else											\
    	listPtr->tail = nodePtr->prev##LType;							\
    }将节点node从链表中删除												\
    static __inline__ bool Is_##LType##_Empty(struct LType *listPtr) {				\
        return listPtr->head == 0;									\
    }判断链表是否为空
    
    #endif  /* GEEKOS_LIST_H */