On Wed, 10 Dec 2008, Linus Torvalds wrote: > > On Wed, 10 Dec 2008, Nicolas Pitre wrote: > > > On Wed, 10 Dec 2008, Linus Torvalds wrote: > > > > > But we should definitely fix this braindamage in fsck. Rather than > > > recursively walk the commits, we should add them to a commit list and just > > > walk the list iteratively. > > > > What about: > > > > http://marc.info/?l=git&m=122889563424786&w=2 > > Not very pretty. The basic notion is ok, but wouldn't it be nicer to at > least use a "struct object_array" instead? > > Let me try to cook something up. I dunno. I like this patch better. It's a bit larger. I think it's a bit more clearly separated (ie a "mark_object_reachable()" _literally_ just puts the object on a list, and the whole traversal is a whole separate phase), but I guess it's a matter of taste. It has gotten no real testing. Caveat emptor. And I didn't even bother to check that it can run with less stack or that it makes any other difference. Linus --- builtin-fsck.c | 38 +++++++++++++++++++++++++++++++------- 1 files changed, 31 insertions(+), 7 deletions(-) diff --git a/builtin-fsck.c b/builtin-fsck.c index afded5e..297b2c4 100644 --- a/builtin-fsck.c +++ b/builtin-fsck.c @@ -64,11 +64,11 @@ static int fsck_error_func(struct object *obj, int type, const char *err, ...) return (type == FSCK_WARN) ? 0 : 1; } +static struct object_array pending; + static int mark_object(struct object *obj, int type, void *data) { - struct tree *tree = NULL; struct object *parent = data; - int result; if (!obj) { printf("broken link from %7s %s\n", @@ -96,6 +96,20 @@ static int mark_object(struct object *obj, int type, void *data) return 1; } + add_object_array(obj, (void *) parent, &pending); + return 0; +} + +static void mark_object_reachable(struct object *obj) +{ + mark_object(obj, OBJ_ANY, 0); +} + +static int traverse_one_object(struct object *obj, struct object *parent) +{ + int result; + struct tree *tree = NULL; + if (obj->type == OBJ_TREE) { obj->parsed = 0; tree = (struct tree *)obj; @@ -107,15 +121,22 @@ static int mark_object(struct object *obj, int type, void *data) free(tree->buffer); tree->buffer = NULL; } - if (result < 0) - result = 1; - return result; } -static void mark_object_reachable(struct object *obj) +static int traverse_reachable(void) { - mark_object(obj, OBJ_ANY, 0); + int result = 0; + while (pending.nr) { + struct object_array_entry *entry; + struct object *obj, *parent; + + entry = pending.objects + --pending.nr; + obj = entry->item; + parent = (struct object *) entry->name; + result |= traverse_one_object(obj, parent); + } + return !!result; } static int mark_used(struct object *obj, int type, void *data) @@ -237,6 +258,9 @@ static void check_connectivity(void) { int i, max; + /* Traverse the pending reachable objects */ + traverse_reachable(); + /* Look up all the requirements, warn about missing objects.. */ max = get_max_object_index(); if (verbose) -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
