Am 10.05.20 um 18:37 schrieb Junio C Hamano: > René Scharfe <l.s.r@xxxxxx> 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. 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é
