Advanced Generic Linked Lists in C

Doubly Linked Lists are fundamental data structures used extensively in operating systems. Double links enable faster insertion and deletion of list nodes in the middle of a liked list chain as compared to singly linked lists. Following is a conceptual description of how generic linked lists can be implemented.
typedef struct LLSTRUCT { struct LLSTRUCT *pPrev; struct LLSTRUCT *pNext; } LINKEDLIST, *PLINKEDLIST;

Note that using the above declaration, the following two statements are identical (they both declare a variable of the linked list type):
struct LLSTRUCT llVar1; LINKEDLIST llVar2;

Similarly, the following three equivalent statements declare pointer variables of the linked list type:
struct LLSTRUCT *pllVar1; LINKEDLIST *pllVar2; PLINKEDLIST pllVar3;

We can use the linked list type declared above to create linked lists of other structures. For example, consider the following code for the process control block structure. This structure is part of two different linked lists: llPCBs is the linked list of all PCBs and llSched is the linked list of all PCBs that are blocking on a semaphore or on the ready list.
typedef struct { unsigned int uiPID; /* process ID */ unsigned int uiBlah1; /* Other PCB data */ /* Linked list of all PCBs */ LINKEDLIST llPCBs; /* Linked list of PCBs in specific scheduler lists. E.g., blocked on a semaphore or in the ready list */ LINKEDLIST llSched; unsigned int uiBlah2; /* Other PCB data */ unsigned int uiBlah3; /* Other PCB data */ /* ETC. */ } PCB, *PPCB;

The idea here is to have the previous and the next pointers point to the linked list entries in the PCB structure, and not to the beginning of the PCB structure. See the figure below.

PllPCBs

llPCBs

llPCBs

llPCBs

pllReady

llSched

llSched

llSched

Note that this means that the API for list insertion will look like as follows:
/* Declare the head of the list of all PCBs */ PLINKEDLIST pllPCBs; /* Declare the head of the list of all ready PCBs */ PLINKEDLIST pllReadyPCBs; /* Allocate memory for a new PCB (worry about memory allocation later) */ PPCB pNewPCB = (PPCB)KernAllocPage(1); /* Add the new PCB to the front of the all PCBs list */ KernAddLL(pllPCBs, &(pNewPCB->llPCBs)); /* Add the new PCB to the front of the all PCBs list */ KernAddLL(pllReadyPCBs, &(pNewPCB->llSched)); /* Remove a PCB from the ready list */ KernUnlinkLL(pllReadyPCBs, &(pSomePCB->llSched)); /* Insert the new PCB after some other existing PCB in the all PCBs list */ KernInsertAfterLL(pllPCBs, &(pSomePCB->llPCBs), &((pNewPCB->llPCBs));

Important Note: we are passing the pointer of the specific linked list entry in the PCB structure corresponding to the linked list we want to add/remove the PCB into/from; we do not pass pointers to the PCB structure. Specifically, we pass the pointer to the llPCBs element when we want to add/remove the PCB to/from the list of all PCBs and we pass the pointer to the llSched element when we want to add/remove the PCB to/from the list of ready PCBs. Mixing the pointers will have disastrous consequences. Also note that we need to pass the pointer to the head of the list as well just in case we need to manipulate it. For example, following is the code for the KernUnlinkLL function.
void KernUnlinkLL(PLINKEDLIST pllHead, PLINKEDLIST pllRem) { /* Make the "next pointer" of the previous node point to the node following pllRem */ if (pllRem->pPrev != NULL) pllRem->pPrev->pNext = pllRem->pNext; else /* If pllRem's "previous" is null then pllRem is at the head of the list, which must be adjusted */ pllHead = pllRem->pNext; /* Make the "previous pointer" of the next node point to the node preceding pllRem */ if (pllRem->pNext != NULL) pllRem->pNext->pPrev = pllRem->pPrev; }

You should have noticed that in the code above, we are manipulating the LINKEDLIST structure using pointers to the LINKEDLIST structure, not the PCB structure. Therefore, the code is completely generic (i.e., any structure that includes the LINKEDLIST structure can be made a part of a linked lists). Another Important Note: The main problem with the approach followed above is that when we traverse a linked list, we are typically manipulating pointers of type LINKEDLIST and not of the structure we are actually holding in the linked list. This means that we need to retrieve the pointer to the actual structure after we have finished traversing the list and are ready to use the lined list node. For example, if we want

to retrieve the PID of the PCB at the head of the ready list, then we cannot simply use pllReady->ulPID because pllReady points to a variable of type LINKEDLIST that does not have the ulPID element; what we really need is the pointer to the PCB node that contains the LINKEDLIST structure pointed to by pllReady. We also cannot simply typecast the pllReady variable to the PCB type because the pllReady element points to the location 8 bytes after the start of the PCB structure in our example code. The compiler will let you typecast, but the result f the typecast will be a pointer of the correct type (i.e., will allow you to dereference the ulPID element) but will be pointing to the wrong location (i.e., will be off by 8 bytes). So ((PCB)*pllReady).uiPID, or equivalently ((PPCB)pllReady)->uiPID, will actually access the pPrev value of the pllSched element of the first PCB in the ready list, not the PID. In order to get to the base of the appropriate structure variable in memory, we will need to write a macro that returns the appropriate pointer.
#define LIST_ENTRY_PTR(LLPTR, ENTRY_TYPE, LLMEMBER) \ ((ENTRY_TYPE *)((char *)LLPTR - \ (unsigned long)&(((ENTRY_TYPE *)0)->LLMEMBER)))

Where LLPTR is a pointer to the linked list (i.e., a pointer of type PLINKEDLIST), ENTRY_TYPE is the type of the larger structure that contains the linked list entry, and LLMEMBER is the name of the structure member representing the specific linked list. In other words, you would use the macro as follows in order to get the pointer to the first PCB in the linked list of ready PCBs:
PPCB pllFirstPCB = LIST_ENTRY_PTR(pllReadyPCBs, PCB, llSched);

It is critically important for you to be careful when using these advanced mechanisms in that you specify the correct types and correct list member elements. The compiler will only perform limited type checking and error detection. Type casts are a useful, but risky, mechanism in that you are overriding the paranoid type checking normally performed by the compiler to keep programmers out of trouble. Your assignment is to design and implement the linked list API. The goal here is to write functions for inserting a node at the beginning of a list, inserting a node after some arbitrary node, and unlinking a node