From owner-freebsd-hackers@FreeBSD.ORG Fri Feb 17 13:55:00 2006 Return-Path: X-Original-To: hackers@freebsd.org Delivered-To: freebsd-hackers@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5295B16A420 for ; Fri, 17 Feb 2006 13:55:00 +0000 (GMT) (envelope-from q@galgenberg.net) Received: from wrzx28.rz.uni-wuerzburg.de (wrzx28.rz.uni-wuerzburg.de [132.187.3.28]) by mx1.FreeBSD.org (Postfix) with ESMTP id 5891843D46 for ; Fri, 17 Feb 2006 13:54:58 +0000 (GMT) (envelope-from q@galgenberg.net) Received: from virusscan.mail (amavis1.rz.uni-wuerzburg.de [132.187.3.48]) by wrzx28.rz.uni-wuerzburg.de (Postfix) with ESMTP id 47000146996; Fri, 17 Feb 2006 14:54:57 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by virusscan.mail (Postfix) with ESMTP id 3A917A4B; Fri, 17 Feb 2006 14:54:57 +0100 (CET) Received: from frodo.galgenberg.net (wwsx14.win-screen.uni-wuerzburg.de [132.187.253.14]) by wrzx28.rz.uni-wuerzburg.de (Postfix) with ESMTP id 038E8146996; Fri, 17 Feb 2006 14:54:57 +0100 (CET) Received: from coyote.q.local (gb-21-237.galgenberg.net [172.16.21.237]) by frodo.galgenberg.net (8.13.1/8.13.1) with ESMTP id k1HDsuHn083286; Fri, 17 Feb 2006 14:54:56 +0100 (CET) (envelope-from q@galgenberg.net) Received: from roadrunner.q.local (roadrunner.q.local [192.168.0.148]) by coyote.q.local (8.13.4/8.13.4) with ESMTP id k1HDsuub024733; Fri, 17 Feb 2006 14:54:56 +0100 (CET) (envelope-from q@galgenberg.net) Received: from roadrunner.q.local (localhost [127.0.0.1]) by roadrunner.q.local (8.13.4/8.13.4) with ESMTP id k1HDsuQJ003976; Fri, 17 Feb 2006 14:54:56 +0100 (CET) (envelope-from q@galgenberg.net) Received: (from q@localhost) by roadrunner.q.local (8.13.4/8.13.4/Submit) id k1HDstou003975; Fri, 17 Feb 2006 14:54:55 +0100 (CET) (envelope-from q@galgenberg.net) Date: Fri, 17 Feb 2006 14:54:55 +0100 From: Ulrich Spoerlein To: Jilles Tjoelker Message-ID: <20060217135455.GB1136@galgenberg.net> Mail-Followup-To: Jilles Tjoelker , Dan Nelson , hackers@freebsd.org References: <20060214212503.GE1107@galgenberg.net> <20060215080532.GB684@turion.vk2pj.dyndns.org> <20060215150237.GA1123@galgenberg.net> <20060215160524.GA70956@dan.emsphone.com> <20060215182730.GB20355@stack.nl> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="v9Ux+11Zm5mwPlX6" Content-Disposition: inline In-Reply-To: <20060215182730.GB20355@stack.nl> X-Virus-Scanned: by amavisd-new at uni-wuerzburg.de Cc: hackers@freebsd.org, Dan Nelson Subject: Re: Naive implementation of strverscmp(3) X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 17 Feb 2006 13:55:00 -0000 --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 #include #include #include #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 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--