From: "Marvin Häuser" <mhaeuser@posteo.de>
To: devel@edk2.groups.io, harlydavidsen@gmail.com
Cc: Andrew Fish <afish@apple.com>,
"Leif Lindholm (Nuvia address)" <leif@nuviainc.com>,
Ray Ni <ray.ni@intel.com>
Subject: Re: [edk2-devel] Using linked lists in EDK II
Date: Mon, 23 Aug 2021 06:45:40 +0000 [thread overview]
Message-ID: <36228d37-d848-d890-a284-df7fc42b9fda@posteo.de> (raw)
In-Reply-To: <CAJQtwF1DdEcmier15=5_HFWXTcnMyFLNergOiS9KWpLjF0wuUg@mail.gmail.com>
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.)
>
prev parent reply other threads:[~2021-08-23 6:45 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-23 3:37 Using linked lists in EDK II Ethin Probst
2021-08-23 6:45 ` Marvin Häuser [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=36228d37-d848-d890-a284-df7fc42b9fda@posteo.de \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox