00001
00020
00021
00022
00023 #include "freelist.h"
00024 #include "closed.h"
00025 #include "cutil.h"
00026 #include "callcpp.h"
00027
00028 #ifdef __UNIX__
00029 #include <assert.h>
00030 #endif
00031
00032
00033
00034
00036 #define TABLE_SIZE 2000
00037 HASH_TABLE global_hash = NULL;
00038
00039
00040
00041
00042
00048 int hash_add(HASH_TABLE state_table, STATE *state) {
00049 int x;
00050 int i = 0;
00051 int table_limit = TABLE_SIZE;
00052
00053 x = state->part2 % table_limit;
00054 while (i < table_limit) {
00055 assert (0 <= x && x < table_limit);
00056
00057 if ((state_table[x].part2 == state->part2) &&
00058 (state_table[x].part1 == state->part1)) {
00059 return (FALSE);
00060 }
00061
00062 else if (state_table[x].part1 == NO_STATE) {
00063 state_table[x].part2 = state->part2;
00064 state_table[x].part1 = state->part1;
00065 return (TRUE);
00066 }
00067 i++;
00068 if (++x >= table_limit)
00069 x = 0;
00070 }
00071 cprintf("warning: hash table is full");
00072
00073 abort();
00074 return 0;
00075 }
00076
00077
00078
00084 int hash_lookup(HASH_TABLE state_table, STATE *state) {
00085 int x;
00086 int i = 0;
00087 int table_limit = TABLE_SIZE;
00088
00089 x = state->part2 % table_limit;
00090 while (i < table_limit) {
00091 assert (0 <= x && x < table_limit);
00092
00093 if ((state_table[x].part2 == state->part2) &&
00094 (state_table[x].part1 == state->part1)) {
00095 return (TRUE);
00096 }
00097
00098 else if (state_table[x].part1 == NO_STATE) {
00099 return (FALSE);
00100 }
00101
00102 i++;
00103 if (++x >= table_limit)
00104 x = 0;
00105 }
00106 cprintf ("warning: fell off end of hash table (%x) %x\n",
00107 state->part2, state->part2 % table_limit);
00108 abort();
00109 return 0;
00110 }
00111
00112
00113
00117 HASH_TABLE new_hash_table() {
00118 HASH_TABLE ht;
00119 int x;
00120
00121 if (global_hash == NULL)
00122 ht = (HASH_TABLE) memalloc (TABLE_SIZE * sizeof (STATE));
00123 else
00124 ht = global_hash;
00125
00126 for (x = 0; x < TABLE_SIZE; x++) {
00127 ht[x].part1 = NO_STATE;
00128 ht[x].part2 = NO_STATE;
00129 }
00130 return (ht);
00131 }