--Signature=_Wed__1_Jun_2005_17_38_56_+0300_HXerwiyz59k62nM1
Content-Type: text/plain; charset=US-ASCII
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, 31 May 2005 16:40:53 -0700
"Simon J. Gerraty" <sjg@crufty.net> wrote:

> Looks good.
>=20
> Can you add test cases in say unit-tests/order
> (you'll need to add order to SUBFILES in unit-tests/Makefile)

OK.

After some valuable input from Simon J. Gerraty, Greg Troxel, and Alan
Barret I would like to publish my new patch (see below). Major changes
are:

  - Randomization (:Ox) has been completely rewritten and now it
    requires much less memory and is O(n).
  - Fixed bug when parsing ':O<unknown>' option.
  - The ':Or' option was removed as duplicate of ':[-1..1]'; the
    alphabetical reverse ordering can be done with ':O:[-1..1]'.
  - Generally improve man page (cleanup, add example).
  - Created a regression test - unit-tests/modorder (I haven't change
    test.exp because my output of make is too differ to it. Is it
    normally?)

Any comments, please?

--
Mishka.


Index: main.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /usr/home/mishka/NetBSD-CVS/src/usr.bin/make/main.c,v
retrieving revision 1.106
diff -u -r1.106 main.c
--- main.c	16 Feb 2005 15:11:52 -0000	1.106
+++ main.c	1 Jun 2005 14:30:57 -0000
@@ -628,6 +628,14 @@
 					/* avoid faults on read-only strings */
 	static char defsyspath[] =3D _PATH_DEFSYSPATH;
 	char found_path[MAXPATHLEN + 1];	/* for searching for sys.mk */
+	struct timeval rightnow;		/* to initialize random seed */
+
+	/*
+	 * Set the seed to produce a different random sequences
+	 * on each program execution.
+	 */
+	gettimeofday(&rightnow, NULL);
+	srandom(rightnow.tv_sec + rightnow.tv_usec);
 =09
 	if ((progname =3D strrchr(argv[0], '/')) !=3D NULL)
 		progname++;
Index: make.1
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /usr/home/mishka/NetBSD-CVS/src/usr.bin/make/make.1,v
retrieving revision 1.107
diff -u -r1.107 make.1
--- make.1	8 May 2005 00:38:47 -0000	1.107
+++ make.1	1 Jun 2005 14:30:57 -0000
@@ -663,7 +663,35 @@
 but selects all words which do not match
 .Ar pattern .
 .It Cm \&:O
-Order every word in variable alphabetically.
+Order every word in variable alphabetically. To sort words in
+reverse order use
+.Ql Cm \&:O:[-1..1]
+combination of modifiers.
+.It Cm \&:Ox
+Randomize words in variable. The results will be different each
+time you are referring to the modified variable; use the assignment
+with expansion
+.Pq Ql Cm \&:=3D
+to prevent such behaviour. For example,
+.Bd -literal -offset indent
+LIST=3D			uno due tre quattro
+RANDOM_LIST=3D		${LIST:Ox}
+STATIC_RANDOM_LIST:=3D	${LIST:Ox}
+
+all:
+	@echo "${RANDOM_LIST}"
+	@echo "${RANDOM_LIST}"
+	@echo "${STATIC_RANDOM_LIST}"
+	@echo "${STATIC_RANDOM_LIST}"
+
+.Ed
+may produce the output similar to:
+.Bd -literal -offset indent
+quattro due tre uno
+tre due quattro uno
+due uno quattro tre
+due uno quattro tre
+.Ed
 .It Cm \&:Q
 Quotes every shell meta-character in the variable, so that it can be passed
 safely through recursive invocations of
Index: var.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /usr/home/mishka/NetBSD-CVS/src/usr.bin/make/var.c,v
retrieving revision 1.92
diff -u -r1.92 var.c
--- var.c	16 Feb 2005 15:11:53 -0000	1.92
+++ var.c	1 Jun 2005 14:30:58 -0000
@@ -286,7 +286,7 @@
     const char *,
     Boolean (*)(GNode *, Var_Parse_State *, char *, Boolean, Buffer, Clien=
tData),
     ClientData);
-static char *VarSort(const char *);
+static char *VarOrder(const char *, const char);
 static char *VarUniq(const char *);
 static int VarWordCompare(const void *, const void *);
 static void VarPrintVar(ClientData);
@@ -1542,14 +1542,15 @@
=20
 /*-
  *-----------------------------------------------------------------------
- * VarSort --
- *	Sort the words in the string.
+ * VarOrder --
+ *	Order the words in the string.
  *
  * Input:
- *	str		String whose words should be sorted
+ *	str		String whose words should be sorted.
+ *	otype		How to order: s - sort, x - random.
  *
  * Results:
- *	A string containing the words sorted
+ *	A string containing the words ordered.
  *
  * Side Effects:
  *	None.
@@ -1557,7 +1558,7 @@
  *-----------------------------------------------------------------------
  */
 static char *
