[ovs-dev] [PATCH 2/4 v4] lib:Data structures: Skiplist implementation

Ben Pfaff blp at ovn.org
Thu Feb 2 16:55:34 UTC 2017


On Wed, Dec 28, 2016 at 07:41:46PM +0000, Rodriguez Betancourt, Esteban wrote:
> Skiplist implementation intended for the IDL compound indexes
> feature.
> 
> Signed-off-by: Esteban Rodriguez Betancourt <estebarb at hpe.com>

Thanks!

Is there a value to having max_levels as a configurable parameter for
the skiplist?  That is, is there a reason for the caller to specify
anything other than SKIPLIST_MAX_LEVELS?  From the comments, it sounds
like, if more levels are needed, then other code has to change anyway.
That means that the only other reason would be to use fewer levels, but
is there value in that?

skiplist_determine_level() seems like it could be implemented more
simply as something like:
        uint32_t level = clz32(random_uint32());
        return MIN(level, cl->max_levels);
or if we get rid of max_levels:
        return clz32(random_uint32());

s/ocurrence/occurrence/ in a comment.

It looks like free_func is only used in skiplist_destroy(), so It might
make more sense to simply pass it as an argument to skiplist_destroy().

Thanks,

Ben.


More information about the dev mailing list