Date: Fri, 17 Feb 2006 14:54:55 +0100 From: Ulrich Spoerlein <q@galgenberg.net> To: Jilles Tjoelker <jilles@stack.nl> Cc: hackers@freebsd.org, Dan Nelson <dnelson@allantgroup.com> Subject: Re: Naive implementation of strverscmp(3) Message-ID: <20060217135455.GB1136@galgenberg.net> In-Reply-To: <20060215182730.GB20355@stack.nl> References: <20060214212503.GE1107@galgenberg.net> <20060215080532.GB684@turion.vk2pj.dyndns.org> <20060215150237.GA1123@galgenberg.net> <20060215160524.GA70956@dan.emsphone.com> <20060215182730.GB20355@stack.nl>
next in thread | previous in thread | raw e-mail | index | archive | help
--v9Ux+11Zm5mwPlX6
Content-Type: multipart/mixed; boundary="a8Wt8u1KmwUX3Y2C"
Content-Disposition: inline
--a8Wt8u1KmwUX3Y2C
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Jilles Tjoelker wrote:
>On Wed, Feb 15, 2006 at 10:05:24AM -0600, Dan Nelson wrote:
> > Your function is simpler than the C implementation on that site, but
> > falls over when a run of numbers exceeds 2^31 (raise it to 2^64 if you
> > use strtoull, but that's as high as you can yet).
>
>That problem can be avoided fairly easily. First skip the leading zeroes
>on both sides, then strspn for digits; the longest run of digits is
>greater, otherwise strncmp it.
Yes, the trouble begins, when you really want to be compatible with the=20
GNU version.
Attached is an new, ugly version of strverscmp(3) that behaves exactly=20
as the glibc version (at least for a limit amount of testing).
Ulrich Spoerlein
--=20
PGP Key ID: 20FEE9DD Encrypted mail welcome!
Fingerprint: AEC9 AF5E 01AC 4EE1 8F70 6CBD E76E 2227 20FE E9DD
Which is worse: ignorance or apathy?
Don't know. Don't care.
--a8Wt8u1KmwUX3Y2C
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="strverscmp.c"
Content-Transfer-Encoding: quoted-printable
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#ifdef __FreeBSD__
int
strverscmp(const char *s1, const char *s2);
int
strverscmp(const char *s1, const char *s2)
{
static const char *digits =3D "0123456789";
int ret, lz1, lz2;
size_t p1, p2;
p1 =3D strcspn(s1, digits);
p2 =3D strcspn(s2, digits);
while (p1 =3D=3D p2 && s1[p1] !=3D '\0' && s2[p2] !=3D '\0') {
/* Different prefix */
if ((ret =3D strncmp(s1, s2, p1)) !=3D 0)
return ret;
s1 +=3D p1;
s2 +=3D p2;
lz1 =3D lz2 =3D 0;
if (*s1 =3D=3D '0')
lz1 =3D 1;
if (*s2 =3D=3D '0')
lz2 =3D 1;
=20
if (lz1 > lz2)
return -1;
else if (lz1 < lz2)
return 1;
else if (lz1 =3D=3D 1) {
/*
* If the common prefix for s1 and s2 consists only of zeros, then the
* "longer" number has to compare less. Otherwise the comparison needs
* to be numerical (just fallthrough). See
* http://refspecs.freestandards.org/LSB_2.0.1/LSB-generic/
* LSB-generic/baselib-strverscmp.html
*/
while (*s1 =3D=3D '0' && *s2 =3D=3D '0') {
++s1;
++s2;
}
p1 =3D strspn(s1, digits);
p2 =3D strspn(s2, digits);
/* Catch empty strings */
if (p1 =3D=3D 0 && p2 > 0)
return 1;
else if (p2 =3D=3D 0 && p1 > 0)
return -1;
/* Prefixes are not same */
if (*s1 !=3D *s2 && *s1 !=3D '0' && *s2 !=3D '0') {
if (p1 < p2)
return 1;
else if (p1 > p2)
return -1;
} else {
if (p1 < p2)
ret =3D strncmp(s1, s2, p1);
else if (p1 > p2)
ret =3D strncmp(s1, s2, p2);
if (ret !=3D 0)
return ret;
}
}
=20
p1 =3D strspn(s1, digits);
p2 =3D strspn(s2, digits);
=20
if (p1 < p2)
return -1;
else if (p1 > p2)
return 1;
else if ((ret =3D strncmp(s1, s2, p1)) !=3D 0)
return ret;
/* Numbers are equal or not present, try with next ones. */
s1 +=3D p1;
s2 +=3D p2;
p1 =3D strcspn(s1, digits);
p2 =3D strcspn(s2, digits);
}
=20
return strcmp(s1, s2);
}
#endif
int
main(int argc, char **argv)
{
char **array, *temp;
int i, j, n =3D 18;
array =3D (char **) calloc(n, sizeof(char *));
array[0] =3D strdup("10.jpg");
array[1] =3D strdup("2.jpg");
array[2] =3D strdup("1.jpg");
array[3] =3D strdup("09.jpg");
array[4] =3D strdup("1.012");
array[5] =3D strdup("0010.jpg");
array[6] =3D strdup("1.002");
array[7] =3D strdup("1.01");
array[8] =3D strdup("1.10");
array[9] =3D strdup("1.01000");
array[10] =3D strdup("00000009999999999999999999999999999999999999999999"=
);
array[11] =3D strdup("00000010000000000000000000000000000000000000000000"=
);
array[12] =3D strdup("9999999999999999999999999999999999999999999");
array[13] =3D strdup("10000000000000000000000000000000000000000000");
array[14] =3D strdup("1.010000");
array[15] =3D strdup("1.09");
array[17] =3D strdup("1.01020");
array[16] =3D strdup("1.0102");
/* Bubble sort */
#if 1
for (i=3D0; i<n; ++i) {
for (j=3Di; j<n; ++j) {
if (strverscmp(array[i], array[j]) > 0) {
temp =3D array[j];
array[j] =3D array[i];
array[i] =3D temp;
}
}
printf("%s\n", array[i]);
}
printf("%2d =3D 0\n", strverscmp("a", "a"));
printf("%2d > 0\n", strverscmp("alpha1", "alpha001"));
printf("%2d > 0\n", strverscmp("part1_f012", "part1_f01"));
printf("%2d < 0\n", strverscmp("item#99", "item#100"));
printf("%2d < 0\n", strverscmp("foo.009", "foo.0"));
printf("%2d < 0\n", strverscmp("0009", "09"));
#endif
printf("%2d < 0\n", strverscmp("1.002", "1.01000"));
printf("%2d < 0\n", strverscmp("1.01000", "1.0102"));
printf("%2d < 0\n", strverscmp("1.002", "1.01"));
printf("%2d < 0\n", strverscmp("1.012", "1.09"));
printf("%2d < 0\n", strverscmp("1.01", "1.012"));
return 0;
}
--a8Wt8u1KmwUX3Y2C--
--v9Ux+11Zm5mwPlX6
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (FreeBSD)
iD8DBQFD9dWv524iJyD+6d0RArHEAJ9pPWCt1uc1eaTquIQMqH5Vrl3uawCfb8gm
516Q/pYcDvwYTYEHyA5LAbQ=
=9LOD
-----END PGP SIGNATURE-----
--v9Ux+11Zm5mwPlX6--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20060217135455.GB1136>