skiplist: Remove 'height' from skiplist_node.

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>

1 files changed, 0 insertions, 2 deletions

diff --git a/lib/skiplist.c b/lib/skiplist.c
index 2cea6d8df..1ae592623 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -40,7 +40,6 @@
 /* Skiplist node container */
 struct skiplist_node {
     const void *data;                 /* Pointer to saved data. */
-    int height;                       /* Height of this node. */
     struct skiplist_node *forward[];  /* Links to the next nodes. */
 };
 
@@ -66,7 +65,6 @@ skiplist_create_node(int level, const void *object)
 
     new_node = xmalloc(alloc_size);
     new_node->data = object;
-    new_node->height = level;
     memset(new_node->forward, 0,
            (level + 1) * sizeof new_node->forward[0]);