summaryrefslogtreecommitdiffstats
path: root/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib
Commit message (Collapse)AuthorAgeFilesLines
* MdePkg: Apply uncrustify changesMichael Kubacki2021-12-071-149/+168
| | | | | | | | | | | | REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3737 Apply uncrustify changes to .c/.h files in the MdePkg package Cc: Andrew Fish <afish@apple.com> Cc: Leif Lindholm <leif@nuviainc.com> Cc: Michael D Kinney <michael.d.kinney@intel.com> Signed-off-by: Michael Kubacki <michael.kubacki@microsoft.com> Reviewed-by: Liming Gao <gaoliming@byosoft.com.cn>
* MdePkg: Replace BSD License with BSD+Patent LicenseMichael D Kinney2019-04-093-23/+3
| | | | | | | | | | | | | | | | | | | | https://bugzilla.tianocore.org/show_bug.cgi?id=1373 Replace BSD 2-Clause License with BSD+Patent License. This change is based on the following emails: https://lists.01.org/pipermail/edk2-devel/2019-February/036260.html https://lists.01.org/pipermail/edk2-devel/2018-October/030385.html RFCs with detailed process for the license change: V3: https://lists.01.org/pipermail/edk2-devel/2019-March/038116.html V2: https://lists.01.org/pipermail/edk2-devel/2019-March/037669.html V1: https://lists.01.org/pipermail/edk2-devel/2019-March/037500.html Contributed-under: TianoCore Contribution Agreement 1.1 Signed-off-by: Michael D Kinney <michael.d.kinney@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com>
* MdePkg: Removing ipf which is no longer supported from edk2.Chen A Chen2018-09-251-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Removing rules for Ipf sources file: * Remove the source file which path with "ipf" and also listed in [Sources.IPF] section of INF file. * Remove the source file which listed in [Components.IPF] section of DSC file and not listed in any other [Components] section. * Remove the embedded Ipf code for MDE_CPU_IPF. Removing rules for Inf file: * Remove IPF from VALID_ARCHITECTURES comments. * Remove DXE_SAL_DRIVER from LIBRARY_CLASS in [Defines] section. * Remove the INF which only listed in [Components.IPF] section in DSC. * Remove statements from [BuildOptions] that provide IPF specific flags. * Remove any IPF sepcific sections. Removing rules for Dec file: * Remove [Includes.IPF] section from Dec. Removing rules for Dsc file: * Remove IPF from SUPPORTED_ARCHITECTURES in [Defines] section of DSC. * Remove any IPF specific sections. * Remove statements from [BuildOptions] that provide IPF specific flags. Cc: Liming Gao <liming.gao@intel.com> Cc: Michael D Kinney <michael.d.kinney@intel.com> Contributed-under: TianoCore Contribution Agreement 1.1 Signed-off-by: Chen A Chen <chen.a.chen@intel.com> Reviewed-by: Liming Gao <liming.gao@intel.com>
* MdePkg: Clean up source filesLiming Gao2018-06-281-3/+3
| | | | | | | | | 1. Do not use tab characters 2. No trailing white space in one line 3. All files must end with CRLF Contributed-under: TianoCore Contribution Agreement 1.1 Signed-off-by: Liming Gao <liming.gao@intel.com>
* MdePkg: Convert all .uni files to utf-8Jordan Justen2015-12-151-0/+0
| | | | | | | | | | | | To convert these files I ran: $ python3 BaseTools/Scripts/ConvertUni.py MdePkg Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Jordan Justen <jordan.l.justen@intel.com> Reviewed-by: Michael Kinney <michael.d.kinney@intel.com> git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@19256 6f19259b-4bc3-4df7-8a09-765794883524
* MdePkg: Convert non DOS format files to DOS formatGao, Liming2014-09-031-0/+0
| | | | | | | | | 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
* MdePkg: INF/DEC file updates to EDK II packagesGao, Liming2014-08-271-0/+0
| | | | | | | | | | | | | 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
* MdePkg: INF/DEC file updates to EDK II packagesGao, Liming2014-08-271-1/+2
| | | | | | | | | | | | | 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
* MdePkg: BaseOrderedCollectionRedBlackTreeLib: improve coding styleEric Dong2014-08-201-22/+36
| | | | | | | | | | | | | | | | | - 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
* MdePkg: library INF files should reference feature PCDs under [FeaturePcd]Laszlo Ersek2014-08-161-2/+2
| | | | | | | | | | | | 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
* MdePkg: BaseOrderedCollectionRedBlackTreeLib: silence invalid VS2005 warningsLaszlo Ersek2014-08-161-2/+2
| | | | | | | | | | | | | | | | | | | | | 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
* MdePkg: BaseOrderedCollectionRedBlackTreeLib: silence invalid gcc warningLaszlo Ersek2014-08-161-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Roll-back from an accidental commit.lhauch2014-08-141-1/+0
| | | | | | | | | 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
* Change svn:mime-type property on all Unicode files (extension .uni) in edk2lhauch2014-08-141-0/+1
| | | | | | | | | 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
* MdePkg: introduce BaseOrderedCollectionRedBlackTreeLib library instanceLaszlo Ersek2014-08-122-0/+1488
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