René Scharfe [off-list ref] writes:
Would a stack work? When we see a candidate non-directory, we put
it on the stack. When we see a candidate directory, we compare it
to the entry at the top of the stack using strcmp(). Equality
indicates a duplicate and we are done. If the directory name is
less then we can pop the entry from the stack and check again, as
we're past the point where a duplicate would be. Makes sense?
Perfectly and quite excited ;-) I wonder if we can do the same in
the unpack-trees side.
Am 10.05.20 um 18:37 schrieb Junio C Hamano:
René Scharfe [off-list ref] writes:
quoted
Would a stack work? When we see a candidate non-directory, we put
it on the stack. When we see a candidate directory, we compare it
to the entry at the top of the stack using strcmp(). Equality
indicates a duplicate and we are done. If the directory name is
less then we can pop the entry from the stack and check again, as
we're past the point where a duplicate would be. Makes sense?
Perfectly and quite excited ;-) I wonder if we can do the same in
the unpack-trees side.
Walking multiple trees in lockstep should be possible as well. We may
want to include a bitmap indicating which trees contain the name in the
stack entry, or any other necessary information.
And output of candidates would be delayed until the matching directory
name is either reached or found to be missing, so it can be out of
order. Sorting like in diffcore_fix_diff_index() is an option if the
order is important and the entries are collected before being used
further. Not sure if streaming in the right order could be done
efficiently.
But lets see if that scheme works in fsck first. I'll send a patch for
making testing a bit easier.
René