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