directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lécharny <>
Subject Re: [index] OneLevel and SubLevel index
Date Thu, 29 Mar 2012 15:59:39 GMT
Le 3/28/12 5:31 PM, Alex Karasulu a écrit :
> On Thu, Mar 22, 2012 at 8:38 PM, Emmanuel Lécharny<>wrote:
>> Hi,
>> one last mail...
>> I will just mention that we alreadu discussed this mater (ie should we
>> keep oneLevel and sublevel index) last year with Stefan, and he thinks that
>> we can get rid of those two guys :
>> http://mail-archives.apache.**org/mod_mbox/directory-dev/**
>> 201110.mbox/%3CCAPz8h_**WfA2Wa2iZpSdwSswKGoFw9aun1---**
>> and
>> http://mail-archives.apache.**org/mod_mbox/directory-dev/**
>> 201110.mbox/%3CCAPz8h_**VTUQKRtgaN4QZ+**4PX3KJTu6DPPjAw6k9roMXvnD7Ok_**
>> No need to rehash them, it's probably time to get the branch merged with
>> the trunk?
> We should review this then proceed accordingly.
So, I have made progress !

Stefan's idea was to add markers (ParentIdAndRdn with RDN : zzz=zzz) in 
the index, to be able to find the children.

This is not even needed, as soon as each element knows how many children 
it has.

What I did was to add such an information in the ParentIdAndRdn class, 
information which gets updated every time we add/remove/move an entry, 
and to use it while browsing the index.

The thing is that a Table contains couple of <Key, Value(s)> (Values if 
the Table allows duplicates, which is not the case for the RDN index). 
We can get a cursor on this table, and set a position in it (the 
position being the first element *before* one given as a marker).

Let's suppose we have such a hierarchy :

   +-- <0, cn=A>[1]
             +-- <1, cn=B>[2]
              +--<1, cn=A>[3]

The forward index will be :

<0, cn=A> : 1
<1, cn=B> : 2
<1, cn=A> : 3

and the reverse index :

1 : <0, cn=A>
2 : <1, cn=B>
3 : <1, cn=A>

So I get a cursor, and considering we are looking for, say, all the 
children for cn=A, which ID is 1, I asked the cursor to be positionned 
before <1, null>, where 1 is the ID for the cn=A element.
Now, I can fetch the context entry and ask how many children it has. 
Here, it has 2. I just have to browe the tree starting at the given 
position (ie, cn=A), and browse the tree until I have fetched 2 
elements. The cursor will return <1, cn=B> and <1, cn=A> which are the 
children of <0, cn=A>.

How do I get the browser to fetch the element in the right order ? It's 
easy : the ParentIdAndRdn class has a compareTo() method which is used 
to compare two instances. I just modified it so that if the ID are not 
equals, then I don't even bother using the RDN. If ID1 = 7 and ID2 = 10, 
then the two instances are not common children of an entry. OTOH, if the 
two instances ID are equals, then that means they have the same parent. 
In this case, in order to insert the elements in the ordered tree, the 
RDN is used to inject the new instance in the right place in the tree.

It works well for the OneLevel scope, and it will also work well for the 
sub-level, except that we will need to use a recursive call for each 
found children.

I will continue my experiments in the index branch, I've not yet removed 
the oneLevel and sublevel indexes...

More to come !

Emmanuel Lécharny

View raw message