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"); | 676 /* printf("success, found a perfect hash\n"); */ |
Nico
2012/03/02 21:32:48
Can you delete them instead?
| |
677 | 677 |
678 free((void *)tabq); | 678 free((void *)tabq); |
679 free((void *)tabh); | 679 free((void *)tabh); |
680 } | 680 } |
681 | 681 |
682 | 682 |
683 /* guess initial values for alen and blen */ | 683 /* guess initial values for alen and blen */ |
684 static void initalen( | 684 static void initalen( |
685 ub4 *alen, /* output, initial alen */ | 685 ub4 *alen, /* output, initial alen */ |
686 ub4 *blen, /* output, initial blen */ | 686 ub4 *blen, /* output, initial blen */ |
(...skipping 209 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
896 duplicates(*tabb, *blen, keys, form); /* check for duplicates */ | 896 duplicates(*tabb, *blen, keys, form); /* check for duplicates */ |
897 fprintf(stderr, "fatal error: Cannot perfect hash: cannot find distinc t (A,B)\n"); | 897 fprintf(stderr, "fatal error: Cannot perfect hash: cannot find distinc t (A,B)\n"); |
898 exit(EXIT_FAILURE); | 898 exit(EXIT_FAILURE); |
899 } | 899 } |
900 bad_initkey = 0; | 900 bad_initkey = 0; |
901 bad_perfect = 0; | 901 bad_perfect = 0; |
902 } | 902 } |
903 continue; /* two keys have same (a,b) pair */ | 903 continue; /* two keys have same (a,b) pair */ |
904 } | 904 } |
905 | 905 |
906 printf("found distinct (A,B) on attempt %ld\n", trysalt); | 906 /* printf("found distinct (A,B) on attempt %ld\n", trysalt); */ |
907 | 907 |
908 /* Given distinct (A,B) for all keys, build a perfect hash */ | 908 /* Given distinct (A,B) for all keys, build a perfect hash */ |
909 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form)) | 909 if (!perfect(*tabb, *tabh, tabq, *blen, *smax, scramble, nkeys, form)) |
910 { | 910 { |
911 if ((form->hashtype != INT_HT && ++bad_perfect >= RETRY_PERFECT) || | 911 if ((form->hashtype != INT_HT && ++bad_perfect >= RETRY_PERFECT) || |
912 (form->hashtype == INT_HT && ++bad_perfect >= RETRY_HEX)) | 912 (form->hashtype == INT_HT && ++bad_perfect >= RETRY_HEX)) |
913 { | 913 { |
914 if (*blen < *smax) | 914 if (*blen < *smax) |
915 { | 915 { |
916 *blen *= 2; | 916 *blen *= 2; |
(...skipping 10 matching lines...) Expand all Loading... | |
927 } | 927 } |
928 bad_perfect = 0; | 928 bad_perfect = 0; |
929 } | 929 } |
930 continue; | 930 continue; |
931 } | 931 } |
932 | 932 |
933 *salt = trysalt; | 933 *salt = trysalt; |
934 break; | 934 break; |
935 } | 935 } |
936 | 936 |
937 printf("built perfect hash table of size %ld\n", *blen); | 937 /* printf("built perfect hash table of size %ld\n", *blen); */ |
938 | 938 |
939 /* free working memory */ | 939 /* free working memory */ |
940 free((void *)tabq); | 940 free((void *)tabq); |
941 } | 941 } |
942 | 942 |
943 #if 0 | 943 #if 0 |
944 /* | 944 /* |
945 ------------------------------------------------------------------------------ | 945 ------------------------------------------------------------------------------ |
946 Input/output type routines | 946 Input/output type routines |
947 ------------------------------------------------------------------------------ | 947 ------------------------------------------------------------------------------ |
(...skipping 190 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1138 keyroot = remkroot(sizeof(key)); | 1138 keyroot = remkroot(sizeof(key)); |
1139 | 1139 |
1140 /* set up code for final hash */ | 1140 /* set up code for final hash */ |
1141 final.line = buf2; | 1141 final.line = buf2; |
1142 final.used = 0; | 1142 final.used = 0; |
1143 final.len = 10; | 1143 final.len = 10; |
1144 for (i=0; i<10; ++i) final.line[i] = buf[i]; | 1144 for (i=0; i<10; ++i) final.line[i] = buf[i]; |
1145 | 1145 |
1146 /* read in the list of keywords */ | 1146 /* read in the list of keywords */ |
1147 getkeys(&keys, &nkeys, textroot, keyroot, form); | 1147 getkeys(&keys, &nkeys, textroot, keyroot, form); |
1148 printf("Read in %ld keys\n",nkeys); | 1148 /* printf("Read in %ld keys\n",nkeys); */ |
1149 | 1149 |
1150 /* find the hash */ | 1150 /* find the hash */ |
1151 findhash(&tab, &alen, &blen, &salt, &final, | 1151 findhash(&tab, &alen, &blen, &salt, &final, |
1152 scramble, &smax, keys, nkeys, form); | 1152 scramble, &smax, keys, nkeys, form); |
1153 | 1153 |
1154 /* generate the phash.c file */ | 1154 /* generate the phash.c file */ |
1155 make_c(tab, smax, blen, scramble, &final, form); | 1155 make_c(tab, smax, blen, scramble, &final, form); |
1156 printf("Wrote phash.c\n"); | 1156 /* printf("Wrote phash.c\n"); */ |
1157 | 1157 |
1158 /* clean up memory sources */ | 1158 /* clean up memory sources */ |
1159 refree(textroot); | 1159 refree(textroot); |
1160 refree(keyroot); | 1160 refree(keyroot); |
1161 free((void *)tab); | 1161 free((void *)tab); |
1162 printf("Cleaned up\n"); | 1162 /* printf("Cleaned up\n"); */ |
1163 } | 1163 } |
1164 | 1164 |
1165 | 1165 |
1166 /* Interpret arguments and call the driver */ | 1166 /* Interpret arguments and call the driver */ |
1167 /* See usage_error for the expected arguments */ | 1167 /* See usage_error for the expected arguments */ |
1168 int main(argc, argv) | 1168 int main(argc, argv) |
1169 int argc; | 1169 int argc; |
1170 char **argv; | 1170 char **argv; |
1171 { | 1171 { |
1172 int mode_given = FALSE; | 1172 int mode_given = FALSE; |
1173 int minimal_given = FALSE; | 1173 int minimal_given = FALSE; |
1174 int speed_given = FALSE; | 1174 int speed_given = FALSE; |
1175 hashform form; | 1175 hashform form; |
1176 char *c; | 1176 char *c; |
1177 | 1177 |
1178 /* default behavior */ | 1178 /* default behavior */ |
1179 form.mode = NORMAL_HM; | 1179 form.mode = NORMAL_HM; |
1180 form.hashtype = STRING_HT; | 1180 form.hashtype = STRING_HT; |
1181 form.perfect = MINIMAL_HP; | 1181 form.perfect = MINIMAL_HP; |
1182 form.speed = SLOW_HS; | 1182 form.speed = SLOW_HS; |
1183 | 1183 |
1184 /* Generate the [minimal] perfect hash */ | 1184 /* Generate the [minimal] perfect hash */ |
1185 driver(&form); | 1185 driver(&form); |
1186 | 1186 |
1187 return EXIT_SUCCESS; | 1187 return EXIT_SUCCESS; |
1188 } | 1188 } |
1189 #endif | 1189 #endif |
OLD | NEW |