| OLD | NEW |
| 1 /* Modified for use with yasm by Peter Johnson. | 1 /* Modified for use with yasm by Peter Johnson. |
| 2 * $Id: perfect.c 1942 2007-09-11 02:11:19Z peter $ | 2 * $Id: perfect.c 1942 2007-09-11 02:11:19Z peter $ |
| 3 */ | 3 */ |
| 4 /* | 4 /* |
| 5 ------------------------------------------------------------------------------ | 5 ------------------------------------------------------------------------------ |
| 6 perfect.c: code to generate code for a hash for perfect hashing. | 6 perfect.c: code to generate code for a hash for perfect hashing. |
| 7 (c) Bob Jenkins, September 1996, December 1999 | 7 (c) Bob Jenkins, September 1996, December 1999 |
| 8 You may use this code in any way you wish, and it is free. No warranty. | 8 You may use this code in any way you wish, and it is free. No warranty. |
| 9 I hereby place this in the public domain. | 9 I hereby place this in the public domain. |
| 10 Source is http://burtleburtle.net/bob/c/perfect.c | 10 Source is http://burtleburtle.net/bob/c/perfect.c |
| (...skipping 655 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 666 } | 666 } |
| 667 else if (*blen < USE_SCRAMBLE) | 667 else if (*blen < USE_SCRAMBLE) |
| 668 { | 668 { |
| 669 sprintf(final->line[0], " unsigned long rsl = (a ^ tab[b]);\n"); | 669 sprintf(final->line[0], " unsigned long rsl = (a ^ tab[b]);\n"); |
| 670 } | 670 } |
| 671 else | 671 else |
| 672 { | 672 { |
| 673 sprintf(final->line[0], " unsigned long rsl = (a ^ scramble[tab[b]]);\n"); | 673 sprintf(final->line[0], " unsigned long rsl = (a ^ scramble[tab[b]]);\n"); |
| 674 } | 674 } |
| 675 | 675 |
| 676 printf("success, found a perfect hash\n"); | |
| 677 | |
| 678 free((void *)tabq); | 676 free((void *)tabq); |
| 679 free((void *)tabh); | 677 free((void *)tabh); |
| 680 } | 678 } |
| 681 | 679 |
| 682 | 680 |
| 683 /* guess initial values for alen and blen */ | 681 /* guess initial values for alen and blen */ |
| 684 static void initalen( | 682 static void initalen( |
| 685 ub4 *alen, /* output, initial alen */ | 683 ub4 *alen, /* output, initial alen */ |
| 686 ub4 *blen, /* output, initial blen */ | 684 ub4 *blen, /* output, initial blen */ |
| 687 ub4 *smax,/* input, power of two greater or equal to max hash value */ | 685 ub4 *smax,/* input, power of two greater or equal to max hash value */ |
| (...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 896 duplicates(*tabb, *blen, keys, form); /* check for duplicates */ | 894 duplicates(*tabb, *blen, keys, form); /* check for duplicates */ |
| 897 fprintf(stderr, "fatal error: Cannot perfect hash: cannot find distinc
t (A,B)\n"); | 895 fprintf(stderr, "fatal error: Cannot perfect hash: cannot find distinc
t (A,B)\n"); |
| 898 exit(EXIT_FAILURE); | 896 exit(EXIT_FAILURE); |
| 899 } | 897 } |
| 900 bad_initkey = 0; | 898 bad_initkey = 0; |
| 901 bad_perfect = 0; | 899 bad_perfect = 0; |
| 902 } | 900 } |
| 903 continue; /* two keys have same (a,b) pair */ | 901 continue; /* two keys have same (a,b) pair */ |
| 904 } | 902 } |
| 905 | 903 |
| 906 printf("found distinct (A,B) on attempt %ld\n", trysalt); | |
| 907 | |
| 908 /* Given distinct (A,B) for all keys, build a perfect hash */ | 904 /* Given distinct (A,B) for all keys, build a perfect hash */ |
| 909 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form)) | 905 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form)) |
| 910 { | 906 { |
| 911 if ((form->hashtype != INT_HT && ++bad_perfect >= RETRY_PERFECT) || | 907 if ((form->hashtype != INT_HT && ++bad_perfect >= RETRY_PERFECT) || |
| 912 (form->hashtype == INT_HT && ++bad_perfect >= RETRY_HEX)) | 908 (form->hashtype == INT_HT && ++bad_perfect >= RETRY_HEX)) |
| 913 { | 909 { |
| 914 if (*blen < *smax) | 910 if (*blen < *smax) |
| 915 { | 911 { |
| 916 *blen *= 2; | 912 *blen *= 2; |
| 917 free(*tabb); | 913 free(*tabb); |
| 918 free(tabq); | 914 free(tabq); |
| 919 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); | 915 *tabb = (bstuff *)yasm_xmalloc((size_t)(sizeof(bstuff)*(*blen))); |
| 920 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1))); | 916 tabq = (qstuff *)yasm_xmalloc((size_t)(sizeof(qstuff)*(*blen+1))); |
| 921 --trysalt; /* we know this salt got distinct (A,B) */ | 917 --trysalt; /* we know this salt got distinct (A,B) */ |
| 922 } | 918 } |
| 923 else | 919 else |
| 924 { | 920 { |
| 925 fprintf(stderr, "fatal error: Cannot perfect hash: cannot build tab[]\
n"); | 921 fprintf(stderr, "fatal error: Cannot perfect hash: cannot build tab[]\
n"); |
| 926 exit(EXIT_FAILURE); | 922 exit(EXIT_FAILURE); |
| 927 } | 923 } |
| 928 bad_perfect = 0; | 924 bad_perfect = 0; |
| 929 } | 925 } |
| 930 continue; | 926 continue; |
| 931 } | 927 } |
| 932 | 928 |
| 933 *salt = trysalt; | 929 *salt = trysalt; |
| 934 break; | 930 break; |
| 935 } | 931 } |
| 936 | 932 |
| 937 printf("built perfect hash table of size %ld\n", *blen); | |
| 938 | |
| 939 /* free working memory */ | 933 /* free working memory */ |
| 940 free((void *)tabq); | 934 free((void *)tabq); |
| 941 } | 935 } |
| 942 | 936 |
| 943 #if 0 | 937 #if 0 |
| 944 /* | 938 /* |
| 945 ------------------------------------------------------------------------------ | 939 ------------------------------------------------------------------------------ |
| 946 Input/output type routines | 940 Input/output type routines |
| 947 ------------------------------------------------------------------------------ | 941 ------------------------------------------------------------------------------ |
| 948 */ | 942 */ |
| (...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1138 keyroot = remkroot(sizeof(key)); | 1132 keyroot = remkroot(sizeof(key)); |
| 1139 | 1133 |
| 1140 /* set up code for final hash */ | 1134 /* set up code for final hash */ |
| 1141 final.line = buf2; | 1135 final.line = buf2; |
| 1142 final.used = 0; | 1136 final.used = 0; |
| 1143 final.len = 10; | 1137 final.len = 10; |
| 1144 for (i=0; i<10; ++i) final.line[i] = buf[i]; | 1138 for (i=0; i<10; ++i) final.line[i] = buf[i]; |
| 1145 | 1139 |
| 1146 /* read in the list of keywords */ | 1140 /* read in the list of keywords */ |
| 1147 getkeys(&keys, &nkeys, textroot, keyroot, form); | 1141 getkeys(&keys, &nkeys, textroot, keyroot, form); |
| 1148 printf("Read in %ld keys\n",nkeys); | |
| 1149 | 1142 |
| 1150 /* find the hash */ | 1143 /* find the hash */ |
| 1151 findhash(&tab, &alen, &blen, &salt, &final, | 1144 findhash(&tab, &alen, &blen, &salt, &final, |
| 1152 scramble, &smax, keys, nkeys, form); | 1145 scramble, &smax, keys, nkeys, form); |
| 1153 | 1146 |
| 1154 /* generate the phash.c file */ | 1147 /* generate the phash.c file */ |
| 1155 make_c(tab, smax, blen, scramble, &final, form); | 1148 make_c(tab, smax, blen, scramble, &final, form); |
| 1156 printf("Wrote phash.c\n"); | |
| 1157 | 1149 |
| 1158 /* clean up memory sources */ | 1150 /* clean up memory sources */ |
| 1159 refree(textroot); | 1151 refree(textroot); |
| 1160 refree(keyroot); | 1152 refree(keyroot); |
| 1161 free((void *)tab); | 1153 free((void *)tab); |
| 1162 printf("Cleaned up\n"); | |
| 1163 } | 1154 } |
| 1164 | 1155 |
| 1165 | 1156 |
| 1166 /* Interpret arguments and call the driver */ | 1157 /* Interpret arguments and call the driver */ |
| 1167 /* See usage_error for the expected arguments */ | 1158 /* See usage_error for the expected arguments */ |
| 1168 int main(argc, argv) | 1159 int main(argc, argv) |
| 1169 int argc; | 1160 int argc; |
| 1170 char **argv; | 1161 char **argv; |
| 1171 { | 1162 { |
| 1172 int mode_given = FALSE; | 1163 int mode_given = FALSE; |
| 1173 int minimal_given = FALSE; | 1164 int minimal_given = FALSE; |
| 1174 int speed_given = FALSE; | 1165 int speed_given = FALSE; |
| 1175 hashform form; | 1166 hashform form; |
| 1176 char *c; | 1167 char *c; |
| 1177 | 1168 |
| 1178 /* default behavior */ | 1169 /* default behavior */ |
| 1179 form.mode = NORMAL_HM; | 1170 form.mode = NORMAL_HM; |
| 1180 form.hashtype = STRING_HT; | 1171 form.hashtype = STRING_HT; |
| 1181 form.perfect = MINIMAL_HP; | 1172 form.perfect = MINIMAL_HP; |
| 1182 form.speed = SLOW_HS; | 1173 form.speed = SLOW_HS; |
| 1183 | 1174 |
| 1184 /* Generate the [minimal] perfect hash */ | 1175 /* Generate the [minimal] perfect hash */ |
| 1185 driver(&form); | 1176 driver(&form); |
| 1186 | 1177 |
| 1187 return EXIT_SUCCESS; | 1178 return EXIT_SUCCESS; |
| 1188 } | 1179 } |
| 1189 #endif | 1180 #endif |
| OLD | NEW |