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
34void 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
46int 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  }
68CPE:
69  if (diff)
70    diff = (diff < 0 ? -1 : 1);
71  return diff;
72}
73
74/* find the bin */
75
76unsigned 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
94int 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
116int 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
151int 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