| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This member was write-only: it was initialized and never used later on.
Thanks to Esteban Rodriguez Betancourt <estebarb@hpe.com> for the
following additional rationale:
In this case you are right, the "height" member is not only not
used, it is in fact not required, and can be safely removed,
without causing security issues.
The code can't read past the end of the 'forward' array because
the skiplist "level" member, that specifies the maximum height of
the whole skiplist.
The "level" field is updated in insertions and deletions, so that
in insertion the root node will point to the newly created item
(if there isn't a list there yet). At the deletions, if the
deleted item is the last one at that height then the root is
modified to point to NULL at that height, and the whole skiplist
height is decremented.
For the forward_to case:
- If a node is found in a list of level/height N, then it has
height N (that's why it was inserted in that list)
- forward_to travels throught nodes in the same level, so it is
safe, as it doesn't go up.
- If a node has height N, then it belongs to all the lists
initiated at root->forward[n, n-1 ,n-2, ..., 0]
- forward_to may go to lower levels, but that is safe, because of
previous point.
So, the protection is given by the "level" field in skiplist root
node, and it is enough to guarantee that the code won't go off
limits at 'forward' array. But yes, the height field is unused,
unneeded, and can be removed safely.
CC: Esteban Rodriguez Betancourt <estebarb@hpe.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
|
