strncmp_in_set(): like strncmp(), but compare characters only in a given set

Question

I want a function like strncmp() except that it only compares characters in a given character set. Given:

#define IDENT_CHARS  "ABCDEFGHIJKLMNOPQRSTUVWXYZ_" \
                     "abcdefghijklmnopqrstuvwxyz" \
                     "0123456789"

int strncmp_in_set( char const *s1, char const *s2, size_t n, char const *charset );

Then the following would all be true:

strncmp_in_set( "", "A", 0, IDENT_CHARS ) == 0
strncmp_in_set( "A", "", 0, IDENT_CHARS ) == 0
strncmp_in_set( "", "A", 1, IDENT_CHARS ) < 0
strncmp_in_set( "A", "", 1, IDENT_CHARS ) > 0

strncmp_in_set( "A", "A", 1, IDENT_CHARS ) == 0
strncmp_in_set( "A", "B", 1, IDENT_CHARS ) < 0
strncmp_in_set( "B", "A", 1, IDENT_CHARS ) > 0

strncmp_in_set( "A", "A", 9, IDENT_CHARS ) == 0
strncmp_in_set( "A", "B", 9, IDENT_CHARS ) < 0
strncmp_in_set( "B", "A", 9, IDENT_CHARS ) > 0

strncmp_in_set( "A", "AB", 2, IDENT_CHARS ) < 0
strncmp_in_set( "AB", "A", 2, IDENT_CHARS ) > 0
strncmp_in_set( "AB", "AX", 1, IDENT_CHARS ) == 0

strncmp_in_set( "-A", "A", 2, IDENT_CHARS ) == 0
strncmp_in_set( "A-", "A", 2, IDENT_CHARS ) == 0
strncmp_in_set( "-A-", "A", 3, IDENT_CHARS ) == 0

strncmp_in_set( "A", "-A", 2, IDENT_CHARS ) == 0
strncmp_in_set( "A", "A-", 1, IDENT_CHARS ) == 0
strncmp_in_set( "A", "-A-", 2, IDENT_CHARS ) == 0

strncmp_in_set( "A-", "A-B", 2, IDENT_CHARS ) == 0

strncmp_in_set( "AB", "AA", 3, IDENT_CHARS ) > 0
strncmp_in_set( "AB", "A-A", 3, IDENT_CHARS ) > 0
strncmp_in_set( "AB", "A~A", 3, IDENT_CHARS ) < 0

strncmp_in_set( "A-B", "A-BC", 3, IDENT_CHARS ) == 0

strncmp_in_set( "-e-a--st-", "east", 9, IDENT_CHARS ) == 0
strncmp_in_set( "-e-a--st-", "east-const", 9, IDENT_CHARS ) == 0
strncmp_in_set( "east-const", "-e-a--st-", 9, IDENT_CHARS ) == 0

strncmp_in_set( "non-e", "non-empty", 5, IDENT_CHARS ) == 0
strncmp_in_set( "non-empty", "non-e", 5, IDENT_CHARS ) == 0

strncmp_in_set( "no-foo", "nofoo", 6, IDENT_CHARS ) == 0

In particular, for cases that should return:

