generate a perfect hash for curl scheme matching

scheme2num.c

#include <stdio.h>
#include <curl/curl.h>

struct detail {
  const char *n;
  const char *ifdef;
};

static const struct detail scheme[] = {
  {"dict", "#ifndef CURL_DISABLE_DICT" },
  {"file", "#ifndef CURL_DISABLE_FILE" },
  {"ftp", "#ifndef CURL_DISABLE_FTP" },
  {"ftps", "#if defined(USE_SSL) && !defined(CURL_DISABLE_FTP)" },
  {"gopher", "#ifndef CURL_DISABLE_GOPHER" },
  {"gophers", "#if defined(USE_SSL) && !defined(CURL_DISABLE_GOPHER)" },
  {"http", "#ifndef CURL_DISABLE_HTTP" },
  {"https", "#if defined(USE_SSL) && !defined(CURL_DISABLE_HTTP)" },
  {"imap", "#ifndef CURL_DISABLE_IMAP" },
  {"imaps", "#if defined(USE_SSL) && !defined(CURL_DISABLE_IMAP)" },
  {"ldap", "#ifndef CURL_DISABLE_LDAP" },
  {"ldaps", "#if !defined(CURL_DISABLE_LDAP) && \\\n"
   "    !defined(CURL_DISABLE_LDAPS) && \\\n"
   "    ((defined(USE_OPENLDAP) && defined(USE_SSL)) || \\\n"
   "    (!defined(USE_OPENLDAP) && defined(HAVE_LDAP_SSL)))" },
  {"mqtt", "#ifndef CURL_DISABLE_MQTT" },
  {"pop3", "#ifndef CURL_DISABLE_POP3" },
  {"pop3s", "#if defined(USE_SSL) && !defined(CURL_DISABLE_POP3)" },
  {"rtmp", "#ifdef USE_LIBRTMP" },
  {"rtmpt", "#ifdef USE_LIBRTMP" },
  {"rtmpe", "#ifdef USE_LIBRTMP" },
  {"rtmpte", "#ifdef USE_LIBRTMP" },
  {"rtmps", "#ifdef USE_LIBRTMP" },
  {"rtmpts", "#ifdef USE_LIBRTMP" },
  {"rtsp", "#ifndef CURL_DISABLE_RTSP" },
  {"scp", "#if defined(USE_SSH) && !defined(USE_WOLFSSH)" },
  {"sftp", "#if defined(USE_SSH)" },
  {"smb", "#if !defined(CURL_DISABLE_SMB) && defined(USE_CURL_NTLM_CORE) && \\\n"
   "    (SIZEOF_CURL_OFF_T > 4)" },
  {"smbs", "#if defined(USE_SSL) && !defined(CURL_DISABLE_SMB) && \\\n"
   "    defined(USE_CURL_NTLM_CORE) && (SIZEOF_CURL_OFF_T > 4)" },
  {"smtp", "#ifndef CURL_DISABLE_SMTP" },
  {"smtps", "#if defined(USE_SSL) && !defined(CURL_DISABLE_SMTP)" },
  {"telnet", "#ifndef CURL_DISABLE_TELNET" },
  {"tftp", "#ifndef CURL_DISABLE_TFTP" },
  {"ws", "#if defined(USE_WEBSOCKETS) && !defined(CURL_DISABLE_HTTP)" },
  {"wss", "#if defined(USE_WEBSOCKETS) && \\\n"
   "    defined(USE_SSL) && !defined(CURL_DISABLE_HTTP)" },
  { NULL, NULL }
};

curl_off_t calc(const char *s)
{
  const char *so = s;
  curl_off_t c = 0;
  while(*s) {
    c <<= 5;
    c += *s;
    s++;
  }
  return c;
}

int main(void)
{
  int i;
  int try;
  curl_off_t num[100];
  unsigned int index[100];
  for(i = 0; scheme[i].n; ++i) {
    curl_off_t v = calc(scheme[i].n);
    int j;
    for(j=0; j < i; j++) {

      if(num[j] == v) {
        printf("NOPE: %u is a dupe (%s and %s)\n", v, scheme[i], scheme[j]);
        break;
      }
    }
    num[i] = v;
  }
#if 0
  for(i = 0; scheme[i]; ++i) {
    printf("%u - %s\n", num[i], scheme[i]);
  }
#endif
  /* try different remainders to find smallest possible table */
  for(try = 28; try < 199; try++) {
    int good = 1;
    for(i = 0; scheme[i].n; ++i) {
      index[i] = num[i] % try;
    }
    /* check for dupes */
    for(i = 0; scheme[i].n && good; ++i) {
      int j;
      for(j=0; j < i; j++) {
        if(index[j] == index[i]) {
          /* printf("NOPE, try %u causes dupes (%d and %d)\n", try, j, i); */
          good = 0;
          break;
        }
      }
    }
    if(good) {
      int nulls = 0;
      printf("  static const struct Curl_handler *i[%d] = {", try);

      /* generate table */
      for(i=0; i < try; i++) {
        int match = 0;
        int j;
        for(j=0; scheme[j].n; j++) {
          if(index[j] == i) {
            printf("\n");
            printf("%s\n", scheme[j].ifdef);
            printf("    &Curl_handler_%s,\n", scheme[j].n);
            printf("#else\n    NULL,\n");
            printf("#endif");
            match = 1;
            nulls = 0;
            break;
          }
        }
        if(!match) {
          if(!nulls || (nulls>10)) {
            printf("\n   ");
            nulls = 0;
          }
          printf(" NULL,", nulls);
          nulls++;
        }
      }
      printf("\n  };\n");
      break;
    }
  }
}