BaseOrderedCollectionRedBlackTreeLib.c@ 87965

Last change on this file since 87965 was 80721, checked in by vboxsync, 5 years ago
Devices/EFI/FirmwareNew: Start upgrade process to edk2-stable201908 (compiles on Windows and works to some extent), bugref:4643
Property svn:eol-style set to `native`
File size: 46.2 KB

Line
1	/** @file
2	An OrderedCollectionLib instance that provides a red-black tree
3	implementation, and allocates and releases tree nodes with
4	MemoryAllocationLib.
5
6	This library instance is useful when a fast associative container is needed.
7	Worst case time complexity is O(log n) for Find(), Next(), Prev(), Min(),
8	Max(), Insert(), and Delete(), where "n" is the number of elements in the
9	tree. Complete ordered traversal takes O(n) time.
10
11	The implementation is also useful as a fast priority queue.
12
13	Copyright (C) 2014, Red Hat, Inc.
14	Copyright (c) 2014, Intel Corporation. All rights reserved.<BR>
15
16	SPDX-License-Identifier: BSD-2-Clause-Patent
17	**/
18
19	#include <Library/OrderedCollectionLib.h>
20	#include <Library/DebugLib.h>
21	#include <Library/MemoryAllocationLib.h>
22
23	typedef enum {
24	RedBlackTreeRed,
25	RedBlackTreeBlack
26	} RED_BLACK_TREE_COLOR;
27
28	//
29	// Incomplete types and convenience typedefs are present in the library class
30	// header. Beside completing the types, we introduce typedefs here that reflect
31	// the implementation closely.
32	//
33	typedef ORDERED_COLLECTION RED_BLACK_TREE;
34	typedef ORDERED_COLLECTION_ENTRY RED_BLACK_TREE_NODE;
35	typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE;
36	typedef ORDERED_COLLECTION_KEY_COMPARE RED_BLACK_TREE_KEY_COMPARE;
37
38	struct ORDERED_COLLECTION {
39	RED_BLACK_TREE_NODE *Root;
40	RED_BLACK_TREE_USER_COMPARE UserStructCompare;
41	RED_BLACK_TREE_KEY_COMPARE KeyCompare;
42	};
43
44	struct ORDERED_COLLECTION_ENTRY {
45	VOID *UserStruct;
46	RED_BLACK_TREE_NODE *Parent;
47	RED_BLACK_TREE_NODE *Left;
48	RED_BLACK_TREE_NODE *Right;
49	RED_BLACK_TREE_COLOR Color;
50	};
51
52
53	/**
54	Retrieve the user structure linked by the specified tree node.
55
56	Read-only operation.
57
58	@param[in] Node Pointer to the tree node whose associated user structure we
59	want to retrieve. The caller is responsible for passing a
60	non-NULL argument.
61
62	@return Pointer to user structure linked by Node.
63	**/
64	VOID *
65	EFIAPI
66	OrderedCollectionUserStruct (
67	IN CONST RED_BLACK_TREE_NODE *Node
68	)
69	{
70	return Node->UserStruct;
71	}
72
73	/**
74	A slow function that asserts that the tree is a valid red-black tree, and
75	that it orders user structures correctly.
76
77	Read-only operation.
78
79	This function uses the stack for recursion and is not recommended for
80	"production use".
81
82	@param[in] Tree The tree to validate.
83	**/
84	VOID
85	RedBlackTreeValidate (
86	IN CONST RED_BLACK_TREE *Tree
87	);
88
89
90	/**
91	Allocate and initialize the RED_BLACK_TREE structure.
92
93	Allocation occurs via MemoryAllocationLib's AllocatePool() function.
94
95	@param[in] UserStructCompare This caller-provided function will be used to
96	order two user structures linked into the
97	tree, during the insertion procedure.
98
99	@param[in] KeyCompare This caller-provided function will be used to
100	order the standalone search key against user
101	structures linked into the tree, during the
102	lookup procedure.
103
104	@retval NULL If allocation failed.
105
106	@return Pointer to the allocated, initialized RED_BLACK_TREE structure,
107	otherwise.
108	**/
109	RED_BLACK_TREE *
110	EFIAPI
111	OrderedCollectionInit (
112	IN RED_BLACK_TREE_USER_COMPARE UserStructCompare,
113	IN RED_BLACK_TREE_KEY_COMPARE KeyCompare
114	)
115	{
116	RED_BLACK_TREE *Tree;
117
118	Tree = AllocatePool (sizeof *Tree);
119	if (Tree == NULL) {
120	return NULL;
121	}
122
123	Tree->Root = NULL;
124	Tree->UserStructCompare = UserStructCompare;
125	Tree->KeyCompare = KeyCompare;
126
127	if (FeaturePcdGet (PcdValidateOrderedCollection)) {
128	RedBlackTreeValidate (Tree);
129	}
130	return Tree;
131	}
132
133
134	/**
135	Check whether the tree is empty (has no nodes).
136
137	Read-only operation.
138
139	@param[in] Tree The tree to check for emptiness.
140
141	@retval TRUE The tree is empty.
142
143	@retval FALSE The tree is not empty.
144	**/
145	BOOLEAN
146	EFIAPI
147	OrderedCollectionIsEmpty (
148	IN CONST RED_BLACK_TREE *Tree
149	)
150	{
151	return (BOOLEAN)(Tree->Root == NULL);
152	}
153
154
155	/**
156	Uninitialize and release an empty RED_BLACK_TREE structure.
157
158	Read-write operation.
159
160	Release occurs via MemoryAllocationLib's FreePool() function.
161
162	It is the caller's responsibility to delete all nodes from the tree before
163	calling this function.
164
165	@param[in] Tree The empty tree to uninitialize and release.
166	**/
167	VOID
168	EFIAPI
169	OrderedCollectionUninit (
170	IN RED_BLACK_TREE *Tree
171	)
172	{
173	ASSERT (OrderedCollectionIsEmpty (Tree));
174	FreePool (Tree);
175	}
176
177
178	/**
179	Look up the tree node that links the user structure that matches the
180	specified standalone key.
181
182	Read-only operation.
183
184	@param[in] Tree The tree to search for StandaloneKey.
185
186	@param[in] StandaloneKey The key to locate among the user structures linked
187	into Tree. StandaloneKey will be passed to
188	Tree->KeyCompare().
189
190	@retval NULL StandaloneKey could not be found.
191
192	@return The tree node that links to the user structure matching
193	StandaloneKey, otherwise.
194	**/
195	RED_BLACK_TREE_NODE *
196	EFIAPI
197	OrderedCollectionFind (
198	IN CONST RED_BLACK_TREE *Tree,
199	IN CONST VOID *StandaloneKey
200	)
201	{
202	RED_BLACK_TREE_NODE *Node;
203
204	Node = Tree->Root;
205	while (Node != NULL) {
206	INTN Result;
207
208	Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct);
209	if (Result == 0) {
210	break;
211	}
212	Node = (Result < 0) ? Node->Left : Node->Right;
213	}
214	return Node;
215	}
216
217
218	/**
219	Find the tree node of the minimum user structure stored in the tree.
220
221	Read-only operation.
222
223	@param[in] Tree The tree to return the minimum node of. The user structure
224	linked by the minimum node compares less than all other user
225	structures in the tree.
226
227	@retval NULL If Tree is empty.
228
229	@return The tree node that links the minimum user structure, otherwise.
230	**/
231	RED_BLACK_TREE_NODE *
232	EFIAPI
233	OrderedCollectionMin (
234	IN CONST RED_BLACK_TREE *Tree
235	)
236	{
237	RED_BLACK_TREE_NODE *Node;
238
239	Node = Tree->Root;
240	if (Node == NULL) {
241	return NULL;
242	}
243	while (Node->Left != NULL) {
244	Node = Node->Left;
245	}
246	return Node;
247	}
248
249
250	/**
251	Find the tree node of the maximum user structure stored in the tree.
252
253	Read-only operation.
254
255	@param[in] Tree The tree to return the maximum node of. The user structure
256	linked by the maximum node compares greater than all other
257	user structures in the tree.
258
259	@retval NULL If Tree is empty.
260
261	@return The tree node that links the maximum user structure, otherwise.
262	**/
263	RED_BLACK_TREE_NODE *
264	EFIAPI
265	OrderedCollectionMax (
266	IN CONST RED_BLACK_TREE *Tree
267	)
268	{
269	RED_BLACK_TREE_NODE *Node;
270
271	Node = Tree->Root;
272	if (Node == NULL) {
273	return NULL;
274	}
275	while (Node->Right != NULL) {
276	Node = Node->Right;
277	}
278	return Node;
279	}
280
281
282	/**
283	Get the tree node of the least user structure that is greater than the one
284	linked by Node.
285
286	Read-only operation.
287
288	@param[in] Node The node to get the successor node of.
289
290	@retval NULL If Node is NULL, or Node is the maximum node of its containing
291	tree (ie. Node has no successor node).
292
293	@return The tree node linking the least user structure that is greater
294	than the one linked by Node, otherwise.
295	**/
296	RED_BLACK_TREE_NODE *
297	EFIAPI
298	OrderedCollectionNext (
299	IN CONST RED_BLACK_TREE_NODE *Node
300	)
301	{
302	RED_BLACK_TREE_NODE *Walk;
303	CONST RED_BLACK_TREE_NODE *Child;
304
305	if (Node == NULL) {
306	return NULL;
307	}
308
309	//
310	// If Node has a right subtree, then the successor is the minimum node of
311	// that subtree.
312	//
313	Walk = Node->Right;
314	if (Walk != NULL) {
315	while (Walk->Left != NULL) {
316	Walk = Walk->Left;
317	}
318	return Walk;
319	}
320
321	//
322	// Otherwise we have to ascend as long as we're our parent's right child (ie.
323	// ascending to the left).
324	//
325	Child = Node;
326	Walk = Child->Parent;
327	while (Walk != NULL && Child == Walk->Right) {
328	Child = Walk;
329	Walk = Child->Parent;
330	}
331	return Walk;
332	}
333
334
335	/**
336	Get the tree node of the greatest user structure that is less than the one
337	linked by Node.
338
339	Read-only operation.
340
341	@param[in] Node The node to get the predecessor node of.
342
343	@retval NULL If Node is NULL, or Node is the minimum node of its containing
344	tree (ie. Node has no predecessor node).
345
346	@return The tree node linking the greatest user structure that is less
347	than the one linked by Node, otherwise.
348	**/
349	RED_BLACK_TREE_NODE *
350	EFIAPI
351	OrderedCollectionPrev (
352	IN CONST RED_BLACK_TREE_NODE *Node
353	)
354	{
355	RED_BLACK_TREE_NODE *Walk;
356	CONST RED_BLACK_TREE_NODE *Child;
357
358	if (Node == NULL) {
359	return NULL;
360	}
361
362	//
363	// If Node has a left subtree, then the predecessor is the maximum node of
364	// that subtree.
365	//
366	Walk = Node->Left;
367	if (Walk != NULL) {
368	while (Walk->Right != NULL) {
369	Walk = Walk->Right;
370	}
371	return Walk;
372	}
373
374	//
375	// Otherwise we have to ascend as long as we're our parent's left child (ie.
376	// ascending to the right).
377	//
378	Child = Node;
379	Walk = Child->Parent;
380	while (Walk != NULL && Child == Walk->Left) {
381	Child = Walk;
382	Walk = Child->Parent;
383	}
384	return Walk;
385	}
386
387
388	/**
389	Rotate tree nodes around Pivot to the right.
390
391	Parent Parent
392	\| \|
393	Pivot LeftChild
394	/ . . \_
395	LeftChild Node1 ---> Node2 Pivot
396	. \ / .
397	Node2 LeftRightChild LeftRightChild Node1
398
399	The ordering Node2 < LeftChild < LeftRightChild < Pivot < Node1 is kept
400	intact. Parent (if any) is either at the left extreme or the right extreme of
401	this ordering, and that relation is also kept intact.
402
403	Edges marked with a dot (".") don't change during rotation.
404
405	Internal read-write operation.
406
407	@param[in,out] Pivot The tree node to rotate other nodes right around. It
408	is the caller's responsibility to ensure that
409	Pivot->Left is not NULL.
410
411	@param[out] NewRoot If Pivot has a parent node on input, then the
412	function updates Pivot's original parent on output
413	according to the rotation, and NewRoot is not
414	accessed.
415
416	If Pivot has no parent node on input (ie. Pivot is
417	the root of the tree), then the function stores the
418	new root node of the tree in NewRoot.
419	**/
420	VOID
421	RedBlackTreeRotateRight (
422	IN OUT RED_BLACK_TREE_NODE *Pivot,
423	OUT RED_BLACK_TREE_NODE **NewRoot
424	)
425	{
426	RED_BLACK_TREE_NODE *Parent;
427	RED_BLACK_TREE_NODE *LeftChild;
428	RED_BLACK_TREE_NODE *LeftRightChild;
429
430	Parent = Pivot->Parent;
431	LeftChild = Pivot->Left;
432	LeftRightChild = LeftChild->Right;
433
434	Pivot->Left = LeftRightChild;
435	if (LeftRightChild != NULL) {
436	LeftRightChild->Parent = Pivot;
437	}
438	LeftChild->Parent = Parent;
439	if (Parent == NULL) {
440	*NewRoot = LeftChild;
441	} else {
442	if (Pivot == Parent->Left) {
443	Parent->Left = LeftChild;
444	} else {
445	Parent->Right = LeftChild;
446	}
447	}
448	LeftChild->Right = Pivot;
449	Pivot->Parent = LeftChild;
450	}
451
452
453	/**
454	Rotate tree nodes around Pivot to the left.
455
456	Parent Parent
457	\| \|
458	Pivot RightChild
459	. \ / .
460	Node1 RightChild ---> Pivot Node2
461	/. . \_
462	RightLeftChild Node2 Node1 RightLeftChild
463
464	The ordering Node1 < Pivot < RightLeftChild < RightChild < Node2 is kept
465	intact. Parent (if any) is either at the left extreme or the right extreme of
466	this ordering, and that relation is also kept intact.
467
468	Edges marked with a dot (".") don't change during rotation.
469
470	Internal read-write operation.
471
472	@param[in,out] Pivot The tree node to rotate other nodes left around. It
473	is the caller's responsibility to ensure that
474	Pivot->Right is not NULL.
475
476	@param[out] NewRoot If Pivot has a parent node on input, then the
477	function updates Pivot's original parent on output
478	according to the rotation, and NewRoot is not
479	accessed.
480
481	If Pivot has no parent node on input (ie. Pivot is
482	the root of the tree), then the function stores the
483	new root node of the tree in NewRoot.
484	**/
485	VOID
486	RedBlackTreeRotateLeft (
487	IN OUT RED_BLACK_TREE_NODE *Pivot,
488	OUT RED_BLACK_TREE_NODE **NewRoot
489	)
490	{
491	RED_BLACK_TREE_NODE *Parent;
492	RED_BLACK_TREE_NODE *RightChild;
493	RED_BLACK_TREE_NODE *RightLeftChild;
494
495	Parent = Pivot->Parent;
496	RightChild = Pivot->Right;
497	RightLeftChild = RightChild->Left;
498
499	Pivot->Right = RightLeftChild;
500	if (RightLeftChild != NULL) {
501	RightLeftChild->Parent = Pivot;
502	}
503	RightChild->Parent = Parent;
504	if (Parent == NULL) {
505	*NewRoot = RightChild;
506	} else {
507	if (Pivot == Parent->Left) {
508	Parent->Left = RightChild;
509	} else {
510	Parent->Right = RightChild;
511	}
512	}
513	RightChild->Left = Pivot;
514	Pivot->Parent = RightChild;
515	}
516
517
518	/**
519	Insert (link) a user structure into the tree.
520
521	Read-write operation.
522
523	This function allocates the new tree node with MemoryAllocationLib's
524	AllocatePool() function.
525
526	@param[in,out] Tree The tree to insert UserStruct into.
527
528	@param[out] Node The meaning of this optional, output-only
529	parameter depends on the return value of the
530	function.
531
532	When insertion is successful (RETURN_SUCCESS),
533	Node is set on output to the new tree node that
534	now links UserStruct.
535
536	When insertion fails due to lack of memory
537	(RETURN_OUT_OF_RESOURCES), Node is not changed.
538
539	When insertion fails due to key collision (ie.
540	another user structure is already in the tree that
541	compares equal to UserStruct), with return value
542	RETURN_ALREADY_STARTED, then Node is set on output
543	to the node that links the colliding user
544	structure. This enables "find-or-insert" in one
545	function call, or helps with later removal of the
546	colliding element.
547
548	@param[in] UserStruct The user structure to link into the tree.
549	UserStruct is ordered against in-tree user
550	structures with the Tree->UserStructCompare()
551	function.
552
553	@retval RETURN_SUCCESS Insertion successful. A new tree node has
554	been allocated, linking UserStruct. The new
555	tree node is reported back in Node (if the
556	caller requested it).
557
558	Existing RED_BLACK_TREE_NODE pointers into
559	Tree remain valid. For example, on-going
560	iterations in the caller can continue with
561	OrderedCollectionNext() /
562	OrderedCollectionPrev(), and they will
563	return the new node at some point if user
564	structure order dictates it.
565
566	@retval RETURN_OUT_OF_RESOURCES AllocatePool() failed to allocate memory for
567	the new tree node. The tree has not been
568	changed. Existing RED_BLACK_TREE_NODE
569	pointers into Tree remain valid.
570
571	@retval RETURN_ALREADY_STARTED A user structure has been found in the tree
572	that compares equal to UserStruct. The node
573	linking the colliding user structure is
574	reported back in Node (if the caller
575	requested it). The tree has not been
576	changed. Existing RED_BLACK_TREE_NODE
577	pointers into Tree remain valid.
578	**/
579	RETURN_STATUS
580	EFIAPI
581	OrderedCollectionInsert (
582	IN OUT RED_BLACK_TREE *Tree,
583	OUT RED_BLACK_TREE_NODE **Node OPTIONAL,
584	IN VOID *UserStruct
585	)
586	{
587	RED_BLACK_TREE_NODE *Tmp;
588	RED_BLACK_TREE_NODE *Parent;
589	INTN Result;
590	RETURN_STATUS Status;
591	RED_BLACK_TREE_NODE *NewRoot;
592
593	Tmp = Tree->Root;
594	Parent = NULL;
595	Result = 0;
596
597	//
598	// First look for a collision, saving the last examined node for the case
599	// when there's no collision.
600	//
601	while (Tmp != NULL) {
602	Result = Tree->UserStructCompare (UserStruct, Tmp->UserStruct);
603	if (Result == 0) {
604	break;
605	}
606	Parent = Tmp;
607	Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;
608	}
609
610	if (Tmp != NULL) {
611	if (Node != NULL) {
612	*Node = Tmp;
613	}
614	Status = RETURN_ALREADY_STARTED;
615	goto Done;
616	}
617
618	//
619	// no collision, allocate a new node
620	//
621	Tmp = AllocatePool (sizeof *Tmp);
622	if (Tmp == NULL) {
623	Status = RETURN_OUT_OF_RESOURCES;
624	goto Done;
625	}
626	if (Node != NULL) {
627	*Node = Tmp;
628	}
629
630	//
631	// reference the user structure from the node
632	//
633	Tmp->UserStruct = UserStruct;
634
635	//
636	// Link the node as a child to the correct side of the parent.
637	// If there's no parent, the new node is the root node in the tree.
638	//
639	Tmp->Parent = Parent;
640	Tmp->Left = NULL;
641	Tmp->Right = NULL;
642	if (Parent == NULL) {
643	Tree->Root = Tmp;
644	Tmp->Color = RedBlackTreeBlack;
645	Status = RETURN_SUCCESS;
646	goto Done;
647	}
648	if (Result < 0) {
649	Parent->Left = Tmp;
650	} else {
651	Parent->Right = Tmp;
652	}
653	Tmp->Color = RedBlackTreeRed;
654
655	//
656	// Red-black tree properties:
657	//
658	// #1 Each node is either red or black (RED_BLACK_TREE_NODE.Color).
659	//
660	// #2 Each leaf (ie. a pseudo-node pointed-to by a NULL valued
661	// RED_BLACK_TREE_NODE.Left or RED_BLACK_TREE_NODE.Right field) is black.
662	//
663	// #3 Each red node has two black children.
664	//
665	// #4 For any node N, and for any leaves L1 and L2 reachable from N, the
666	// paths N..L1 and N..L2 contain the same number of black nodes.
667	//
668	// #5 The root node is black.
669	//
670	// By replacing a leaf with a red node above, only property #3 may have been
671	// broken. (Note that this is the only edge across which property #3 might
672	// not hold in the entire tree.) Restore property #3.
673	//
674
675	NewRoot = Tree->Root;
676	while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
677	RED_BLACK_TREE_NODE *GrandParent;
678	RED_BLACK_TREE_NODE *Uncle;
679
680	//
681	// Tmp is not the root node. Tmp is red. Tmp's parent is red. (Breaking
682	// property #3.)
683	//
684	// Due to property #5, Tmp's parent cannot be the root node, hence Tmp's
685	// grandparent exists.
686	//
687	// Tmp's grandparent is black, because property #3 is only broken between
688	// Tmp and Tmp's parent.
689	//
690	GrandParent = Parent->Parent;
691
692	if (Parent == GrandParent->Left) {
693	Uncle = GrandParent->Right;
694	if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
695	//
696	// GrandParent (black)
697	// / \_
698	// Parent (red) Uncle (red)
699	// \|
700	// Tmp (red)
701	//
702
703	Parent->Color = RedBlackTreeBlack;
704	Uncle->Color = RedBlackTreeBlack;
705	GrandParent->Color = RedBlackTreeRed;
706
707	//
708	// GrandParent (red)
709	// / \_
710	// Parent (black) Uncle (black)
711	// \|
712	// Tmp (red)
713	//
714	// We restored property #3 between Tmp and Tmp's parent, without
715	// breaking property #4. However, we may have broken property #3
716	// between Tmp's grandparent and Tmp's great-grandparent (if any), so
717	// repeat the loop for Tmp's grandparent.
718	//
719	// If Tmp's grandparent has no parent, then the loop will terminate,
720	// and we will have broken property #5, by coloring the root red. We'll
721	// restore property #5 after the loop, without breaking any others.
722	//
723	Tmp = GrandParent;
724	Parent = Tmp->Parent;
725	} else {
726	//
727	// Tmp's uncle is black (satisfied by the case too when Tmp's uncle is
728	// NULL, see property #2).
729	//
730
731	if (Tmp == Parent->Right) {
732	//
733	// GrandParent (black): D
734	// / \_
735	// Parent (red): A Uncle (black): E
736	// \_
737	// Tmp (red): B
738	// \_
739	// black: C
740	//
741	// Rotate left, pivoting on node A. This keeps the breakage of
742	// property #3 in the same spot, and keeps other properties intact
743	// (because both Tmp and its parent are red).
744	//
745	Tmp = Parent;
746	RedBlackTreeRotateLeft (Tmp, &NewRoot);
747	Parent = Tmp->Parent;
748
749	//
750	// With the rotation we reached the same configuration as if Tmp had
751	// been a left child to begin with.
752	//
753	// GrandParent (black): D
754	// / \_
755	// Parent (red): B Uncle (black): E
756	// / \_
757	// Tmp (red): A black: C
758	//
759	ASSERT (GrandParent == Parent->Parent);
760	}
761
762	Parent->Color = RedBlackTreeBlack;
763	GrandParent->Color = RedBlackTreeRed;
764
765	//
766	// Property #3 is now restored, but we've broken property #4. Namely,
767	// paths going through node E now see a decrease in black count, while
768	// paths going through node B don't.
769	//
770	// GrandParent (red): D
771	// / \_
772	// Parent (black): B Uncle (black): E
773	// / \_
774	// Tmp (red): A black: C
775	//
776
777	RedBlackTreeRotateRight (GrandParent, &NewRoot);
778
779	//
780	// Property #4 has been restored for node E, and preserved for others.
781	//
782	// Parent (black): B
783	// / \_
784	// Tmp (red): A [GrandParent] (red): D
785	// / \_
786	// black: C [Uncle] (black): E
787	//
788	// This configuration terminates the loop because Tmp's parent is now
789	// black.
790	//
791	}
792	} else {
793	//
794	// Symmetrical to the other branch.
795	//
796	Uncle = GrandParent->Left;
797	if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
798	Parent->Color = RedBlackTreeBlack;
799	Uncle->Color = RedBlackTreeBlack;
800	GrandParent->Color = RedBlackTreeRed;
801	Tmp = GrandParent;
802	Parent = Tmp->Parent;
803	} else {
804	if (Tmp == Parent->Left) {
805	Tmp = Parent;
806	RedBlackTreeRotateRight (Tmp, &NewRoot);
807	Parent = Tmp->Parent;
808	ASSERT (GrandParent == Parent->Parent);
809	}
810	Parent->Color = RedBlackTreeBlack;
811	GrandParent->Color = RedBlackTreeRed;
812	RedBlackTreeRotateLeft (GrandParent, &NewRoot);
813	}
814	}
815	}
816
817	NewRoot->Color = RedBlackTreeBlack;
818	Tree->Root = NewRoot;
819	Status = RETURN_SUCCESS;
820
821	Done:
822	if (FeaturePcdGet (PcdValidateOrderedCollection)) {
823	RedBlackTreeValidate (Tree);
824	}
825	return Status;
826	}
827
828
829	/**
830	Check if a node is black, allowing for leaf nodes (see property #2).
831
832	This is a convenience shorthand.
833
834	param[in] Node The node to check. Node may be NULL, corresponding to a leaf.
835
836	@return If Node is NULL or colored black.
837	**/
838	BOOLEAN
839	NodeIsNullOrBlack (
840	IN CONST RED_BLACK_TREE_NODE *Node
841	)
842	{
843	return (BOOLEAN)(Node == NULL \|\| Node->Color == RedBlackTreeBlack);
844	}
845
846
847	/**
848	Delete a node from the tree, unlinking the associated user structure.
849
850	Read-write operation.
851
852	@param[in,out] Tree The tree to delete Node from.
853
854	@param[in] Node The tree node to delete from Tree. The caller is
855	responsible for ensuring that Node belongs to
856	Tree, and that Node is non-NULL and valid. Node is
857	typically an earlier return value, or output
858	parameter, of:
859
860	- OrderedCollectionFind(), for deleting a node by
861	user structure key,
862
863	- OrderedCollectionMin() / OrderedCollectionMax(),
864	for deleting the minimum / maximum node,
865
866	- OrderedCollectionNext() /
867	OrderedCollectionPrev(), for deleting a node
868	found during an iteration,
869
870	- OrderedCollectionInsert() with return value
871	RETURN_ALREADY_STARTED, for deleting a node
872	whose linked user structure caused collision
873	during insertion.
874
875	Given a non-empty Tree, Tree->Root is also a valid
876	Node argument (typically used for simplicity in
877	loops that empty the tree completely).
878
879	Node is released with MemoryAllocationLib's
880	FreePool() function.
881
882	Existing RED_BLACK_TREE_NODE pointers (ie.
883	iterators) different from Node remain valid. For
884	example:
885
886	- OrderedCollectionNext() /
887	OrderedCollectionPrev() iterations in the caller
888	can be continued from Node, if
889	OrderedCollectionNext() or
890	OrderedCollectionPrev() is called on Node
891	before OrderedCollectionDelete() is. That is,
892	fetch the successor / predecessor node first,
893	then delete Node.
894
895	- On-going iterations in the caller that would
896	have otherwise returned Node at some point, as
897	dictated by user structure order, will correctly
898	reflect the absence of Node after
899	OrderedCollectionDelete() is called
900	mid-iteration.
901
902	@param[out] UserStruct If the caller provides this optional output-only
903	parameter, then on output it is set to the user
904	structure originally linked by Node (which is now
905	freed).
906
907	This is a convenience that may save the caller a
908	OrderedCollectionUserStruct() invocation before
909	calling OrderedCollectionDelete(), in order to
910	retrieve the user structure being unlinked.
911	**/
912	VOID
913	EFIAPI
914	OrderedCollectionDelete (
915	IN OUT RED_BLACK_TREE *Tree,
916	IN RED_BLACK_TREE_NODE *Node,
917	OUT VOID **UserStruct OPTIONAL
918	)
919	{
920	RED_BLACK_TREE_NODE *NewRoot;
921	RED_BLACK_TREE_NODE *OrigLeftChild;
922	RED_BLACK_TREE_NODE *OrigRightChild;
923	RED_BLACK_TREE_NODE *OrigParent;
924	RED_BLACK_TREE_NODE *Child;
925	RED_BLACK_TREE_NODE *Parent;
926	RED_BLACK_TREE_COLOR ColorOfUnlinked;
927
928	NewRoot = Tree->Root;
929	OrigLeftChild = Node->Left,
930	OrigRightChild = Node->Right,
931	OrigParent = Node->Parent;
932
933	if (UserStruct != NULL) {
934	*UserStruct = Node->UserStruct;
935	}
936
937	//
938	// After this block, no matter which branch we take:
939	// - Child will point to the unique (or NULL) original child of the node that
940	// we will have unlinked,
941	// - Parent will point to the position of the original parent of the node
942	// that we will have unlinked.
943	//
944	if (OrigLeftChild == NULL \|\| OrigRightChild == NULL) {
945	//
946	// Node has at most one child. We can connect that child (if any) with
947	// Node's parent (if any), unlinking Node. This will preserve ordering
948	// because the subtree rooted in Node's child (if any) remains on the same
949	// side of Node's parent (if any) that Node was before.
950	//
951	Parent = OrigParent;
952	Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
953	ColorOfUnlinked = Node->Color;
954
955	if (Child != NULL) {
956	Child->Parent = Parent;
957	}
958	if (OrigParent == NULL) {
959	NewRoot = Child;
960	} else {
961	if (Node == OrigParent->Left) {
962	OrigParent->Left = Child;
963	} else {
964	OrigParent->Right = Child;
965	}
966	}
967	} else {
968	//
969	// Node has two children. We unlink Node's successor, and then link it into
970	// Node's place, keeping Node's original color. This preserves ordering
971	// because:
972	// - Node's left subtree is less than Node, hence less than Node's
973	// successor.
974	// - Node's right subtree is greater than Node. Node's successor is the
975	// minimum of that subtree, hence Node's successor is less than Node's
976	// right subtree with its minimum removed.
977	// - Node's successor is in Node's subtree, hence it falls on the same side
978	// of Node's parent as Node itself. The relinking doesn't change this
979	// relation.
980	//
981	RED_BLACK_TREE_NODE *ToRelink;
982
983	ToRelink = OrigRightChild;
984	if (ToRelink->Left == NULL) {
985	//
986	// OrigRightChild itself is Node's successor, it has no left child:
987	//
988	// OrigParent
989	// \|
990	// Node: B
991	// / \_
992	// OrigLeftChild: A OrigRightChild: E <--- Parent, ToRelink
993	// \_
994	// F <--- Child
995	//
996	Parent = OrigRightChild;
997	Child = OrigRightChild->Right;
998	} else {
999	do {
1000	ToRelink = ToRelink->Left;
1001	} while (ToRelink->Left != NULL);
1002
1003	//
1004	// Node's successor is the minimum of OrigRightChild's proper subtree:
1005	//
1006	// OrigParent
1007	// \|
1008	// Node: B
1009	// / \_
1010	// OrigLeftChild: A OrigRightChild: E <--- Parent
1011	// /
1012	// C <--- ToRelink
1013	// \_
1014	// D <--- Child
1015	Parent = ToRelink->Parent;
1016	Child = ToRelink->Right;
1017
1018	//
1019	// Unlink Node's successor (ie. ToRelink):
1020	//
1021	// OrigParent
1022	// \|
1023	// Node: B
1024	// / \_
1025	// OrigLeftChild: A OrigRightChild: E <--- Parent
1026	// /
1027	// D <--- Child
1028	//
1029	// C <--- ToRelink
1030	//
1031	Parent->Left = Child;
1032	if (Child != NULL) {
1033	Child->Parent = Parent;
1034	}
1035
1036	//
1037	// We start to link Node's unlinked successor into Node's place:
1038	//
1039	// OrigParent
1040	// \|
1041	// Node: B C <--- ToRelink
1042	// / \_
1043	// OrigLeftChild: A OrigRightChild: E <--- Parent
1044	// /
1045	// D <--- Child
1046	//
1047	//
1048	//
1049	ToRelink->Right = OrigRightChild;
1050	OrigRightChild->Parent = ToRelink;
1051	}
1052
1053	//
1054	// The rest handles both cases, attaching ToRelink (Node's original
1055	// successor) to OrigLeftChild and OrigParent.
1056	//
1057	// Parent,
1058	// OrigParent ToRelink OrigParent
1059	// \| \| \|
1060	// Node: B \| Node: B Parent
1061	// v \|
1062	// OrigRightChild: E C <--- ToRelink \|
1063	// / \ / \ v
1064	// OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1065	// ^ /
1066	// \| D <--- Child
1067	// Child
1068	//
1069	ToRelink->Left = OrigLeftChild;
1070	OrigLeftChild->Parent = ToRelink;
1071
1072	//
1073	// Node's color must be preserved in Node's original place.
1074	//
1075	ColorOfUnlinked = ToRelink->Color;
1076	ToRelink->Color = Node->Color;
1077
1078	//
1079	// Finish linking Node's unlinked successor into Node's place.
1080	//
1081	// Parent,
1082	// Node: B ToRelink Node: B
1083	// \|
1084	// OrigParent \| OrigParent Parent
1085	// \| v \| \|
1086	// OrigRightChild: E C <--- ToRelink \|
1087	// / \ / \ v
1088	// OrigLeftChild: A F OrigLeftChild: A OrigRightChild: E
1089	// ^ /
1090	// \| D <--- Child
1091	// Child
1092	//
1093	ToRelink->Parent = OrigParent;
1094	if (OrigParent == NULL) {
1095	NewRoot = ToRelink;
1096	} else {
1097	if (Node == OrigParent->Left) {
1098	OrigParent->Left = ToRelink;
1099	} else {
1100	OrigParent->Right = ToRelink;
1101	}
1102	}
1103	}
1104
1105	FreePool (Node);
1106
1107	//
1108	// If the node that we unlinked from its original spot (ie. Node itself, or
1109	// Node's successor), was red, then we broke neither property #3 nor property
1110	// #4: we didn't create any red-red edge between Child and Parent, and we
1111	// didn't change the black count on any path.
1112	//
1113	if (ColorOfUnlinked == RedBlackTreeBlack) {
1114	//
1115	// However, if the unlinked node was black, then we have to transfer its
1116	// "black-increment" to its unique child (pointed-to by Child), lest we
1117	// break property #4 for its ancestors.
1118	//
1119	// If Child is red, we can simply color it black. If Child is black
1120	// already, we can't technically transfer a black-increment to it, due to
1121	// property #1.
1122	//
1123	// In the following loop we ascend searching for a red node to color black,
1124	// or until we reach the root (in which case we can drop the
1125	// black-increment). Inside the loop body, Child has a black value of 2,
1126	// transitorily breaking property #1 locally, but maintaining property #4
1127	// globally.
1128	//
1129	// Rotations in the loop preserve property #4.
1130	//
1131	while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
1132	RED_BLACK_TREE_NODE *Sibling;
1133	RED_BLACK_TREE_NODE *LeftNephew;
1134	RED_BLACK_TREE_NODE *RightNephew;
1135
1136	if (Child == Parent->Left) {
1137	Sibling = Parent->Right;
1138	//
1139	// Sibling can never be NULL (ie. a leaf).
1140	//
1141	// If Sibling was NULL, then the black count on the path from Parent to
1142	// Sibling would equal Parent's black value, plus 1 (due to property
1143	// #2). Whereas the black count on the path from Parent to any leaf via
1144	// Child would be at least Parent's black value, plus 2 (due to Child's
1145	// black value of 2). This would clash with property #4.
1146	//
1147	// (Sibling can be black of course, but it has to be an internal node.
1148	// Internality allows Sibling to have children, bumping the black
1149	// counts of paths that go through it.)
1150	//
1151	ASSERT (Sibling != NULL);
1152	if (Sibling->Color == RedBlackTreeRed) {
1153	//
1154	// Sibling's red color implies its children (if any), node C and node
1155	// E, are black (property #3). It also implies that Parent is black.
1156	//
1157	// grandparent grandparent
1158	// \| \|
1159	// Parent,b:B b:D
1160	// / \ / \_
1161	// Child,2b:A Sibling,r:D ---> Parent,r:B b:E
1162	// /\ /\_
1163	// b:C b:E Child,2b:A Sibling,b:C
1164	//
1165	Sibling->Color = RedBlackTreeBlack;
1166	Parent->Color = RedBlackTreeRed;
1167	RedBlackTreeRotateLeft (Parent, &NewRoot);
1168	Sibling = Parent->Right;
1169	//
1170	// Same reasoning as above.
1171	//
1172	ASSERT (Sibling != NULL);
1173	}
1174
1175	//
1176	// Sibling is black, and not NULL. (Ie. Sibling is a black internal
1177	// node.)
1178	//
1179	ASSERT (Sibling->Color == RedBlackTreeBlack);
1180	LeftNephew = Sibling->Left;
1181	RightNephew = Sibling->Right;
1182	if (NodeIsNullOrBlack (LeftNephew) &&
1183	NodeIsNullOrBlack (RightNephew)) {
1184	//
1185	// In this case we can "steal" one black value from Child and Sibling
1186	// each, and pass it to Parent. "Stealing" means that Sibling (black
1187	// value 1) becomes red, Child (black value 2) becomes singly-black,
1188	// and Parent will have to be examined if it can eat the
1189	// black-increment.
1190	//
1191	// Sibling is allowed to become red because both of its children are
1192	// black (property #3).
1193	//
1194	// grandparent Parent
1195	// \| \|
1196	// Parent,x:B Child,x:B
1197	// / \ / \_
1198	// Child,2b:A Sibling,b:D ---> b:A r:D
1199	// /\ /\_
1200	// LeftNephew,b:C RightNephew,b:E b:C b:E
1201	//
1202	Sibling->Color = RedBlackTreeRed;
1203	Child = Parent;
1204	Parent = Parent->Parent;
1205	//
1206	// Continue ascending.
1207	//
1208	} else {
1209	//
1210	// At least one nephew is red.
1211	//
1212	if (NodeIsNullOrBlack (RightNephew)) {
1213	//
1214	// Since the right nephew is black, the left nephew is red. Due to
1215	// property #3, LeftNephew has two black children, hence node E is
1216	// black.
1217	//
1218	// Together with the rotation, this enables us to color node F red
1219	// (because property #3 will be satisfied). We flip node D to black
1220	// to maintain property #4.
1221	//
1222	// grandparent grandparent
1223	// \| \|
1224	// Parent,x:B Parent,x:B
1225	// /\ /\_
1226	// Child,2b:A Sibling,b:F ---> Child,2b:A Sibling,b:D
1227	// /\ / \_
1228	// LeftNephew,r:D RightNephew,b:G b:C RightNephew,r:F
1229	// /\ /\_
1230	// b:C b:E b:E b:G
1231	//
1232	LeftNephew->Color = RedBlackTreeBlack;
1233	Sibling->Color = RedBlackTreeRed;
1234	RedBlackTreeRotateRight (Sibling, &NewRoot);
1235	Sibling = Parent->Right;
1236	RightNephew = Sibling->Right;
1237	//
1238	// These operations ensure that...
1239	//
1240	}
1241	//
1242	// ... RightNephew is definitely red here, plus Sibling is (still)
1243	// black and non-NULL.
1244	//
1245	ASSERT (RightNephew != NULL);
1246	ASSERT (RightNephew->Color == RedBlackTreeRed);
1247	ASSERT (Sibling != NULL);
1248	ASSERT (Sibling->Color == RedBlackTreeBlack);
1249	//
1250	// In this case we can flush the extra black-increment immediately,
1251	// restoring property #1 for Child (node A): we color RightNephew
1252	// (node E) from red to black.
1253	//
1254	// In order to maintain property #4, we exchange colors between
1255	// Parent and Sibling (nodes B and D), and rotate left around Parent
1256	// (node B). The transformation doesn't change the black count
1257	// increase incurred by each partial path, eg.
1258	// - ascending from node A: 2 + x == 1 + 1 + x
1259	// - ascending from node C: y + 1 + x == y + 1 + x
1260	// - ascending from node E: 0 + 1 + x == 1 + x
1261	//
1262	// The color exchange is valid, because even if x stands for red,
1263	// both children of node D are black after the transformation
1264	// (preserving property #3).
1265	//
1266	// grandparent grandparent
1267	// \| \|
1268	// Parent,x:B x:D
1269	// / \ / \_
1270	// Child,2b:A Sibling,b:D ---> b:B b:E
1271	// / \ / \_
1272	// y:C RightNephew,r:E b:A y:C
1273	//
1274	//
1275	Sibling->Color = Parent->Color;
1276	Parent->Color = RedBlackTreeBlack;
1277	RightNephew->Color = RedBlackTreeBlack;
1278	RedBlackTreeRotateLeft (Parent, &NewRoot);
1279	Child = NewRoot;
1280	//
1281	// This terminates the loop.
1282	//
1283	}
1284	} else {
1285	//
1286	// Mirrors the other branch.
1287	//
1288	Sibling = Parent->Left;
1289	ASSERT (Sibling != NULL);
1290	if (Sibling->Color == RedBlackTreeRed) {
1291	Sibling->Color = RedBlackTreeBlack;
1292	Parent->Color = RedBlackTreeRed;
1293	RedBlackTreeRotateRight (Parent, &NewRoot);
1294	Sibling = Parent->Left;
1295	ASSERT (Sibling != NULL);
1296	}
1297
1298	ASSERT (Sibling->Color == RedBlackTreeBlack);
1299	RightNephew = Sibling->Right;
1300	LeftNephew = Sibling->Left;
1301	if (NodeIsNullOrBlack (RightNephew) &&
1302	NodeIsNullOrBlack (LeftNephew)) {
1303	Sibling->Color = RedBlackTreeRed;
1304	Child = Parent;
1305	Parent = Parent->Parent;
1306	} else {
1307	if (NodeIsNullOrBlack (LeftNephew)) {
1308	RightNephew->Color = RedBlackTreeBlack;
1309	Sibling->Color = RedBlackTreeRed;
1310	RedBlackTreeRotateLeft (Sibling, &NewRoot);
1311	Sibling = Parent->Left;
1312	LeftNephew = Sibling->Left;
1313	}
1314	ASSERT (LeftNephew != NULL);
1315	ASSERT (LeftNephew->Color == RedBlackTreeRed);
1316	ASSERT (Sibling != NULL);
1317	ASSERT (Sibling->Color == RedBlackTreeBlack);
1318	Sibling->Color = Parent->Color;
1319	Parent->Color = RedBlackTreeBlack;
1320	LeftNephew->Color = RedBlackTreeBlack;
1321	RedBlackTreeRotateRight (Parent, &NewRoot);
1322	Child = NewRoot;
1323	}
1324	}
1325	}
1326
1327	if (Child != NULL) {
1328	Child->Color = RedBlackTreeBlack;
1329	}
1330	}
1331
1332	Tree->Root = NewRoot;
1333
1334	if (FeaturePcdGet (PcdValidateOrderedCollection)) {
1335	RedBlackTreeValidate (Tree);
1336	}
1337	}
1338
1339
1340	/**
1341	Recursively check the red-black tree properties #1 to #4 on a node.
1342
1343	@param[in] Node The root of the subtree to validate.
1344
1345	@retval The black-height of Node's parent.
1346	**/
1347	UINT32
1348	RedBlackTreeRecursiveCheck (
1349	IN CONST RED_BLACK_TREE_NODE *Node
1350	)
1351	{
1352	UINT32 LeftHeight;
1353	UINT32 RightHeight;
1354
1355	//
1356	// property #2
1357	//
1358	if (Node == NULL) {
1359	return 1;
1360	}
1361
1362	//
1363	// property #1
1364	//
1365	ASSERT (Node->Color == RedBlackTreeRed \|\| Node->Color == RedBlackTreeBlack);
1366
1367	//
1368	// property #3
1369	//
1370	if (Node->Color == RedBlackTreeRed) {
1371	ASSERT (NodeIsNullOrBlack (Node->Left));
1372	ASSERT (NodeIsNullOrBlack (Node->Right));
1373	}
1374
1375	//
1376	// property #4
1377	//
1378	LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
1379	RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
1380	ASSERT (LeftHeight == RightHeight);
1381
1382	return (Node->Color == RedBlackTreeBlack) + LeftHeight;
1383	}
1384
1385
1386	/**
1387	A slow function that asserts that the tree is a valid red-black tree, and
1388	that it orders user structures correctly.
1389
1390	Read-only operation.
1391
1392	This function uses the stack for recursion and is not recommended for
1393	"production use".
1394
1395	@param[in] Tree The tree to validate.
1396	**/
1397	VOID
1398	RedBlackTreeValidate (
1399	IN CONST RED_BLACK_TREE *Tree
1400	)
1401	{
1402	UINT32 BlackHeight;
1403	UINT32 ForwardCount;
1404	UINT32 BackwardCount;
1405	CONST RED_BLACK_TREE_NODE *Last;
1406	CONST RED_BLACK_TREE_NODE *Node;
1407
1408	DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));
1409
1410	//
1411	// property #5
1412	//
1413	ASSERT (NodeIsNullOrBlack (Tree->Root));
1414
1415	//
1416	// check the other properties
1417	//
1418	BlackHeight = RedBlackTreeRecursiveCheck (Tree->Root) - 1;
1419
1420	//
1421	// forward ordering
1422	//
1423	Last = OrderedCollectionMin (Tree);
1424	ForwardCount = (Last != NULL);
1425	for (Node = OrderedCollectionNext (Last); Node != NULL;
1426	Node = OrderedCollectionNext (Last)) {
1427	ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
1428	Last = Node;
1429	++ForwardCount;
1430	}
1431
1432	//
1433	// backward ordering
1434	//
1435	Last = OrderedCollectionMax (Tree);
1436	BackwardCount = (Last != NULL);
1437	for (Node = OrderedCollectionPrev (Last); Node != NULL;
1438	Node = OrderedCollectionPrev (Last)) {
1439	ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
1440	Last = Node;
1441	++BackwardCount;
1442	}
1443
1444	ASSERT (ForwardCount == BackwardCount);
1445
1446	DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
1447	__FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount));
1448	}

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Devices/EFI/Firmware/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c@ 87965

Download in other formats: