From af1a266670d040d2f4083ff309d732d648afba2a Mon Sep 17 00:00:00 2001 From: Angelos Mouzakitis Date: Tue, 10 Oct 2023 14:33:42 +0000 Subject: Add submodule dependency files Change-Id: Iaf8d18082d3991dec7c0ebbea540f092188eb4ec --- roms/edk2/MdePkg/Library/BaseLib/LinkedList.c | 599 ++++++++++++++++++++++++++ 1 file changed, 599 insertions(+) create mode 100644 roms/edk2/MdePkg/Library/BaseLib/LinkedList.c (limited to 'roms/edk2/MdePkg/Library/BaseLib/LinkedList.c') diff --git a/roms/edk2/MdePkg/Library/BaseLib/LinkedList.c b/roms/edk2/MdePkg/Library/BaseLib/LinkedList.c new file mode 100644 index 000000000..5648c1877 --- /dev/null +++ b/roms/edk2/MdePkg/Library/BaseLib/LinkedList.c @@ -0,0 +1,599 @@ +/** @file + Linked List Library Functions. + + Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.
+ SPDX-License-Identifier: BSD-2-Clause-Patent + +**/ + +#include "BaseLibInternals.h" + +/** + If PcdVerifyNodeInList is TRUE, ASSERTs when SecondEntry is or is not part of + the same doubly-linked list as FirstEntry depending on the value of InList. + Independent of PcdVerifyNodeInList, ASSERTs when FirstEntry is not part of a + valid list. + + If FirstEntry is NULL, then ASSERT(). + If FirstEntry->ForwardLink is NULL, then ASSERT(). + If FirstEntry->BackLink is NULL, then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and List contains more than + PcdMaximumLinkedListLength nodes, then ASSERT(). + If PcdVerifyNodeInList is TRUE and SecondEntry is NULL, then ASSERT(). + + @param FirstEntry A pointer to a node in a linked list. + @param SecondEntry A pointer to the node to locate. + @param InList Defines whether to check if SecondEntry is or is not part + of the same doubly-linked list as FirstEntry. + +**/ +#if !defined (MDEPKG_NDEBUG) + #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList) \ + do { \ + if (FeaturePcdGet (PcdVerifyNodeInList)) { \ + ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry))); \ + } else { \ + ASSERT (InternalBaseLibIsListValid (FirstEntry)); \ + } \ + } while (FALSE) +#else + #define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList) +#endif + +/** + Worker function that verifies the validity of this list. + + If List is NULL, then ASSERT(). + If List->ForwardLink is NULL, then ASSERT(). + If List->BackLink is NULL, then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and List contains more than + PcdMaximumLinkedListLength nodes, then ASSERT(). + + @param List A pointer to a node in a linked list. + + @retval TRUE if PcdVerifyNodeInList is FALSE + @retval TRUE if DoMembershipCheck is FALSE + @retval TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE + and Node is a member of List. + @retval FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE + and Node is in not a member of List. + +**/ +BOOLEAN +EFIAPI +InternalBaseLibIsListValid ( + IN CONST LIST_ENTRY *List + ) +{ + UINTN Count; + CONST LIST_ENTRY *Ptr; + + // + // Test the validity of List and Node + // + ASSERT (List != NULL); + ASSERT (List->ForwardLink != NULL); + ASSERT (List->BackLink != NULL); + + if (PcdGet32 (PcdMaximumLinkedListLength) > 0) { + Count = 0; + Ptr = List; + + // + // Count the total number of nodes in List. + // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength + // + do { + Ptr = Ptr->ForwardLink; + Count++; + } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength))); + + // + // return whether linked list is too long + // + return (BOOLEAN)(Count < PcdGet32 (PcdMaximumLinkedListLength)); + } + + return TRUE; +} + +/** + Checks whether FirstEntry and SecondEntry are part of the same doubly-linked + list. + + If FirstEntry is NULL, then ASSERT(). + If FirstEntry->ForwardLink is NULL, then ASSERT(). + If FirstEntry->BackLink is NULL, then ASSERT(). + If SecondEntry is NULL, then ASSERT(); + If PcdMaximumLinkedListLength is not zero, and List contains more than + PcdMaximumLinkedListLength nodes, then ASSERT(). + + @param FirstEntry A pointer to a node in a linked list. + @param SecondEntry A pointer to the node to locate. + + @retval TRUE SecondEntry is in the same doubly-linked list as FirstEntry. + @retval FALSE SecondEntry isn't in the same doubly-linked list as FirstEntry, + or FirstEntry is invalid. + +**/ +BOOLEAN +EFIAPI +IsNodeInList ( + IN CONST LIST_ENTRY *FirstEntry, + IN CONST LIST_ENTRY *SecondEntry + ) +{ + UINTN Count; + CONST LIST_ENTRY *Ptr; + + // + // ASSERT List not too long + // + ASSERT (InternalBaseLibIsListValid (FirstEntry)); + + ASSERT (SecondEntry != NULL); + + Count = 0; + Ptr = FirstEntry; + + // + // Check to see if SecondEntry is a member of FirstEntry. + // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength + // + do { + Ptr = Ptr->ForwardLink; + if (PcdGet32 (PcdMaximumLinkedListLength) > 0) { + Count++; + + // + // Return if the linked list is too long + // + if (Count == PcdGet32 (PcdMaximumLinkedListLength)) { + return (BOOLEAN)(Ptr == SecondEntry); + } + } + + if (Ptr == SecondEntry) { + return TRUE; + } + } while (Ptr != FirstEntry); + + return FALSE; +} + +/** + Initializes the head node of a doubly-linked list, and returns the pointer to + the head node of the doubly-linked list. + + Initializes the forward and backward links of a new linked list. After + initializing a linked list with this function, the other linked list + functions may be used to add and remove nodes from the linked list. It is up + to the caller of this function to allocate the memory for ListHead. + + If ListHead is NULL, then ASSERT(). + + @param ListHead A pointer to the head node of a new doubly-linked list. + + @return ListHead + +**/ +LIST_ENTRY * +EFIAPI +InitializeListHead ( + IN OUT LIST_ENTRY *ListHead + ) + +{ + ASSERT (ListHead != NULL); + + ListHead->ForwardLink = ListHead; + ListHead->BackLink = ListHead; + return ListHead; +} + +/** + Adds a node to the beginning of a doubly-linked list, and returns the pointer + to the head node of the doubly-linked list. + + Adds the node Entry at the beginning of the doubly-linked list denoted by + ListHead, and returns ListHead. + + If ListHead is NULL, then ASSERT(). + If Entry is NULL, then ASSERT(). + If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and prior to insertion the number + of nodes in ListHead, including the ListHead node, is greater than or + equal to PcdMaximumLinkedListLength, then ASSERT(). + + @param ListHead A pointer to the head node of a doubly-linked list. + @param Entry A pointer to a node that is to be inserted at the beginning + of a doubly-linked list. + + @return ListHead + +**/ +LIST_ENTRY * +EFIAPI +InsertHeadList ( + IN OUT LIST_ENTRY *ListHead, + IN OUT LIST_ENTRY *Entry + ) +{ + // + // ASSERT List not too long and Entry is not one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE); + + Entry->ForwardLink = ListHead->ForwardLink; + Entry->BackLink = ListHead; + Entry->ForwardLink->BackLink = Entry; + ListHead->ForwardLink = Entry; + return ListHead; +} + +/** + Adds a node to the end of a doubly-linked list, and returns the pointer to + the head node of the doubly-linked list. + + Adds the node Entry to the end of the doubly-linked list denoted by ListHead, + and returns ListHead. + + If ListHead is NULL, then ASSERT(). + If Entry is NULL, then ASSERT(). + If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and prior to insertion the number + of nodes in ListHead, including the ListHead node, is greater than or + equal to PcdMaximumLinkedListLength, then ASSERT(). + + @param ListHead A pointer to the head node of a doubly-linked list. + @param Entry A pointer to a node that is to be added at the end of the + doubly-linked list. + + @return ListHead + +**/ +LIST_ENTRY * +EFIAPI +InsertTailList ( + IN OUT LIST_ENTRY *ListHead, + IN OUT LIST_ENTRY *Entry + ) +{ + // + // ASSERT List not too long and Entry is not one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE); + + Entry->ForwardLink = ListHead; + Entry->BackLink = ListHead->BackLink; + Entry->BackLink->ForwardLink = Entry; + ListHead->BackLink = Entry; + return ListHead; +} + +/** + Retrieves the first node of a doubly-linked list. + + Returns the first node of a doubly-linked list. List must have been + initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). + If List is empty, then List is returned. + + If List is NULL, then ASSERT(). + If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes + in List, including the List node, is greater than or equal to + PcdMaximumLinkedListLength, then ASSERT(). + + @param List A pointer to the head node of a doubly-linked list. + + @return The first node of a doubly-linked list. + @retval List The list is empty. + +**/ +LIST_ENTRY * +EFIAPI +GetFirstNode ( + IN CONST LIST_ENTRY *List + ) +{ + // + // ASSERT List not too long + // + ASSERT (InternalBaseLibIsListValid (List)); + + return List->ForwardLink; +} + +/** + Retrieves the next node of a doubly-linked list. + + Returns the node of a doubly-linked list that follows Node. + List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE() + or InitializeListHead(). If List is empty, then List is returned. + + If List is NULL, then ASSERT(). + If Node is NULL, then ASSERT(). + If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and List contains more than + PcdMaximumLinkedListLength nodes, then ASSERT(). + If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT(). + + @param List A pointer to the head node of a doubly-linked list. + @param Node A pointer to a node in the doubly-linked list. + + @return A pointer to the next node if one exists. Otherwise List is returned. + +**/ +LIST_ENTRY * +EFIAPI +GetNextNode ( + IN CONST LIST_ENTRY *List, + IN CONST LIST_ENTRY *Node + ) +{ + // + // ASSERT List not too long and Node is one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE); + + return Node->ForwardLink; +} + +/** + Retrieves the previous node of a doubly-linked list. + + Returns the node of a doubly-linked list that precedes Node. + List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE() + or InitializeListHead(). If List is empty, then List is returned. + + If List is NULL, then ASSERT(). + If Node is NULL, then ASSERT(). + If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and List contains more than + PcdMaximumLinkedListLength nodes, then ASSERT(). + If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT(). + + @param List A pointer to the head node of a doubly-linked list. + @param Node A pointer to a node in the doubly-linked list. + + @return A pointer to the previous node if one exists. Otherwise List is returned. + +**/ +LIST_ENTRY * +EFIAPI +GetPreviousNode ( + IN CONST LIST_ENTRY *List, + IN CONST LIST_ENTRY *Node + ) +{ + // + // ASSERT List not too long and Node is one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE); + + return Node->BackLink; +} + +/** + Checks to see if a doubly-linked list is empty or not. + + Checks to see if the doubly-linked list is empty. If the linked list contains + zero nodes, this function returns TRUE. Otherwise, it returns FALSE. + + If ListHead is NULL, then ASSERT(). + If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes + in List, including the List node, is greater than or equal to + PcdMaximumLinkedListLength, then ASSERT(). + + @param ListHead A pointer to the head node of a doubly-linked list. + + @retval TRUE The linked list is empty. + @retval FALSE The linked list is not empty. + +**/ +BOOLEAN +EFIAPI +IsListEmpty ( + IN CONST LIST_ENTRY *ListHead + ) +{ + // + // ASSERT List not too long + // + ASSERT (InternalBaseLibIsListValid (ListHead)); + + return (BOOLEAN)(ListHead->ForwardLink == ListHead); +} + +/** + Determines if a node in a doubly-linked list is the head node of a the same + doubly-linked list. This function is typically used to terminate a loop that + traverses all the nodes in a doubly-linked list starting with the head node. + + Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the + nodes in the doubly-linked list specified by List. List must have been + initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). + + If List is NULL, then ASSERT(). + If Node is NULL, then ASSERT(). + If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(), + then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes + in List, including the List node, is greater than or equal to + PcdMaximumLinkedListLength, then ASSERT(). + If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not + equal to List, then ASSERT(). + + @param List A pointer to the head node of a doubly-linked list. + @param Node A pointer to a node in the doubly-linked list. + + @retval TRUE Node is the head of the doubly-linked list pointed by List. + @retval FALSE Node is not the head of the doubly-linked list pointed by List. + +**/ +BOOLEAN +EFIAPI +IsNull ( + IN CONST LIST_ENTRY *List, + IN CONST LIST_ENTRY *Node + ) +{ + // + // ASSERT List not too long and Node is one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE); + + return (BOOLEAN)(Node == List); +} + +/** + Determines if a node the last node in a doubly-linked list. + + Returns TRUE if Node is the last node in the doubly-linked list specified by + List. Otherwise, FALSE is returned. List must have been initialized with + INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). + + If List is NULL, then ASSERT(). + If Node is NULL, then ASSERT(). + If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or + InitializeListHead(), then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes + in List, including the List node, is greater than or equal to + PcdMaximumLinkedListLength, then ASSERT(). + If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT(). + + @param List A pointer to the head node of a doubly-linked list. + @param Node A pointer to a node in the doubly-linked list. + + @retval TRUE Node is the last node in the linked list. + @retval FALSE Node is not the last node in the linked list. + +**/ +BOOLEAN +EFIAPI +IsNodeAtEnd ( + IN CONST LIST_ENTRY *List, + IN CONST LIST_ENTRY *Node + ) +{ + // + // ASSERT List not too long and Node is one of the nodes of List + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE); + + return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node); +} + +/** + Swaps the location of two nodes in a doubly-linked list, and returns the + first node after the swap. + + If FirstEntry is identical to SecondEntry, then SecondEntry is returned. + Otherwise, the location of the FirstEntry node is swapped with the location + of the SecondEntry node in a doubly-linked list. SecondEntry must be in the + same double linked list as FirstEntry and that double linked list must have + been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). + SecondEntry is returned after the nodes are swapped. + + If FirstEntry is NULL, then ASSERT(). + If SecondEntry is NULL, then ASSERT(). + If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the + same linked list, then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes in the + linked list containing the FirstEntry and SecondEntry nodes, including + the FirstEntry and SecondEntry nodes, is greater than or equal to + PcdMaximumLinkedListLength, then ASSERT(). + + @param FirstEntry A pointer to a node in a linked list. + @param SecondEntry A pointer to another node in the same linked list. + + @return SecondEntry. + +**/ +LIST_ENTRY * +EFIAPI +SwapListEntries ( + IN OUT LIST_ENTRY *FirstEntry, + IN OUT LIST_ENTRY *SecondEntry + ) +{ + LIST_ENTRY *Ptr; + + if (FirstEntry == SecondEntry) { + return SecondEntry; + } + + // + // ASSERT Entry1 and Entry2 are in the same linked list + // + ASSERT_VERIFY_NODE_IN_VALID_LIST (FirstEntry, SecondEntry, TRUE); + + // + // Ptr is the node pointed to by FirstEntry->ForwardLink + // + Ptr = RemoveEntryList (FirstEntry); + + // + // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed + // immediately in front of SecondEntry + // + if (Ptr->BackLink == SecondEntry) { + return InsertTailList (SecondEntry, FirstEntry); + } + + // + // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry, + // then there are no further steps necessary + // + if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) { + return Ptr; + } + + // + // Move SecondEntry to the front of Ptr + // + RemoveEntryList (SecondEntry); + InsertTailList (Ptr, SecondEntry); + return SecondEntry; +} + +/** + Removes a node from a doubly-linked list, and returns the node that follows + the removed node. + + Removes the node Entry from a doubly-linked list. It is up to the caller of + this function to release the memory used by this node if that is required. On + exit, the node following Entry in the doubly-linked list is returned. If + Entry is the only node in the linked list, then the head node of the linked + list is returned. + + If Entry is NULL, then ASSERT(). + If Entry is the head node of an empty list, then ASSERT(). + If PcdMaximumLinkedListLength is not zero, and the number of nodes in the + linked list containing Entry, including the Entry node, is greater than + or equal to PcdMaximumLinkedListLength, then ASSERT(). + + @param Entry A pointer to a node in a linked list. + + @return Entry. + +**/ +LIST_ENTRY * +EFIAPI +RemoveEntryList ( + IN CONST LIST_ENTRY *Entry + ) +{ + ASSERT (!IsListEmpty (Entry)); + + Entry->ForwardLink->BackLink = Entry->BackLink; + Entry->BackLink->ForwardLink = Entry->ForwardLink; + return Entry->ForwardLink; +} -- cgit