Age | Commit message (Collapse) | Author |
|
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
|
|
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
|
|
Signed-off-by: Gao, Liming <liming.gao@intel.com>
Reviewed-by: Tian, Hot <hot.tian@intel.com>
git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@15065 6f19259b-4bc3-4df7-8a09-765794883524
|
|
BootScriptExecutorDxe driver for the return status of S3BootScriptExecute().
Signed-off-by: Shumin Qiu <shumin.qiu@intel.com>
Reviewed-by: Liming Gao <liming.gao@intel.com>
git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@14830 6f19259b-4bc3-4df7-8a09-765794883524
|
|
Contributed-under: TianoCore Contribution Agreement 1.0
Signed-off-by: Harry Liebel <Harry.Liebel@arm.com>
Signed-off-by: Olivier Martin <olivier.martin@arm.com>
Reviewed-by: Liming Gao <liming.gao@intel.com>
git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@14513 6f19259b-4bc3-4df7-8a09-765794883524
|
|
ConvertDevicePathToText, ConvertTextToDeviceNode and ConvertTextToDevicePath.
Add a new instance of DevicePathLib which tries to locate the protocol and if it's not found, it uses the internal functions.
Signed-off-by: Ruiyu Ni <ruiyu.ni@intel.com>
Reviewed-by: Liming Gao <liming.gao@intel.com>
git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@14504 6f19259b-4bc3-4df7-8a09-765794883524
|
|
MdePkg 1.02->1.03
EdkCompatibilityPkg 0.91->0.92
PerformancePkg 0.1->0.2
Signed-off-by: lgao4
Reviewed-by: hhtian
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@12844 6f19259b-4bc3-4df7-8a09-765794883524
|
|
Signed-off-by: jljusten
Reviewed-by: mdkinney
Reviewed-by: rsun3
Reviewed-by: jyao1
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@12222 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@11784 6f19259b-4bc3-4df7-8a09-765794883524
|
|
adjust the filter mask for DEBUG() messages. The "err" command provide the ability to adjust this filter mask at a global level through an EFI Variable and at the module level through a the Debug Mask Protocol. In order to support the degree of flexibility, the DebugLib needs to use library to abstract the get/set operations to the filter mask.
1) Add new DebugPrintErrorLevelLib instances to DSC files.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@11383 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@11302 6f19259b-4bc3-4df7-8a09-765794883524
|
|
1. Remove PCDs those use the default values/types from the DEC file.
2. Remove the unused library instances.
3. Group common library instances in common [LibraryClasses] section as the default library instance for all modules.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10531 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10459 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10416 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10383 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10201 6f19259b-4bc3-4df7-8a09-765794883524
|
|
2. Remove unnecessary .common] postfix on section.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10052 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@10002 6f19259b-4bc3-4df7-8a09-765794883524
|
|
to both Framework SMM and PI SMM implementations.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9840 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9735 6f19259b-4bc3-4df7-8a09-765794883524
|
|
1. Add SmmServicesTableLib library class/instance.
2. Add SmmIoLibCpuIo/SmmPciLibPciRootBridgeIo library instance.
3. Update some library INF to support SMM_CORE module type.
4. Update dec/dsc to include new modules.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9590 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9198 6f19259b-4bc3-4df7-8a09-765794883524
|
|
are no other updates besides that change.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9141 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9105 6f19259b-4bc3-4df7-8a09-765794883524
|
|
update MdeModulePkg version to 0.90
update IntelFrameworkPkg version to 0.90
update IntelFrameworkModulePkg version to 0.90
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9021 6f19259b-4bc3-4df7-8a09-765794883524
|
|
"BasePeCoffExtraActionLibNull"
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7823 6f19259b-4bc3-4df7-8a09-765794883524
|
|
PeCoffExtraActionLib class and instances.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7811 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7780 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7600 6f19259b-4bc3-4df7-8a09-765794883524
|
|
section.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7490 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7377 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7148 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6704 6f19259b-4bc3-4df7-8a09-765794883524
|
|
Rename DxePciSegmentLibPciRootBridgeIo to UefiPciSegmentLibPciRootBridgeIo.
Update MODULE_TYPE and BASE_NAME accordingly.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6697 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6519 6f19259b-4bc3-4df7-8a09-765794883524
|
|
1. DxePciLibPciRootBridgeIo
2. DxePciSegmentLibPciRootBridgeIo
3. PeiPciLibPciCfg2
4. PeiPciSegmentLibPciCfg2
5. UefiPalLib
6. UefiSalLib
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6451 6f19259b-4bc3-4df7-8a09-765794883524
|
|
package dependency issue, and update all DSC files accordingly.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6286 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6282 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6268 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6267 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@6226 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@5693 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@5524 6f19259b-4bc3-4df7-8a09-765794883524
|
|
instance is EFI agnostic.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@5523 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4661 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4600 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4395 6f19259b-4bc3-4df7-8a09-765794883524
|
|
2) Add BaseMemoryLibOptXXX in MdePkg.dsc.
3) Clean up the MdeModulePkg.dsc.
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4286 6f19259b-4bc3-4df7-8a09-765794883524
|
|
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4113 6f19259b-4bc3-4df7-8a09-765794883524
|
|
components in open source packages.
Use meaningful arguments defined in PalLib.h when invoking PalCall().
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@4094 6f19259b-4bc3-4df7-8a09-765794883524
|