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 |