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 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 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 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 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 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 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