-VarSort(const char *str)
+VarOrder(const char *str, const char otype)
 {
     Buffer  	  buf;	    	    /* Buffer for the new string */
     char **av;			    /* word list [first word does not count] */
@@ -1569,7 +1570,31 @@
     av =3D brk_string(str, &ac, FALSE, &as);
=20
     if (ac > 0)
-	qsort(av, ac, sizeof(char *), VarWordCompare);
+	switch (otype) {
+	case 's':	/* sort alphabetically */
+	    qsort(av, ac, sizeof(char *), VarWordCompare);
+	    break;
+	case 'x':	/* randomize */
+	{
+	    int rndidx;
+	    char *t;
+
+	    /*
+	     * We will use [ac..2] range for mod factors. This will produce
+	     * random numbers in [(ac-1)..0] interval, and minimal
+	     * reasonable value for mod factor is 2 (the mod 1 will produce
+	     * 0 with probability 1).
+	     */
+	    for (i =3D ac-1; i > 0; i--) {
+		rndidx =3D random() % (i + 1);
+		if (i !=3D rndidx) {
+		    t =3D av[i];
+		    av[i] =3D av[rndidx];
+		    av[rndidx] =3D t;
+		}
+	    }
+	}
+	} /* end of switch */
=20
     for (i =3D 0; i < ac; i++) {
 	Buf_AddBytes(buf, strlen(av[i]), (Byte *) av[i]);
@@ -2149,7 +2174,8 @@
      *  	  	    	each word
      *  	  :R	    	Substitute the root of each word
      *  	  	    	(pathname minus the suffix).
-     *		  :O		("Order") Sort words in variable.
+     *		  :O		("Order") Alphabeticaly sort words in variable.
+     *		  :Ox		("intermiX") Randomize words in variable.
      *		  :u		("uniq") Remove adjacent duplicate words.
      *		  :tu		Converts the variable contents to uppercase.
      *		  :tl		Converts the variable contents to lowercase.
@@ -3007,13 +3033,24 @@
 		    }
 		    /*FALLTHRU*/
 		case 'O':
+		{
+		    char otype;
+
+		    cp =3D tstr + 1;	/* skip to the rest in any case */
 		    if (tstr[1] =3D=3D endc || tstr[1] =3D=3D ':') {
-			newStr =3D VarSort(nstr);
-			cp =3D tstr + 1;
+			otype =3D 's';
 			termc =3D *cp;
-			break;
+		    } else if ( (tstr[1] =3D=3D 'x') &&
+		    		(tstr[2] =3D=3D endc || tstr[2] =3D=3D ':') ) {
+			otype =3D tstr[1];
+			cp =3D tstr + 2;
+			termc =3D *cp;
+		    } else {
+			goto bad_modifier;
 		    }
-		    /*FALLTHRU*/
+		    newStr =3D VarOrder(nstr, otype);
+		    break;
+		}   /*FALLTHRU*/
 		case 'u':
 		    if (tstr[1] =3D=3D endc || tstr[1] =3D=3D ':') {
 			newStr =3D VarUniq(nstr);
Index: unit-tests/Makefile
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /usr/home/mishka/NetBSD-CVS/src/usr.bin/make/unit-tests/Makefile,v
retrieving revision 1.14
diff -u -r1.14 Makefile
--- unit-tests/Makefile	30 Jun 2004 03:26:26 -0000	1.14
+++ unit-tests/Makefile	1 Jun 2005 14:30:58 -0000
@@ -21,6 +21,7 @@
 SUBFILES=3D \
 	cond1 \
 	modmatch \
+	modorder \
 	modts \
 	modword \
 	posix \
Index: unit-tests/modorder
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: unit-tests/modorder
diff -N unit-tests/modorder
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ unit-tests/modorder	1 Jun 2005 14:30:58 -0000
@@ -0,0 +1,19 @@
+# $NetBSD$
+
+LIST=3D		one two three four five six seven eigth nine ten
+LISTX=3D		${LIST:Ox}
+LISTSX:=3D	${LIST:Ox}
+
+all:
+	@echo "LIST      =3D ${LIST}"
+	@echo "LIST:O    =3D ${LIST:O}"
+	@echo "LIST:Ox   =3D ${LIST:Ox}"
+	@echo "LIST:O:Ox =3D ${LIST:O:Ox}"
+	@echo "LISTX 1   =3D ${LISTX}"
+	@echo "LISTX 2   =3D ${LISTX}"
+	@echo "LISTX 3   =3D ${LISTX}"
+	@echo "LISTSX 1  =3D ${LISTSX}"
+	@echo "LISTSX 2  =3D ${LISTSX}"
+	@echo "LISTSX 3  =3D ${LISTSX}"
+	@echo "BADMOD 1  =3D ${LIST:OX}"
+	@echo "BADMOD 2  =3D ${LIST:OxXX}"

--Signature=_Wed__1_Jun_2005_17_38_56_+0300_HXerwiyz59k62nM1
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (NetBSD)

iD8DBQFCnciCHwrNSUJZSkURAiiZAKCqovHk0J8gRCXQ/kPcWcytjgjquwCdHqmM
h1c7zydZ/WrEsEe4PMR2nU4=
=2gVC
-----END PGP SIGNATURE-----

--Signature=_Wed__1_Jun_2005_17_38_56_+0300_HXerwiyz59k62nM1--