1 /*---------------------------------------------------------------------------*
2 * astar_pphash.c *
3 * *
4 * Copyright 2007, 2008 Nuance Communciations, Inc. *
5 * *
6 * Licensed under the Apache License, Version 2.0 (the 'License'); *
7 * you may not use this file except in compliance with the License. *
8 * *
9 * You may obtain a copy of the License at *
10 * http://www.apache.org/licenses/LICENSE-2.0 *
11 * *
12 * Unless required by applicable law or agreed to in writing, software *
13 * distributed under the License is distributed on an 'AS IS' BASIS, *
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
15 * See the License for the specific language governing permissions and *
16 * limitations under the License. *
17 * *
18 *---------------------------------------------------------------------------*/
19
20 #include "pstdio.h"
21 #include "passert.h"
22 #include "portable.h"
23
24 #include"duk_err.h"
25 #include"srec.h"
26 #include"astar.h"
27 #include"astar_pphash.h"
28
29 #define DEBUG_PPHASH 0
30
31
32 /* initialize the hash with no elements defined */
33
hash_init(FixedSizeHash * hash,srec * rec_debug)34 void hash_init(FixedSizeHash* hash, srec* rec_debug)
35 {
36 int i;
37 hash->hashsize = FSH_HASHSIZE;
38 for (i = 0; i < hash->hashsize; i++)
39 hash->items[i] = FSH_NULL;
40 hash->rec = rec_debug;
41 }
42
43 /* compare a couple of paths,
44 ie see whether the word history is the same */
45
compare_parp(partial_path * parp1,partial_path * parp2,srec * rec)46 int compare_parp(partial_path* parp1, partial_path* parp2, srec* rec)
47 {
48 asr_int32_t diff = 0;
49 if (parp1->first_prev_arc != PARP_TERMINAL ||
50 parp2->first_prev_arc != PARP_TERMINAL)
51 {
52 diff = parp1->token_index - parp2->token_index;
53 }
54 else
55 {
56 while (parp1->next && parp2->next)
57 {
58 diff = parp1->word - parp2->word;
59 if (diff)
60 {
61 goto CPE;
62 }
63 parp1 = parp1->next;
64 parp2 = parp2->next;
65 }
66 diff = (int)parp1->next - (int)parp2->next;
67 }
68 CPE:
69 if (diff)
70 diff = (diff < 0 ? -1 : 1);
71 return diff;
72 }
73
74 /* find the bin */
75
hashfunc(partial_path * parp)76 unsigned int hashfunc(partial_path* parp)
77 {
78 unsigned int hashval;
79 if (parp->first_prev_arc != PARP_TERMINAL)
80 hashval = parp->token_index;
81 else
82 hashval = 0;
83 hashval = (hashval << 10) + parp->word;
84 while ((parp = parp->next) != NULL)
85 {
86 if (parp->word != MAXwordID)
87 hashval = hashval * 64 + parp->word + hashval % 65536;
88 }
89 return hashval;
90 }
91
92 /* get a history same as this one */
93
hash_get(FixedSizeHash * hash,partial_path * parp,void ** hval)94 int hash_get(FixedSizeHash* hash, partial_path* parp, void** hval)
95 {
96 unsigned int hkey_index = hashfunc(parp);
97 partial_path* p_return;
98
99 hkey_index = hkey_index % hash->hashsize;
100 p_return = hash->items[hkey_index];
101 if (!p_return)
102 return FSH_NO_SUCH_KEY;
103 for (; p_return; p_return = p_return->hashlink)
104 {
105 if (compare_parp(p_return, parp, hash->rec) == 0)
106 {
107 *hval = p_return;
108 return FSH_SUCCESS;
109 }
110 }
111 return FSH_NO_SUCH_KEY;
112 }
113
114 /* set this, return error is same path already there */
115
hash_set(FixedSizeHash * hash,partial_path * parp)116 int hash_set(FixedSizeHash* hash, partial_path* parp)
117 {
118 unsigned int hkey_index = hashfunc(parp);
119 partial_path** p_insert;
120
121 hkey_index = hkey_index % hash->hashsize;
122 p_insert = &hash->items[hkey_index];
123 for (; *p_insert; p_insert = &((*p_insert)->hashlink))
124 {
125 if (*p_insert == parp)
126 {
127 #if 1||DEBUG_PPHASH
128 print_path(parp, hash->rec, "problem in astar_pphash hash_set ");
129 #endif
130 return FSH_SUCCESS;
131 }
132 else if (compare_parp(*p_insert, parp, hash->rec) == 0)
133 {
134 #if DEBUG_PPHASH
135 print_path(*p_insert, hash->rec, "key taken in astar_pphash hash_set ");
136 #endif
137 return FSH_KEY_OCCUPIED;
138 }
139 }
140 *p_insert = parp;
141 #if DEBUG_PPHASH
142 printf("setting at %d ", hkey_index);
143 print_path(parp, hash->rec, "");
144 #endif
145 parp->hashlink = FSH_NULL;
146 return FSH_SUCCESS;
147 }
148
149 /* delete an element */
150
hash_del(FixedSizeHash * hash,partial_path * parp)151 int hash_del(FixedSizeHash* hash, partial_path* parp)
152 {
153 unsigned int hkey_index = hashfunc(parp);
154 partial_path** p_insert;
155
156 hkey_index = hkey_index % hash->hashsize;
157 p_insert = &hash->items[hkey_index];
158 for (; *p_insert; p_insert = &((*p_insert)->hashlink))
159 {
160 if (compare_parp(*p_insert, parp, hash->rec) == 0)
161 {
162 *p_insert = parp->hashlink;
163 #if DEBUG_PPHASH
164 printf("delhash at %d\n", hkey_index);
165 print_path(parp, hash->rec, "deleted ");
166 #endif
167 return FSH_SUCCESS;
168 }
169 }
170 return FSH_NO_SUCH_KEY;
171 }
172
173