Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

lib/rbtree: Remove dead case in rb_remove() #33239

Closed
Zhaoningx opened this issue Mar 11, 2021 · 1 comment
Closed

lib/rbtree: Remove dead case in rb_remove() #33239

Zhaoningx opened this issue Mar 11, 2021 · 1 comment
Assignees
Labels
bug The issue is a bug, or the PR is fixing a bug priority: low Low impact/importance bug

Comments

@Zhaoningx
Copy link
Collaborator

Zhaoningx commented Mar 11, 2021

Describe the bug
I find some code that never been reached here in rb.c(lines 486~489) , the code screenshot as below:
image
let's do something firstly, Naming node that ready to be removed as A, and naming the biggest node of side 0 about A as B, so let me show you my point.
After my analysis, I think if the code can be reached here, It must meet the following conditions:
The first condition, the node A has two child, demo it such as(A is 30, B is 25, C is 23):

image

I think when B is red or C is black can reach the else{...} code (lines 486~489), but as you see, it is not satisfied the Red/black tree's principle.

The second condition, the node A just has one left child, demo it such as(A is 50, B is 45):
image

I think when A and B are both same color can reach the else{...} code (lines 486~489), but it's also not satisfied the rbtree's principle.

In my opinion, whatever we do, it can't be covered for the else{ ... } code except two conditions(with corrupt rbtree) above. So I think we should delete else{} code(lines 486~489).

Impact
It will makes a impact for tree's code coverage.

@Zhaoningx Zhaoningx added the bug The issue is a bug, or the PR is fixing a bug label Mar 11, 2021
@explora26 explora26 changed the title Reb/black tree: maybe we can remove some bed code Reb/black tree: maybe we can remove some bad code Mar 11, 2021
@nashif nashif added the priority: low Low impact/importance bug label Mar 11, 2021
@andyross andyross assigned Zhaoningx and unassigned andyross Mar 11, 2021
@Zhaoningx Zhaoningx changed the title Reb/black tree: maybe we can remove some bad code lib/rbtree: Remove dead case in rb_remove() Mar 12, 2021
Zhaoningx added a commit to Zhaoningx/zephyr that referenced this issue Mar 12, 2021
This "else" clause was dead code, in a valid
tree it's not possible to have a node and
its child both be red.
Fix issue zephyrproject-rtos#33239.

Signed-off-by: Ningx Zhao <[email protected]>
nashif pushed a commit that referenced this issue Mar 13, 2021
This "else" clause was dead code, in a valid
tree it's not possible to have a node and
its child both be red.
Fix issue #33239.

Signed-off-by: Ningx Zhao <[email protected]>
@Zhaoningx
Copy link
Collaborator Author

It has fixed, so closed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug The issue is a bug, or the PR is fixing a bug priority: low Low impact/importance bug
Projects
None yet
Development

No branches or pull requests

3 participants