Module Name: src
Committed By: martin
Date: Fri Aug 23 17:21:05 UTC 2024
Modified Files:
src/usr.bin/config [netbsd-9]: defs.h files.c mkioconf.c mkmakefile.c
pack.c
Log Message:
Pull up following revision(s) (requested by riastradh in ticket #1875):
usr.bin/config/defs.h: revision 1.109
usr.bin/config/files.c: revision 1.38
usr.bin/config/mkmakefile.c: revision 1.73
usr.bin/config/pack.c: revision 1.11
usr.bin/config/mkioconf.c: revision 1.36
config(1): Make sort order deterministic.
Ensure we break ties in every case. This way, even though we use the
unstable qsort(3) library routine, the output is reproducible, no
matter what algorithm is behind qsort(3).
It would be nice if we could just use a stable sort function here,
but mergesort(3) is nonstandard, so we'd have to add it to
tools/compat, which is a big pain.
Instead, put a tie-breaking rule in every comparison function we use
with qsort, and abort() in the event of ties -- that way, we noisily
refuse to rely on unstable sort order.
While here, dispense with any question of integer overflow, and
sprinkle comments.
PR bin/58115
To generate a diff of this commit:
cvs rdiff -u -r1.104.2.2 -r1.104.2.3 src/usr.bin/config/defs.h
cvs rdiff -u -r1.36.16.1 -r1.36.16.2 src/usr.bin/config/files.c
cvs rdiff -u -r1.35 -r1.35.6.1 src/usr.bin/config/mkioconf.c
cvs rdiff -u -r1.71 -r1.71.2.1 src/usr.bin/config/mkmakefile.c
cvs rdiff -u -r1.10 -r1.10.18.1 src/usr.bin/config/pack.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.bin/config/defs.h
diff -u src/usr.bin/config/defs.h:1.104.2.2 src/usr.bin/config/defs.h:1.104.2.3
--- src/usr.bin/config/defs.h:1.104.2.2 Fri Apr 30 14:07:02 2021
+++ src/usr.bin/config/defs.h Fri Aug 23 17:21:05 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: defs.h,v 1.104.2.2 2021/04/30 14:07:02 martin Exp $ */
+/* $NetBSD: defs.h,v 1.104.2.3 2024/08/23 17:21:05 martin Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -206,6 +206,8 @@ struct attr {
/* "device class" */
const char *a_devclass; /* device class described */
struct where a_where;
+
+ size_t a_idx; /* index to break sorting ties */
};
/*
Index: src/usr.bin/config/files.c
diff -u src/usr.bin/config/files.c:1.36.16.1 src/usr.bin/config/files.c:1.36.16.2
--- src/usr.bin/config/files.c:1.36.16.1 Mon Mar 9 15:22:21 2020
+++ src/usr.bin/config/files.c Fri Aug 23 17:21:05 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: files.c,v 1.36.16.1 2020/03/09 15:22:21 martin Exp $ */
+/* $NetBSD: files.c,v 1.36.16.2 2024/08/23 17:21:05 martin Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -45,7 +45,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: files.c,v 1.36.16.1 2020/03/09 15:22:21 martin Exp $");
+__RCSID("$NetBSD: files.c,v 1.36.16.2 2024/08/23 17:21:05 martin Exp $");
#include <sys/param.h>
#include <assert.h>
@@ -281,9 +281,9 @@ cmpfiles(const void *a, const void *b)
if (sa < sb)
return -1;
else if (sa > sb)
- return 1;
+ return +1;
else
- return 0;
+ abort(); /* no ties possible */
}
/*
Index: src/usr.bin/config/mkioconf.c
diff -u src/usr.bin/config/mkioconf.c:1.35 src/usr.bin/config/mkioconf.c:1.35.6.1
--- src/usr.bin/config/mkioconf.c:1.35 Sun Nov 19 01:46:29 2017
+++ src/usr.bin/config/mkioconf.c Fri Aug 23 17:21:05 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: mkioconf.c,v 1.35 2017/11/19 01:46:29 christos Exp $ */
+/* $NetBSD: mkioconf.c,v 1.35.6.1 2024/08/23 17:21:05 martin Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -45,7 +45,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: mkioconf.c,v 1.35 2017/11/19 01:46:29 christos Exp $");
+__RCSID("$NetBSD: mkioconf.c,v 1.35.6.1 2024/08/23 17:21:05 martin Exp $");
#include <sys/param.h>
#include <err.h>
@@ -136,7 +136,12 @@ cforder(const void *a, const void *b)
n1 = (*(const struct devi * const *)a)->i_cfindex;
n2 = (*(const struct devi * const *)b)->i_cfindex;
- return (n1 - n2);
+ if (n1 < n2)
+ return -1;
+ else if (n1 > n2)
+ return +1;
+ else
+ abort(); /* no ties possible */
}
static void
Index: src/usr.bin/config/mkmakefile.c
diff -u src/usr.bin/config/mkmakefile.c:1.71 src/usr.bin/config/mkmakefile.c:1.71.2.1
--- src/usr.bin/config/mkmakefile.c:1.71 Mon Aug 27 05:35:00 2018
+++ src/usr.bin/config/mkmakefile.c Fri Aug 23 17:21:05 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: mkmakefile.c,v 1.71 2018/08/27 05:35:00 riastradh Exp $ */
+/* $NetBSD: mkmakefile.c,v 1.71.2.1 2024/08/23 17:21:05 martin Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -45,7 +45,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: mkmakefile.c,v 1.71 2018/08/27 05:35:00 riastradh Exp $");
+__RCSID("$NetBSD: mkmakefile.c,v 1.71.2.1 2024/08/23 17:21:05 martin Exp $");
#include <sys/param.h>
#include <ctype.h>
@@ -396,6 +396,7 @@ emitallkobjscb(const char *name, void *v
return 0;
if (TAILQ_EMPTY(&a->a_files))
return 0;
+ a->a_idx = attridx;
attrbuf[attridx++] = a;
/* XXX nattrs tracking is not exact yet */
if (attridx == nattrs) {
@@ -430,7 +431,21 @@ attrcmp(const void *l, const void *r)
{
const struct attr * const *a = l, * const *b = r;
const int wa = (*a)->a_weight, wb = (*b)->a_weight;
- return (wa > wb) ? -1 : (wa < wb) ? 1 : 0;
+
+ /*
+ * Higher-weight first; then, among equal weights, earlier
+ * index first.
+ */
+ if (wa > wb)
+ return -1;
+ else if (wa < wb)
+ return +1;
+ else if ((*a)->a_idx < (*b)->a_idx)
+ return -1;
+ else if ((*a)->a_idx > (*b)->a_idx)
+ return +1;
+ else
+ abort(); /* no ties possible */
}
static void
Index: src/usr.bin/config/pack.c
diff -u src/usr.bin/config/pack.c:1.10 src/usr.bin/config/pack.c:1.10.18.1
--- src/usr.bin/config/pack.c:1.10 Sat Sep 12 19:11:13 2015
+++ src/usr.bin/config/pack.c Fri Aug 23 17:21:05 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: pack.c,v 1.10 2015/09/12 19:11:13 joerg Exp $ */
+/* $NetBSD: pack.c,v 1.10.18.1 2024/08/23 17:21:05 martin Exp $ */
/*
* Copyright (c) 1992, 1993
@@ -45,7 +45,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: pack.c,v 1.10 2015/09/12 19:11:13 joerg Exp $");
+__RCSID("$NetBSD: pack.c,v 1.10.18.1 2024/08/23 17:21:05 martin Exp $");
#include <sys/param.h>
#include <stdlib.h>
@@ -319,21 +319,38 @@ addlocs(const char **locs, int len)
/*
* Comparison function for qsort-by-locator-length, longest first.
- * We rashly assume that subtraction of these lengths does not overflow.
+ *
+ * In the event of equality, break ties by i_cfindex, which should be
+ * unique, obviating the need for a stable sort.
*/
static int
loclencmp(const void *a, const void *b)
{
+ const struct devi *const *d1p = a, *d1 = *d1p;
+ const struct devi *const *d2p = b, *d2 = *d2p;
const struct pspec *p1, *p2;
int l1, l2;
- p1 = (*(const struct devi * const *)a)->i_pspec;
+ p1 = d1->i_pspec;
l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0;
- p2 = (*(const struct devi * const *)b)->i_pspec;
+ p2 = d2->i_pspec;
l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0;
- return (l2 - l1);
+ /*
+ * Longer locators first; among equal locator lengths, earliest
+ * index first.
+ */
+ if (l2 < l1)
+ return -1;
+ else if (l2 > l1)
+ return +1;
+ else if (d2->i_cfindex > d1->i_cfindex)
+ return -1;
+ else if (d2->i_cfindex < d1->i_cfindex)
+ return +1;
+ else
+ abort(); /* no ties possible */
}
static void
