[389-devel] MemberOf: New Algorithm reference impl in python

[William Brown]

Hi,

We have been discussing the algorithm used for memberof and how to make
it faster.

We've had a number of discussions about it, and Thierry and Ludwig both
have made some great comments, and discussions of the problem cases. For
more, see

http://www.port389.org/docs/389ds/design/memberof-scalability.html#reusin...

The main problematic case, was if you have multiple paths to a node,
then delete one of the paths, ensuring that children do not have the
memberof invalidated.

Here is the reference implementation in python, that proves the
correctness of the algorithm, and that it works even for the problematic
cases that Thierry discovered. It handles recursions, branch additions,
deletions, replaces and more.

Additionally, it shows how the fixup task will work, and how the fixup
task is actually an extension of the add/delete/replace case.

The majority of the algorithm is in update_memberof() of MoDb and
fixup_subtree() also on MoDb. 

The code is commented extensively, so I hope it explains it. This is a
patch to DS.git, and part of the memberof test suite.

I look forwards to your comments,

-- 
Sincerely,

William Brown
Software Engineer
Red Hat, Brisbane