Module Name:	basesrc
Committed By:	mycroft
Date:		Tue Jan  9 05:51:15 UTC 2001

Modified Files:
	basesrc/sbin/fsck_ffs: dir.c extern.h fsck.h pass2.c pass3.c

Log Message:
The reconnect algorithm was historically O(n^4).
Some years ago I made it O(n^2).
Someone helpfully made it O(n^4) again.
Today I'm making it O(n).
If that's not good enough, I don't know what else to do.  B-)

Technical details:
* The graph traversal in propagate() is modified to be able to start from any
  point in the tree.  To handle certain exceptional cases, it is also modified
  to work in two passes, marking the tree with a special tag and then changing
  it to DFOUND.
* The reconnect case now modifies the child/sibling pointers and calls
  propagate() to propagate the connection state starting with the reconnected
  directory.

Pray that you never encounter a file system trashed enough for this to matter.


To generate a diff of this commit:
cvs rdiff -r1.28 -r1.29 basesrc/sbin/fsck_ffs/dir.c \
    basesrc/sbin/fsck_ffs/pass2.c
cvs rdiff -r1.10 -r1.11 basesrc/sbin/fsck_ffs/extern.h \
    basesrc/sbin/fsck_ffs/pass3.c
cvs rdiff -r1.21 -r1.22 basesrc/sbin/fsck_ffs/fsck.h

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.