--- /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