Mailing-List: contact dev-help@apr.apache.org; run by ezmlm
Precedence: bulk
Received-SPF: neutral (athena.apache.org: 76.96.59.212 is neither permitted
 nor denied by domain of jim@jagunet.com)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
Subject: Re: Skiplist improvements
From: Jim Jagielski <jim@jaguNET.com>
In-Reply-To: 
 <CAKQ1sVO1EECMvSOz7Udqv83MJ_BR+KBed6wKgh8VG-ij9+qhtg@mail.gmail.com>
Date: Thu, 10 Jul 2014 15:55:10 -0400
Cc: apr <dev@apr.apache.org>
Content-Transfer-Encoding: 7bit
Message-Id: <257A1897-4A9D-41F8-B6C6-C49A296DA919@jaguNET.com>
References: 
 <CAKQ1sVO1EECMvSOz7Udqv83MJ_BR+KBed6wKgh8VG-ij9+qhtg@mail.gmail.com>
To: Yann Ylavic <ylavic.dev@gmail.com>


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?