From 586cd1f1f4129ab7ec24543d4968801e17cc870b Mon Sep 17 00:00:00 2001 From: lhauch Date: Fri, 1 Jun 2007 14:49:55 +0000 Subject: Moved the MdePkg to OldMdePkg so that new code in MdePkg does not break existing builds. Also updated the SPD and FPD files UiNames git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@2616 6f19259b-4bc3-4df7-8a09-765794883524 --- MdePkg/Library/BaseLib/LinkedList.c | 465 ------------------------------------ 1 file changed, 465 deletions(-) delete mode 100644 MdePkg/Library/BaseLib/LinkedList.c (limited to 'MdePkg/Library/BaseLib/LinkedList.c') diff --git a/MdePkg/Library/BaseLib/LinkedList.c b/MdePkg/Library/BaseLib/LinkedList.c deleted file mode 100644 index f588eacd0c..0000000000 --- a/MdePkg/Library/BaseLib/LinkedList.c +++ /dev/null @@ -1,465 +0,0 @@ -/** @file - Linked List Library Functions. - - Copyright (c) 2006, Intel Corporation
- All rights reserved. This program and the accompanying materials - are licensed and made available under the terms and conditions of the BSD License - which accompanies this distribution. The full text of the license may be found at - http://opensource.org/licenses/bsd-license.php - - THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, - WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. - - Module Name: LinkedList.c - -**/ - -#include "BaseLibInternals.h" - -/** - Worker function that locates the Node in the List - - By searching the List, finds the location of the Node in List. At the same time, - 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 Node is NULL, then ASSERT(); - If PcdMaximumLinkedListLenth 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 List A pointer to a node in a linked list. - @param Node A pointer to one nod. - - @retval TRUE Node is in List - @retval FALSE Node isn't in List, or List is invalid - -**/ -BOOLEAN -IsNodeInList ( - IN CONST LIST_ENTRY *List, - IN CONST LIST_ENTRY *Node - ) -{ - UINTN Count; - CONST LIST_ENTRY *Ptr; - BOOLEAN Found; - - // - // Test the validity of List and Node - // - ASSERT (List != NULL); - ASSERT (List->ForwardLink != NULL); - ASSERT (List->BackLink != NULL); - ASSERT (Node != NULL); - - Count = PcdGet32 (PcdMaximumLinkedListLength); - - Ptr = List; - do { - Ptr = Ptr->ForwardLink; - Count--; - } while ((Ptr != List) && (Ptr != Node) && (Count > 0)); - Found = (BOOLEAN)(Ptr == Node); - - if (PcdGet32 (PcdMaximumLinkedListLength) > 0) { - while ((Count > 0) && (Ptr != List)) { - Ptr = Ptr->ForwardLink; - Count--; - } - ASSERT (Count > 0); - } - - return Found; -} - -/** - 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 *List - ) - -{ - ASSERT (List != NULL); - - List->ForwardLink = List; - List->BackLink = List; - return List; -} - -/** - 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 InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth 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 *List, - IN OUT LIST_ENTRY *Entry - ) -{ - // - // ASSERT List not too long and Entry is not one of the nodes of List - // - ASSERT (!IsNodeInList (List, Entry)); - - Entry->ForwardLink = List->ForwardLink; - Entry->BackLink = List; - Entry->ForwardLink->BackLink = Entry; - List->ForwardLink = Entry; - return List; -} - -/** - 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 InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth 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 *List, - IN OUT LIST_ENTRY *Entry - ) -{ - // - // ASSERT List not too long and Entry is not one of the nodes of List - // - ASSERT (!IsNodeInList (List, Entry)); - - Entry->ForwardLink = List; - Entry->BackLink = List->BackLink; - Entry->BackLink->ForwardLink = Entry; - List->BackLink = Entry; - return List; -} - -/** - Retrieves the first node of a doubly linked list. - - Returns the first node of a doubly linked list. List must have been - initialized with InitializeListHead(). If List is empty, then NULL is - returned. - - If List is NULL, then ASSERT(). - If List was not initialized with InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth 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 NULL The list is empty. - -**/ -LIST_ENTRY * -EFIAPI -GetFirstNode ( - IN CONST LIST_ENTRY *List - ) -{ - // - // ASSERT List not too long - // - ASSERT (IsNodeInList (List, 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 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 InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth is not zero, and List contains more than - PcdMaximumLinkedListLenth nodes, then ASSERT(). - If 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 Pointer to the next node if one exists. Otherwise a null value which - is actually 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 (IsNodeInList (List, Node)); - - return Node->ForwardLink; -} - -/** - 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 InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth 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 *List - ) -{ - // - // ASSERT List not too long - // - ASSERT (IsNodeInList (List, List)); - - return (BOOLEAN)(List->ForwardLink == List); -} - -/** - Determines if a node in a doubly linked list is null. - - Returns FALSE if Node is one of the nodes in the doubly linked list specified - by List. Otherwise, TRUE is returned. List must have been initialized with - InitializeListHead(). - - If List is NULL, then ASSERT(). - If Node is NULL, then ASSERT(). - If List was not initialized with InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth is not zero, and the number of nodes - in List, including the List node, is greater than or equal to - PcdMaximumLinkedListLength, then ASSERT(). - If 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 one of the nodes in the doubly linked list. - @retval FALSE Node is not one of the nodes in the doubly linked 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 (IsNodeInList (List, Node)); - - 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 - InitializeListHead(). - - If List is NULL, then ASSERT(). - If Node is NULL, then ASSERT(). - If List was not initialized with InitializeListHead(), then ASSERT(). - If PcdMaximumLinkedListLenth is not zero, and the number of nodes - in List, including the List node, is greater than or equal to - PcdMaximumLinkedListLength, then ASSERT(). - If 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 (IsNodeInList (List, Node)); - - 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 InitializeListHead(). SecondEntry is returned after the - nodes are swapped. - - If FirstEntry is NULL, then ASSERT(). - If SecondEntry is NULL, then ASSERT(). - If 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. - -**/ -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 (IsNodeInList (FirstEntry, SecondEntry)); - - // - // Ptr is the node pointed to by FirstEntry->ForwardLink - // - Ptr = RemoveEntryList (FirstEntry); - - // - // If FirstEntry immediately follows SecondEntry, FirstEntry willl 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 v1.2.3