双链表:
LIST_ENTRY:
typedef struct _LIST_ENTRY { struct _LIST_ENTRY *Flink; follow: next entry, header if it is the last entry in the list struct _LIST_ENTRY *Blink; before: previous entry, header if it is the first entry in the list } LIST_ENTRY, *PLIST_ENTRY;
链表空是,header->Flink == header->Blink == &header; 这是初始化头部时的动作。
//code expample
typedef struct _MY_STRUCT{ NDIS_SPIN_LOCK spinLock; LIST_ENTRY header; }MY_STRUCT,PMY_STRUCT;//header typedef struct _MY_PACKET{ LIST_ENYRY entry; xxx xxx }MY_PACKET,PMP_PACKET;// each element PMY_STRUCT pMyStruct = alloc_mem(); //初始化链表头: InitializeListHead(&pMyStruct->header); //创建整个链表: for(int i=0;i<num_packets;i++){ PMP_PACKET pMyPacket= alloc_mem(); NdisInterlockedInsertTailList(&pMyStruct->header,&pMyPacket->entry,pMyStruct->spinLock); }//here,整个双链表已经创建完成。 //想要用这个链表的时候,very easy,用的时候从头部取,用完插到链表尾: PLIST_ENTRY listEntry; listEntry = NdisInterlockedRemoveHeadList(&pMyStruct->header,pMyStruct->spinLock); PMP_PACKET pPacket = CONTAINING_RECORD(listEntry,MY_PACKET, Entry); //用完之后继续放到链表尾部: NdisInterlockedInsertTailList(&pMyStruct->header,&pPacket->entry,pMyStruct->spinLock);
TAILQ_ENTRY
#define TAILQ_HEAD(name, type) struct name { struct type *tqh_first; /* first element */ struct type **tqh_last; /* addr of last next element */ } #define TAILQ_ENTRY(type) struct { struct type *tqe_next; /* next element */ struct type **tqe_prev; /* address of previous next element */ TRACEBUF } #define TAILQ_INIT(head) do { (head)->tqh_first = NULL; (head)->tqh_last = &(head)->tqh_first; } while (0) #define TAILQ_INSERT_TAIL(head, elm, field) do { (elm)->field.tqe_next = NULL; (elm)->field.tqe_prev = (head)->tqh_last; *(head)->tqh_last = (elm); (head)->tqh_last = &(elm)->field.tqe_next; } while (0) #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { (elm)->field.tqe_prev = (listelm)->field.tqe_prev; (elm)->field.tqe_next = (listelm); *(listelm)->field.tqe_prev = (elm); (listelm)->field.tqe_prev = &(elm)->field.tqe_next; } while (0) #define TAILQ_FIRST(head) ((head)->tqh_first) #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)