Hi Ben,
I've taken a look at the code in skiplist.c and I think your concerns
aren't an issue. My search isn't exhaustive by any means, but I haven't
seen any way to make the implementation explode on itself. The
implementation mirrors the pseudocode used in the skiplist paper that is
referenced at the top of the file (including the naming of variables).
The biggest difference I see is that the sentinel "NIL" node at the end
of the skiplist is not used. Instead, there are checks for the nullity
of x->forward[i] in a bunch of places.
As far as the "height" field is concerned, the skiplist paper doesn't
ever define exactly what fields are required for a skiplist node.
However, you can infer that the "forward" and "key" [1] fields are
necessary. The author of the file likely either thought they would need
the height field and then it turned out they didn't, or they put it in
as a debugging aid.
Mark Michelson
[1] OVS code uses the term "data" instead of "key" even though most of
the other naming in the OVS code mirrors the skiplist paper.
On 1/24/19 12:49 AM, Ben Pfaff wrote:
I'm really suspicious about the code in lib/skiplist.c, because I
noticed that it writes, but never reads, the 'height' member of struct
skiplist_node. I suspect that, therefore, in some circumstances the
code can read past the end of the 'forward' array in skiplist_node.
I'd appreciate it if someone out there has time to verify that I'm right
or I'm wrong.
Thanks,
Ben.
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
