1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: closed.c (Formerly closed.c)
5 * Description: Hash table for closed search states.
6 * Author: Mark Seaman, OCR Technology
7 * Created: Fri Oct 16 14:37:00 1987
8 * Modified: Fri May 25 11:31:16 1990 (Mark Seaman) marks@hpgrlt
9 * Language: C
10 * Package: N/A
11 * Status: Reusable Software Component
12 *
13 * (c) Copyright 1987, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 *
24 *********************************************************************************/
25 /*----------------------------------------------------------------------
26 I n c l u d e s
27 ----------------------------------------------------------------------*/
28 #include "freelist.h"
29 #include "closed.h"
30 #include "cutil.h"
31 #include "callcpp.h"
32 //#include <process.h>
33 #ifdef __UNIX__
34 #include <assert.h>
35 #endif
36
37 /*----------------------------------------------------------------------
38 V a r i a b l e s
39 ----------------------------------------------------------------------*/
40 #define TABLE_SIZE 2000
41 HASH_TABLE global_hash = NULL;
42
43 /*----------------------------------------------------------------------
44 F u n c t i o n s
45 ----------------------------------------------------------------------*/
46 /**********************************************************************
47 * hash_add
48 *
49 * Look in the hash table for a particular value. If it is not there
50 * then add it.
51 **********************************************************************/
hash_add(HASH_TABLE state_table,STATE * state)52 int hash_add(HASH_TABLE state_table, STATE *state) {
53 int x;
54 int i = 0;
55 int table_limit = TABLE_SIZE;
56
57 x = state->part2 % table_limit;
58 while (i < table_limit) {
59 assert (0 <= x && x < table_limit);
60 /* Found it */
61 if ((state_table[x].part2 == state->part2) &&
62 (state_table[x].part1 == state->part1)) {
63 return (FALSE);
64 }
65 /* Not in table */
66 else if (state_table[x].part1 == NO_STATE) {
67 state_table[x].part2 = state->part2;
68 state_table[x].part1 = state->part1;
69 return (TRUE);
70 }
71 i++;
72 if (++x >= table_limit)
73 x = 0;
74 }
75 cprintf("warning: hash table is full");
76
77 abort();
78 return 0;
79 }
80
81
82 /**********************************************************************
83 * hash_lookup
84 *
85 * Look in the hash table for a particular value. If the value is there
86 * then return TRUE, FALSE otherwise.
87 **********************************************************************/
hash_lookup(HASH_TABLE state_table,STATE * state)88 int hash_lookup(HASH_TABLE state_table, STATE *state) {
89 int x;
90 int i = 0;
91 int table_limit = TABLE_SIZE;
92
93 x = state->part2 % table_limit;
94 while (i < table_limit) {
95 assert (0 <= x && x < table_limit);
96 /* Found it */
97 if ((state_table[x].part2 == state->part2) &&
98 (state_table[x].part1 == state->part1)) {
99 return (TRUE);
100 }
101 /* Not in table */
102 else if (state_table[x].part1 == NO_STATE) {
103 return (FALSE);
104 }
105
106 i++;
107 if (++x >= table_limit)
108 x = 0;
109 }
110 cprintf ("warning: fell off end of hash table (%x) %x\n",
111 state->part2, state->part2 % table_limit);
112 abort();
113 return 0;
114 }
115
116
117 /**********************************************************************
118 * new_hash_table
119 *
120 * Create and initialize a hash table.
121 **********************************************************************/
new_hash_table()122 HASH_TABLE new_hash_table() {
123 HASH_TABLE ht;
124 int x;
125
126 if (global_hash == NULL)
127 ht = (HASH_TABLE) memalloc (TABLE_SIZE * sizeof (STATE));
128 else
129 ht = global_hash;
130
131 for (x = 0; x < TABLE_SIZE; x++) {
132 ht[x].part1 = NO_STATE;
133 ht[x].part2 = NO_STATE;
134 }
135 return (ht);
136 }
137