On Jul 10, 2014, at 1:53 PM, Yann Ylavic <[email protected]> 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?
