Using linked lists in EDK II

Using linked lists in EDK II

[Ethin Probst]

Hey all,

I've come across a situation where I need linked lists but I don't
know how to actually use the linked list functionality. Looking at the
API and existing uses of it doesn't really help -- it appears more
complex than I'm sure it really is. Could someone explain how it
works? (What I'm confused on primarily is where do I store LIST_ENTRY
pointers, and how do I write the structs so that I can actually pull
out the data that each list entry stores? From what I can tell, a
LIST_ENTRY just contains pointers to other LIST_ENTRY structs.)

-- 
Signed,
Ethin D. Probst

Re: [edk2-devel] Using linked lists in EDK II

[Marvin Häuser]

Good day Ethin,

Well, first of all, it's a doubly-linked list from the books, so you 
have a circular chain in both directions. There is no explicit "list 
head" type, rather you have a LIST_ENTRY instance that acts as your root 
(it may or may not contain data on its own based on your own design).

You embed a LIST_ENTRY instance (not pointer!) into each data payload:

   #define PAYLOAD_SIG  SIGNATURE_32 ('L', 'P', 'L', 'D')

   typedef struct {
     UINT32 Signature; // Not mandatory, but common with CR() to detect 
list corruption
     LIST_ENTRY Link; // Stores predecessor and successor
     UINT8 Payload[32]; // Example payload data
   } LIST_PAYLOAD;

And you may have a list head with no data:

   LIST_HEAD ListHead;

You initialise the list with:

   InitializeListHead (&ListHead);

The list is now valid and empty, i.e. the predecessor and successor of 
the list head are now the list head.
You may allocate new entries:

   LIST_PAYLOAD *Payload = AllocatePool (sizeof (*Payload));
   // [...] Handle NULL :)
   Payload->Signature = PAYLOAD_SIG;

And insert them into the list at the end...:

   InsertTailList (&ListHead, &Payload->Link);

... or the start:

   InsertHeadList (&ListHead, &Payload->Link);

The predecessors and successors of the list head and the payload item 
now point to each other respectively.
When iterating the list, assuming the "list head carries no payload" 
design from above, you iterate over the payload link pointers...:

   LIST_ENTRY *Entry = GetFirstNode (&ListHead);
   while (!IsNull (&ListHead, Entry)) { // Checks whether Entry is list head
     [...]
     Entry = GetNextNode (&ListHead, Entry); // advances Entry
   }

... and you can retrieve the stored data with a call to the CR 
("containing record" or "container record") macro:

   LIST_PAYLOAD *Payload = CR (Link, LIST_PAYLOAD, Entry, PAYLOAD_SIG);

You can read it as "Retrieve the pointer to an instance of LIST_PAYLOAD 
if Entry is a pointer to the structure member Link. ASSERT it has the 
signature PAYLOAD_SIG." Payload now points to the data stored by the 
payload you allocated. If you want to omit Signature, you can use 
BASE_CR() with the same prototype minus the Signature argument.

The rest of the API should be clear I hope, remove and free are 
analogous. I didn't throw the code into an IDE to check for 
typos/consistency, so sorry if there are mistakes.

Best regards,
Marvin


On 23/08/2021 05:37, Ethin Probst wrote:
> Hey all,
>
> I've come across a situation where I need linked lists but I don't
> know how to actually use the linked list functionality. Looking at the
> API and existing uses of it doesn't really help -- it appears more
> complex than I'm sure it really is. Could someone explain how it
> works? (What I'm confused on primarily is where do I store LIST_ENTRY
> pointers, and how do I write the structs so that I can actually pull
> out the data that each list entry stores? From what I can tell, a
> LIST_ENTRY just contains pointers to other LIST_ENTRY structs.)
>