strcmp() but with 0-9 AFTER A-Z? (C/C++)

Question

For reasons I completely disagree with but "The Powers (of Anti-Usability) That Be" continue to decree despite my objections, I have a sorting routine which does basic strcmp() compares to sort by its name. It works great; it's hard to get that one wrong. However, at the 11th hour, it's been decided that entries which begin with a number should come AFTER entries which begin with a letter, contrary to the ASCII ordering. They cite the EBCDIC standard has numbers following letters so the prior assumption isn't a universal truth, and I have no power to win this argument... but I digress.

Therein lies my problem. I've replaced all appropriate references to strcmp with a new function call nonstd_strcmp, and now need to implement the modifications to accomplish the sort change. I've used a FreeBSD source as my base: http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/libkern/strncmp.c.html

 if (n == 0)
  return (0);
 do {
  if (*s1 != *s2++)
   return (*(const unsigned char *)s1 -
    *(const unsigned char *)(s2 - 1));
  if (*s1++ == 0)
   break;
 } while (--n != 0);
 return (0);

I guess I might need to take some time away to really think about how it should be done, but I'm sure I'm not the only one who's experienced the brain-deadness of just-before-release spec changes.

Answer 1

You could use a lookup table to translate ASCII to EBCDIC when comparing characters ;-)

Answer 2

What you need to do is create an ordering table for each character. This is also the easiest way to do case-insensitive comparisons as well.

if (order_table[*s1] != order_table[*s2++])

Be aware that characters might be signed, in which case the index to your table might go negative. This code is for signed chars only:

int raw_order_table[256];
int * order_table = raw_order_table + 128;
for (int i = -128;  i < 128;  ++i)
    order_table[i] = (i >= '0' && i <= '9') ? i + 256 : toupper(i);

Answer 3

If your powers-that-be are like all the other powers-that-be that I've run into, you may want to make it an option (even if it's hidden):

Sort Order:

o Numbers after Letters

o Letters after Numbers

or even worse, they might figure out that they want Numbers to be sorted numerically (e.g. "A123" comes after "A15"), then it can be

o Numbers after Letters

o Letters after Numbers

o Smart Numbers after Letters

o Letters after Smart Numbers

This gets into diagnosing the real problem, not the symptom. I bet there's a slight chance they may change their mind at the 11th hour and 59th minute.

Answer 4

Here is what should be a pretty good implementation of the string compare similar to the one described by other posts.

static const unsigned char char_remap_table[256] = /* values */

#define char_remap(c) (char_remap_table[(unsigned char) c])

int nonstd_strcmp(const char * restrict A, const char * restrict B) {
     while (1) {
          char a = *A++;
          char b = *B++;
          int x = char_remap(a) - char_remap(b);
          if (x) {
               return x;
          }
          /* Still using null termination, so test that from the original char,
           * but if \0 maps to \0 or you want to use a different end of string
           * then you could use the remapped version, which would probably work
           * a little better b/c the compiler wouldn't have to keep the original
           * var a around. */
          if (!a) { /* You already know b == a here, so only one test is needed */
               return x;  /* x is already 0 and returning it allows the compiler to
                           * store it in the register that it would store function
                           * return values in without doing any extra moves. */
          }
     }
}

Above and beyond that you could generalize the function to take the char_remap_table as a parameter which would allow you to easily use different mappings later if you needed to.

int nonstd_strcmp(const char * restrict a, const char * restrict b, const char * restrict map);

Answer 5

While in general agreement with the above answers, I think that it is silly to do lookups for every iteration of the loop, unless you think that most comparisons will have different first characters, when you could instead do

char c1, c2;
while((c1 = *(s1++)) == (c2 = *(s2++)) && c1 != '\0');
return order_table[c1] - order_table[c2];

Also, I would recommend constructing the order_table with a static initializer, which will improve speed (no need to generate every time -- or ever) and also perhaps readability

Answer 6

In this special case with only uppercase letters (as mentioned by the OP in comments) and digits 0-9, you could also omit the order table and instead multiply both differing characters by 4 and compare the results modulo 256. The range of ASCII digits (48 to 57) will not overflow 8 bits (57 × 4 = 228), but the range of uppercase letters (65 to 90) will (65 × 4 = 260). When we compare the multiplied values modulo 256, the value for each letter will be less than that of any digit: 90×4 % 256 = 104 < 192 = 48×4

The code might look something like:

int my_strcmp (const char *s1, const char *s2) {
    for (; *s1 == *s2 && *s1; ++s1, ++s2);
    return (((*(const unsigned char *)s1) * 4) & 0xFF) - \
           (((*(const unsigned char *)s2) * 4) & 0xFF);
}

Of course, the order table solution is far more versatile in general as it allows one to define a sort order for every character—this solution is sensible only for this special case with uppercase letters vs digits. (But e.g. on microcontroller platforms, saving even the small amount of memory used by the table can be a real benefit.)