[MERGE/RFC] CHKMap._check_remap()

[John Arbash Meinel]

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

The attached patch is targeted to the split-inventory work.

The important bit is adding CHKMap._check_remap() which does some work
to see if child entries can be packed into a single page. This is
important to ensure canonical form even when we only create a new CHKMap
via a delta.

I also found a small bug in plain map() when a split is triggered and
one of the keys is identical to the common prefix. There is a test for
it, and we just add '\0' to the end of that key's prefix in serialized form.

I'm approx 90% confident that this is enough to ensure canonical form.
At the end of the conversion I did:

python -c "import bzrlib.branch
b = bzrlib.branch.Branch.open('.')
b.lock_write()
b.repository.start_write_group()
rt = b.repository.revision_tree(b.last_revision())
i = rt.inventory.id_to_entry
print i.key()
chk = bzrlib.chk_map.CHKMap(b.repository.chk_bytes, None)
chk._root_node.set_maximum_size(4096)
for k, v in i.iteritems():
  chk.map(k,v)
print chk._save()
b.repository.abort_write_group()
b.unlock()
"

And it comes out with the same final sha1 sum. So after 21k revisions
that add/remove/rename/etc, we still have canonical form.
('sha1:67a41796266642d4714b40d9708f61af70d003af',)
('sha1:67a41796266642d4714b40d9708f61af70d003af',)

John
=:->


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkk19kgACgkQJdeBCYSNAAOhcwCfTyNEOUruYJ+9CNA7yljo1ZT3
tb0An1HAJI7foSFkuFnCFkXhjcGF2Mr9
=Vnnr
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: chk_map_stability.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20081202/145a1cbb/attachment-0001.diff