summaryrefslogtreecommitdiff
path: root/MdePkg
AgeCommit message (Collapse)Author
2014-11-12MdePkg: Add RETURN_ADDRESS macro into Base.h.Star Zeng
Based on compiler intrinsic function. MSVC: _ReturnAddress GCC: __builtin_return_address Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed-by: Jiewen Yao <jiewen.yao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16334 6f19259b-4bc3-4df7-8a09-765794883524
2014-11-07Add safe string function to base lib.jyao1
Contributed-under: TianoCore Contribution Agreement 1.0 signed off by: Yao, Jiewen <jiewen.yao@intel.com> reviewed by: Ni, Ruiyu <ruiyu.ni@intel.com> reviewed by: Long, Qin <qin.long@intel.com> reviewed by: Kinney, Michael D <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16312 6f19259b-4bc3-4df7-8a09-765794883524
2014-11-04MdePkg: fix comments typo about EFIAPI for X64Chen Fan
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Chen Fan <chen.fan.fnst@cn.fujitsu.com> Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16299 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-31EDK II Contributions.txt: Update patch format informationJordan Justen
Update to show what the patch looks like in email form. NOTE: This does not modify the wording of the "TianoCore Contribution Agreement 1.0" section Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Jaben Carsey <jaben.carsey@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16297 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-31MdePkg/ProcessorBind.h: Add ARM and AArch64 GCC macros for ClangOlivier Martin
When compiling with Clang, we still use GNU as for the assembler, so we still need to define the GCC_ASM* macros. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Olivier Martin <olivier.martin@arm.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16282 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-31MdePkg/IntelFrameworkPkg HobLib: Update BuildResourceDescriptorWithOwnerHob()Star Zeng
to align the behavior of BuildResourceDescriptorHob(). Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16279 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-27MdePkg/IntelFrameworkPkg HobLib: Add BuildResourceDescriptorWithOwnerHob() API.Star Zeng
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> Reviewed-by: Jiewen Yao <jiewen.yao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16230 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-24Clean not in pub spec comments status codes returned for functions of ↵Gao, Liming
EFI_TCG_PROTOCOL Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Long, Qin <qin.long@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16229 6f19259b-4bc3-4df7-8a09-765794883524
2014-10-22[MdePkg] Code clean-up: Remove trailing spacesLee Leahy
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Lee Leahy <leroy.p.leahy@intel.com> Reviewed-by: Erik Bjorge <erik.c.bjorge@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16223 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-04MdePkg NASM Thunk16: Add missing ASM_PFX for InternalAsmThunk16Jordan Justen
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16059 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-04MdePkg NASM Thunk16: Work around NASM 2.09.04 - 2.10rc1 bugJordan Justen
Without this change, NASM 2.09.04 will hang with OVMF+CSM on both IA32 and X64. Tested on OVMF+CSM on GCC49 with NASM 2.07, 2.09.04 and 2.11. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16058 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-03MdePkg: Convert non DOS format files to DOS formatGao, Liming
Module UNI and Package UNI files are not DOS format. Convert them to DOS format. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16042 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-02Update MdePkg package version from 1.04 to 1.05Gao, Liming
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16028 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib NASM Thunk16: Initialize _16GdtrBase to 0Jordan Justen
Previously we were setting it to the start of the GDT in the UEFI driver's copy of BaseLib. This address is irrelavent, since the C code will initialize it to the cooresponding address after the Thunk16 code has been placed in low memory. Additionally, initializing this was causing a link error for the XCLANG toolchain. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16025 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib NASM Thunk16: Remove remaining 'DB' codeJordan Justen
Convert remaining 'DB' code to assembly code by: * Move instruction immediate data labels to end of instruction * Use strict keyword to make sure immediate data size is not optimized Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16024 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib NASM Thunk16: Use bits 16 for 16-bit codeJordan Justen
By using 'bits 16', we can write code for 16-bit use the actual assembly syntax rather than 'DB' and sometimes writing code with seemingly incorrect operands because we know it will run correctly when the processor is running in 16-bit mode. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16023 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib NASM Thunk16: Use NASM local labelsJordan Justen
http://www.nasm.us/doc/nasmdoc3.html#section-3.9 A local label is a label beginning with the period, and it's actual name is prefixed by the previous non-local label. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16022 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib Thunk16: Replace X64 GAS Thunk16 with NASM versionJordan Justen
This is a translation of X64/Thunk16.asm to NASM. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16021 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg BaseLib Thunk16: Replace IA32 GAS Thunk16 with NASM versionJordan Justen
This is a translation of Ia32/Thunk16.asm to NASM. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16020 6f19259b-4bc3-4df7-8a09-765794883524
2014-09-01MdePkg Base.h: Always define ASM_PFXJordan Justen
Some compilers may define __USER_LABEL_PREFIX__ to determine the prefix used with ASM_PFX. Otherwise, IA32 will use a single underscore '_' character, and all other architectures will use an empty prefix. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@16019 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-28Don't initialize local variables in its declaration. Gao, Liming
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15972 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-28Add IMAGE_ATTRIBUTE_UEFI_IMAGE definition from UEFI 2.4 specification.Samer El-Haj-Mahmoud elhaj
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Samer El-Haj-Mahmoud elhaj@hp.com Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15970 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-28MdePkg Acpi51.h:Correct the declaration of ↵Star Zeng
EFI_ACPI_5_1_GTDT_SBSA_GENERIC_WATCHDOG_STRUCTURE. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed by: Jiewen Yao <jiewen.yao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15961 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-27MdePkg: INF/DEC file updates to EDK II packagesGao, Liming
5. Add PACKAGE_UNI_FILE UNI file that contains the localized Abstract and Description of a package and localized strings associated with PCDs. a. Addresses an information gap between DEC files and the UEFI Distribution Packaging Specification XML schema b. There will be an associated update to UPT in BaseTools to consume PACKAGE_UNI_FILE and associated UNI file during UDP creation that performs the DEC -> XML conversion. c. There will be an associated update to UPT in BaseTools to produce PACKAGE_UNI_FILE and associated UNI file during UDP installation that performs the XML -> DEC conversion. 6. Add Package Extra UNI file that provides the localized Name of a package. a. [UserExtensions.TianoCore."ExtraFiles"] provides an easy method for a package to specify extra files to be added to a UDP without having to list the files in the UPT package information data file. b. There will be an associated update to UPT in BaseTools to package up files listed in [UserExtensions.TianoCore."ExtraFiles"] during UDP creation. c. UNI file contains localized name of a package to go along with the localized Abstract and Description from the PACKAGE_UNI_FILE. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15920 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-27MdePkg: INF/DEC file updates to EDK II packagesGao, Liming
4. PCD information in DEC file comment blocks are either incomplete or incorrect. This includes detailed description, @Prompt, @ValidRange, @ValidList, @Expression, and [Error.<TokenSpaceGuid>] validation error messages. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15919 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-27MdePkg: INF/DEC file updates to EDK II packagesGao, Liming
2. Add MODULE_UNI_FILE file that contains the localized Abstract and Description of a module. a. Addresses an information gap between INF files and the UEFI Distribution Packaging Specification XML schema b. There will be an associated update to UPT in BaseTools to consume MODULE_UNI_FILE and associated UNI file during UDP creation that performs the INF -> XML conversion. c. There will be an associated update to UPT in BaseTools to produce MODULE_UNI_FILE and associated UNI file during UDP installation that performs the XML -> INF conversion. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15918 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-27MdePkg: INF/DEC file updates to EDK II packagesGao, Liming
1. Usage information in INF file comment blocks are either incomplete or incorrect. This includes usage information for Protocols/PPIs/GUIDs/PCDs/HOBs/Events/BootModes. The syntax for usage information in comment blocks is defined in the EDK II Module Information (INF) Specification Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15917 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-26Add PCI PMC and PMCSR register definitions from PCI Power Management ↵Samer El-Haj-Mahmoud elhaj
Interface Specification Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Samer El-Haj-Mahmoud elhaj@hp.com Reviewed-by: Ruiyu Ni <ruiyu.ni@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15895 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-26Update EFI_DRIVER_HEALTH_HII_MESSAGE definition from UEFI 2.4 specification ↵Samer El-Haj-Mahmoud elhaj
to replace Reserved with MessageCode. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Samer El-Haj-Mahmoud elhaj@hp.com Reviewed-by: Ruiyu Ni <ruiyu.ni@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15894 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-25EDK II Contributions.txt: Note acceptable contribution licensesJordan Justen
We strongly prefer that contribtions be offered using the same license as the project/module. But, we should document other acceptable licenses for contributions. This will allow package owners to more easily know if they can accept a contribution under a different source license. NOTE: This does not modify the wording of the "TianoCore Contribution Agreement 1.0" section Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Mark Doran <mark.doran@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15892 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-22Only reserve the aligned memory instead of reserving the unaligned memory in ↵Gao, Liming
PeiMemoryAllocationLib Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15878 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-21MdePkg: Introduced BaseStackCheckLib (cont.)Andrew Fish
Liming proposed different changes compare to the latest patch. This commit ensures the changes goes in his direction. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Andrew Fish <afish@apple.com> Signed-off-by: Olivier Martin <olivier.martin@arm.com Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15866 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-20MdePkg: Introduced BaseStackCheckLib (cont.)Andrew Fish
This library only support GCC, RVCT and XCode for now. The new files were missing from SVN rev15851. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Andrew Fish <afish@apple.com> Signed-off-by: Olivier Martin <olivier.martin@arm.com Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15852 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-20MdePkg: Introduced BaseStackCheckLibAndrew Fish
This library only support GCC, RVCT and XCode for now. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Andrew Fish <afish@apple.com> Signed-off-by: Olivier Martin <olivier.martin@arm.com Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15851 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-20MdePkg: BaseOrderedCollectionRedBlackTreeLib: improve coding styleEric Dong
- The edk2 coding style prefers each variable declaration to stand on its own line. - Internal linkage (ie. STATIC) functions have caused problems with source level debugging before, so we generally avoid STATIC in MdePkg. - Even forward declarations of functions should carry full comment blocks. - Nullity checks in controlling expressions should be spelled out explicitly, as (Ptr != NULL). Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Eric Dong <eric.dong@intel.com> Reviewed-by: Laszlo Ersek <lersek@redhat.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15843 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-16MdePkg: library INF files should reference feature PCDs under [FeaturePcd]Laszlo Ersek
This patch updates users of PcdVerifyNodeInList and PcdValidateOrderedCollection. Suggested-by: Liming Gao <liming.gao@intel.com> Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Jordan Justen <jordan.l.justen@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15814 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-16MdePkg: BaseOrderedCollectionRedBlackTreeLib: silence invalid VS2005 warningsLaszlo Ersek
VS2005 reports the following build failure: BaseOrderedCollectionRedBlackTreeLib.c(151) : warning C4244: 'return' : conversion from 'int' to 'BOOLEAN', possible loss of data BaseOrderedCollectionRedBlackTreeLib.c(840) : warning C4244: 'return' : conversion from 'int' to 'BOOLEAN', possible loss of data This is incorrect. The ISO C standard guarantees that the expressions in question can only return values 0 and 1, both of which can be represented by BOOLEAN (== UINT8, == unsigned char). Silence the incorrect warnings with explicit casts to BOOLEAN. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Jordan Justen <jordan.l.justen@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15813 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-16MdePkg: BaseOrderedCollectionRedBlackTreeLib: silence invalid gcc warningLaszlo Ersek
Gcc-4.4 reports the following build failure: BaseOrderedCollectionRedBlackTreeLib.c: In function 'OrderedCollectionInsert': BaseOrderedCollectionRedBlackTreeLib.c:586: error: 'Result' may be used uninitialized in this function This is incorrect. There are two areas of use of Result to consider: - In the very first while loop. The warning is likely not about this code area, because Result is assigned directly before use. - The last use of Result in the function. The build warning / error is incorrect. For Result to be uninitialized at that point, the very first while loop must not have been entered at all (because that loop assigns a value to Result). However, if that loop is never entered, then Parent is still NULL. And Parent==NULL implies that the use of Result is never reached, because we jump to the Done label just before it. Assign an irrelevant value of 0 to Result at the beginning of the function in order to silence the incorrect warning. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Jordan Justen <jordan.l.justen@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15812 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-14Roll-back from an accidental commit.lhauch
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: lhauch <larry.hauch@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15807 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-14Change svn:mime-type property on all Unicode files (extension .uni) in edk2lhauch
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: lhauch <larry.hauch@intel.com> Reviewed-by: Samer El-Haj-Mahmoud <samer.el-haj-mahmoud@hp.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15806 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-12MdePkg: introduce BaseOrderedCollectionRedBlackTreeLib library instanceLaszlo Ersek
edk2 should have a fast and easy-to-use associative array (a dictionary) type. Red-black trees have O(log(n)) worst case time complexity for lookup, insertion, and deletion (where n is the number of nodes in the tree). They support minimum and maximum lookup with the same time complexity, hence red-black trees double as priority queues as well. Given an iterator to a red-black tree node, getting the next or previous node (which corresponds to the ordered successor or the predecessor, respectively, according to the user-defined ordering) is O(log(n)) as well. The code reflects the Binary Search Trees and Red-Black Trees chapters of Introduction to Algorithms, by Cormen, Leiserson, Rivest. One point where the implementation diverges is the first phase of the Delete() operation. During that phase, the book's algorithm copies the key and other business *contents* of the successor node (in case the successor node is affected), and releases the successor node (instead of the node that the user requested to delete). While semantically correct, this would break the above iterator validity guarantee. This implementation replaces the copying of business contents between nodes with suitable relinking of nodes, so that all iterators (except the one whose deletion is being requested) remain valid. I had written this code originally in approx. 2002. I personally own the copyright of that version and am hereby relicensing it to Red Hat, under the BSDL. I had used the original code in a few personal projects since, for example in the lbzip2-0.x parallel (de)compressor, and now I've ported the library to edk2. Both during the original implementation and now during the porting I verified all the cases and their proofs as rigorously as I could, on paper. (NB, I couldn't find any errors in the 2002 code now.) During the porting to edk2, I documented all those cases in code comments as well (at least half of the source is documentation). These comments are not blind copies of diagrams from the Algorithms book, nor are they copies from my original code -- I've done them all fresh now, and I've only matched the results against the book. Reviewers are invited to sit down with a pen, some paper, the book, and the code. The Validate() function verifies the internal red-black properties of the tree. This function helps with unit testing, and is only invoked when requested with the PcdValidateOrderedCollection feature flag. A note about diagrams: edges represented by backslash (\) characters are often written as "\_", ie. with a following underscore. This is because line-trailing backslashes are processed very early in compilation (in translation phase 2), "splicing physical source lines to form logical source lines". Since the edk2 coding style requires "//" comments for such documentation, a trailing backslash would splice the next physical line into the "scope" of the comment. To prevent this, trailing backslashes are defanged by appending underscores, which should be visually bearable. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15791 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-12MdePkg: introduce OrderedCollectionLib library classKinney, Michael D
This library class provides a set of APIs to manage an ordered collection of items: - Init(), - UnInit(), - Insert(), - Delete(), - IsEmpty(), - Next(), - Prev(), - Min(), - Max(), - Find(), - UserStruct(). There are many ways to implement an ordered collection. Depending on the frequency of the different actions, different internal implementations may have different performance, memory overhead, or code size. Developers can select the library instance for a platform or module in their DSC files that meets the needs of that platform or module. Commit-message-from: "Kinney, Michael D" <michael.d.kinney@intel.com> Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15790 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-11MdePkg: Fix Clang build failureGao, Liming
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Gao, Liming <liming.gao@intel.com> Reviewed-by: Andrew Fish <afish@apple.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15784 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-08Added SMBIOS 2.8.0 updates.Elvin Li
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Elvin Li <elvin.li@intel.com> Reviewed-by: Star Zeng <star.zeng@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15780 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-07Add type cast for better coding style.Qiu Shumin
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Qiu Shumin <shumin.qiu@intel.com> Reviewed-by: Eric Dong <eric.dong@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15769 6f19259b-4bc3-4df7-8a09-765794883524
2014-08-04Add missing ACPI5.1 table.jyao1
Contributed-under: TianoCore Contribution Agreement 1.0 Signed off by: Jiewen Yao <jiewen.yao@intel.com> Reviewed by: Star Zeng <star.zeng@intel.com> Reviewed by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15746 6f19259b-4bc3-4df7-8a09-765794883524
2014-07-28Add ACPI5.1 header file.jyao1
Contributed-under: TianoCore Contribution Agreement 1.0 Signed off by: Jiewen Yao <jiewen.yao@intel.com> Reviewed by: Star Zeng <star.zeng@intel.com> Reviewed by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15689 6f19259b-4bc3-4df7-8a09-765794883524
2014-07-21MdePkg BaseLib: Fix a corner case of Source and Destination overlap.Star Zeng
The overlap may happen when the address of Destination in UnicodeStrToAsciiStr() or Source in AsciiStrToUnicodeStr() is not two bytes aligned. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15665 6f19259b-4bc3-4df7-8a09-765794883524
2014-07-14MdePkg PeiHobLib: Initialize Owner field of Resource HOB to 0 rather than ↵Star Zeng
random value. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Star Zeng <star.zeng@intel.com> Reviewed-by: Jiewen Yao <jiewen.yao@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15653 6f19259b-4bc3-4df7-8a09-765794883524
2014-07-09MdePkg/BasePrintLib: Do not do operations with NULLHarry Liebel
Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Harry Liebel <Harry.Liebel@arm.com> Reviewed-By: Olivier Martin <olivier.martin@arm.com> Reviewed-by: Gao, Liming <liming.gao@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15646 6f19259b-4bc3-4df7-8a09-765794883524
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-09 14:02:25 +0000