Skip site navigation (1)Skip section navigation (2) 
Date:      Wed, 15 Feb 2006 18:09:19 +0100
From:      Ulrich Spoerlein <q@galgenberg.net>
To:        Dan Nelson <dnelson@allantgroup.com>
Cc:        hackers@freebsd.org
Subject:   Re: Naive implementation of strverscmp(3)
Message-ID:  <20060215170919.GB1123@galgenberg.net>
In-Reply-To: <20060215160524.GA70956@dan.emsphone.com>
References:  <20060214212503.GE1107@galgenberg.net> <20060215080532.GB684@turion.vk2pj.dyndns.org> <20060215150237.GA1123@galgenberg.net> <20060215160524.GA70956@dan.emsphone.com>
next in thread | previous in thread | raw e-mail | index | archive | help 

--Ycz6tD7Th1CMF4v7
Content-Type: multipart/mixed; boundary="4ZLFUWh1odzi/v6L"
Content-Disposition: inline


--4ZLFUWh1odzi/v6L
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Dan Nelson wrote:
>This looks a lot like strnatcmp, which is "natural sort" or "do what I
>mean" sort :)
>
>http://sourcefrog.net/projects/natsort/

Heh, I didn't know about that one, but since gqview uses strverscmp I=20
only google for that one.

>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's true, I didn't think of that. It's funny how a simple function=20
like comparing alphanumerical strings can cause that much trouble.

Anyway, attached is a last version, which now also functions for strings=20
starting with numbers and which I'll probably try getting committed to=20
the gqview port.

You may do with the code whatever you want. :)

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.

--4ZLFUWh1odzi/v6L
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";
  char *t1, *t2;
  int ret;
  long n1, n2;
  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;
    n1 =3D strtol(s1, &t1, 10);
    n2 =3D strtol(s2, &t2, 10);
   =20
    if (n1 < n2)
      return -1;
    else if (n1 > n2)
      return 1;

    /* One number is "shorter", e.g., "07" vs "007" */
    if (t1-s1 < t2-s2)
      return 1;
    else if (t1-s1 > t2-s2)
      return -1;

    /* Numbers are equal or not present, try with next ones. */
    s1 =3D t1;
    s2 =3D t2;
    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 10;

  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("a01b2");
  array[5] =3D strdup("a1b1");
  array[6] =3D strdup("a");
  array[7] =3D strdup("1.001");
  array[8] =3D strdup("1.1");
  array[9] =3D strdup("1.01");

  /* Bubble sort */
  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;
      }
    }
  }

  for (i=3D0; i<n; ++i) {
    printf("%s\n", array[i]);
  }

  printf("%d =3D 0\n", strverscmp("a", "a"));
  printf("%d < 0\n", strverscmp("item#99", "item#100"));
  printf("%d > 0\n", strverscmp("alpha1", "alpha001"));
  printf("%d > 0\n", strverscmp("part1_f012", "part1_f01"));
  printf("%d < 0\n", strverscmp("foo.009", "foo.0"));

  return 0;
}

--4ZLFUWh1odzi/v6L--

--Ycz6tD7Th1CMF4v7
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (FreeBSD)

iD8DBQFD82A/524iJyD+6d0RAraQAKCUDQ73nYHAsNOzzRxWxHFV7pNJmwCdGd4J
zHCLxsexnK2PMzL61wt4ALQ=
=maYq
-----END PGP SIGNATURE-----

--Ycz6tD7Th1CMF4v7--

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20060215170919.GB1123>