+++ /dev/null
-/** @file\r
- Class for arbitrary sized FIFO queues.\r
-\r
- The FIFO is empty if both the Read and Write indexes are equal.\r
- The FIFO is full if the next write would make the Read and Write indexes equal.\r
-\r
- Member variable NumElements is the maximum number of elements that can be\r
- contained in the FIFO.\r
- If NumElements is ZERO, there is an error.\r
- NumElements should be in the range 1:N.\r
-\r
- Members WriteIndex and ReadIndex are indexes into the array implementing the\r
- FIFO. They should be in the range 0:(NumElements - 1).\r
-\r
- One element of the FIFO is always reserved as the "terminator" element. Thus,\r
- the capacity of a FIFO is actually NumElements-1.\r
-\r
- Copyright (c) 2012 - 2014, Intel Corporation. All rights reserved.<BR>\r
- This program and the accompanying materials are licensed and made available\r
- under the terms and conditions of the BSD License which accompanies this\r
- 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
-#include <Uefi.h>\r
-#include <Library/BaseLib.h>\r
-#include <Library/BaseMemoryLib.h>\r
-#include <Library/MemoryAllocationLib.h>\r
-\r
-#include <LibConfig.h>\r
-\r
-#include <assert.h>\r
-#include <errno.h>\r
-#include <stdlib.h>\r
-#include <stdint.h>\r
-#include <wchar.h>\r
-#include <Containers/Fifo.h>\r
-\r
-/** Determine number of items available to read from the FIFO.\r
-\r
- The number of items are either the number of bytes, or the number of elements\r
- depending upon the value of the As enumerator.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[in] As An enumeration variable whose value determines whether the\r
- returned value is the number of bytes or the number of elements\r
- currently contained by the FIFO.\r
-\r
- @retval 0 The FIFO is empty.\r
- @retval >=0 The number of items contained by the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_NumInQueue (\r
- cFIFO *Self,\r
- FIFO_ElemBytes As\r
-)\r
-{\r
- size_t Count;\r
-\r
- if(Self->ReadIndex <= Self->WriteIndex) {\r
- Count = Self->WriteIndex - Self->ReadIndex;\r
- }\r
- else {\r
- Count = Self->NumElements - (Self->ReadIndex - Self->WriteIndex);\r
- }\r
- if(As == AsBytes) {\r
- Count *= Self->ElementSize;\r
- }\r
- return Count;\r
-}\r
-\r
-/** Determine amount of free space in the FIFO that can be written into.\r
-\r
- The number of items are either the number of bytes, or the number of elements\r
- depending upon the value of the As enumerator.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[in] As An enumeration variable whose value determines whether the\r
- returned value is the number of bytes or the number of elements\r
- currently available in the FIFO.\r
-\r
- @retval 0 The FIFO is full.\r
- @retval >=0 The number of items which can be accepted by the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_FreeSpace (\r
- cFIFO *Self,\r
- FIFO_ElemBytes As\r
-)\r
-{\r
- size_t Count;\r
- UINT32 RDex;\r
- UINT32 WDex;\r
-\r
- RDex = Self->ReadIndex;\r
- WDex = Self->WriteIndex;\r
-\r
- if(RDex <= WDex) {\r
- Count = (Self->NumElements - (WDex - RDex)) - 1;\r
- }\r
- else {\r
- Count = (RDex - WDex)-1;\r
- }\r
- if(As == AsBytes) {\r
- Count *= Self->ElementSize;\r
- }\r
- return Count;\r
-}\r
-\r
-/** Reduce the FIFO contents by NumElem elements.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[in] NumElem Number of elements to delete from the FIFO.\r
-\r
- @retval 0 FIFO is now empty.\r
- @retval N>0 There are still N elements in the FIFO.\r
- @retval -1 There are fewer than NumElem elements in the FIFO.\r
-**/\r
-static\r
-ssize_t\r
-FIFO_Reduce (\r
- cFIFO *Self,\r
- size_t NumElem\r
- )\r
-{\r
- size_t QCount;\r
- ssize_t RetVal;\r
-\r
- assert(Self != NULL);\r
-\r
- QCount = FIFO_NumInQueue(Self, AsElements);\r
- if(NumElem > QCount) {\r
- RetVal = -1;\r
- errno = EINVAL;\r
- }\r
- else {\r
- RetVal = (ssize_t)ModuloAdd(Self->ReadIndex, (UINT32)NumElem, Self->NumElements);\r
- Self->ReadIndex = (UINT32)RetVal;\r
-\r
- RetVal = (ssize_t)(QCount - NumElem);\r
- }\r
- return RetVal;\r
-}\r
-\r
-/** Test whether the FIFO is empty.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-\r
- @retval TRUE The FIFO is empty.\r
- @retval FALSE There is data in the FIFO.\r
-**/\r
-static\r
-BOOLEAN\r
-EFIAPI\r
-FIFO_IsEmpty (\r
- cFIFO *Self\r
- )\r
-{\r
- assert(Self != NULL);\r
-\r
- return (BOOLEAN)(Self->WriteIndex == Self->ReadIndex);\r
-}\r
-\r
-/** Test whether the FIFO is full.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-\r
- @retval TRUE The FIFO is full.\r
- @retval FALSE There is free space in the FIFO.\r
-**/\r
-static\r
-BOOLEAN\r
-EFIAPI\r
-FIFO_IsFull (\r
- cFIFO *Self\r
- )\r
-{\r
- assert(Self != NULL);\r
-\r
- return (BOOLEAN)(ModuloIncrement(Self->WriteIndex, Self->NumElements) == (INT32)Self->ReadIndex);\r
-}\r
-\r
-/** Add one or more elements to the FIFO.\r
-\r
- This function allows one to add one or more elements, as specified by Count,\r
- to the FIFO. Each element is of the size specified when the FIFO object\r
- was instantiated (FIFO.ElementSize).\r
-\r
- pElement points to the first byte of the first element to be added.\r
- If multiple elements are to be added, the elements are expected to be\r
- organized as a packed array.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[in] pElement Pointer to the element(s) to enqueue (add).\r
- @param[in] Count Number of elements to add.\r
-\r
- @retval 0 The FIFO is full.\r
- @retval >=0 The number of elements added to the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Enqueue (\r
- cFIFO *Self,\r
- const void *pElement,\r
- size_t Count\r
- )\r
-{\r
- uintptr_t ElemPtr;\r
- uintptr_t QPtr;\r
- size_t i;\r
- UINT32 SizeOfElement;\r
- UINT32 Windex;\r
-\r
- assert(Self != NULL);\r
- assert(pElement != NULL);\r
-\r
- if(FIFO_IsFull(Self)) { // FIFO is full so can't add to it\r
- Count = 0; // Zero characters added\r
- }\r
- else { // Otherwise, FIFO is not full...\r
- Count = MIN(Count, Self->FreeSpace(Self, AsElements)); // Smaller of requested or available space\r
- SizeOfElement = Self->ElementSize; // Size of Elements, in bytes\r
- Windex = Self->WriteIndex; // Index of first writable slot in FIFO\r
-\r
- ElemPtr = (uintptr_t)pElement; // Addr. of element to add, as an integer\r
- QPtr = (uintptr_t)Self->Queue + (SizeOfElement * Windex); // Addr. in FIFO to write, as an integer\r
-\r
- for(i = 0; i < Count; ++i) { // For Count elements...\r
- (void)CopyMem((void *)QPtr, (const void *)ElemPtr, SizeOfElement); // Copy an element into the FIFO\r
- Windex = (UINT32)ModuloIncrement(Windex, Self->NumElements); // Increment the Write index, wrap if necessary\r
- if(Windex == 0) { // If the index wrapped\r
- QPtr = (uintptr_t)Self->Queue; // Go to the beginning\r
- }\r
- else {\r
- QPtr += SizeOfElement; // Otherwise, point to next in FIFO\r
- }\r
- ElemPtr += SizeOfElement; // And also point to next Element to add\r
- }\r
- Self->WriteIndex = Windex; // Finally, save the new Write Index\r
- }\r
- return Count; // Number of elements added to FIFO\r
-}\r
-\r
-/** Read or copy elements from the FIFO.\r
-\r
- This function allows one to read one or more elements, as specified by Count,\r
- from the FIFO. Each element is of the size specified when the FIFO object\r
- was instantiated (FIFO.ElementSize).\r
-\r
- pElement points to the destination of the first byte of the first element\r
- to be read. If multiple elements are to be read, the elements are expected\r
- to be organized as a packed array.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[out] pElement Pointer to where to store the element(s) read from the FIFO.\r
- @param[in] Count Number of elements to dequeue.\r
- @param[in] Consume If TRUE, consume read elements. Otherwise, preserve.\r
-\r
- @retval 0 The FIFO is empty.\r
- @retval >=0 The number of elements read from the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Dequeue (\r
- cFIFO *Self,\r
- void *pElement,\r
- size_t Count,\r
- BOOLEAN Consume\r
- )\r
-{\r
- UINTN QPtr;\r
- UINT32 RDex;\r
- UINT32 SizeOfElement;\r
- UINT32 i;\r
-\r
- assert(Self != NULL);\r
- assert(pElement != NULL);\r
-\r
- if(FIFO_IsEmpty(Self)) {\r
- Count = 0;\r
- }\r
- else {\r
- RDex = Self->ReadIndex; // Get this FIFO's Read Index\r
- SizeOfElement = Self->ElementSize; // Get size of this FIFO's elements\r
- Count = MIN(Count, Self->Count(Self, AsElements)); // Lesser of requested or actual\r
-\r
- QPtr = (UINTN)Self->Queue + (RDex * SizeOfElement); // Point to Read location in FIFO\r
- for(i = 0; i < Count; ++i) { // Iterate Count times...\r
- (void)CopyMem(pElement, (const void *)QPtr, SizeOfElement); // Copy element from FIFO to caller's buffer\r
- RDex = (UINT32)ModuloIncrement(RDex, Self->NumElements); // Increment Read Index\r
- if(RDex == 0) { // If the index wrapped\r
- QPtr = (UINTN)Self->Queue; // Point back to beginning of data\r
- }\r
- else { // Otherwise\r
- QPtr += SizeOfElement; // Point to the next element in FIFO\r
- }\r
- pElement = (char*)pElement + SizeOfElement; // Point to next element in caller's buffer\r
- } // Iterate: for loop\r
- if(Consume) { // If caller requests data consumption\r
- Self->ReadIndex = RDex; // Set FIFO's Read Index to new Index\r
- }\r
- }\r
- return Count; // Return number of elements actually read\r
-}\r
-\r
-/** Read elements from the FIFO.\r
-\r
- Read the specified number of elements from the FIFO, removing each element read.\r
- The number of elements actually read from the FIFO is returned. This number can differ\r
- from the Count requested if more elements are requested than are in the FIFO.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[out] pElement Pointer to where to store the element read from the FIFO.\r
- @param[in] Count Number of elements to dequeue.\r
-\r
- @retval 0 The FIFO is empty.\r
- @retval >=0 The number of elements read from the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Read (\r
- cFIFO *Self,\r
- void *pElement,\r
- size_t Count\r
- )\r
-{\r
- return FIFO_Dequeue(Self, pElement, Count, TRUE);\r
-}\r
-\r
-/** Make a copy of the FIFO's data.\r
- The contents of the FIFO is copied out and linearized without affecting the\r
- FIFO contents. This function is idempotent.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[out] pElement Pointer to where to store the elements copied from the FIFO.\r
- @param[in] Count Number of elements to copy.\r
-\r
- @retval 0 The FIFO is empty.\r
- @retval >=0 The number of elements copied from the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Copy (\r
- cFIFO *Self,\r
- void *pElement,\r
- size_t Count\r
- )\r
-{\r
- return FIFO_Dequeue(Self, pElement, Count, FALSE);\r
-}\r
-\r
-/** Get the FIFO's current Read Index.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-**/\r
-static\r
-UINT32\r
-EFIAPI\r
-FIFO_GetRDex (\r
- cFIFO *Self\r
-)\r
-{\r
- assert(Self != NULL);\r
-\r
- return Self->ReadIndex;\r
-}\r
-\r
-/** Get the FIFO's current Write Index.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-\r
- @return The current value of the FIFO's WriteIndex member is returned.\r
-**/\r
-static\r
-UINT32\r
-EFIAPI\r
-FIFO_GetWDex (\r
- cFIFO *Self\r
-)\r
-{\r
- assert(Self != NULL);\r
-\r
- return Self->WriteIndex;\r
-}\r
-\r
-/** Cleanly delete a FIFO instance.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-**/\r
-static\r
-void\r
-EFIAPI\r
-FIFO_Delete (\r
- cFIFO *Self\r
- )\r
-{\r
- assert(Self != NULL);\r
-\r
- if(Self->Queue != NULL) {\r
- FreePool(Self->Queue);\r
- Self->Queue = NULL; // Zombie catcher\r
- }\r
- FreePool(Self);\r
-}\r
-\r
-/** Empty the FIFO, discarding up to NumToFlush elements.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
- @param[in] NumToFlush Number of elements to flush from the FIFO.\r
- If larger than the number of elements in the\r
- FIFO, the FIFO is emptied.\r
-\r
- @return Returns the number of elements remaining in the FIFO after the flush.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Flush (\r
- cFIFO *Self,\r
- size_t NumToFlush\r
- )\r
-{\r
- size_t NumInQ;\r
- size_t Remainder;\r
-\r
- assert(Self != NULL);\r
-\r
- NumInQ = FIFO_NumInQueue(Self, AsElements);\r
- if(NumToFlush >= NumInQ) {\r
- Self->ReadIndex = 0;\r
- Self->WriteIndex = 0;\r
- Remainder = 0;\r
- }\r
- else {\r
- Remainder = FIFO_Reduce(Self, NumToFlush);\r
- }\r
- return Remainder;\r
-}\r
-\r
-/** Remove the most recently added element from the FIFO.\r
-\r
- @param[in] Self Pointer to the FIFO instance.\r
-\r
- @return Returns the number of elements remaining in the FIFO.\r
-**/\r
-static\r
-size_t\r
-EFIAPI\r
-FIFO_Truncate (\r
- cFIFO *Self\r
- )\r
-{\r
- size_t Remainder;\r
-\r
- assert(Self != NULL);\r
-\r
- Remainder = FIFO_NumInQueue(Self, AsElements);\r
- if(Remainder > 0) {\r
- Self->WriteIndex = (UINT32)ModuloDecrement(Self->WriteIndex, Self->NumElements);\r
- --Remainder;\r
- }\r
- return Remainder;\r
-}\r
-\r
-/** Construct a new instance of a FIFO Queue.\r
-\r
- @param[in] NumElements Number of elements to be contained in the new FIFO.\r
- @param[in] ElementSize Size, in bytes, of an element.\r
-\r
- @retval NULL Unable to create the instance.\r
- @retval NonNULL Pointer to the new FIFO instance.\r
-**/\r
-cFIFO *\r
-EFIAPI\r
-New_cFIFO(\r
- UINT32 NumElements,\r
- size_t ElementSize\r
- )\r
-{\r
- cFIFO *FIFO;\r
- UINT8 *Queue;\r
-\r
- FIFO = NULL;\r
- if((NumElements > 2) && (ElementSize > 0)) {\r
- FIFO = (cFIFO *)AllocatePool(sizeof(cFIFO));\r
- if(FIFO != NULL) {\r
- Queue = (UINT8 *)AllocateZeroPool(NumElements * ElementSize);\r
- if(Queue != NULL) {\r
- FIFO->Write = FIFO_Enqueue;\r
- FIFO->Read = FIFO_Read;\r
- FIFO->Copy = FIFO_Copy;\r
- FIFO->IsEmpty = FIFO_IsEmpty;\r
- FIFO->IsFull = FIFO_IsFull;\r
- FIFO->Count = FIFO_NumInQueue;\r
- FIFO->FreeSpace = FIFO_FreeSpace;\r
- FIFO->Flush = FIFO_Flush;\r
- FIFO->Truncate = FIFO_Truncate;\r
- FIFO->Delete = FIFO_Delete;\r
- FIFO->GetRDex = FIFO_GetRDex;\r
- FIFO->GetWDex = FIFO_GetWDex;\r
-\r
- FIFO->Queue = Queue;\r
- FIFO->ElementSize = (UINT32)ElementSize;\r
- FIFO->NumElements = (UINT32)NumElements;\r
- FIFO->ReadIndex = 0;\r
- FIFO->WriteIndex = 0;\r
- }\r
- else {\r
- FreePool(FIFO);\r
- FIFO = NULL;\r
- }\r
- }\r
- }\r
- return FIFO;\r
-}\r