| #include <stdio.h> |
| #include <string.h> |
| #include <limits.h> |
| |
| static char *days[] = {"sunday", "monday", "tuesday", "wednesday", "thursday", "friday", "saturday"}; |
| |
| |
| static char * |
| num2day(int i) |
| { |
| if (i > 6) return ""; |
| return days[i]; |
| } |
| |
| #include "tdhfunc.c" |
| |
| int |
| main(void) |
| { |
| int i; |
| int hashes[7]; |
| |
| for (i = 0; i < 7; i++) |
| { |
| hashes[i] = tdhfunc(days[i]); |
| } |
| |
| for (i = 7; i < INT_MAX; i++) |
| { |
| int j; |
| int collide = 0; |
| |
| for (j = 0; j < 7; j++) |
| { |
| int k; |
| |
| int h = hashes[j] % i; |
| //printf("h(%i) = %i\n",j,h); |
| |
| for (k = 0; k < 7; k++) |
| { |
| if (j == k) continue; |
| if (h == (hashes[k] % i)) |
| { |
| //printf("collide on %i = %i\n", j, k); |
| collide = 1; |
| break; |
| } |
| } |
| if (collide) |
| break; |
| } |
| |
| if (!collide) |
| { |
| int m = 0; |
| int table[i]; |
| |
| memset(table, -1, i * sizeof(int)); |
| |
| for (m = 0; m < 7; m++) |
| { |
| table[hashes[m] % i] = m; |
| } |
| |
| printf("/* generated by %s. This makes tdhfunc() a perfect hash. */\n", __FILE__); |
| printf("typedef struct daybucket\n" |
| "{\n" |
| " int8 dow; /* the day of the week, starting at zero for Sunday */\n" |
| " uint8 daylen; /* length of the field below, cached */\n" |
| " char *day; /* the day name */\n" |
| "} daybucket;\n"); |
| printf("#define TDH_SIZE %i\n", i); |
| printf("static const daybucket TDH[TDH_SIZE] = {"); |
| |
| for (m = 0; m < i; m++) |
| { |
| if (m) |
| printf(", "); |
| if (m && m % 2 == 0) |
| printf("\n\t\t"); |
| |
| |
| printf("{%i, ", table[m]); |
| |
| if (table[m] >= 0) |
| { |
| char *s = num2day(table[m]); |
| |
| printf("%u, \"%s\"}", (unsigned int)strlen(s), s); |
| } |
| else |
| printf("0, \"\"}"); |
| |
| } |
| printf("};\n\n"); |
| break; |
| } |
| } |
| |
| return 0; |
| } |