From d5c9b65dfd42e2487b344532e4d1bda153b840ec Mon Sep 17 00:00:00 2001 From: wlestes Date: Fri, 17 Feb 2012 22:22:59 +0000 Subject: speed up things for complex inputs; resolves #2891390 --- dfa.c | 13 ++++------ flexdef.h | 8 +++---- misc.c | 81 ++++++++++----------------------------------------------------- parse.y | 6 ++--- 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], -- cgit v1.2.1