On Saturday 27 of September 2008 08:47:51 you wrote: > You should use the c_isalnum and c_isalpha functions in place of the > macros. They come from the c-ctype module and the "c-ctype.h" header. > And I suggest using this macro in place of ISDIGIT: > > #define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9) Hopefully final version of the patch, copyright assignment left as TODO in the source code. Patch for coretuils ls and sort should be simple, I'll send it on Monday.
Kamil
From 0a584ead92d6c17cbf6b8cb133369da1906cae43 Mon Sep 17 00:00:00 2001 From: Kamil Dudka <[EMAIL PROTECTED]> Date: Sat, 27 Sep 2008 13:14:34 +0000 Subject: [PATCH] add new module filevercmp * lib/filevercmp.h: New function filevercmp comparing version strings. * lib/filevercmp.c: Implementation of filevercmp function. * modules/filevercmp: Module metadata. * tests/test-filevercmp.c: Unit test for new module. * modules/filevercmp-tests: Unit test metadata. * MODULES.html.sh: Add filevercmp module. --- MODULES.html.sh | 1 + lib/filevercmp.c | 151 ++++++++++++++++++++++++++++++++++++++++++++++ lib/filevercmp.h | 40 ++++++++++++ modules/filevercmp | 26 ++++++++ modules/filevercmp-tests | 10 +++ tests/test-filevercmp.c | 96 +++++++++++++++++++++++++++++ 6 files changed, 324 insertions(+), 0 deletions(-) create mode 100644 lib/filevercmp.c create mode 100644 lib/filevercmp.h create mode 100644 modules/filevercmp create mode 100644 modules/filevercmp-tests create mode 100644 tests/test-filevercmp.c diff --git a/MODULES.html.sh b/MODULES.html.sh index afaf8ba..3ab5a90 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -1856,6 +1856,7 @@ func_all_modules () func_module readtokens func_module readtokens0 func_module strverscmp + func_module filevercmp func_end_table element="Support for systems lacking ISO C 99" diff --git a/lib/filevercmp.c b/lib/filevercmp.c new file mode 100644 index 0000000..8f0785b --- /dev/null +++ b/lib/filevercmp.c @@ -0,0 +1,151 @@ +/* +TODO: copyright? + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> +#include "filevercmp.h" + +#include <sys/types.h> +#include <stdlib.h> +#include <stdbool.h> +#include <string.h> +#include <c-ctype.h> +#include <limits.h> + +#define ISALNUM(c) c_isalnum ((unsigned char) (c)) +#define ISALPHA(c) c_isalpha ((unsigned char) (c)) +#define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9) + +/* + match file suffix defined as RE (\.[A-Za-z][A-Za-z0-9]*)*$ + + Scan string pointed by *str and return pointer to suffix begin or NULL if + not found. Pointer *str points to ending zero of scanned string after + return. */ +static const char * +match_suffix (const char **str) +{ + const char *match = NULL; + bool read_alpha = false; + while (**str) + { + if (read_alpha) + { + read_alpha = false; + if (!ISALPHA (**str)) + match = NULL; + } + else if ('.' == **str) + { + read_alpha = true; + if (!match) + match = *str; + } + else if (!ISALNUM (**str)) + match = NULL; + (*str)++; + } + return match; +} + +/* verrevcmp helper function */ +static inline int +order (unsigned char c) +{ + if (ISDIGIT (c)) + return 0; + else if (ISALPHA (c)) + return c; + else if (c == '~') + return -1; + else + return (int) c + UCHAR_MAX + 1; +} + +/* slightly modified ververcmp function from dpkg + S1, S2 - compared string + S1_LEN, S2_LEN - length of strings to be scanned */ +static int +verrevcmp (const char *s1, size_t s1_len, const char *s2, size_t s2_len) +{ + size_t s1_pos = 0; + size_t s2_pos = 0; + while (s1_pos < s1_len || s2_pos < s2_len) + { + int first_diff = 0; + while ((s1_pos < s1_len && !ISDIGIT (s1[s1_pos])) || (s2_pos < s2_len + && !ISDIGIT (s2[s2_pos]))) + { + int s1_c = (s1_pos == s1_len) ? 0 : order (s1[s1_pos]); + int s2_c = (s2_pos == s2_len) ? 0 : order (s2[s2_pos]); + if (s1_c != s2_c) + return s1_c - s2_c; + s1_pos++; + s2_pos++; + } + while (s1[s1_pos] == '0') + s1_pos++; + while (s2[s2_pos] == '0') + s2_pos++; + while (ISDIGIT (s1[s1_pos]) && ISDIGIT (s2[s2_pos])) + { + if (!first_diff) + first_diff = s1[s1_pos] - s2[s2_pos]; + s1_pos++; + s2_pos++; + } + if (ISDIGIT (s1[s1_pos])) + return 1; + if (ISDIGIT (s2[s2_pos])) + return -1; + if (first_diff) + return first_diff; + } + return 0; +} + +/* Compare version strings S1 and S2. + See filevercmp.h for function description. */ +int +filevercmp (const char *s1, const char *s2) +{ + const char *s1_pos = s1; + const char *s2_pos = s2; + const char *s1_suffix, *s2_suffix; + size_t s1_len, s2_len; + int result; + + /* easy comparison to see if strings are identical */ + int simple_cmp = strcmp (s1, s2); + if (simple_cmp == 0) + return 0; + + /* "cut" file suffixes */ + s1_suffix = match_suffix (&s1_pos); + s2_suffix = match_suffix (&s2_pos); + s1_len = (s1_suffix ? s1_suffix : s1_pos) - s1; + s2_len = (s2_suffix ? s2_suffix : s2_pos) - s2; + + /* restore file suffixes if strings are identical after "cut" */ + if ((s1_suffix || s2_suffix) && (s1_len == s2_len) + && 0 == strncmp (s1, s2, s1_len)) + { + s1_len = s1_pos - s1; + s2_len = s2_pos - s2; + } + + result = verrevcmp (s1, s1_len, s2, s2_len); + return result == 0 ? simple_cmp : result; +} diff --git a/lib/filevercmp.h b/lib/filevercmp.h new file mode 100644 index 0000000..2f40cdd --- /dev/null +++ b/lib/filevercmp.h @@ -0,0 +1,40 @@ +/* +TODO: copyright? + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef FILEVERCMP_H +#define FILEVERCMP_H + +/* Compare version strings: + + This function compares strings S1 and S2: + 1) By PREFIX in the same way as strcmp. + 2) Then by VERSION (most similarly to version compare of Debian's dpkg). + Leading zeros in version numbers are ignored. + 3) If both (PREFIX and VERSION) are equal, strcmp function is used for + comparison. So this function can return 0 if (and only if) strings S1 + and S2 are identical. + + It returns number >0 for S1 > S2, 0 for S1 == S2 and number <0 for S1 < S2. + + This function compares strings, in a way that if VER1 and VER2 are version + numbers and PREFIX and SUFFIX (SUFFIX defined as (\.[A-Za-z][A-Za-z0-9]*)*) + are strings then VER1 < VER2 implies filevercmp (PREFIX VER1 SUFFIX, + PREFIX VER2 SUFFIX) < 0. + + This function is intended to be a replacement for strverscmp. */ +int filevercmp (const char *s1, const char *s2); + +#endif /* FILEVERCMP_H */ diff --git a/modules/filevercmp b/modules/filevercmp new file mode 100644 index 0000000..db71442 --- /dev/null +++ b/modules/filevercmp @@ -0,0 +1,26 @@ +Description: +function comparing version strings (and file names with version) + +Files: +lib/filevercmp.h +lib/filevercmp.c + +Depends-on: +c-ctype +inline +stdbool +string + +configure.ac: + +Makefile.am: +lib_SOURCES += filevercmp.c + +Include: +"filevercmp.h" + +License: +LGPL + +Maintainer: +all diff --git a/modules/filevercmp-tests b/modules/filevercmp-tests new file mode 100644 index 0000000..165ecfe --- /dev/null +++ b/modules/filevercmp-tests @@ -0,0 +1,10 @@ +Files: +tests/test-filevercmp.c + +Depends-on: + +configure.ac: + +Makefile.am: +TESTS += test-filevercmp +check_PROGRAMS += test-filevercmp diff --git a/tests/test-filevercmp.c b/tests/test-filevercmp.c new file mode 100644 index 0000000..af5ca4a --- /dev/null +++ b/tests/test-filevercmp.c @@ -0,0 +1,96 @@ +/* Test of filevercmp() function. + Copyright (C) 2008 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +#include <config.h> + +#include "filevercmp.h" + +#include <stdio.h> +#include <stdlib.h> + +#define ASSERT(expr) \ + do \ + { \ + if (!(expr)) \ + { \ + fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \ + fflush (stderr); \ + abort (); \ + } \ + } \ + while (0) + +/* set of well sorted examples */ +static const char *const examples[] = +{ + "gcc-c++-10.fc9.tar.gz", + "gcc-c++-10.8.12-0.7rc2.fc9.tar.bz2", + "glibc-2-0.1.beta1.fc10.rpm", + "glibc-common-5-0.2.beta2.fc9.ebuild", + "glibc-common-5-0.2b.deb", + "glibc-common-11b.ebuild", + "glibc-common-11-0.6rc2.ebuild", + "libstdc++-0.5.8.11-0.7rc2.fc10.tar.gz", + "libstdc++-4a.fc8.tar.gz", + "libstdc++-4.10.4.20040204svn.rpm", + "libstdc++-devel-3.fc8.ebuild", + "libstdc++-devel-3a.fc9.tar.gz", + "libstdc++-devel-8.fc8.deb", + "libstdc++-devel-8.6.2-0.4b.fc8", + "nss_ldap-1-0.2b.fc9.tar.bz2", + "nss_ldap-1-0.6rc2.fc8.tar.gz", + "nss_ldap-1.0-0.1a.tar.gz", + "nss_ldap-10beta1.fc8.tar.gz", + "nss_ldap-10.11.8.6.20040204cvs.fc10.ebuild", + 0 +}; + +int +main (int argc, char **argv) +{ + const char *const *i; + + /* Following tests taken from test-strverscmp.c */ + ASSERT (filevercmp ("", "") == 0); + ASSERT (filevercmp ("a", "a") == 0); + ASSERT (filevercmp ("a", "b") < 0); + ASSERT (filevercmp ("b", "a") > 0); + ASSERT (filevercmp ("a0", "a") > 0); + ASSERT (filevercmp ("00", "01") < 0); + ASSERT (filevercmp ("01", "010") < 0); + ASSERT (filevercmp ("9", "10") < 0); + ASSERT (filevercmp ("0a", "0") > 0); + + /* compare each version string with each other - O(n^2) */ + for (i = examples; *i; i++) + { + const char *const *j; + for (j = examples; *j; j++) + { + int result = filevercmp (*i, *j); + if (result < 0) + ASSERT (i < j); + else if (0 < result) + ASSERT (j < i); + else + ASSERT (i == j); + } + } + + return 0; +} + -- 1.5.6.4
