1 /*
2  * Copyright (C) 2022 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include "rb_tree.h"
17 
18 #ifdef __cplusplus
19 extern "C" {
20 #endif
21 
FillpRbRotateLeft(struct RbNode * x,struct RbRoot * root)22 static void FillpRbRotateLeft(struct RbNode *x, struct RbRoot *root)
23 {
24     /*
25      * rotate Node x to left *
26      */
27     struct RbNode *y = x->rbRight;
28 
29     /* estblish x->Right link */
30     x->rbRight = y->rbLeft;
31     if (y->rbLeft != FILLP_NULL_PTR) {
32         y->rbLeft->rbParent = x;
33     }
34 
35     /* estblish y->parent link */
36     y->rbParent = x->rbParent;
37     if (x->rbParent != FILLP_NULL_PTR) {
38         if (x == x->rbParent->rbLeft) {
39             x->rbParent->rbLeft = y;
40         } else {
41             x->rbParent->rbRight = y;
42         }
43     } else {
44         root->rbNode = y;
45     }
46 
47     /* link x and y */
48     y->rbLeft = x;
49     x->rbParent = y;
50 }
51 
52 
FillpRbRotateRight(struct RbNode * x,struct RbRoot * root)53 static void FillpRbRotateRight(struct RbNode *x, struct RbRoot *root)
54 {
55     /*
56      * rotate Node x to right  *
57      */
58     struct RbNode *y = x->rbLeft;
59 
60     /* estblish x->Left link */
61     x->rbLeft = y->rbRight;
62     if (y->rbRight != FILLP_NULL_PTR) {
63         y->rbRight->rbParent = x;
64     }
65 
66     /* estblish y->parent link */
67     y->rbParent = x->rbParent;
68     if (x->rbParent != FILLP_NULL_PTR) {
69         if (x == x->rbParent->rbRight) {
70             x->rbParent->rbRight = y;
71         } else {
72             x->rbParent->rbLeft = y;
73         }
74     } else {
75         root->rbNode = y;
76     }
77 
78     /* link x and y */
79     y->rbRight = x;
80     x->rbParent = y;
81 }
82 
EqualRight(struct RbNode * x,struct RbRoot * root)83 static struct RbNode *EqualRight(struct RbNode *x, struct RbRoot *root)
84 {
85     if (x == x->rbParent->rbRight) {
86         /* make x a left child */
87         x = x->rbParent;
88         FillpRbRotateLeft(x, root);
89     }
90     return x;
91 }
92 
EqualLeft(struct RbNode * x,struct RbRoot * root)93 static struct RbNode *EqualLeft(struct RbNode *x, struct RbRoot *root)
94 {
95     if (x == x->rbParent->rbLeft) {
96         x = x->rbParent;
97         FillpRbRotateRight(x, root);
98     }
99     return x;
100 }
101 
102 /* x, y are for application */
FillpRbInsertColor(struct RbNode * x,struct RbRoot * root)103 void FillpRbInsertColor(struct RbNode *x, struct RbRoot *root)
104 {
105     /* maintain red-black tree balance  *
106      * after inserting node x           *
107      * check red-black properties */
108     while (x != root->rbNode && x->rbParent->color == RB_RED) {
109         /* we have a violation */
110         if (x->rbParent == x->rbParent->rbParent->rbLeft) {
111             struct RbNode *y = x->rbParent->rbParent->rbRight;
112             if (y && y->color == RB_RED) {
113                 /* uncle is red */
114                 x->rbParent->color = RB_BLACK;
115                 y->color = RB_BLACK;
116                 x->rbParent->rbParent->color = RB_RED;
117                 x = x->rbParent->rbParent;
118             } else {
119                 /* uncle is black */
120                 x = EqualRight(x, root);
121 
122                 /* recolor and rotate */
123                 x->rbParent->color = RB_BLACK;
124                 x->rbParent->rbParent->color = RB_RED;
125                 FillpRbRotateRight(x->rbParent->rbParent, root);
126             }
127         } else {
128             /* miror image of above code */
129             struct RbNode *y = x->rbParent->rbParent->rbLeft;
130             if ((y != FILLP_NULL_PTR) && (y->color == RB_RED)) {
131                 /* uncle is red */
132                 x->rbParent->color = RB_BLACK;
133                 y->color = RB_BLACK;
134                 x->rbParent->rbParent->color = RB_RED;
135                 x = x->rbParent->rbParent;
136             } else {
137                 /* uncle is black */
138                 x = EqualLeft(x, root);
139                 x->rbParent->color = RB_BLACK;
140                 x->rbParent->rbParent->color = RB_RED;
141                 FillpRbRotateLeft(x->rbParent->rbParent, root);
142             }
143         }
144     }
145 
146     root->rbNode->color = RB_BLACK;
147 }
148 
FillpRbEraseColorAtLeft(struct RbNode ** x,struct RbNode ** parent,struct RbRoot * root)149 static int FillpRbEraseColorAtLeft(struct RbNode **x, struct RbNode **parent, struct RbRoot *root)
150 {
151     struct RbNode *w = (*parent)->rbRight;
152     if (w->color == RB_RED) {
153         w->color = RB_BLACK;
154         (*parent)->color = RB_RED; /* parent != NIL? */
155         FillpRbRotateLeft((*parent), root);
156         return 0;
157     }
158     if (((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) &&
159         ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK))) {
160         w->color = RB_RED;
161         (*x) = (*parent);
162         (*parent) = (*x)->rbParent;
163         return 0;
164     } else {
165         if ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK)) {
166             if (w->rbLeft != FILLP_NULL_PTR) {
167                 w->rbLeft->color = RB_BLACK;
168             }
169             w->color = RB_RED;
170             FillpRbRotateRight(w, root);
171             w = (*parent)->rbRight;
172         }
173         w->color = (*parent)->color;
174         (*parent)->color = RB_BLACK;
175         if (w->rbRight->color != RB_BLACK) {
176             w->rbRight->color = RB_BLACK;
177         }
178         FillpRbRotateLeft((*parent), root);
179         (*x) = root->rbNode;
180         return 1;
181     }
182 }
183 
FillpRbEraseColorAtRight(struct RbNode ** x,struct RbNode ** parent,struct RbRoot * root)184 static int FillpRbEraseColorAtRight(struct RbNode **x, struct RbNode **parent, struct RbRoot *root)
185 {
186     struct RbNode *w = (*parent)->rbLeft;
187     if (w->color == RB_RED) {
188         w->color = RB_BLACK;
189         (*parent)->color = RB_RED; /* parent != NIL? */
190         FillpRbRotateRight((*parent), root);
191         return 0;
192     }
193     if (((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) &&
194         ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK))) {
195         w->color = RB_RED;
196         (*x) = (*parent);
197         (*parent) = (*x)->rbParent;
198         return 0;
199     } else {
200         if ((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) {
201             if (w->rbRight != FILLP_NULL_PTR) {
202                 w->rbRight->color = RB_BLACK;
203             }
204             w->color = RB_RED;
205             FillpRbRotateLeft(w, root);
206             w = (*parent)->rbLeft;
207         }
208         w->color = (*parent)->color;
209         (*parent)->color = RB_BLACK;
210         if (w->rbLeft->color != RB_BLACK) {
211             w->rbLeft->color = RB_BLACK;
212         }
213         FillpRbRotateRight((*parent), root);
214         (*x) = root->rbNode;
215         return 1;
216     }
217 }
218 
FillpRbEraseColor(struct RbNode * x,struct RbNode * parent,struct RbRoot * root)219 static void FillpRbEraseColor(struct RbNode *x, struct RbNode *parent, struct RbRoot *root)
220 {
221     /*
222      * maintain red-black tree balance  *
223      * after deleting node x            *
224      */
225     int ret;
226     while ((x != root->rbNode) && ((x == FILLP_NULL_PTR) || (x->color == RB_BLACK))) {
227         if (parent == FILLP_NULL_PTR) {
228             break;
229         }
230 
231         if (x == parent->rbLeft) {
232             ret = FillpRbEraseColorAtLeft(&x, &parent, root);
233             if (ret != 0) {
234                 break;
235             }
236         } else {
237             ret = FillpRbEraseColorAtRight(&x, &parent, root);
238             if (ret != 0) {
239                 break;
240             }
241         }
242     }
243 
244     if (x != FILLP_NULL_PTR) {
245         x->color = RB_BLACK;
246     }
247 }
248 
FillpRbEraseLowlvlNode(struct RbNode * node,struct RbRoot * root)249 static void FillpRbEraseLowlvlNode(struct RbNode *node, struct RbRoot *root)
250 {
251     struct RbNode *childNode = FILLP_NULL_PTR;
252     struct RbNode *parentNode = FILLP_NULL_PTR;
253     struct RbNode *oldNode = node;
254     struct RbNode *leftNode;
255     FILLP_UINT color;
256 
257     node = node->rbRight;
258     leftNode = node->rbLeft;
259     while (leftNode != FILLP_NULL_PTR) {
260         node = leftNode;
261         leftNode = node->rbLeft;
262     }
263 
264     if (oldNode->rbParent != FILLP_NULL_PTR) {
265         if (oldNode->rbParent->rbLeft == oldNode) {
266             oldNode->rbParent->rbLeft = node;
267         } else {
268             oldNode->rbParent->rbRight = node;
269         }
270     } else {
271         root->rbNode = node;
272     }
273 
274     childNode = node->rbRight;
275     parentNode = node->rbParent;
276     color = node->color;
277 
278     if (parentNode == oldNode) {
279         parentNode = node;
280     } else {
281         if (childNode != FILLP_NULL_PTR) {
282             childNode->rbParent = parentNode;
283         }
284 
285         parentNode->rbLeft = childNode;
286 
287         node->rbRight = oldNode->rbRight;
288         oldNode->rbRight->rbParent = node;
289     }
290 
291     node->color = oldNode->color;
292     node->rbParent = oldNode->rbParent;
293     node->rbLeft = oldNode->rbLeft;
294     oldNode->rbLeft->rbParent = node;
295 
296     if (color == RB_BLACK) {
297         FillpRbEraseColor(childNode, parentNode, root);
298     }
299 }
300 
FillpRbErase(struct RbNode * node,struct RbRoot * root)301 void FillpRbErase(struct RbNode *node, struct RbRoot *root)
302 {
303     struct RbNode *childNode = FILLP_NULL_PTR;
304     struct RbNode *parentNode = FILLP_NULL_PTR;
305     FILLP_UINT color;
306 
307     if (node->rbLeft == FILLP_NULL_PTR) {
308         childNode = node->rbRight;
309     } else if (node->rbRight == FILLP_NULL_PTR) {
310         childNode = node->rbLeft;
311     } else {
312         FillpRbEraseLowlvlNode(node, root);
313         return;
314     }
315 
316     parentNode = node->rbParent;
317     color = node->color;
318 
319     if (childNode != FILLP_NULL_PTR) {
320         childNode->rbParent = parentNode;
321     }
322 
323     if (parentNode != FILLP_NULL_PTR) {
324         if (parentNode->rbLeft == node) {
325             parentNode->rbLeft = childNode;
326         } else {
327             parentNode->rbRight = childNode;
328         }
329     } else {
330         root->rbNode = childNode;
331     }
332 
333     if (color == RB_BLACK) {
334         FillpRbEraseColor(childNode, parentNode, root);
335     }
336 }
337 
338 
339 #ifdef __cplusplus
340 }
341 #endif
342