apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Jagielski <...@jaguNET.com>
Subject Re: Skiplist improvements
Date Thu, 10 Jul 2014 19:55:10 GMT

On Jul 10, 2014, at 1:53 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:

> Hello,
> 
> while trying to play with skiplists and multiple identical values
> (doublons, inserted with apr_skiplist_add), I have faced several
> issues.
> 
> The doublons compare equally but do not necessarily contain the same
> object, hence I had hoped that doublons added last would have been
> inserted last (this is the case, apr_skiplist_pop() works as
> expected), and that apr_skiplist_find() would have returned the first
> (oldest, FIFO) or last (newest, LIFO) all the time (this is not the
> case).
> 
> The issue is that when a doublon is insert_compare()d, it will not
> necessarily (and even unlikely) be at the same height as the existing
> doublon(s).
> Hence a "skip path" may be created between any previous value and the
> new doublon just inserted, and that path may be taken by
> apr_skiplist_find() to skip the oldest doublon(s).
> 
> I think this is not a desirable behaviour (the internals are
> probabilistic but the returned values through the API shouldn't be :p
> ).
> 

What does the canonical description of skiplists say?
Is that desirable or expected behavior? What do other
skiplist implementations do?


Mime
View raw message