> I will do some effort on testing performance of various approaches, and then code up one (or possibly more) of them.

Start with the simple, frequently occurring cases first.

> Is this a feature that could be accepted into gperf?

Yes, because the techniques to solve it are similar to the in_word_set use-case.

> Would it be a requirement that both prefix-matching and membership-testing functions could be generated simultaneously?

I don't think so. It seems rare that you would need both. To me, this means just add a command-line option which causes a prefix-test to be generated instead of the membership-test.

> If so, which approach do you think would be best

I haven't understood your subhashes based algorithm so far. But I would start to think along these lines:

1. The principle of gperf is to have a single memcmp or strncmp comparison. The entire hash code business before it serves only the purpose of constraining the possible matches as quickly as possible.

2. So, before you define a 'hash' function, start by designing how the in_prefix_set (or better: find_prefix) function would look like.

Suppose the prefixes to look for are "From:", "To:", "Subject:", and I want some additional info to be returned. What would the function look like?

struct foo { const char *name; unsigned int info; };
struct foo table[] = {
  { "From:", X_FROM },
  { "To:", X_TO },
  { "Subject:", X_SUBJECT }
};

I would write it like this:

size_t lengthtable[] = { 5, 2, 8 };

unsigned int asso_values[] = {
  'F' -> 0,
  'T' -> 1,
  'S' -> 2,
  other -> 3
};

struct foo *find_prefix (const char *str, size_t len)
{
  if (len >= 1)
    {
      unsigned int a = asso_values[(unsigned char)str[0]];
      if (a < 3)
        {
          if (len >= lengthtable[a]
              && memcmp (table[a].name, str, lengthtable[a]) == 0)
            return &table[a];
        }
    }
  return NULL;
}

Now, see how to accommodate the more complicated cases:
  - the case where more than 1 character position is needed to disambiguate,
  - the case where the maximum character position is larger than the minimum prefix length,
  - the case where some prefixes overlap (e.g. "Foo" and "Foobar").

Hi! I'd like to propose adding a new feature to gperf: generating a function which uses precomputed perfect hashes for testing if a string is prefixed by any of a list of fixed strings.

This is very similar to what gperf already does, and writing a different utility to do this would duplicate a lot of code (making its maintenance and the necessary tracking of gperf changes tedious), so I think it makes sense to augment gperf.

I've been working on several different approaches to this problem, and I'd like input from the maintainer(s) before I put more effort into this. Feedback from the community would also be welcome, of course.

It is true that gperf as-is could be used to perform this
function. For example:

const char *
in_prefix_set(const char *string, unsigned int len) {
    const char *result = NULL;
    const unsigned int pfx_lens[] = { 15, 14, 13, 12, 10, 7 };
    unsigned int idx = 0;

    do {
        if (pfx_lens[idx] <= len) {
            result = in_word_set(string, pfx_lens[idx]);
            if (result != NULL)
                break;
        }
    } while (pfx_lens[++idx] > 0);

    return result;
}

But this approach requires additional computation on the keyword list to produce pfx_lens[], complexity in duplicating the return type of in_word_set(), and is slower (potentially much slower) than it could be if gperf used its knowledge of how in_word_set() and (especially) its hash function is constructed.

I can see 3 possible approaches to adding this feature to gperf.

1) Simply generate the above function inside gperf, and live with the additional calls to in_word_set(),

2) Modify gperf to produce a hash function that generates an array of all possible hashes of the input string, then compare the input string to the wordlist[] based on these hashes,

3) Modify gperf to produce a trie and have the prefix lookup function use perfect hashes to lookup substrings along the edges of the trie.

Approach 1 is obviously very simple and straightforward, totally backwards compatible, as absolutely no existing API or even function in the generated code is modified in any way. It is the worst performer of the 3, however.

My mock-up of what approach 2 might look like is (indented oddly to reduce vertical length):

