<p>The algorithm of<font face="sans-serif"><span style="line-height:19px"> </span></font>many rbtree lookup functions in nginx requires that nodes with the same hash</p><p>value are linked together, but sometimes this may be broken with the rebalance of the tree </p>








<p>after new nodes inserted.  See the following example, the number contains hash value and node</p><p>key, 51 shares the same hash value with 52. After the inserting of 63 and the rebalancing of the</p><p>tree, they are separated. Then 51 is "lost" from the tree. every lookup for 51 returns null and new</p>




<p>nodes are always alloced until one of them is linked with 52 again.</p>

<p><img src="cid:ii_135be1430888bf2c" alt="ÄÚǶͼƬ 1"></p><p>rbtree2.diff is a clean diff which ignores white space changes.</p>