directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lécharny <>
Subject Re: [Mavibot] Cursor handling
Date Mon, 19 Oct 2015 09:57:12 GMT
Le 19/10/15 04:37, Emmanuel Lécharny a écrit :
> Le 19/10/15 03:24, Howard Chu a écrit :
>> Emmanuel Lécharny wrote:
>>> Hi,
>>> some thoughts about the current implementation :
>>> Cursor support in Mavibot
>>> -------------------------
>>> The current implementation is a bit unsastifactory, and it does not
>>> necessarily fits with the simplifications we are introducing (namely,
>>> the removal of duplicate values). Typically, the current cursor allows
>>> the user to move forward and backward across keys and values, when we
>>> only need to move across keys now.
>>> Moving
>>> ------
>>> First of all, we must be able to move backward and forward. Fetching an
>>> element is a different operation than moving, but one should still be
>>> able to get back an element when moving. This is done through 4 methods,
>>> 2 which are relative, and 2 which are absolute.
>>> Relative moves :
>>> next() : move forward to the net key
>>> prev() : move forward to the net key
>>> Absolute moves :
>>> next(K) : move after the given key
>>> prev(K) : move before the given key
>> These absolute moves seem like an extravagance. I have never seen a
>> dbm-style library with such methods. It's more natural to have an
>> explicit seek() method and then do a relative next/prev after that.
> It is used for searches like (age>20). If the key 20 does not exist in
> the B-tree, next(20) will move to the closest key above 20, and prev(20)
> will move to the closest key below 20. If the key 20 exists, then
> next(20) will be moved after the key 20 and prev(20) before the key 20.
> Now, we may need a seek(K) to fetch an element we know exists in the
> Btree, to avoid having to do things like prev(K); tuple = next();
> I have to thought a bit more about the real need for those before(K) and
> after(K) methods, wil wait for my morning shower for that : insomnia is
> not the best timing to have a clear thought about API design decisions ;-)

Second thought :

if we want to efficiently browse forward *and* backward, the seek(K)
method is not sufficient to correctly guess what to do when doing the
first next or prev move when the K is not present. Either we set the
position after K, or before K, but in any case, we have to do annoying
things like :

(NOTE : we don't check the limits here, which means some extra checks
have to be done to see if we are at the beginning or at the end of the
B-tree. This can also be done using exceptions)

(NOTE 2 : I assume the  position is set after K if K is not existent, or
set on K if it exists)

getting the previous key

tuple = seek(K);

if ( tuple == null )
    tuple = prev();

getting the next key

tuple = seek(K);

if ( tuple == null )
    tuple = get();

If the key is present, we are done, the seek(K) will return the value.

OTOH, using the before(K)/after(K), it's easier :

getting the previous key

tuple = before(K);

getting the next key

tuple = after(K);

No test, not need to remember if the seek(K) method set the position
before or after K.

Is that extravagant, or just spurious ? I mean, we can live with
seek(K), it does the job, I just wonder if the additional methods don't
mke the developer lifer easier.

wdyt ?

View raw message