LinkedList.c

Go to the documentation of this file.

 
#include "BaseLibInternals.h"
 
#if !defined (MDEPKG_NDEBUG)
#define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)  \
    do {                                                                     \
      if (FeaturePcdGet (PcdVerifyNodeInList)) {                             \
        ASSERT (InList == IsNodeInList ((FirstEntry), (SecondEntry)));       \
      } else {                                                               \
        ASSERT (InternalBaseLibIsListValid (FirstEntry));                    \
      }                                                                      \
    } while (FALSE)
#else
#define ASSERT_VERIFY_NODE_IN_VALID_LIST(FirstEntry, SecondEntry, InList)
#endif
 
BOOLEAN
EFIAPI
InternalBaseLibIsListValid (
  IN CONST LIST_ENTRY  *List
  )
{
  UINTN             Count;
  CONST LIST_ENTRY  *Ptr;
 
  //
  // Test the validity of List and Node
  //
  ASSERT (List != NULL);
  ASSERT (List->ForwardLink != NULL);
  ASSERT (List->BackLink != NULL);
 
  if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
    Count = 0;
    Ptr   = List;
 
    //
    // Count the total number of nodes in List.
    // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
    //
    do {
      Ptr = Ptr->ForwardLink;
      Count++;
    } while ((Ptr != List) && (Count < PcdGet32 (PcdMaximumLinkedListLength)));
 
    //
    // return whether linked list is too long
    //
    return (BOOLEAN)(Count < PcdGet32 (PcdMaximumLinkedListLength));
  }
 
  return TRUE;
}
 
BOOLEAN
EFIAPI
IsNodeInList (
  IN      CONST LIST_ENTRY  *FirstEntry,
  IN      CONST LIST_ENTRY  *SecondEntry
  )
{
  UINTN             Count;
  CONST LIST_ENTRY  *Ptr;
 
  //
  // ASSERT List not too long
  //
  ASSERT (InternalBaseLibIsListValid (FirstEntry));
 
  ASSERT (SecondEntry != NULL);
 
  Count = 0;
  Ptr   = FirstEntry;
 
  //
  // Check to see if SecondEntry is a member of FirstEntry.
  // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
  //
  do {
    Ptr = Ptr->ForwardLink;
    if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
      Count++;
 
      //
      // Return if the linked list is too long
      //
      if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
        return (BOOLEAN)(Ptr == SecondEntry);
      }
    }
 
    if (Ptr == SecondEntry) {
      return TRUE;
    }
  } while (Ptr != FirstEntry);
 
  return FALSE;
}
 
LIST_ENTRY *
EFIAPI
InitializeListHead (
  IN OUT  LIST_ENTRY  *ListHead
  )
 
{
  ASSERT (ListHead != NULL);
 
  ListHead->ForwardLink = ListHead;
  ListHead->BackLink    = ListHead;
  return ListHead;
}
 
LIST_ENTRY *
EFIAPI
InsertHeadList (
  IN OUT  LIST_ENTRY  *ListHead,
  IN OUT  LIST_ENTRY  *Entry
  )
{
  //
  // ASSERT List not too long and Entry is not one of the nodes of List
  //
  ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
 
  Entry->ForwardLink           = ListHead->ForwardLink;
  Entry->BackLink              = ListHead;
  Entry->ForwardLink->BackLink = Entry;
  ListHead->ForwardLink        = Entry;
  return ListHead;
}
 
LIST_ENTRY *
EFIAPI
InsertTailList (
  IN OUT  LIST_ENTRY  *ListHead,
  IN OUT  LIST_ENTRY  *Entry
  )
{
  //
  // ASSERT List not too long and Entry is not one of the nodes of List
  //
  ASSERT_VERIFY_NODE_IN_VALID_LIST (ListHead, Entry, FALSE);
 
  Entry->ForwardLink           = ListHead;
  Entry->BackLink              = ListHead->BackLink;
  Entry->BackLink->ForwardLink = Entry;
  ListHead->BackLink           = Entry;
  return ListHead;
}
 
LIST_ENTRY *
EFIAPI
GetFirstNode (
  IN      CONST LIST_ENTRY  *List
  )
{
  //
  // ASSERT List not too long
  //
  ASSERT (InternalBaseLibIsListValid (List));
 
  return List->ForwardLink;
}
 
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_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 
  return Node->ForwardLink;
}
 
LIST_ENTRY *
EFIAPI
GetPreviousNode (
  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_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 
  return Node->BackLink;
}
 
BOOLEAN
EFIAPI
IsListEmpty (
  IN      CONST LIST_ENTRY  *ListHead
  )
{
  //
  // ASSERT List not too long
  //
  ASSERT (InternalBaseLibIsListValid (ListHead));
 
  return (BOOLEAN)(ListHead->ForwardLink == ListHead);
}
 
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_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 
  return (BOOLEAN)(Node == 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_VERIFY_NODE_IN_VALID_LIST (List, Node, TRUE);
 
  return (BOOLEAN)(!IsNull (List, Node) && List->BackLink == Node);
}
 
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_VERIFY_NODE_IN_VALID_LIST (FirstEntry, SecondEntry, TRUE);
 
  //
  // Ptr is the node pointed to by FirstEntry->ForwardLink
  //
  Ptr = RemoveEntryList (FirstEntry);
 
  //
  // If FirstEntry immediately follows SecondEntry, FirstEntry will 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;
}
 
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;
}