Opened 2 years ago

Closed 2 years ago

#1518 closed defect (invalid)

ngx_rbtree small bug

Reported by: lwppwl@… Owned by:
Priority: minor Milestone:
Component: other Version: 1.13.x
Keywords: Cc:
uname -a: Linux lwp-All-Series 4.10.0-19-generic #21-Ubuntu SMP Thu Apr 6 17:04:57 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
nginx -V: nginx-1.12.2

Description

The ngx_rbtree.c file ngx_rbtree_next() The last line of the for loop,
"node = parent", is a small bug that does not affect the correct result
but can affect performance.
According to the context, "node" is the right child of the parent node and
the node's right sub-tree does not exist.
There are no nodes larger than node. NULL should be returned directly.

Change History (1)

comment:1 by Maxim Dounin, 2 years ago

Resolution: invalid
Status: newclosed

You can't return NULL directly without further checks here. Consider the following tree fragment:

  A
 /
B
 \
  C

Correct order should be: B, C, A. Assume we are at C, so node->right is empty, node != root, and node != parent->left. You suggest to return NULL here, but returning NULL is wrong - we should return A instead, and this is what happens in the code.

Note: See TracTickets for help on using tickets.