[MERGE] walkdirs sort order

[John Arbash Meinel]

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

Robert Collins wrote:
> This patch adds a sort key, and compare operator for paths that will
> result in the same sort order that iter_entries_by_dirs and walkdirs
> use.
> 
> The interesting thing to note here is that if we have the number of '/'
> in a path prefixed to it, a normal bisect call can find a path in the
> planned dirstate output trivially.
> 
> We might want to cache that value in the dirstate: i.e.
> instead of 
> ====
> 
> ====
> for an empty path, use
> ====
> 0 
> ====
> 
> and instead of 
> ====
> /foo/bar
> ====
> use
> ====
> 2 /foo/bar
> ====
> 
> Dunno if this is cheaper than just counting the '/' at parse time.
> 
> Rob
> 

+1 from me. I would guess that it is cheaper to cache the value, but I
couldn't give you a guarantee of it. I suppose if you were bisecting you
still need to do some searching. ie You jump to the middle, seek until
you get to a '\n', and then seek until you read in the path. If you have
to read the path, it probably isn't too hard to just count as you go.
However, you could fast-path if you had the number, and only compare the
value, and if == then you would read the path, otherwise you only need
to read the first character. Could be a lot faster.

John
=:->

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

iD4DBQFEksScJdeBCYSNAAMRAoLoAJ9Xx4S5iX5Ch1GZ4kfIXUxdFm4qmgCYhpUI
vTyQUy421iKLlmNQvCaopw==
=Zgpf
-----END PGP SIGNATURE-----