2 * Generic list data type
3 * Copyright (c) 2001,2004 David H. Hovemeyer <daveho@cs.umd.edu>
6 * This is free software. You are permitted to use,
7 * redistribute, and modify it as specified in the file "COPYING".
13 #include <geekos/ktypes.h>
14 #include <geekos/kassert.h>
19 #define DEFINE_LIST(listTypeName, nodeTypeName) \
20 struct listTypeName { \
21 struct nodeTypeName *head, *tail; \
25 * Define members of a struct to be used as link fields for
26 * membership in given list type.
28 #define DEFINE_LINK(listTypeName, nodeTypeName) \
29 struct nodeTypeName * prev##listTypeName, * next##listTypeName
32 * Define inline list manipulation and access functions.
34 #define IMPLEMENT_LIST(LType, NType) \
35 static __inline__ void Clear_##LType(struct LType *listPtr) { \
36 listPtr->head = listPtr->tail = 0; \
38 static __inline__ bool Is_Member_Of_##LType(struct LType *listPtr, struct NType *nodePtr) { \
39 struct NType *cur = listPtr->head; \
43 cur = cur->next##LType; \
47 static __inline__ struct NType * Get_Front_Of_##LType(struct LType *listPtr) { \
48 return listPtr->head; \
50 static __inline__ struct NType * Get_Back_Of_##LType(struct LType *listPtr) { \
51 return listPtr->tail; \
53 static __inline__ struct NType * Get_Next_In_##LType(struct NType *nodePtr) { \
54 return nodePtr->next##LType; \
56 static __inline__ void Set_Next_In_##LType(struct NType *nodePtr, struct NType *value) { \
57 nodePtr->next##LType = value; \
59 static __inline__ struct NType * Get_Prev_In_##LType(struct NType *nodePtr) { \
60 return nodePtr->prev##LType; \
62 static __inline__ void Set_Prev_In_##LType(struct NType *nodePtr, struct NType *value) { \
63 nodePtr->prev##LType = value; \
65 static __inline__ void Add_To_Front_Of_##LType(struct LType *listPtr, struct NType *nodePtr) { \
66 KASSERT(!Is_Member_Of_##LType(listPtr, nodePtr)); \
67 nodePtr->prev##LType = 0; \
68 if (listPtr->head == 0) { \
69 listPtr->head = listPtr->tail = nodePtr; \
70 nodePtr->next##LType = 0; \
72 listPtr->head->prev##LType = nodePtr; \
73 nodePtr->next##LType = listPtr->head; \
74 listPtr->head = nodePtr; \
77 static __inline__ void Add_To_Back_Of_##LType(struct LType *listPtr, struct NType *nodePtr) { \
78 /* KASSERT(!Is_Member_Of_##LType(listPtr, nodePtr)); */ \
79 nodePtr->next##LType = 0; \
80 if (listPtr->tail == 0) { \
81 listPtr->head = listPtr->tail = nodePtr; \
82 nodePtr->prev##LType = 0; \
85 listPtr->tail->next##LType = nodePtr; \
86 nodePtr->prev##LType = listPtr->tail; \
87 listPtr->tail = nodePtr; \
90 static __inline__ void Append_##LType(struct LType *listToModify, struct LType *listToAppend) { \
91 if (listToAppend->head != 0) { \
92 if (listToModify->head == 0) { \
93 listToModify->head = listToAppend->head; \
94 listToModify->tail = listToAppend->tail; \
96 KASSERT(listToAppend->head != 0); \
97 KASSERT(listToModify->tail != 0); \
98 listToAppend->head->prev##LType = listToModify->tail; \
99 listToModify->tail->next##LType = listToAppend->head; \
100 listToModify->tail = listToAppend->tail; \
103 listToAppend->head = listToAppend->tail = 0; \
105 static __inline__ struct NType * Remove_From_Front_Of_##LType(struct LType *listPtr) { \
106 struct NType *nodePtr; \
107 nodePtr = listPtr->head; \
108 KASSERT(nodePtr != 0); \
109 listPtr->head = listPtr->head->next##LType; \
110 if (listPtr->head == 0) \
113 listPtr->head->prev##LType = 0; \
116 static __inline__ void Remove_From_##LType(struct LType *listPtr, struct NType *nodePtr) { \
117 KASSERT(Is_Member_Of_##LType(listPtr, nodePtr)); \
118 if (nodePtr->prev##LType != 0) \
119 nodePtr->prev##LType->next##LType = nodePtr->next##LType; \
121 listPtr->head = nodePtr->next##LType; \
122 if (nodePtr->next##LType != 0) \
123 nodePtr->next##LType->prev##LType = nodePtr->prev##LType; \
125 listPtr->tail = nodePtr->prev##LType; \
127 static __inline__ bool Is_##LType##_Empty(struct LType *listPtr) { \
128 return listPtr->head == 0; \
131 #endif /* GEEKOS_LIST_H */