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.)
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#79705): https://edk2.groups.io/g/devel/message/79705
Mute This Topic: https://groups.io/mt/85078100/21656
Group Owner: devel+ow...@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com]
-=-=-=-=-=-=-=-=-=-=-=-
