+++ /dev/null
-/** @file\r
- Linked List Library Functions.\r
-\r
- Copyright (c) 2006, Intel Corporation<BR>\r
- All rights reserved. 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
- Module Name: LinkedList.c\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 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 List A pointer to a node in a linked list.\r
- @param Node A pointer to one nod.\r
-\r
- @retval TRUE Node is in List\r
- @retval FALSE Node isn't in List, or List is invalid\r
-\r
-**/\r
-BOOLEAN\r
-IsNodeInList (\r
- IN CONST LIST_ENTRY *List,\r
- IN CONST LIST_ENTRY *Node\r
- )\r
-{\r
- UINTN Count;\r
- CONST LIST_ENTRY *Ptr;\r
- BOOLEAN Found;\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 = PcdGet32 (PcdMaximumLinkedListLength);\r
-\r
- Ptr = List;\r
- do {\r
- Ptr = Ptr->ForwardLink;\r
- Count--;\r
- } while ((Ptr != List) && (Ptr != Node) && (Count > 0));\r
- Found = (BOOLEAN)(Ptr == Node);\r
-\r
- if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {\r
- while ((Count > 0) && (Ptr != List)) {\r
- Ptr = Ptr->ForwardLink;\r
- Count--;\r
- }\r
- ASSERT (Count > 0);\r
- }\r
-\r
- return Found;\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 *List\r
- )\r
-\r
-{\r
- ASSERT (List != NULL);\r
-\r
- List->ForwardLink = List;\r
- List->BackLink = List;\r
- return List;\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 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 *List,\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 (!IsNodeInList (List, Entry));\r
-\r
- Entry->ForwardLink = List->ForwardLink;\r
- Entry->BackLink = List;\r
- Entry->ForwardLink->BackLink = Entry;\r
- List->ForwardLink = Entry;\r
- return List;\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 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 *List,\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 (!IsNodeInList (List, Entry));\r
-\r
- Entry->ForwardLink = List;\r
- Entry->BackLink = List->BackLink;\r
- Entry->BackLink->ForwardLink = Entry;\r
- List->BackLink = Entry;\r
- return List;\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 InitializeListHead(). If List is empty, then NULL is\r
- returned.\r
-\r
- If List is NULL, then ASSERT().\r
- If List was not initialized with 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 (IsNodeInList (List, List));\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. List must have\r
- been initialized with InitializeListHead(). If List is empty, then List is\r
- returned.\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with InitializeListHead(), then ASSERT().\r
- If PcdMaximumLinkedListLenth is not zero, and List contains more than\r
- PcdMaximumLinkedListLenth nodes, then ASSERT().\r
- If 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 Pointer to the next node if one exists. Otherwise a null value which\r
- is actually 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 (IsNodeInList (List, Node));\r
-\r
- return Node->ForwardLink;\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 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 *List\r
- )\r
-{\r
- //\r
- // ASSERT List not too long\r
- //\r
- ASSERT (IsNodeInList (List, List));\r
-\r
- return (BOOLEAN)(List->ForwardLink == List);\r
-}\r
-\r
-/**\r
- Determines if a node in a doubly linked list is null.\r
-\r
- Returns FALSE if Node is one of the nodes in the doubly linked list specified\r
- by List. Otherwise, TRUE is returned. List must have been initialized with\r
- InitializeListHead().\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with 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 Node is not a node in List and Node is not 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 (IsNodeInList (List, Node));\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
- InitializeListHead().\r
-\r
- If List is NULL, then ASSERT().\r
- If Node is NULL, then ASSERT().\r
- If List was not initialized with 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 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 (IsNodeInList (List, Node));\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 InitializeListHead(). SecondEntry is returned after the\r
- nodes are swapped.\r
-\r
- If FirstEntry is NULL, then ASSERT().\r
- If SecondEntry is NULL, then ASSERT().\r
- If SecondEntry and FirstEntry are not in the 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
-**/\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 (IsNodeInList (FirstEntry, SecondEntry));\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 willl 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
projects / mirror_edk2.git / blobdiff