Module Name: src Committed By: christos Date: Tue Apr 23 22:12:16 UTC 2024
Modified Files: src/usr.sbin/makefs: walk.c Log Message: makefs: Sort directory contents by name (Jan-Benedict Glaw) `makefs` inserts nodes into its internal data structures in the order as returned by `readdir()` calls. As this is unpredictable, sort entries by name before creating the target filesystem. This is done by first converting the (per-directory) linked list into a plain array, sort it, finally re-link the list. Special case for the sorting function: The "." directory entry seems to be ment to be always at the front, so always check that first. To generate a diff of this commit: cvs rdiff -u -r1.33 -r1.34 src/usr.sbin/makefs/walk.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/usr.sbin/makefs/walk.c diff -u src/usr.sbin/makefs/walk.c:1.33 src/usr.sbin/makefs/walk.c:1.34 --- src/usr.sbin/makefs/walk.c:1.33 Thu Dec 28 07:13:55 2023 +++ src/usr.sbin/makefs/walk.c Tue Apr 23 18:12:16 2024 @@ -1,4 +1,4 @@ -/* $NetBSD: walk.c,v 1.33 2023/12/28 12:13:55 tsutsui Exp $ */ +/* $NetBSD: walk.c,v 1.34 2024/04/23 22:12:16 christos Exp $ */ /* * Copyright (c) 2001 Wasabi Systems, Inc. @@ -41,7 +41,7 @@ #include <sys/cdefs.h> #if defined(__RCSID) && !defined(__lint) -__RCSID("$NetBSD: walk.c,v 1.33 2023/12/28 12:13:55 tsutsui Exp $"); +__RCSID("$NetBSD: walk.c,v 1.34 2024/04/23 22:12:16 christos Exp $"); #endif /* !__lint */ #include <sys/param.h> @@ -66,6 +66,24 @@ static fsnode *create_fsnode(const char struct stat *); static fsinode *link_check(fsinode *); +/* + * fsnode_cmp -- + * This function is used by `qsort` so sort one directory's + * entries. `.` is always first, sollowed by anything else + * as compared by `strcmp()`. + */ +static int +fsnode_cmp (const void *_left, const void *_right) +{ + const fsnode * const left = *(const fsnode * const *)_left; + const fsnode * const right = *(const fsnode * const *)_right; + + if (strcmp (left->name, ".") == 0) + return -1; + if (strcmp (right->name, ".") == 0) + return 1; + return strcmp (left->name, right->name); +} /* * walk_dir -- @@ -87,6 +105,9 @@ walk_dir(const char *root, const char *d char *name, *rp; int dot, len; + fsnode **list, **listptr; + int num = 0; + assert(root != NULL); assert(dir != NULL); @@ -241,7 +262,36 @@ walk_dir(const char *root, const char *d cur->first = first; if (closedir(dirp) == -1) err(EXIT_FAILURE, "Can't closedir `%s/%s'", root, dir); - return (first); + + /* + * Sort entries. + */ + /* Create a plain list: Count, alloc, add. */ + for (fsnode *tmp = first; tmp; tmp = tmp->next) { + num++; + if (debug & DEBUG_DUMP_FSNODES_VERBOSE) + printf ("pre sort: %s %s %s\n", root, dir, tmp->name); + } + list = listptr = ecalloc (num, sizeof (*list)); + for (fsnode *tmp = first; tmp; tmp = tmp->next) + *listptr++ = tmp; + /* Sort plain list. */ + qsort (list, num, sizeof (*list), &fsnode_cmp); + /* Rewire. */ + for (int i = 0; i < num - 1; ++i) + list[i]->next = list[i+1]; + list[num - 1]->next = NULL; + first = list[0]; + /* Check `first` to be ".". */ + assert (strcmp (first->name, ".") == 0); + /* Free. */ + free (list); + /* Dump sorted state. */ + if (debug & DEBUG_DUMP_FSNODES_VERBOSE) + for (fsnode *tmp = first; tmp; tmp = tmp->next) + printf ("post sort: %s %s %s\n", root, dir, tmp->name); + + return first; } static fsnode *