14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*---------------------------------------------------------------------------* 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * astar_pphash.c * 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Copyright 2007, 2008 Nuance Communciations, Inc. * 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the 'License'); * 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * you may not use this file except in compliance with the License. * 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * You may obtain a copy of the License at * 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 * 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Unless required by applicable law or agreed to in writing, software * 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * distributed under the License is distributed on an 'AS IS' BASIS, * 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * See the License for the specific language governing permissions and * 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * limitations under the License. * 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *---------------------------------------------------------------------------*/ 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "pstdio.h" 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "passert.h" 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "portable.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include"duk_err.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include"srec.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include"astar.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include"astar_pphash.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define DEBUG_PPHASH 0 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* initialize the hash with no elements defined */ 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid hash_init(FixedSizeHash* hash, srec* rec_debug) 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int i; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hash->hashsize = FSH_HASHSIZE; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < hash->hashsize; i++) 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hash->items[i] = FSH_NULL; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hash->rec = rec_debug; 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* compare a couple of paths, 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ie see whether the word history is the same */ 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint compare_parp(partial_path* parp1, partial_path* parp2, srec* rec) 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project asr_int32_t diff = 0; 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (parp1->first_prev_arc != PARP_TERMINAL || 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parp2->first_prev_arc != PARP_TERMINAL) 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diff = parp1->token_index - parp2->token_index; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (parp1->next && parp2->next) 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diff = parp1->word - parp2->word; 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (diff) 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project goto CPE; 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parp1 = parp1->next; 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parp2 = parp2->next; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diff = (int)parp1->next - (int)parp2->next; 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source ProjectCPE: 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (diff) 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project diff = (diff < 0 ? -1 : 1); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return diff; 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* find the bin */ 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectunsigned int hashfunc(partial_path* parp) 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hashval; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (parp->first_prev_arc != PARP_TERMINAL) 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashval = parp->token_index; 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashval = 0; 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashval = (hashval << 10) + parp->word; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((parp = parp->next) != NULL) 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (parp->word != MAXwordID) 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hashval = hashval * 64 + parp->word + hashval % 65536; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return hashval; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* get a history same as this one */ 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint hash_get(FixedSizeHash* hash, partial_path* parp, void** hval) 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hkey_index = hashfunc(parp); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partial_path* p_return; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hkey_index = hkey_index % hash->hashsize; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project p_return = hash->items[hkey_index]; 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!p_return) 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_NO_SUCH_KEY; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; p_return; p_return = p_return->hashlink) 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (compare_parp(p_return, parp, hash->rec) == 0) 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *hval = p_return; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_SUCCESS; 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_NO_SUCH_KEY; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* set this, return error is same path already there */ 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint hash_set(FixedSizeHash* hash, partial_path* parp) 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hkey_index = hashfunc(parp); 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partial_path** p_insert; 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hkey_index = hkey_index % hash->hashsize; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project p_insert = &hash->items[hkey_index]; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; *p_insert; p_insert = &((*p_insert)->hashlink)) 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (*p_insert == parp) 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#if 1||DEBUG_PPHASH 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project print_path(parp, hash->rec, "problem in astar_pphash hash_set "); 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_SUCCESS; 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (compare_parp(*p_insert, parp, hash->rec) == 0) 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#if DEBUG_PPHASH 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project print_path(*p_insert, hash->rec, "key taken in astar_pphash hash_set "); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_KEY_OCCUPIED; 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *p_insert = parp; 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#if DEBUG_PPHASH 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project printf("setting at %d ", hkey_index); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project print_path(parp, hash->rec, ""); 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project parp->hashlink = FSH_NULL; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_SUCCESS; 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* delete an element */ 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint hash_del(FixedSizeHash* hash, partial_path* parp) 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int hkey_index = hashfunc(parp); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project partial_path** p_insert; 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hkey_index = hkey_index % hash->hashsize; 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project p_insert = &hash->items[hkey_index]; 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; *p_insert; p_insert = &((*p_insert)->hashlink)) 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (compare_parp(*p_insert, parp, hash->rec) == 0) 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *p_insert = parp->hashlink; 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#if DEBUG_PPHASH 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project printf("delhash at %d\n", hkey_index); 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project print_path(parp, hash->rec, "deleted "); 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_SUCCESS; 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return FSH_NO_SUCH_KEY; 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 173