linux-kernel - 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 25 Aug 2021 18:26:59 +0000
From:   "Li,Rongqing" <lirongqing@...du.com>
To:     Peter Zijlstra <peterz@...radead.org>
CC:     Michel Lespinasse <michel@...pinasse.org>,
        "dbueso@...e.de" <dbueso@...e.de>,
        "mingo@...nel.org" <mingo@...nel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first









    
On Wed, Aug 25, 2021 at 04:01:53PM +0000, Li,Rongqing wrote:
> 
> >>
> >>
> >>                         10
> >>                       /
> >>                      5
> >>                       \
> >>                        10

>That again breaks the above case.

                       10
                     /
                    5
                       \
                      10

the above case should not exist. like below, when second 10 is inserted, it should be inserted to right leaf
                       10
                     /
                    5

as a result, it should be

                       10
                     /     \
                    5      10

since 10 is not less 10, so new 10 is inserted to right.
and it depends on 
bool (*less)(struct rb_node *, const struct rb_node *) which not return true when equal

this case should be ok
                       10
                           \
                           12
                            /
                          10

-Li