[ovs-dev] skiplist: Drop data comparison in skiplist_delete.

Message ID 20190129130955.28197-1-i.maximets@samsung.com
State Accepted
Headers show
Series
  • [ovs-dev] skiplist: Drop data comparison in skiplist_delete.
Related show

Commit Message

Ilya Maximets Jan. 29, 2019, 1:09 p.m.
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>
---
 lib/skiplist.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

Comments

Ben Pfaff Feb. 5, 2019, 12:23 a.m. | #1
On Tue, Jan 29, 2019 at 04:09:55PM +0300, Ilya Maximets wrote:
> 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.

Thanks!  Applied to master.

Patch

diff --git a/lib/skiplist.c b/lib/skiplist.c
index 2cea6d8df..ed33e97bb 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -190,9 +190,7 @@  skiplist_delete(struct skiplist *list, const void *value)
 
     if (x && list->cmp(x->data, value, list->cfg) == 0) {
         for (i = 0; i <= list->level; i++) {
-            if (!update[i]->forward[i] ||
-                list->cmp(update[i]->forward[i]->data, value,
-                          list->cfg) != 0) {
+            if (update[i]->forward[i] != x) {
                 break;
             }
             update[i]->forward[i] = x->forward[i];