]> git.proxmox.com Git - ovs.git/commit
skiplist: Drop data comparison in skiplist_delete.
authorIlya Maximets <i.maximets@samsung.com>
Tue, 29 Jan 2019 13:09:55 +0000 (16:09 +0300)
committerBen Pfaff <blp@ovn.org>
Tue, 5 Feb 2019 00:22:04 +0000 (16:22 -0800)
commit7f289e0212c799a083cbf123a9c08bc65ca14f58
treede630c4f8dd76795c54fed130f2bafc916dae0d1
parent29e41156d65f584e89d4b5f84ef82e03127b07e3
skiplist: Drop data comparison in skiplist_delete.

Current version of 'skiplist_delete' uses data comparator to check
if the node that we're removing exists on current level. i.e. our
node 'x' is the next of update[i] on the level i.
But it's enough to just check pointers for that purpose.

Here is the small example of how the data structures looks at
this moment:

        i   a   b   c        x        d   e   f
        0  [ ]>[ ]>[*] ---> [ ] ---> [#]>[ ]>[ ]
        1  [ ]>[*] -------> [ ] -------> [#]>[ ]
        2  [ ]>[*] -------> [ ] -----------> [#]
        3  [ ]>[*] ------------------------> [ ]
        4  [*] ----------------------------> [ ]

                        0  1  2  3  4
           update[] = { c, b, b, b, a }
        x.forward[] = { d, e, f }

        c.forward[0] = x
        b.forward[1] = x
        b.forward[2] = x
        b.forward[3] = f
        a.forward[4] = f

  Target:

        i   a   b   c                 d   e   f
        0  [ ]>[ ]>[*] ------------> [#]>[ ]>[ ]
        1  [ ]>[*] --------------------> [#]>[ ]
        2  [ ]>[*] ------------------------> [#]
        3  [ ]>[*] ------------------------> [ ]
        4  [*] ----------------------------> [ ]

        c.forward[0] = x.forward[0] = d
        b.forward[1] = x.forward[1] = e
        b.forward[2] = x.forward[2] = f
        b.forward[3] = f
        a.forward[4] = f

i.e. we're updating forward pointers while update[i].forward[i] == x.

Signed-off-by: Ilya Maximets <i.maximets@samsung.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
lib/skiplist.c