From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by mx.groups.io with SMTP id smtpd.web10.20360.1629701145220676080 for ; Sun, 22 Aug 2021 23:45:46 -0700 Authentication-Results: mx.groups.io; dkim=fail reason="body hash did not verify" header.i=@posteo.de header.s=2017 header.b=G503+y43; spf=pass (domain: posteo.de, ip: 185.67.36.66, mailfrom: mhaeuser@posteo.de) Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id A76DC240104 for ; Mon, 23 Aug 2021 08:45:41 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1629701141; bh=0cRJu5aj0d/giNKHZN4IQTiFMO/8YN8OwXoSvclnGhM=; h=Subject:To:Cc:From:Date:From; b=G503+y43c8yODEDH0iUqmUrUIPEoURElxiCZaKyCJtlsavJKeoAsxbo3hrW4an/Rq SsU5Il+fBhEppTvOoU5qW0z327kP5RjnUBVT3gO+XyANs/8L5sC1dlw/2BWXvQtzPs Ja2/6papdStOW05hIrD/IQ0xlEuxZmRD08ZGqTQeSmCl0x48beSOUO6rEO3lXE1Ezi f6cdGVfwM34VauiVDlS1FA+DlZPUtKaLKpfgHEMgipccWTM5oIuvKv0ZhV2P8vep9z OA9oPZVouzohH1//edTCT6pQyp0P28KThaqPpETtD2B4XXJmSbhKVIsywkcSitLWyz uWCypgBJSpupQ== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4GtN6X4C9Lz6tmW; Mon, 23 Aug 2021 08:45:40 +0200 (CEST) Subject: Re: [edk2-devel] Using linked lists in EDK II To: devel@edk2.groups.io, harlydavidsen@gmail.com Cc: Andrew Fish , "Leif Lindholm (Nuvia address)" , Ray Ni References: From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= Message-ID: <36228d37-d848-d890-a284-df7fc42b9fda@posteo.de> Date: Mon, 23 Aug 2021 06:45:40 +0000 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-GB Content-Transfer-Encoding: quoted-printable Good day Ethin, Well, first of all, it's a doubly-linked list from the books, so you=20 have a circular chain in both directions. There is no explicit "list=20 head" type, rather you have a LIST_ENTRY instance that acts as your root=20 (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: =C2=A0 #define PAYLOAD_SIG=C2=A0 SIGNATURE_32 ('L', 'P', 'L', 'D') =C2=A0 typedef struct { =C2=A0=C2=A0=C2=A0 UINT32 Signature; // Not mandatory, but common with C= R() to detect=20 list corruption =C2=A0=C2=A0=C2=A0 LIST_ENTRY Link; // Stores predecessor and successor =C2=A0=C2=A0=C2=A0 UINT8 Payload[32]; // Example payload data =C2=A0 } LIST_PAYLOAD; And you may have a list head with no data: =C2=A0 LIST_HEAD ListHead; You initialise the list with: =C2=A0 InitializeListHead (&ListHead); The list is now valid and empty, i.e. the predecessor and successor of=20 the list head are now the list head. You may allocate new entries: =C2=A0 LIST_PAYLOAD *Payload =3D AllocatePool (sizeof (*Payload)); =C2=A0 // [...] Handle NULL :) =C2=A0 Payload->Signature =3D PAYLOAD_SIG; And insert them into the list at the end...: =C2=A0 InsertTailList (&ListHead, &Payload->Link); ... or the start: =C2=A0 InsertHeadList (&ListHead, &Payload->Link); The predecessors and successors of the list head and the payload item=20 now point to each other respectively. When iterating the list, assuming the "list head carries no payload"=20 design from above, you iterate over the payload link pointers...: =C2=A0 LIST_ENTRY *Entry =3D GetFirstNode (&ListHead); =C2=A0 while (!IsNull (&ListHead, Entry)) { // Checks whether Entry is l= ist head =C2=A0=C2=A0=C2=A0 [...] =C2=A0=C2=A0=C2=A0 Entry =3D GetNextNode (&ListHead, Entry); // advances= Entry =C2=A0 } ... and you can retrieve the stored data with a call to the CR=20 ("containing record" or "container record") macro: =C2=A0 LIST_PAYLOAD *Payload =3D CR (Link, LIST_PAYLOAD, Entry, PAYLOAD_= SIG); You can read it as "Retrieve the pointer to an instance of LIST_PAYLOAD=20 if Entry is a pointer to the structure member Link. ASSERT it has the=20 signature PAYLOAD_SIG." Payload now points to the data stored by the=20 payload you allocated. If you want to omit Signature, you can use=20 BASE_CR() with the same prototype minus the Signature argument. The rest of the API should be clear I hope, remove and free are=20 analogous. I didn't throw the code into an IDE to check for=20 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.) >