--- /dev/null
+/*++\r
+\r
+Copyright (c) 2004, Intel Corporation \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:\r
+\r
+ LinkedList.c\r
+\r
+Abstract:\r
+\r
+ Linked List Library Functions\r
+\r
+--*/\r
+\r
+#include "Tiano.h"\r
+#include "EfiDriverLib.h"\r
+\r
+\r
+VOID\r
+InitializeListHead (\r
+ EFI_LIST_ENTRY *List\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Initialize the head of the List. The caller must allocate the memory \r
+ for the EFI_LIST. This function must be called before the other linked\r
+ list macros can be used.\r
+ \r
+Arguments:\r
+\r
+ List - Pointer to list head to initialize\r
+ \r
+Returns:\r
+\r
+ None.\r
+\r
+--*/\r
+\r
+{\r
+ List->ForwardLink = List;\r
+ List->BackLink = List;\r
+}\r
+\r
+\r
+BOOLEAN\r
+IsListEmpty (\r
+ EFI_LIST_ENTRY *List\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
+ The list must have been initialized with InitializeListHead () before using \r
+ this function.\r
+ \r
+Arguments:\r
+\r
+ List - Pointer to list head to test\r
+\r
+ \r
+Returns:\r
+\r
+ Return TRUE is the list contains zero nodes. Otherzise return FALSE.\r
+\r
+--*/\r
+{\r
+ return (BOOLEAN)(List->ForwardLink == List);\r
+}\r
+\r
+\r
+VOID\r
+RemoveEntryList (\r
+ EFI_LIST_ENTRY *Entry\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Remove Node from the doubly linked list. It is the caller's responsibility\r
+ to free any memory used by the entry if needed. The list must have been \r
+ initialized with InitializeListHead () before using this function.\r
+ \r
+Arguments:\r
+\r
+ Entry - Element to remove from the list.\r
+ \r
+Returns:\r
+ \r
+ None\r
+\r
+--*/\r
+{\r
+ EFI_LIST_ENTRY *_ForwardLink;\r
+ EFI_LIST_ENTRY *_BackLink;\r
+\r
+ _ForwardLink = Entry->ForwardLink;\r
+ _BackLink = Entry->BackLink; \r
+ _BackLink->ForwardLink = _ForwardLink;\r
+ _ForwardLink->BackLink = _BackLink; \r
+\r
+ DEBUG_CODE (\r
+ Entry->ForwardLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
+ Entry->BackLink = (EFI_LIST_ENTRY *) EFI_BAD_POINTER;\r
+ )\r
+}\r
+\r
+\r
+VOID\r
+InsertTailList (\r
+ EFI_LIST_ENTRY *ListHead,\r
+ EFI_LIST_ENTRY *Entry\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Insert a Node into the end of a doubly linked list. The list must have \r
+ been initialized with InitializeListHead () before using this function.\r
+ \r
+Arguments:\r
+\r
+ ListHead - Head of doubly linked list\r
+\r
+ Entry - Element to insert at the end of the list.\r
+ \r
+Returns:\r
+ \r
+ None\r
+\r
+--*/\r
+{\r
+ EFI_LIST_ENTRY *_ListHead;\r
+ EFI_LIST_ENTRY *_BackLink;\r
+\r
+ _ListHead = ListHead; \r
+ _BackLink = _ListHead->BackLink; \r
+ Entry->ForwardLink = _ListHead; \r
+ Entry->BackLink = _BackLink; \r
+ _BackLink->ForwardLink = Entry; \r
+ _ListHead->BackLink = Entry; \r
+}\r
+\r
+\r
+\r
+VOID\r
+InsertHeadList (\r
+ EFI_LIST_ENTRY *ListHead,\r
+ EFI_LIST_ENTRY *Entry\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Insert a Node into the start of a doubly linked list. The list must have \r
+ been initialized with InitializeListHead () before using this function.\r
+ \r
+Arguments:\r
+\r
+ ListHead - Head of doubly linked list\r
+\r
+ Entry - Element to insert to beginning of list\r
+ \r
+Returns:\r
+ \r
+ None\r
+\r
+--*/\r
+{\r
+ EFI_LIST_ENTRY *_ListHead;\r
+ EFI_LIST_ENTRY *_ForwardLink;\r
+\r
+ _ListHead = ListHead; \r
+ _ForwardLink = _ListHead->ForwardLink; \r
+ Entry->ForwardLink = _ForwardLink; \r
+ Entry->BackLink = _ListHead; \r
+ _ForwardLink->BackLink = Entry; \r
+ _ListHead->ForwardLink = Entry; \r
+}\r
+\r
+VOID\r
+SwapListEntries (\r
+ EFI_LIST_ENTRY *Entry1,\r
+ EFI_LIST_ENTRY *Entry2\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Swap the location of the two elements of a doubly linked list. Node2 \r
+ is placed in front of Node1. The list must have been initialized with \r
+ InitializeListHead () before using this function.\r
+ \r
+Arguments:\r
+\r
+ Entry1 - Element in the doubly linked list in front of Node2. \r
+\r
+ Entry2 - Element in the doubly linked list behind Node1.\r
+ \r
+Returns:\r
+ \r
+ None\r
+\r
+--*/\r
+{\r
+ EFI_LIST_ENTRY *Entry1ForwardLink;\r
+ EFI_LIST_ENTRY *Entry1BackLink;\r
+ EFI_LIST_ENTRY *Entry2ForwardLink;\r
+ EFI_LIST_ENTRY *Entry2BackLink;\r
+\r
+ Entry2ForwardLink = Entry2->ForwardLink; \r
+ Entry2BackLink = Entry2->BackLink; \r
+ Entry1ForwardLink = Entry1->ForwardLink; \r
+ Entry1BackLink = Entry1->BackLink; \r
+ Entry2BackLink->ForwardLink = Entry2ForwardLink; \r
+ Entry2ForwardLink->BackLink = Entry2BackLink; \r
+ Entry2->ForwardLink = Entry1; \r
+ Entry2->BackLink = Entry1BackLink; \r
+ Entry1BackLink->ForwardLink = Entry2; \r
+ Entry1->BackLink = Entry2; \r
+}\r
+\r
+\r
+EFI_LIST_ENTRY *\r
+GetFirstNode (\r
+ EFI_LIST_ENTRY *List \r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Return the first node pointed to by the list head. The list must \r
+ have been initialized with InitializeListHead () before using this \r
+ function and must contain data.\r
+ \r
+Arguments:\r
+\r
+ List - The head of the doubly linked list.\r
+ \r
+Returns:\r
+ \r
+ Pointer to the first node, if the list contains nodes. The list will\r
+ return a null value--that is, the value of List--when the list is empty.\r
+ See the description of IsNull for more information.\r
+\r
+\r
+--*/\r
+{\r
+ return List->ForwardLink;\r
+}\r
+\r
+\r
+EFI_LIST_ENTRY *\r
+GetNextNode (\r
+ EFI_LIST_ENTRY *List,\r
+ EFI_LIST_ENTRY *Node\r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Returns the node following Node in the list. The list must \r
+ have been initialized with InitializeListHead () before using this \r
+ function and must contain data.\r
+ \r
+Arguments:\r
+\r
+ List - The head of the list. MUST NOT be the literal value NULL.\r
+ Node - The node in the list. This value MUST NOT be the literal value NULL.\r
+ See the description of IsNull for more information.\r
+ \r
+Returns:\r
+ \r
+ Pointer to the next node, if one exists. Otherwise, returns a null value,\r
+ which is actually a pointer to List.\r
+ See the description of IsNull for more information.\r
+\r
+--*/\r
+{\r
+ if (Node == List) {\r
+ return List;\r
+ } \r
+ return Node->ForwardLink;\r
+}\r
+\r
+\r
+BOOLEAN \r
+IsNull ( \r
+ EFI_LIST_ENTRY *List,\r
+ EFI_LIST_ENTRY *Node \r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Determines whether the given node is null. Note that Node is null\r
+ when its value is equal to the value of List. It is an error for\r
+ Node to be the literal value NULL [(VOID*)0x0].\r
+\r
+Arguments:\r
+\r
+ List - The head of the list. MUST NOT be the literal value NULL.\r
+ Node - The node to test. MUST NOT be the literal value NULL. See\r
+ the description above.\r
+ \r
+Returns:\r
+ \r
+ Returns true if the node is null.\r
+\r
+--*/\r
+{\r
+ return (BOOLEAN)(Node == List);\r
+}\r
+\r
+\r
+BOOLEAN \r
+IsNodeAtEnd ( \r
+ EFI_LIST_ENTRY *List, \r
+ EFI_LIST_ENTRY *Node \r
+ )\r
+/*++\r
+\r
+Routine Description:\r
+\r
+ Determines whether the given node is at the end of the list. Used\r
+ to walk the list. The list must have been initialized with \r
+ InitializeListHead () before using this function and must contain \r
+ data.\r
+\r
+Arguments:\r
+\r
+ List - The head of the list. MUST NOT be the literal value NULL.\r
+ Node - The node to test. MUST NOT be the literal value NULL.\r
+ See the description of IsNull for more information.\r
+ \r
+Returns:\r
+ \r
+ Returns true if the list is the tail.\r
+\r
+--*/\r
+{\r
+ if (IsNull (List, Node)) {\r
+ return FALSE;\r
+ }\r
+ return (BOOLEAN)(List->BackLink == Node);\r
+}\r
+\r
projects / mirror_edk2.git / blobdiff