1#include "nc3internal.h"
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <assert.h>
7
8/* this should be prime */
9#define TABLE_STARTSIZE 1021
10
11#define ACTIVE 1
12
13#define MAX(a,b) ((a) > (b) ? (a) : (b))
14
15extern uint32_t hash_fast(const void *key, size_t length);
16
17static int isPrime(unsigned long val)
18{
19  int i;
20
21  for (i = 9; i--;)
22  {
23#ifdef HAVE_RANDOM
24    unsigned long a = ((unsigned long)random() % (val-4)) + 2;
25#else
26   unsigned long a = ((unsigned long)rand() % (val - 4)) + 2;
27#endif
28    unsigned long p = 1;
29    unsigned long exp = val-1;
30    while (exp)
31    {
32      if (exp & 1)
33 p = (p*a)%val;
34
35      a = (a*a)%val;
36      exp >>= 1;
37    }
38
39    if (p != 1)
40      return 0;
41  }
42
43  return 1;
44}
45
46static unsigned long findPrimeGreaterThan(unsigned long val)
47{
48  if (val & 1)
49    val+=2;
50  else
51    val++;
52
53  while (!isPrime(val))
54    val+=2;
55
56  return val;
57}
58
59static void rehashDim(const NC_dimarrayncap)
60{
61  NC_hashmaphm = ncap->hashmap;
62  unsigned long size = hm->size;
63  unsigned long count = hm->count;
64
65  hEntrytable = hm->table;
66
67  hm->size = findPrimeGreaterThan(size<<1);
68  hm->table = (hEntry*)calloc(sizeof(hEntry), hm->size);
69  hm->count = 0;
70
71  while(size > 0) {
72    --size;
73    if (table[size].flags == ACTIVE) {
74      NC_dim *elem = ncap->value[table[size].data-1];
75      NC_hashmapAddDim(ncaptable[size].data-1, elem->name->cp);
76      assert(NC_hashmapGetDim(ncapelem->name->cp) == table[size].data-1);
77    }
78  }
79
80  free(table);
81  assert(count == hm->count);
82}
83
84static void rehashVar(const NC_vararrayncap)
85{
86  NC_hashmaphm = ncap->hashmap;
87  unsigned long size = hm->size;
88  unsigned long count = hm->count;
89
90  hEntrytable = hm->table;
91
92  hm->size = findPrimeGreaterThan(size<<1);
93  hm->table = (hEntry*)calloc(sizeof(hEntry), (size_t)hm->size);
94  hm->count = 0;
95
96  while(size > 0) {
97    --size;
98    if (table[size].flags == ACTIVE) {
99      NC_var *elem = ncap->value[table[size].data-1];
100      NC_hashmapAddVar(ncaptable[size].data-1, elem->name->cp);
101      assert(NC_hashmapGetVar(ncapelem->name->cp) == table[size].data-1);
102    }
103  }
104
105  free(table);
106  assert(count == hm->count);
107}
108
109NC_hashmapNC_hashmapCreate(unsigned long startsize)
110{
111  NC_hashmaphm = (NC_hashmap*)malloc(sizeof(NC_hashmap));
112
113  if (!startsize)
114    startsize = TABLE_STARTSIZE;
115  else {
116    startsize *= 4;
117    startsize /= 3;
118    startsize = findPrimeGreaterThan(startsize-2);
119  }
120
121  hm->table = (hEntry*)calloc(sizeof(hEntry), (size_t)startsize);
122  hm->size = startsize;
123  hm->count = 0;
124
125  return hm;
126}
127
128void NC_hashmapAddDim(const NC_dimarrayncap, long data, const char *name)
129{
130  unsigned long key = hash_fast(name, strlen(name));
131  NC_hashmaphash = ncap->hashmap;
132
133  if (hash->size*3/4 <= hash->count) {
134    rehashDim(ncap);
135  }
136
137  do
138  {
139    unsigned long i;
140    unsigned long index = key % hash->size;
141    unsigned long step = (key % MAX(1,(hash->size-2))) + 1;
142
143    for (i = 0; i < hash->sizei++)
144    {
145      if (hash->table[index].flags & ACTIVE)
146      {
147 hEntry entry = hash->table[index];
148 if (entry.key == key &&
149     strncmp(namencap->value[entry.data-1]->name->cp,
150     ncap->value[entry.data-1]->name->nchars) == 0)
151   {
152   hash->table[index].data = data+1;
153   return;
154 }
155      }
156      else
157      {
158 hash->table[index].flags |= ACTIVE;
159 hash->table[index].data = data+1;
160 hash->table[index].key = key;
161 ++hash->count;
162 return;
163      }
164
165      index = (index + step) % hash->size;
166    }
167
168    /* it should not be possible that we EVER come this far, but unfortunately
169       not every generated prime number is prime (Carmichael numbers...) */
170    rehashDim(ncap);
171  }
172  while (1);
173}
174
175void NC_hashmapAddVar(const NC_vararrayncap, long data, const char *name)
176{
177  unsigned long key = hash_fast(name, strlen(name));
178  NC_hashmaphash = ncap->hashmap;
179
180  if (hash->size*3/4 <= hash->count) {
181    rehashVar(ncap);
182  }
183
184  do
185  {
186    unsigned long i;
187    unsigned long index = key % hash->size;
188    unsigned long step = (key % MAX(1,(hash->size-2))) + 1;
189
190    for (i = 0; i < hash->sizei++)
191    {
192      if (hash->table[index].flags & ACTIVE)
193      {
194 hEntry entry = hash->table[index];
195 if (entry.key == key &&
196     strncmp(namencap->value[entry.data-1]->name->cp,
197     ncap->value[entry.data-1]->name->nchars) == 0)
198 {
199   hash->table[index].data = data+1;
200   return;
201 }
202      }
203      else
204      {
205 hash->table[index].flags |= ACTIVE;
206 hash->table[index].data = data+1;
207 hash->table[index].key = key;
208 ++hash->count;
209 return;
210      }
211
212      index = (index + step) % hash->size;
213    }
214
215    /* it should not be possible that we EVER come this far, but unfortunately
216       not every generated prime number is prime (Carmichael numbers...) */
217    rehashVar(ncap);
218  }
219  while (1);
220}
221
222long NC_hashmapRemoveDim(const NC_dimarrayncap, const char *name)
223{
224  unsigned long i;
225  unsigned long key = hash_fast(name, strlen(name));
226  NC_hashmaphash = ncap->hashmap;
227
228  unsigned long index = key % hash->size;
229  unsigned long step = (key % (hash->size-2)) + 1;
230
231  for (i = 0; i < hash->sizei++)
232  {
233    if (hash->table[index].data > 0)
234    {
235      hEntry entry = hash->table[index];
236      if (entry.key == key &&
237   strncmp(namencap->value[entry.data-1]->name->cp,
238   ncap->value[entry.data-1]->name->nchars) == 0)
239      {
240 if (hash->table[index].flags & ACTIVE)
241 {
242   hash->table[index].flags &= ~ACTIVE;
243   --hash->count;
244   return hash->table[index].data-1;
245 }
246 else /* in, but not active (i.e. deleted) */
247   return -1;
248      }
249    }
250    else /* found an empty place (can't be in) */
251      return -1;
252
253    index = (index + step) % hash->size;
254  }
255  /* everything searched through, but not in */
256  return -1;
257}
258
259long NC_hashmapRemoveVar(const NC_vararrayncap, const char *name)
260{
261  unsigned long i;
262  unsigned long key = hash_fast(name, strlen(name));
263  NC_hashmaphash = ncap->hashmap;
264
265  unsigned long index = key % hash->size;
266  unsigned long step = (key % (hash->size-2)) + 1;
267
268  for (i = 0; i < hash->sizei++)
269  {
270    if (hash->table[index].data > 0)
271    {
272      hEntry entry = hash->table[index];
273      if (entry.key == key &&
274   strncmp(namencap->value[entry.data-1]->name->cp,
275   ncap->value[entry.data-1]->name->nchars) == 0)
276      {
277 if (hash->table[index].flags & ACTIVE)
278 {
279   hash->table[index].flags &= ~ACTIVE;
280   --hash->count;
281   return hash->table[index].data-1;
282 }
283 else /* in, but not active (i.e. deleted) */
284   return -1;
285      }
286    }
287    else /* found an empty place (can't be in) */
288      return -1;
289
290    index = (index + step) % hash->size;
291  }
292  /* everything searched through, but not in */
293  return -1;
294}
295
296long NC_hashmapGetDim(const NC_dimarrayncap, const char *name)
297{
298  NC_hashmaphash = ncap->hashmap;
299  if (hash->count)
300  {
301    unsigned long key = hash_fast(name, strlen(name));
302    NC_hashmaphash = ncap->hashmap;
303
304    unsigned long i;
305    unsigned long index = key % hash->size;
306    unsigned long step = (key % (hash->size-2)) + 1;
307
308    for (i = 0; i < hash->sizei++)
309    {
310      hEntry entry = hash->table[index];
311      if (entry.key == key &&
312   strncmp(namencap->value[entry.data-1]->name->cp,
313   ncap->value[entry.data-1]->name->nchars) == 0)
314      {
315 if (entry.flags & ACTIVE)
316   return entry.data-1;
317 break;
318      }
319      else
320 if (!(entry.flags & ACTIVE))
321   break;
322
323      index = (index + step) % hash->size;
324    }
325  }
326
327  return -1;
328}
329
330long NC_hashmapGetVar(const NC_vararrayncap, const char *name)
331{
332  NC_hashmaphash = ncap->hashmap;
333  if (hash->count)
334  {
335    unsigned long key = hash_fast(name, strlen(name));
336    NC_hashmaphash = ncap->hashmap;
337
338    unsigned long i;
339    unsigned long index = key % hash->size;
340    unsigned long step = (key % (hash->size-2)) + 1;
341
342    for (i = 0; i < hash->sizei++)
343    {
344      hEntry entry = hash->table[index];
345      if (entry.key == key &&
346   strncmp(namencap->value[entry.data-1]->name->cp,
347   ncap->value[entry.data-1]->name->nchars) == 0)
348      {
349 if (entry.flags & ACTIVE)
350   return entry.data-1;
351 break;
352      }
353      else
354 if (!(entry.flags & ACTIVE))
355   break;
356
357      index = (index + step) % hash->size;
358    }
359  }
360
361  return -1;
362}
363
364unsigned long NC_hashmapCount(NC_hashmaphash)
365{
366  return hash->count;
367}
368
369void NC_hashmapDelete(NC_hashmaphash)
370{
371  if (hash) {
372    free(hash->table);
373    free(hash);
374  }
375}


HyperKWIC - Version 7.20DA executed at 11:37 on 27 Oct 2017 | Polyhedron Solutions - INTERNAL USE | COMMERCIAL (Any O/S) SN 4AKIed