#include "freelist.h"
#include "closed.h"
#include "cutil.h"
#include "callcpp.h"
Go to the source code of this file.
#define TABLE_SIZE 2000 |
Definition at line 36 of file closed.cpp.
Referenced by hash_add(), hash_lookup(), and new_hash_table().
int hash_add | ( | HASH_TABLE | state_table, | |
STATE * | state | |||
) |
Look in the hash table for a particular value & if not in there, add it.
See http://en.wikipedia.org/wiki/Hash_table
Definition at line 48 of file closed.cpp.
References assert(), cprintf(), FALSE, NO_STATE, STATE::part1, STATE::part2, TABLE_SIZE, and TRUE.
Referenced by best_first_search().
00048 { 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 /* Found it */ 00057 if ((state_table[x].part2 == state->part2) && 00058 (state_table[x].part1 == state->part1)) { 00059 return (FALSE); 00060 } 00061 /* Not in table */ 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 }
int hash_lookup | ( | HASH_TABLE | state_table, | |
STATE * | state | |||
) |
Look in the hash table for a particular value.
Definition at line 84 of file closed.cpp.
References assert(), cprintf(), FALSE, NO_STATE, STATE::part1, STATE::part2, TABLE_SIZE, and TRUE.
Referenced by best_first_search(), and expand_node().
00084 { 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 /* Found it */ 00093 if ((state_table[x].part2 == state->part2) && 00094 (state_table[x].part1 == state->part1)) { 00095 return (TRUE); 00096 } 00097 /* Not in table */ 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 }
HASH_TABLE new_hash_table | ( | ) |
Create and initialize a hash table.
Definition at line 117 of file closed.cpp.
References global_hash, memalloc(), NO_STATE, NULL, STATE::part2, and TABLE_SIZE.
Referenced by new_search().
00117 { 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 }
Global table of states of searches
Definition at line 37 of file closed.cpp.
Referenced by new_hash_table(), and program_editdown().