#define SUBHASH_COUNT 4
static unsigned int
hash (register const char *str, register size_t len, register unsigned int subhashes[SUBHASH_COUNT]) {
      static unsigned char asso_values[] = {
          /* list of computed values, exactly as now */
      };
      register unsigned int idx = 0;
      register unsigned int max = 0;

      switch (len) {
      default:
          subhashes[3] = asso_values[(unsigned char)str[9]]; max++;
          /*FALLTHROUGH*/
      case 9: case 8: case 7: case 6:
          subhashes[2] = asso_values[(unsigned char)str[5]]; max++;
          /*FALLTHROUGH*/
      case 5:
          subhashes[1] = asso_values[(unsigned char)str[4]+1]; max++;
          /*FALLTHROUGH*/
      case 4: case 3: case 2:
          subhashes[0] = asso_values[(unsigned char)str[1]];
          break;
      }
      while (subhashes[idx] <= MAX_HASH_VALUE && idx++ < max)
          subhashes[idx] += subhashes[idx - 1];
      return idx;
}

static unsigned char lengthtable[] = {
    /* list of lengths, exactly as now */
};
static const char * wordlist[] = {
    /* list of keywords, exactly as now */
};

const char *
in_prefix_set (register const char *str, register size_t len) {
    if (len >= MIN_WORD_LENGTH) {
        unsigned int subhashes[SUBHASH_COUNT];
        register unsigned int idx = hash (str, len, subhashes);
        while (idx > 0) {
            register unsigned int key = subhashes[--idx];
            register const char *s = wordlist[key];
            if (*str == *s && !memcmp (str + 1, s + 1, lengthtable[key] - 1))
                return s;
        }
    }
    return 0;

}

This mock-up assumes mandating the -l and -G options if the user wants to generate in_prefix_set() code. The first option (-l) does seem to be necessary for in_prefix_set(), as I can't see any way of using the available set of string functions in UNIX to do the necessary sort of match. If strncmp() returned the offset where it failed, for instance, then this could be done. The second option (-G) is not strictly necessary, but if it was wanted to simultaneously support in_word_set() and in_prefix_set() then either the wordlist[] needs to be global, or some sort of internal helper function that owns the list would need to be emitted, so that both "external" functions could access it. There would also be some additional changes needed for  his support, since hash() above does not give enough information to compute the result for in_word_set().

This approach changes the hash() function API. As this API is
explicitly documented, implementing this approach might break things, and so a new major release number would likely be required.

My mock-up of what approach 3 might look like is (again, indented oddly to reduce vertical length):

const char *
in_prefix_set (register const char *str, register size_t len) {
    static const char tbl[] = {
        -8,  -5, -10, -12,  -7,   7,   3,  -8,   0,  -7,  -1,
         2,   1,  -9,   2,   5, -11,  -5, -12,   5, -13,   6,
         1,   3, -14,   4,
    };
    size_t l = 3;
    unsigned idx = 0;
    const char *bestmatch = NULL;
    struct components *cand;

    do {
        if ((len < l) || ((cand = in_word_set(str, l)) == NULL)) break;
        do {
            if (-tbl[idx++] == cand->lineno) {
                if (tbl[idx] >= 0) bestmatch = wordlist[tbl[idx]];
                break;
            }
        } while (tbl[++idx] < 0);
        if (tbl[idx] >= 0)
           break;
        idx -= tbl[idx]; str += l; len -= l; l = tbl[idx++];
        if (tbl[idx] >= 0)
            bestmatch = wordlist[tbl[idx++]];
    } while (1);

    return bestmatch;
}

This code is a hand-generated proof-of-concept, more than anything. It could be optimized further, and an ugly convention or two could definitely be removed, if you think this is worth pursuing.

This code might be a little confusing, but it's just to give you an idea of what the trie itself might look like (the contents of tbl[] and the initial value of l), and the general shape of the code for traversing it using the existing in_word_set() function assuming that the wordlist[] contains not only the entire  user-supplied set of data but also an entry for each string fragment in the edges of the trie. If it was wanted to support exposing the existing in_word_set() function at the same time as in_prefix_set(), that would be totally doable, but implementation details regarding the scope of wordlist[] would need to be decided upon, just as in the second approach.

The code for implementing approach 3 would likely be much more complex than approach 2, but I suspect that approach 3 would perform significantly better. Again, if you approve the general idea then I would move forward with doing performance tests.

So, my questions are:
1) Is this a feature that could be accepted into gperf?
2) If so, which approach do you think would be best (either one of the above or something else entirely)?
3) Would it be a requirement that both prefix-matching and membership-testing functions could be generated simultaneously?