speed up things for complex inputs; resolves #2891390

4 files changed, 23 insertions, 85 deletions

diff --git a/dfa.c b/dfa.c
index 8613d75..b8b68eb 100644
--- a/dfa.c
+++ b/dfa.c
@@ -161,7 +161,7 @@ void dump_associated_rules (file, ds)
 		}
 	}
 
-	bubble (rule_set, num_associated_rules);
+	qsort (&rule_set [1], num_associated_rules, sizeof (rule_set [1]), intcmp);
 
 	fprintf (file, _(" associated rule line numbers:"));
 
@@ -835,10 +835,8 @@ int snstods (sns, numstates, accset, nacc, hashval, newds_addr)
 				if (!didsort) {
 					/* We sort the states in sns so we
 					 * can compare it to oldsns quickly.
-					 * We use bubble because there probably
-					 * aren't very many states.
 					 */
-					bubble (sns, numstates);
+					qsort (&sns [1], numstates, sizeof (sns [1]), intcmp);
 					didsort = 1;
 				}
 
@@ -873,7 +871,7 @@ int snstods (sns, numstates, accset, nacc, hashval, newds_addr)
 	 */
 
 	if (!didsort)
-		bubble (sns, numstates);
+		qsort (&sns [1], numstates, sizeof (sns [1]), intcmp);
 
 	for (i = 1; i <= numstates; ++i)
 		dss[newds][i] = sns[i];
@@ -893,11 +891,10 @@ int snstods (sns, numstates, accset, nacc, hashval, newds_addr)
 	else if (reject) {
 		/* We sort the accepting set in increasing order so the
 		 * disambiguating rule that the first rule listed is considered
-		 * match in the event of ties will work.  We use a bubble
-		 * sort since the list is probably quite small.
+		 * match in the event of ties will work.
 		 */
 
-		bubble (accset, nacc);
+		qsort (&accset [1], nacc, sizeof (accset [1]), intcmp);
 
 		dfaacc[newds].dfaacc_set =
 			allocate_integer_array (nacc + 1);
diff --git a/flexdef.h b/flexdef.h
index 7282711..572fe2a 100644
--- a/flexdef.h
+++ b/flexdef.h
@@ -849,8 +849,8 @@ extern int all_lower PROTO ((register char *));
 /* True if a string is all upper case. */
 extern int all_upper PROTO ((register char *));
 
-/* Bubble sort an integer array. */
-extern void bubble PROTO ((int[], int));
+/* Compare two integers for use by qsort. */
+extern int intcmp PROTO ((const void *, const void *));
 
 /* Check a character to make sure it's in the expected range. */
 extern void check_char PROTO ((int c));
@@ -864,8 +864,8 @@ extern char *copy_string PROTO ((register const char *));
 /* Returns a dynamically allocated copy of a (potentially) unsigned string. */
 extern Char *copy_unsigned_string PROTO ((register Char *));
 
-/* Shell sort a character array. */
-extern void cshell PROTO ((Char[], int, int));
+/* Compare two characters for use by qsort with '\0' sorting last. */
+extern int cclcmp PROTO ((const void *, const void *));
 
 /* Finish up a block of data declarations. */
 extern void dataend PROTO ((void));
diff --git a/misc.c b/misc.c
index d819c61..bf405cc 100644
--- a/misc.c
+++ b/misc.c
@@ -210,33 +210,11 @@ int all_upper (str)
 }
 
 
-/* bubble - bubble sort an integer array in increasing order
- *
- * synopsis
- *   int v[n], n;
- *   void bubble( v, n );
- *
- * description
- *   sorts the first n elements of array v and replaces them in
- *   increasing order.
- *
- * passed
- *   v - the array to be sorted
- *   n - the number of elements of 'v' to be sorted
- */
+/* intcmp - compares two integers for use by qsort. */
 
-void bubble (v, n)
-     int v[], n;
+int intcmp (const void *a, const void *b)
 {
-	register int i, j, k;
-
-	for (i = n; i > 1; --i)
-		for (j = 1; j < i; ++j)
-			if (v[j] > v[j + 1]) {	/* compare */
-				k = v[j];	/* exchange */
-				v[j] = v[j + 1];
-				v[j + 1] = k;
-			}
+  return *(const int *) a - *(const int *) b;
 }
 
 
@@ -316,52 +294,17 @@ Char   *copy_unsigned_string (str)
 }
 
 
-/* cshell - shell sort a character array in increasing order
- *
- * synopsis
- *
- *   Char v[n];
- *   int n, special_case_0;
- *   cshell( v, n, special_case_0 );
- *
- * description
- *   Does a shell sort of the first n elements of array v.
- *   If special_case_0 is true, then any element equal to 0
- *   is instead assumed to have infinite weight.
- *
- * passed
- *   v - array to be sorted
- *   n - number of elements of v to be sorted
- */
+/* cclcmp - compares two characters for use by qsort with '\0' sorting last. */
 
-void cshell (v, n, special_case_0)
-     Char v[];
-     int n, special_case_0;
+int cclcmp (const void *a, const void *b)
 {
-	int     gap, i, j, jg;
-	Char    k;
-
-	for (gap = n / 2; gap > 0; gap = gap / 2)
-		for (i = gap; i < n; ++i)
-			for (j = i - gap; j >= 0; j = j - gap) {
-				jg = j + gap;
-
-				if (special_case_0) {
-					if (v[jg] == 0)
-						break;
-
-					else if (v[j] != 0
-						 && v[j] <= v[jg])
-						break;
-				}
-
-				else if (v[j] <= v[jg])
-					break;
-
-				k = v[j];
-				v[j] = v[jg];
-				v[jg] = k;
-			}
+  if (!*(const Char *) a)
+	return 1;
+  else
+	if (!*(const Char *) b)
+	  return - 1;
+	else
+	  return *(const Char *) a - *(const Char *) b;
 }
 
 
diff --git a/parse.y b/parse.y
index 04e84d9..bbc738c 100644
--- a/parse.y
+++ b/parse.y
@@ -723,11 +723,9 @@ singleton	:  singleton '*'
 
 		|  fullccl
 			{
-				/* Sort characters for fast searching.  We
-				 * use a shell sort since this list could
-				 * be large.
+				/* Sort characters for fast searching.
 				 */
-				cshell( ccltbl + cclmap[$1], ccllen[$1], true );
+				qsort( ccltbl + cclmap[$1], ccllen[$1], sizeof (*ccltbl), cclcmp );
 
 			if ( useecs )
 				mkeccl( ccltbl + cclmap[$1], ccllen[$1],