| rbtree.c (7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0) | rbtree.c (59633abf34e2f44b8e772a2c12a92132aa7c2220) |
|---|---|
| 1/* 2 Red Black Trees 3 (C) 1999 Andrea Arcangeli <andrea@suse.de> 4 (C) 2002 David Woodhouse <dwmw2@infradead.org> 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2 of the License, or --- 93 unchanged lines hidden (view full) --- 102 if (!parent) { 103 rb_set_parent_color(node, NULL, RB_BLACK); 104 break; 105 } else if (rb_is_black(parent)) 106 break; 107 108 gparent = rb_red_parent(parent); 109 | 1/* 2 Red Black Trees 3 (C) 1999 Andrea Arcangeli <andrea@suse.de> 4 (C) 2002 David Woodhouse <dwmw2@infradead.org> 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2 of the License, or --- 93 unchanged lines hidden (view full) --- 102 if (!parent) { 103 rb_set_parent_color(node, NULL, RB_BLACK); 104 break; 105 } else if (rb_is_black(parent)) 106 break; 107 108 gparent = rb_red_parent(parent); 109 |
| 110 if (parent == gparent->rb_left) { 111 tmp = gparent->rb_right; | 110 tmp = gparent->rb_right; 111 if (parent != tmp) { /* parent == gparent->rb_left */ |
| 112 if (tmp && rb_is_red(tmp)) { 113 /* 114 * Case 1 - color flips 115 * 116 * G g 117 * / \ / \ 118 * p u --> P U 119 * / / --- 6 unchanged lines hidden (view full) --- 126 rb_set_parent_color(tmp, gparent, RB_BLACK); 127 rb_set_parent_color(parent, gparent, RB_BLACK); 128 node = gparent; 129 parent = rb_parent(node); 130 rb_set_parent_color(node, parent, RB_RED); 131 continue; 132 } 133 | 112 if (tmp && rb_is_red(tmp)) { 113 /* 114 * Case 1 - color flips 115 * 116 * G g 117 * / \ / \ 118 * p u --> P U 119 * / / --- 6 unchanged lines hidden (view full) --- 126 rb_set_parent_color(tmp, gparent, RB_BLACK); 127 rb_set_parent_color(parent, gparent, RB_BLACK); 128 node = gparent; 129 parent = rb_parent(node); 130 rb_set_parent_color(node, parent, RB_RED); 131 continue; 132 } 133 |
| 134 if (parent->rb_right == node) { | 134 tmp = parent->rb_right; 135 if (node == tmp) { |
| 135 /* 136 * Case 2 - left rotate at parent 137 * 138 * G G 139 * / \ / \ 140 * p U --> n U 141 * \ / 142 * n p 143 * 144 * This still leaves us in violation of 4), the 145 * continuation into Case 3 will fix that. 146 */ 147 parent->rb_right = tmp = node->rb_left; 148 node->rb_left = parent; 149 if (tmp) 150 rb_set_parent_color(tmp, parent, 151 RB_BLACK); 152 rb_set_parent_color(parent, node, RB_RED); 153 parent = node; | 136 /* 137 * Case 2 - left rotate at parent 138 * 139 * G G 140 * / \ / \ 141 * p U --> n U 142 * \ / 143 * n p 144 * 145 * This still leaves us in violation of 4), the 146 * continuation into Case 3 will fix that. 147 */ 148 parent->rb_right = tmp = node->rb_left; 149 node->rb_left = parent; 150 if (tmp) 151 rb_set_parent_color(tmp, parent, 152 RB_BLACK); 153 rb_set_parent_color(parent, node, RB_RED); 154 parent = node; |
| 155 tmp = node->rb_right; |
|
| 154 } 155 156 /* 157 * Case 3 - right rotate at gparent 158 * 159 * G P 160 * / \ / \ 161 * p U --> n g 162 * / \ 163 * n U 164 */ | 156 } 157 158 /* 159 * Case 3 - right rotate at gparent 160 * 161 * G P 162 * / \ / \ 163 * p U --> n g 164 * / \ 165 * n U 166 */ |
| 165 gparent->rb_left = tmp = parent->rb_right; | 167 gparent->rb_left = tmp; /* == parent->rb_right */ |
| 166 parent->rb_right = gparent; 167 if (tmp) 168 rb_set_parent_color(tmp, gparent, RB_BLACK); 169 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 170 break; 171 } else { 172 tmp = gparent->rb_left; 173 if (tmp && rb_is_red(tmp)) { 174 /* Case 1 - color flips */ 175 rb_set_parent_color(tmp, gparent, RB_BLACK); 176 rb_set_parent_color(parent, gparent, RB_BLACK); 177 node = gparent; 178 parent = rb_parent(node); 179 rb_set_parent_color(node, parent, RB_RED); 180 continue; 181 } 182 | 168 parent->rb_right = gparent; 169 if (tmp) 170 rb_set_parent_color(tmp, gparent, RB_BLACK); 171 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 172 break; 173 } else { 174 tmp = gparent->rb_left; 175 if (tmp && rb_is_red(tmp)) { 176 /* Case 1 - color flips */ 177 rb_set_parent_color(tmp, gparent, RB_BLACK); 178 rb_set_parent_color(parent, gparent, RB_BLACK); 179 node = gparent; 180 parent = rb_parent(node); 181 rb_set_parent_color(node, parent, RB_RED); 182 continue; 183 } 184 |
| 183 if (parent->rb_left == node) { | 185 tmp = parent->rb_left; 186 if (node == tmp) { |
| 184 /* Case 2 - right rotate at parent */ 185 parent->rb_left = tmp = node->rb_right; 186 node->rb_right = parent; 187 if (tmp) 188 rb_set_parent_color(tmp, parent, 189 RB_BLACK); 190 rb_set_parent_color(parent, node, RB_RED); 191 parent = node; | 187 /* Case 2 - right rotate at parent */ 188 parent->rb_left = tmp = node->rb_right; 189 node->rb_right = parent; 190 if (tmp) 191 rb_set_parent_color(tmp, parent, 192 RB_BLACK); 193 rb_set_parent_color(parent, node, RB_RED); 194 parent = node; |
| 195 tmp = node->rb_left; |
|
| 192 } 193 194 /* Case 3 - left rotate at gparent */ | 196 } 197 198 /* Case 3 - left rotate at gparent */ |
| 195 gparent->rb_right = tmp = parent->rb_left; | 199 gparent->rb_right = tmp; /* == parent->rb_left */ |
| 196 parent->rb_left = gparent; 197 if (tmp) 198 rb_set_parent_color(tmp, gparent, RB_BLACK); 199 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 200 break; 201 } 202 } 203} --- 14 unchanged lines hidden (view full) --- 218 * Otherwise, we need to adjust the tree through color flips 219 * and tree rotations as per one of the 4 cases below. 220 */ 221 if (node && rb_is_red(node)) { 222 rb_set_parent_color(node, parent, RB_BLACK); 223 break; 224 } else if (!parent) { 225 break; | 200 parent->rb_left = gparent; 201 if (tmp) 202 rb_set_parent_color(tmp, gparent, RB_BLACK); 203 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 204 break; 205 } 206 } 207} --- 14 unchanged lines hidden (view full) --- 222 * Otherwise, we need to adjust the tree through color flips 223 * and tree rotations as per one of the 4 cases below. 224 */ 225 if (node && rb_is_red(node)) { 226 rb_set_parent_color(node, parent, RB_BLACK); 227 break; 228 } else if (!parent) { 229 break; |
| 226 } else if (parent->rb_left == node) { 227 sibling = parent->rb_right; | 230 } 231 sibling = parent->rb_right; 232 if (node != sibling) { /* node == parent->rb_left */ |
| 228 if (rb_is_red(sibling)) { 229 /* 230 * Case 1 - left rotate at parent 231 * 232 * P S 233 * / \ / \ 234 * N s --> p Sr 235 * / \ / \ --- 370 unchanged lines hidden --- | 233 if (rb_is_red(sibling)) { 234 /* 235 * Case 1 - left rotate at parent 236 * 237 * P S 238 * / \ / \ 239 * N s --> p Sr 240 * / \ / \ --- 370 unchanged lines hidden --- |