+++ /dev/null
-/** @file\r
- Linked List Library Functions.\r
-\r
- Copyright (c) 2006 - 2010, Intel Corporation. All rights reserved.<BR>\r
- This program and the accompanying materials\r
- are licensed and made available under the terms and conditions of the BSD License\r
- which accompanies this distribution. The full text of the license may be found at\r
- http://opensource.org/licenses/bsd-license.php.\r
-\r
- THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
- WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
-\r
-**/\r
-\r
-#include "BaseLibInternals.h"\r
-\r
-/**\r
- Worker function that locates the Node in the List.\r
-\r
- By searching the List, finds the location of the Node in List. At the same time,\r
- verifies the validity of this list.\r
-\r
- If List is NULL, then ASSERT().\r
- If List->ForwardLink is NULL, then ASSERT().\r
- If List->backLink is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE and Node \r
- is in not a member of List, then return FALSE\r
- If PcdMaximumLinkedListLenth is not zero, and List contains more than\r
- PcdMaximumLinkedListLenth nodes, then ASSERT().\r
-\r
- @param List A pointer to a node in a linked list.\r
- @param Node A pointer to a node in a linked list.\r
- @param VerifyNodeInList TRUE if a check should be made to see if Node is a \r
- member of List. FALSE if no membership test should \r
- be performed.\r
-\r
- @retval TRUE if PcdVerifyNodeInList is FALSE\r
- @retval TRUE if DoMembershipCheck is FALSE\r
- @retval TRUE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE \r
- and Node is a member of List.\r
- @retval FALSE if PcdVerifyNodeInList is TRUE and DoMembershipCheck is TRUE \r
- and Node is in not a member of List.\r
-\r
-**/\r
-BOOLEAN\r
-EFIAPI\r
-InternalBaseLibIsNodeInList (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node,\r
- IN BOOLEAN VerifyNodeInList\r
- )\r
-{\r
- UINTN Count;\r
- CONST LIST_ENTRY *Ptr;\r
-\r
- //\r
- // Test the validity of List and Node\r
- //\r
- ASSERT (List != NULL);\r
- ASSERT (List->ForwardLink != NULL);\r
- ASSERT (List->BackLink != NULL);\r
- ASSERT (Node != NULL);\r
-\r
- Count = 0;\r
- Ptr = List;\r
-\r
- if (FeaturePcdGet (PcdVerifyNodeInList) && VerifyNodeInList) {\r
- //\r
- // Check to see if Node is a member of List. \r
- // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength\r
- //\r
- do {\r
- Ptr = Ptr->ForwardLink;\r
- if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r
- Count++;\r
- //\r
- // ASSERT() if the linked list is too long\r
- //\r
- ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));\r
-\r
- //\r
- // Return if the linked list is too long\r
- //\r
- if (Count >= PcdGet32 (PcdMaximumLinkedListLength)) {\r
- return (BOOLEAN)(Ptr == Node);\r
- }\r
- }\r
- } while ((Ptr != List) && (Ptr != Node)); \r
-\r
- if (Ptr != Node) {\r
- return FALSE;\r
- }\r
- }\r
-\r
- if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r
- //\r
- // Count the total number of nodes in List.\r
- // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength\r
- //\r
- do {\r
- Ptr = Ptr->ForwardLink;\r
- Count++;\r
- } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));\r
-\r
- //\r
- // ASSERT() if the linked list is too long\r
- //\r
- ASSERT (Count < PcdGet32 (PcdMaximumLinkedListLength));\r
- }\r
-\r
- return TRUE;\r
-}\r
-\r
-/**\r
- Initializes the head node of a doubly-linked list, and returns the pointer to\r
- the head node of the doubly-linked list.\r
-\r
- Initializes the forward and backward links of a new linked list. After\r
- initializing a linked list with this function, the other linked list\r
- functions may be used to add and remove nodes from the linked list. It is up\r
- to the caller of this function to allocate the memory for ListHead.\r
-\r
- If ListHead is NULL, then ASSERT().\r
-\r
- @param ListHead A pointer to the head node of a new doubly-linked list.\r
-\r
- @return ListHead\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-InitializeListHead (\r
- IN OUT LIST_ENTRY *ListHead\r
- )\r
-\r
-{\r
- ASSERT (ListHead != NULL);\r
-\r
- ListHead->ForwardLink = ListHead;\r
- ListHead->BackLink = ListHead;\r
- return ListHead;\r
-}\r
-\r
-/**\r
- Adds a node to the beginning of a doubly-linked list, and returns the pointer\r
- to the head node of the doubly-linked list.\r
-\r
- Adds the node Entry at the beginning of the doubly-linked list denoted by\r
- ListHead, and returns ListHead.\r
-\r
- If ListHead is NULL, then ASSERT().\r
- If Entry is NULL, then ASSERT().\r
- If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or\r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r
- of nodes in ListHead, including the ListHead node, is greater than or\r
- equal to PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param ListHead A pointer to the head node of a doubly-linked list.\r
- @param Entry A pointer to a node that is to be inserted at the beginning\r
- of a doubly-linked list.\r
-\r
- @return ListHead\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-InsertHeadList (\r
- IN OUT LIST_ENTRY *ListHead,\r
- IN OUT LIST_ENTRY *Entry\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Entry is not one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));\r
- \r
- Entry->ForwardLink = ListHead->ForwardLink;\r
- Entry->BackLink = ListHead;\r
- Entry->ForwardLink->BackLink = Entry;\r
- ListHead->ForwardLink = Entry;\r
- return ListHead;\r
-}\r
-\r
-/**\r
- Adds a node to the end of a doubly-linked list, and returns the pointer to\r
- the head node of the doubly-linked list.\r
-\r
- Adds the node Entry to the end of the doubly-linked list denoted by ListHead,\r
- and returns ListHead.\r
-\r
- If ListHead is NULL, then ASSERT().\r
- If Entry is NULL, then ASSERT().\r
- If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and prior to insertion the number\r
- of nodes in ListHead, including the ListHead node, is greater than or\r
- equal to PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param ListHead A pointer to the head node of a doubly-linked list.\r
- @param Entry A pointer to a node that is to be added at the end of the\r
- doubly-linked list.\r
-\r
- @return ListHead\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-InsertTailList (\r
- IN OUT LIST_ENTRY *ListHead,\r
- IN OUT LIST_ENTRY *Entry\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Entry is not one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry, FALSE));\r
- \r
- Entry->ForwardLink = ListHead;\r
- Entry->BackLink = ListHead->BackLink;\r
- Entry->BackLink->ForwardLink = Entry;\r
- ListHead->BackLink = Entry;\r
- return ListHead;\r
-}\r
-\r
-/**\r
- Retrieves the first node of a doubly-linked list.\r
-\r
- Returns the first node of a doubly-linked list. List must have been \r
- initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r
- If List is empty, then List is returned.\r
-\r
- If List is NULL, then ASSERT().\r
- If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r
- in List, including the List node, is greater than or equal to\r
- PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param List A pointer to the head node of a doubly-linked list.\r
-\r
- @return The first node of a doubly-linked list.\r
- @retval NULL The list is empty.\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-GetFirstNode (\r
- IN CONST LIST_ENTRY *List\r
- )\r
-{\r
- //\r
- // ASSERT List not too long\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (List, List, FALSE));\r
-\r
- return List->ForwardLink;\r
-}\r
-\r
-/**\r
- Retrieves the next node of a doubly-linked list.\r
-\r
- Returns the node of a doubly-linked list that follows Node. \r
- List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()\r
- or InitializeListHead(). If List is empty, then List is returned.\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and List contains more than\r
- PcdMaximumLinkedListLenth nodes, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r
-\r
- @param List A pointer to the head node of a doubly-linked list.\r
- @param Node A pointer to a node in the doubly-linked list.\r
-\r
- @return A pointer to the next node if one exists. Otherwise List is returned.\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-GetNextNode (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Node is one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r
-\r
- return Node->ForwardLink;\r
-}\r
-\r
-/**\r
- Retrieves the previous node of a doubly-linked list.\r
- \r
- Returns the node of a doubly-linked list that precedes Node. \r
- List must have been initialized with INTIALIZE_LIST_HEAD_VARIABLE()\r
- or InitializeListHead(). If List is empty, then List is returned.\r
- \r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and List contains more than\r
- PcdMaximumLinkedListLenth nodes, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r
- \r
- @param List A pointer to the head node of a doubly-linked list.\r
- @param Node A pointer to a node in the doubly-linked list.\r
- \r
- @return A pointer to the previous node if one exists. Otherwise List is returned.\r
- \r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-GetPreviousNode (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Node is one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r
- \r
- return Node->BackLink;\r
-}\r
-\r
-/**\r
- Checks to see if a doubly-linked list is empty or not.\r
-\r
- Checks to see if the doubly-linked list is empty. If the linked list contains\r
- zero nodes, this function returns TRUE. Otherwise, it returns FALSE.\r
-\r
- If ListHead is NULL, then ASSERT().\r
- If ListHead was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or \r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r
- in List, including the List node, is greater than or equal to\r
- PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param ListHead A pointer to the head node of a doubly-linked list.\r
-\r
- @retval TRUE The linked list is empty.\r
- @retval FALSE The linked list is not empty.\r
-\r
-**/\r
-BOOLEAN\r
-EFIAPI\r
-IsListEmpty (\r
- IN CONST LIST_ENTRY *ListHead\r
- )\r
-{\r
- //\r
- // ASSERT List not too long\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (ListHead, ListHead, FALSE));\r
- \r
- return (BOOLEAN)(ListHead->ForwardLink == ListHead);\r
-}\r
-\r
-/**\r
- Determines if a node in a doubly-linked list is the head node of a the same\r
- doubly-linked list. This function is typically used to terminate a loop that\r
- traverses all the nodes in a doubly-linked list starting with the head node.\r
-\r
- Returns TRUE if Node is equal to List. Returns FALSE if Node is one of the\r
- nodes in the doubly-linked list specified by List. List must have been\r
- initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(), \r
- then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r
- in List, including the List node, is greater than or equal to\r
- PcdMaximumLinkedListLength, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and Node is not a node in List and Node is not \r
- equal to List, then ASSERT().\r
-\r
- @param List A pointer to the head node of a doubly-linked list.\r
- @param Node A pointer to a node in the doubly-linked list.\r
-\r
- @retval TRUE Node is one of the nodes in the doubly-linked list.\r
- @retval FALSE Node is not one of the nodes in the doubly-linked list.\r
-\r
-**/\r
-BOOLEAN\r
-EFIAPI\r
-IsNull (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Node is one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r
- \r
- return (BOOLEAN)(Node == List);\r
-}\r
-\r
-/**\r
- Determines if a node the last node in a doubly-linked list.\r
-\r
- Returns TRUE if Node is the last node in the doubly-linked list specified by\r
- List. Otherwise, FALSE is returned. List must have been initialized with\r
- INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead().\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with INTIALIZE_LIST_HEAD_VARIABLE() or\r
- InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and the number of nodes\r
- in List, including the List node, is greater than or equal to\r
- PcdMaximumLinkedListLength, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and Node is not a node in List, then ASSERT().\r
-\r
- @param List A pointer to the head node of a doubly-linked list.\r
- @param Node A pointer to a node in the doubly-linked list.\r
-\r
- @retval TRUE Node is the last node in the linked list.\r
- @retval FALSE Node is not the last node in the linked list.\r
-\r
-**/\r
-BOOLEAN\r
-EFIAPI\r
-IsNodeAtEnd (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node\r
- )\r
-{\r
- //\r
- // ASSERT List not too long and Node is one of the nodes of List\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (List, Node, TRUE));\r
- \r
- return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);\r
-}\r
-\r
-/**\r
- Swaps the location of two nodes in a doubly-linked list, and returns the\r
- first node after the swap.\r
-\r
- If FirstEntry is identical to SecondEntry, then SecondEntry is returned.\r
- Otherwise, the location of the FirstEntry node is swapped with the location\r
- of the SecondEntry node in a doubly-linked list. SecondEntry must be in the\r
- same double linked list as FirstEntry and that double linked list must have\r
- been initialized with INTIALIZE_LIST_HEAD_VARIABLE() or InitializeListHead(). \r
- SecondEntry is returned after the nodes are swapped.\r
-\r
- If FirstEntry is NULL, then ASSERT().\r
- If SecondEntry is NULL, then ASSERT().\r
- If PcdVerifyNodeInList is TRUE and SecondEntry and FirstEntry are not in the \r
- same linked list, then ASSERT().\r
- If PcdMaximumLinkedListLength is not zero, and the number of nodes in the\r
- linked list containing the FirstEntry and SecondEntry nodes, including\r
- the FirstEntry and SecondEntry nodes, is greater than or equal to\r
- PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param FirstEntry A pointer to a node in a linked list.\r
- @param SecondEntry A pointer to another node in the same linked list.\r
- \r
- @return SecondEntry.\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-SwapListEntries (\r
- IN OUT LIST_ENTRY *FirstEntry,\r
- IN OUT LIST_ENTRY *SecondEntry\r
- )\r
-{\r
- LIST_ENTRY *Ptr;\r
-\r
- if (FirstEntry == SecondEntry) {\r
- return SecondEntry;\r
- }\r
-\r
- //\r
- // ASSERT Entry1 and Entry2 are in the same linked list\r
- //\r
- ASSERT (InternalBaseLibIsNodeInList (FirstEntry, SecondEntry, TRUE));\r
- \r
- //\r
- // Ptr is the node pointed to by FirstEntry->ForwardLink\r
- //\r
- Ptr = RemoveEntryList (FirstEntry);\r
-\r
- //\r
- // If FirstEntry immediately follows SecondEntry, FirstEntry will be placed\r
- // immediately in front of SecondEntry\r
- //\r
- if (Ptr->BackLink == SecondEntry) {\r
- return InsertTailList (SecondEntry, FirstEntry);\r
- }\r
-\r
- //\r
- // Ptr == SecondEntry means SecondEntry immediately follows FirstEntry,\r
- // then there are no further steps necessary\r
- //\r
- if (Ptr == InsertHeadList (SecondEntry, FirstEntry)) {\r
- return Ptr;\r
- }\r
-\r
- //\r
- // Move SecondEntry to the front of Ptr\r
- //\r
- RemoveEntryList (SecondEntry);\r
- InsertTailList (Ptr, SecondEntry);\r
- return SecondEntry;\r
-}\r
-\r
-/**\r
- Removes a node from a doubly-linked list, and returns the node that follows\r
- the removed node.\r
-\r
- Removes the node Entry from a doubly-linked list. It is up to the caller of\r
- this function to release the memory used by this node if that is required. On\r
- exit, the node following Entry in the doubly-linked list is returned. If\r
- Entry is the only node in the linked list, then the head node of the linked\r
- list is returned.\r
-\r
- If Entry is NULL, then ASSERT().\r
- If Entry is the head node of an empty list, then ASSERT().\r
- If PcdMaximumLinkedListLength is not zero, and the number of nodes in the\r
- linked list containing Entry, including the Entry node, is greater than\r
- or equal to PcdMaximumLinkedListLength, then ASSERT().\r
-\r
- @param Entry A pointer to a node in a linked list.\r
-\r
- @return Entry.\r
-\r
-**/\r
-LIST_ENTRY *\r
-EFIAPI\r
-RemoveEntryList (\r
- IN CONST LIST_ENTRY *Entry\r
- )\r
-{\r
- ASSERT (!IsListEmpty (Entry));\r
- \r
- Entry->ForwardLink->BackLink = Entry->BackLink;\r
- Entry->BackLink->ForwardLink = Entry->ForwardLink;\r
- return Entry->ForwardLink;\r
-}\r