• zero (strings compare equal), the order of the arguments s1 and s2 must not matter, i.e., you must get 0 in either case.
• non-zero (strings don't compare equal), the sign of the value returned must match whatever strncmp() would return.

The second bullet is important to preserve ordering. For example, an implementation that first stripped characters not in the set from both strings then called strncmp() on those strings wouldn't work. For example, given "AB" and "A~A", stripping would yield "AB" and "AA". strncmp() on those strings would return +1, but it should return -1.

I came up with this:

int strncmp_in_set( char const *s1, char const *s2, size_t n,
                    char const *charset ) {
  assert( s1 != NULL );
  assert( s2 != NULL );
  assert( charset != NULL );

  // First, determine shorter string and its length.
  // Note: doing it this way is faster than calling strlen() on both strings.

  char const *t1, *t2;
  for ( t1 = s1, t2 = s2; *t1 != '\0' && *t2 != '\0'; ++t1, ++t2 )
    ;

  char const *shorter, *longer;
  size_t shorter_len;

  if ( *t1 == '\0' ) {
    shorter = s1;
    longer  = s2;
    shorter_len = (size_t)(t1 - s1);
  } else {
    shorter = s2;
    longer  = s1;
    shorter_len = (size_t)(t2 - s2);
  }

  // Second, see if shorter string contains any chars in set.
  // If not, just return whatever strncmp() returns.

  for ( t1 = shorter; *t1 != '\0'; ++t1 ) {
    if ( strchr( charset, *t1 ) == NULL )
      --shorter_len;
  }
  if ( shorter_len == 0 )
    return strncmp( s1, s2, n );

  // Finally, compare strings.

  size_t const orig_n = n;

  while ( n > 0 && *shorter != '\0' ) {
    if ( strchr( charset, *shorter ) == NULL ) {
      ++shorter;
      continue;
    }
    if ( strchr( charset, *longer ) != NULL && *shorter++ != *longer )
      return strncmp( s1, s2, orig_n );
    ++longer;
    --n;
  }

  return 0;
}

AFAICT, it works, but it seems verbose. Is there any way this can be simplified?

Answer 1

Review:

The problem statement is not clear to me, and the OP is not certain that the code works as intended (cf. "AFAICT"). Reviewing is, therefore, problematic.

EDIT
It turns out that the OP's posted code and problem statement were incorrect.
Below has been stripped back to remaining applicable comments.

---

Take-away:

Adding more variables does not always simplify code.

---

re: "AFAICT"

The reader has been presented with a description, a handful of cases & expected results, and some code that may-or-may-not be an expression of the OP's intent.

Suggestion: Write a "test harness" to exercise the function being developed in every way imaginable. Put in more effort than a simple copy/paste wall of function calls.

Add as many cases as you can imagine, disable (comment out) those that give correct results, and fire up the debugger to trace execution of those that do not.

PS: Using sample strings being "A", then "east", then "nofoo" does not help the reader to see what is being tested. Pick one, then stick with it in all cases (as much as possible).

---

Know your data

#define IDENT_CHARS  "ABCDEFGHIJKLMNOPQRSTUVWXYZ_" \
                     "abcdefghijklmnopqrstuvwxyz" \
                     "0123456789"
...
if ( strchr( charset, *t1 ) == NULL )

• This looks like 7bit ASCII, so let's go with that...
• The underscore is somewhat hidden and could easily be overlooked.
• My gut tells me lowercase strings will be more common than uppercase

Suggest:

#define IDENT_CHARS  "abcdefghijklmnopqrstuvwxyz" \
                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ" \
                     "0123456789_"

would (likely? usually?) find the current character with fewer iterations within each execution of strchr().

---

Given further consideration, it's now apparent that rejecting invalid characters will entail scanning all 2*26 + 11 = 63 characters to determine that a character is "filler".

Suggest (going with the 7bit ASCII assumption):

#include <ctype.h>
#define GOOD(uch) ( isalnum(uch) || (uch) == '_' )

Caveats about unsigned char would apply if the data is not 7bit ASCII.

---

What about compound "words"? "door-to-door" is one example in common use. What about "isn't", "don't" and "aren't"?

---

What is the objective of the OP's function? What is its use?
This is a function being developed for some special purpose. What, exactly?

And where does the value of the function's parameter n come from?

Answer 2

Your Set Should be a Lookup Table

Finding if a set represented as a string of length \$M\$ contains a character takes \$\mathcal{O}(M)\$ time, so the overall operation takes \$\mathcal{O}(MN)\$ time. Looking the character up in a table of _Bool[256] takes constant time, reducing the overall time to \$\mathcal{O}(N)\$.

Changing the interface also lets you use a C99-style function definition that tells the compiler about the array bounds and which pointers must not be null. it also removes the potential danger that the set argument is a zero-terminated string with no maximum length, so it is easy to make it overrun the buffer.

You can still keep the current interface as a wrapper to the more modern one, such as:

typedef struct {
    _Bool is_elem[256];
} charset;

static_assert(CHAR_BIT == 8, "");


charset cstr_to_charset(const char* set) {
    charset to_return = {.is_elem = {false}};
    unsigned char c = '\0';
    
    assert(set);
    while ((c = (unsigned char)*set) != '\0') {
        to_return.is_elem[c] = true;
        ++set;
    }

    return to_return;
}


int strnsetcmp( size_t n,
                const unsigned char s1[static n],
                const unsigned char s2[static n],
                const charset set[static 1] );


int strncmp_in_set( char const *s1,
                    char const *s2,
                    size_t n,
                    char const *set ) {
    const charset char_table = cstr_to_charset(set);
    return strnsetcmp( n,
                       (const unsigned char*)s1,
                       (const unsigned char*)s2,
                       &char_table );
}

Now you just need to write strnsetcmp. If it skips over characters not in the set, in-place, that can be made less verbose, such as:

while (!set->is_elem[*++s1])
    ;

Oh, and one other wrinkle: MSVC chokes on this C99 syntax. If you need to support it, either use clang to compile Windows programs that use the same ABI, or you’ll need a bunch of #ifdef blocks.

Eight-Bit Character Sets Are Obsolete

In 2024, a program that does text processing will be handling UTF-8, not some 8-bit codepage from last century. This implies that the algorithm should work on codepoints, and the set parameter should be represented either as something like a short sorted array of char32_t codepoints, a short sorted array of UTF-8 codepoints, or a hash table. If you go with a short sorted array, do a binary search for each codepoint in the strings being compared, rather than a linear one.

If you present an API that is supposed to work that way, clients are likely to want to use it to compare base characters in NFD-encoded strings, ignoring combining characters.

You can get away with specifying that the strings must be canonicalized before comparing them.

Tail-Recursion is Great. But ....

Like @mmusante, I like writing tail-recursive functions. However, C traditionally does not have great support for them, or even guarantee tail-call elimination.

LLVM compilers rectify this with a [[clang::musttail]] attribute in newer versions and an __attribute((musttail)) attribute in older ones. So, if your code only needs to be compatible with C23 and up, you can add the following macro:

#if __has_c_attribute(clang::musttail)
#  define MUSTTAIL [[clang::musttail]]
#else
#  define MUSTTAIL /**/
#endif

Whereas, if you need to support older compilers that support neither __has_c_attribute nor short-circuiting #if defined(__has_c_attribute) && __has_c_attribute(clang::musttail), you must use:

#if defined(__has_c_attribute)
#  if __has_c_attribute(clang::musttail)
#    define MUSTTAIL [[clang::musttail]]
#  endif
#elif defined(__has_cpp_attribute)
#  if __has_cpp_attribute(clang::musttail)
#    define MUSTTAIL [[clang::musttail]]
#  endif
#endif

#if !defined(MUSTTAIL) && (__clang__ || __INTEL_LLVM_COMPILER)
#  define MUSTTAIL __attribute__((musttail))
#endif

#if !defined(MUSTTAIL)
#  define MUSTTAIL /**/
#endif

Either of these lets you write a tail recursive call like

MUSTTAIL return strnsetcmp(n-1, s1+1, s2+1, setp);

where MUSTTAIL expands to the extension that forces tail-call optimization on compilers that support it, or is otherwise a no-op.

Answer 3

Comparing if the character is in the charset can be expensive (walking a long string of acceptable characters), simple (a table look-up) or complicated, rather than passing in a pointer to a string, consider passing in a pointer to a user provided optimized function.

// int strncmp_in_set( char const *s1, char const *s2, size_t n, char const *charset ) {
int strncmp_in_set( char const *s1, char const *s2, size_t n, int (*acceptable)(int c)) {
    ...
    // if ( strchr( charset, *shorter ) == NULL )
    if (!acceptable((unsigned char)*shorter))
    ...
}

Example call:

// strncmp_in_set( "", "A", 0, IDENT_CHARS ) == 0
strncmp_in_set( "", "A", 0, isalnum) == 0

Advanced: to also handle UTF-8 compares, acceptable could take a char * and on success, return a char * pointer to the next character - or NULL on unacceptable. Of course a few other parts of code need adjustment, yet the algorithm remains the same.

Answer 4

REVISED CODE

I decided to use the set idea since it's only 3 lines. Using two counters (i and j) makes things simpler instead of trying to not decrement n more than you should. It also eliminates the need to find the shorter string.

The test-cases were updated in the original question.

int strncmp_in_set( char const *s1, char const *s2, size_t n,
                    char const *charset ) {
  assert( s1 != NULL );
  assert( s2 != NULL );
  assert( charset != NULL );
  assert( charset[0] != '\0' );

  if ( n == 0 )
    return 0;

  bool in_set[256] = { true };          // always put '\0' in the set
  while ( *charset != 0 )
    in_set[ (unsigned char)*charset++ ] = true;

  for ( size_t i = 0, j = 0; i < n && j < n; ) {
    if ( !in_set[ (unsigned char)s1[i] ] )
      ++i;
    else if ( !in_set[ (unsigned char)s2[j] ] )
      ++j;
    else if ( s1[i] != s2[j] )
      return strncmp( s1, s2, n );
    else if ( s1[i] == '\0' )           // s2[j] == '\0' also
      break;
    else {
      ++i;
      ++j;
    }
  } // for

  return 0;
}