palacios/include/geekos/list.h

   1 /*
   2  * Generic list data type
   3  * Copyright (c) 2001,2004 David H. Hovemeyer <daveho@cs.umd.edu>
   4  * $Revision: 1.1.1.1 $
   5  *
   6  * This is free software.  You are permitted to use,
   7  * redistribute, and modify it as specified in the file "COPYING".
   8  */
   9
  10 #ifndef GEEKOS_LIST_H
  11 #define GEEKOS_LIST_H
  12
  13 #include <geekos/ktypes.h>
  14 #include <geekos/kassert.h>
  15
  16 /*
  17  * Define a list type.
  18  */
  19 #define DEFINE_LIST(listTypeName, nodeTypeName)         \
  20 struct listTypeName {                                   \
  21     struct nodeTypeName *head, *tail;                   \
  22 }
  23
  24 /*
  25  * Define members of a struct to be used as link fields for
  26  * membership in given list type.
  27  */
  28 #define DEFINE_LINK(listTypeName, nodeTypeName) \
  29     struct nodeTypeName * prev##listTypeName, * next##listTypeName
  30
  31 /*
  32  * Define inline list manipulation and access functions.
  33  */
  34 #define IMPLEMENT_LIST(LType, NType)                                                            \
  35 static __inline__ void Clear_##LType(struct LType *listPtr) {                                   \
  36     listPtr->head = listPtr->tail = 0;                                                          \
  37 }                                                                                               \
  38 static __inline__ bool Is_Member_Of_##LType(struct LType *listPtr, struct NType *nodePtr) {     \
  39     struct NType *cur = listPtr->head;                                                          \
  40     while (cur != 0) {                                                                          \
  41         if (cur == nodePtr)                                                                     \
  42             return true;                                                                        \
  43         cur = cur->next##LType;                                                                 \
  44     }                                                                                           \
  45     return false;                                                                               \
  46 }                                                                                               \
  47 static __inline__ struct NType * Get_Front_Of_##LType(struct LType *listPtr) {                  \
  48     return listPtr->head;                                                                       \
  49 }                                                                                               \
  50 static __inline__ struct NType * Get_Back_Of_##LType(struct LType *listPtr) {                   \
  51     return listPtr->tail;                                                                       \
  52 }                                                                                               \
  53 static __inline__ struct NType * Get_Next_In_##LType(struct NType *nodePtr) {                   \
  54     return nodePtr->next##LType;                                                                \
  55 }                                                                                               \
  56 static __inline__ void Set_Next_In_##LType(struct NType *nodePtr, struct NType *value) {        \
  57     nodePtr->next##LType = value;                                                               \
  58 }                                                                                               \
  59 static __inline__ struct NType * Get_Prev_In_##LType(struct NType *nodePtr) {                   \
  60     return nodePtr->prev##LType;                                                                \
  61 }                                                                                               \
  62 static __inline__ void Set_Prev_In_##LType(struct NType *nodePtr, struct NType *value) {        \
  63     nodePtr->prev##LType = value;                                                               \
  64 }                                                                                               \
  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;                                                               \
  71     } else {                                                                                    \
  72         listPtr->head->prev##LType = nodePtr;                                                   \
  73         nodePtr->next##LType = listPtr->head;                                                   \
  74         listPtr->head = nodePtr;                                                                \
  75     }                                                                                           \
  76 }                                                                                               \
  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;                                                               \
  83     }                                                                                           \
  84     else {                                                                                      \
  85         listPtr->tail->next##LType = nodePtr;                                                   \
  86         nodePtr->prev##LType = listPtr->tail;                                                   \
  87         listPtr->tail = nodePtr;                                                                \
  88     }                                                                                           \
  89 }                                                                                               \
  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;                                            \
  95         } else {                                                                                \
  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;                                            \
 101         }                                                                                       \
 102     }                                                                                           \
 103     listToAppend->head = listToAppend->tail = 0;                                                \
 104 }                                                                                               \
 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)                                                                     \
 111         listPtr->tail = 0;                                                                      \
 112     else                                                                                        \
 113         listPtr->head->prev##LType = 0;                                                         \
 114     return nodePtr;                                                                             \
 115 }                                                                                               \
 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;                               \
 120     else                                                                                        \
 121         listPtr->head = nodePtr->next##LType;                                                   \
 122     if (nodePtr->next##LType != 0)                                                              \
 123         nodePtr->next##LType->prev##LType = nodePtr->prev##LType;                               \
 124     else                                                                                        \
 125         listPtr->tail = nodePtr->prev##LType;                                                   \
 126 }                                                                                               \
 127 static __inline__ bool Is_##LType##_Empty(struct LType *listPtr) {                              \
 128     return listPtr->head == 0;                                                                  \
 129 }
 130
 131 #endif  /* GEEKOS_LIST_H */