Chromium Code Reviews| 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 |