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 cxd 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
---
lib/skiplist.c | 4 +---
1 file changed, 1 insertion(+), 3 deletions(-)
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];
--
2.17.1
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
