| Message ID | 20190129130955.28197-1-i.maximets@samsung.com |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] skiplist: Drop data comparison in skiplist_delete. | expand |
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.
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];
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(-)