[MERGE] Common dominator ancestor picker

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi all,

I've implemented an ancestor picker based on the closest common
dominator.  This speeds up find-merge-base by a factor of 10 on the bzr
source tree, and is likely to do even better as the bzr ancestry gets
bigger.

The old algorithm scaled linearly with the number of nodes in the
ancestry.  This algorithm scales linearly with the number of nodes
between each revision and their closest common dominator.  I invented it
myself, so let me know if there's anything wrong with the theory.

Not only is this algorithm faster, but it's also more correct, as it
will handle criss-cross merges better.

Monotone's is slightly fancier; they find the common merge that is a
dominator of one.  I don't think the difference will be significant, and
we can always implement it later.

Could someone give me a review?  If approved, I'll stick it in my
integration.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFD9jeS0F+nu1YWqI0RAgwgAJ4waj1aIrV7gNj9Yy3siT80ehONVACeJLN9
mRZyXPWtq5jNaZ+QVtVlNfg=
=JLU4
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominator.patch
Type: text/x-patch
Size: 6807 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060217/2115daf4/attachment.bin