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 return;
52 }
53
54
FillpRbRotateRight(struct RbNode * x,struct RbRoot * root)55 static void FillpRbRotateRight(struct RbNode *x, struct RbRoot *root)
56 {
57 /*
58 * rotate Node x to right *
59 */
60 struct RbNode *y = x->rbLeft;
61
62 /* estblish x->Left link */
63 x->rbLeft = y->rbRight;
64 if (y->rbRight != FILLP_NULL_PTR) {
65 y->rbRight->rbParent = x;
66 }
67
68 /* estblish y->parent link */
69 y->rbParent = x->rbParent;
70 if (x->rbParent != FILLP_NULL_PTR) {
71 if (x == x->rbParent->rbRight) {
72 x->rbParent->rbRight = y;
73 } else {
74 x->rbParent->rbLeft = y;
75 }
76 } else {
77 root->rbNode = y;
78 }
79
80 /* link x and y */
81 y->rbRight = x;
82 x->rbParent = y;
83
84 return;
85 }
86
EqualRight(struct RbNode * x,struct RbRoot * root)87 static struct RbNode *EqualRight(struct RbNode *x, struct RbRoot *root)
88 {
89 if (x == x->rbParent->rbRight) {
90 /* make x a left child */
91 x = x->rbParent;
92 FillpRbRotateLeft(x, root);
93 }
94 return x;
95 }
96
EqualLeft(struct RbNode * x,struct RbRoot * root)97 static struct RbNode *EqualLeft(struct RbNode *x, struct RbRoot *root)
98 {
99 if (x == x->rbParent->rbLeft) {
100 x = x->rbParent;
101 FillpRbRotateRight(x, root);
102 }
103 return x;
104 }
105
106 /* x, y are for application */
FillpRbInsertColor(struct RbNode * x,struct RbRoot * root)107 void FillpRbInsertColor(struct RbNode *x, struct RbRoot *root)
108 {
109 /* maintain red-black tree balance *
110 * after inserting node x *
111 * check red-black properties */
112 while (x != root->rbNode && x->rbParent->color == RB_RED) {
113 /* we have a violation */
114 if (x->rbParent == x->rbParent->rbParent->rbLeft) {
115 struct RbNode *y = x->rbParent->rbParent->rbRight;
116 if (y && y->color == RB_RED) {
117 /* uncle is red */
118 x->rbParent->color = RB_BLACK;
119 y->color = RB_BLACK;
120 x->rbParent->rbParent->color = RB_RED;
121 x = x->rbParent->rbParent;
122 } else {
123 /* uncle is black */
124 x = EqualRight(x, root);
125
126 /* recolor and rotate */
127 x->rbParent->color = RB_BLACK;
128 x->rbParent->rbParent->color = RB_RED;
129 FillpRbRotateRight(x->rbParent->rbParent, root);
130 }
131 } else {
132 /* miror image of above code */
133 struct RbNode *y = x->rbParent->rbParent->rbLeft;
134 if ((y != FILLP_NULL_PTR) && (y->color == RB_RED)) {
135 /* uncle is red */
136 x->rbParent->color = RB_BLACK;
137 y->color = RB_BLACK;
138 x->rbParent->rbParent->color = RB_RED;
139 x = x->rbParent->rbParent;
140 } else {
141 /* uncle is black */
142 x = EqualLeft(x, root);
143 x->rbParent->color = RB_BLACK;
144 x->rbParent->rbParent->color = RB_RED;
145 FillpRbRotateLeft(x->rbParent->rbParent, root);
146 }
147 }
148 }
149
150 root->rbNode->color = RB_BLACK;
151
152 return;
153 }
154
FillpRbEraseColorAtLeft(struct RbNode ** x,struct RbNode ** parent,struct RbRoot * root)155 static int FillpRbEraseColorAtLeft(struct RbNode **x, struct RbNode **parent, struct RbRoot *root)
156 {
157 struct RbNode *w = (*parent)->rbRight;
158 if (w->color == RB_RED) {
159 w->color = RB_BLACK;
160 (*parent)->color = RB_RED; /* parent != NIL? */
161 FillpRbRotateLeft((*parent), root);
162 return 0;
163 }
164 if (((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) &&
165 ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK))) {
166 w->color = RB_RED;
167 (*x) = (*parent);
168 (*parent) = (*x)->rbParent;
169 return 0;
170 } else {
171 if ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK)) {
172 if (w->rbLeft != FILLP_NULL_PTR) {
173 w->rbLeft->color = RB_BLACK;
174 }
175 w->color = RB_RED;
176 FillpRbRotateRight(w, root);
177 w = (*parent)->rbRight;
178 }
179 w->color = (*parent)->color;
180 (*parent)->color = RB_BLACK;
181 if (w->rbRight->color != RB_BLACK) {
182 w->rbRight->color = RB_BLACK;
183 }
184 FillpRbRotateLeft((*parent), root);
185 (*x) = root->rbNode;
186 return 1;
187 }
188 }
189
FillpRbEraseColorAtRight(struct RbNode ** x,struct RbNode ** parent,struct RbRoot * root)190 static int FillpRbEraseColorAtRight(struct RbNode **x, struct RbNode **parent, struct RbRoot *root)
191 {
192 struct RbNode *w = (*parent)->rbLeft;
193 if (w->color == RB_RED) {
194 w->color = RB_BLACK;
195 (*parent)->color = RB_RED; /* parent != NIL? */
196 FillpRbRotateRight((*parent), root);
197 return 0;
198 }
199 if (((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) &&
200 ((w->rbRight == FILLP_NULL_PTR) || (w->rbRight->color == RB_BLACK))) {
201 w->color = RB_RED;
202 (*x) = (*parent);
203 (*parent) = (*x)->rbParent;
204 return 0;
205 } else {
206 if ((w->rbLeft == FILLP_NULL_PTR) || (w->rbLeft->color == RB_BLACK)) {
207 if (w->rbRight != FILLP_NULL_PTR) {
208 w->rbRight->color = RB_BLACK;
209 }
210 w->color = RB_RED;
211 FillpRbRotateLeft(w, root);
212 w = (*parent)->rbLeft;
213 }
214 w->color = (*parent)->color;
215 (*parent)->color = RB_BLACK;
216 if (w->rbLeft->color != RB_BLACK) {
217 w->rbLeft->color = RB_BLACK;
218 }
219 FillpRbRotateRight((*parent), root);
220 (*x) = root->rbNode;
221 return 1;
222 }
223 }
224
FillpRbEraseColor(struct RbNode * x,struct RbNode * parent,struct RbRoot * root)225 static void FillpRbEraseColor(struct RbNode *x, struct RbNode *parent, struct RbRoot *root)
226 {
227 /*
228 * maintain red-black tree balance *
229 * after deleting node x *
230 */
231 int ret;
232 while ((x != root->rbNode) && ((x == FILLP_NULL_PTR) || (x->color == RB_BLACK))) {
233 if (parent == FILLP_NULL_PTR) {
234 break;
235 }
236
237 if (x == parent->rbLeft) {
238 ret = FillpRbEraseColorAtLeft(&x, &parent, root);
239 if (ret != 0) {
240 break;
241 }
242 } else {
243 ret = FillpRbEraseColorAtRight(&x, &parent, root);
244 if (ret != 0) {
245 break;
246 }
247 }
248 }
249
250 if (x != FILLP_NULL_PTR) {
251 x->color = RB_BLACK;
252 }
253
254 return;
255 }
256
FillpRbEraseLowlvlNode(struct RbNode * node,struct RbRoot * root)257 static void FillpRbEraseLowlvlNode(struct RbNode *node, struct RbRoot *root)
258 {
259 struct RbNode *childNode = FILLP_NULL_PTR;
260 struct RbNode *parentNode = FILLP_NULL_PTR;
261 struct RbNode *oldNode = node;
262 struct RbNode *leftNode;
263 FILLP_UINT color;
264
265 node = node->rbRight;
266 leftNode = node->rbLeft;
267 while (leftNode != FILLP_NULL_PTR) {
268 node = leftNode;
269 leftNode = node->rbLeft;
270 }
271
272 if (oldNode->rbParent != FILLP_NULL_PTR) {
273 if (oldNode->rbParent->rbLeft == oldNode) {
274 oldNode->rbParent->rbLeft = node;
275 } else {
276 oldNode->rbParent->rbRight = node;
277 }
278 } else {
279 root->rbNode = node;
280 }
281
282 childNode = node->rbRight;
283 parentNode = node->rbParent;
284 color = node->color;
285
286 if (parentNode == oldNode) {
287 parentNode = node;
288 } else {
289 if (childNode != FILLP_NULL_PTR) {
290 childNode->rbParent = parentNode;
291 }
292
293 parentNode->rbLeft = childNode;
294
295 node->rbRight = oldNode->rbRight;
296 oldNode->rbRight->rbParent = node;
297 }
298
299 node->color = oldNode->color;
300 node->rbParent = oldNode->rbParent;
301 node->rbLeft = oldNode->rbLeft;
302 oldNode->rbLeft->rbParent = node;
303
304 if (color == RB_BLACK) {
305 FillpRbEraseColor(childNode, parentNode, root);
306 }
307 }
308
FillpRbErase(struct RbNode * node,struct RbRoot * root)309 void FillpRbErase(struct RbNode *node, struct RbRoot *root)
310 {
311 struct RbNode *childNode = FILLP_NULL_PTR;
312 struct RbNode *parentNode = FILLP_NULL_PTR;
313 FILLP_UINT color;
314
315 if (node->rbLeft == FILLP_NULL_PTR) {
316 childNode = node->rbRight;
317 } else if (node->rbRight == FILLP_NULL_PTR) {
318 childNode = node->rbLeft;
319 } else {
320 FillpRbEraseLowlvlNode(node, root);
321 return;
322 }
323
324 parentNode = node->rbParent;
325 color = node->color;
326
327 if (childNode != FILLP_NULL_PTR) {
328 childNode->rbParent = parentNode;
329 }
330
331 if (parentNode != FILLP_NULL_PTR) {
332 if (parentNode->rbLeft == node) {
333 parentNode->rbLeft = childNode;
334 } else {
335 parentNode->rbRight = childNode;
336 }
337 } else {
338 root->rbNode = childNode;
339 }
340
341 if (color == RB_BLACK) {
342 FillpRbEraseColor(childNode, parentNode, root);
343 }
344
345 return;
346 }
347
348
349 #ifdef __cplusplus
350 }
351 #endif
352