1 /*
2 * Revision Control Information
3 *
4 * /projects/hsis/CVS/utilities/st/st.c,v
5 * serdar
6 * 1.1
7 * 1993/07/29 01:00:13
8 *
9 */
10 #include <stdio.h>
11 #include "misc/extra/extra.h"
12 #include "stmm.h"
13
14 ABC_NAMESPACE_IMPL_START
15
16
17 #define STMM_NUMCMP(x,y) ((x) != (y))
18 #define STMM_NUMHASH(x,size) (Abc_AbsInt((long)x)%(size))
19 //#define STMM_PTRHASH(x,size) ((int)((ABC_PTRUINT_T)(x)>>2)%size) // 64-bit bug fix 9/17/2007
20 #define STMM_PTRHASH(x,size) ((int)(((ABC_PTRUINT_T)(x)>>2)%size))
21 #define EQUAL(func, x, y) \
22 ((((func) == stmm_numcmp) || ((func) == stmm_ptrcmp)) ?\
23 (STMM_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
24
25
26 #define do_hash(key, table)\
27 ((table->hash == stmm_ptrhash) ? STMM_PTRHASH((key),(table)->num_bins) :\
28 (table->hash == stmm_numhash) ? STMM_NUMHASH((key), (table)->num_bins) :\
29 (*table->hash)((key), (table)->num_bins))
30
31 static int rehash (stmm_table *table);
32 //int stmm_numhash (), stmm_ptrhash (), stmm_numcmp (), stmm_ptrcmp ();
33
34 stmm_table *
stmm_init_table_with_params(stmm_compare_func_type compare,stmm_hash_func_type hash,int size,int density,double grow_factor,int reorder_flag)35 stmm_init_table_with_params (stmm_compare_func_type compare, stmm_hash_func_type hash, int size, int density, double grow_factor, int reorder_flag)
36 {
37 int i;
38 stmm_table *newTable;
39
40 newTable = ABC_ALLOC(stmm_table, 1);
41 if (newTable == NULL) {
42 return NULL;
43 }
44 newTable->compare = compare;
45 newTable->hash = hash;
46 newTable->num_entries = 0;
47 newTable->max_density = density;
48 newTable->grow_factor = grow_factor;
49 newTable->reorder_flag = reorder_flag;
50 if (size <= 0) {
51 size = 1;
52 }
53 newTable->num_bins = size;
54 newTable->bins = ABC_ALLOC(stmm_table_entry *, size);
55 if (newTable->bins == NULL) {
56 ABC_FREE(newTable);
57 return NULL;
58 }
59 for (i = 0; i < size; i++) {
60 newTable->bins[i] = 0;
61 }
62
63 // added by alanmi
64 newTable->pMemMan = Extra_MmFixedStart(sizeof (stmm_table_entry));
65 return newTable;
66 }
67
68 stmm_table *
stmm_init_table(stmm_compare_func_type compare,stmm_hash_func_type hash)69 stmm_init_table (stmm_compare_func_type compare, stmm_hash_func_type hash)
70 {
71 return stmm_init_table_with_params (compare, hash,
72 STMM_DEFAULT_INIT_TABLE_SIZE,
73 STMM_DEFAULT_MAX_DENSITY,
74 STMM_DEFAULT_GROW_FACTOR,
75 STMM_DEFAULT_REORDER_FLAG);
76 }
77
78 void
stmm_free_table(stmm_table * table)79 stmm_free_table (stmm_table *table)
80 {
81 /*
82 stmm_table_entry *ptr, *next;
83 int i;
84 for ( i = 0; i < table->num_bins; i++ )
85 {
86 ptr = table->bins[i];
87 while ( ptr != NULL )
88 {
89 next = ptr->next;
90 ABC_FREE( ptr );
91 ptr = next;
92 }
93 }
94 */
95 // no need to deallocate entries because they are in the memory manager now
96 // added by alanmi
97 if ( table->pMemMan )
98 Extra_MmFixedStop ((Extra_MmFixed_t *)table->pMemMan);
99 ABC_FREE(table->bins);
100 ABC_FREE(table);
101 }
102
103 // this function recycles all the bins
104 void
stmm_clean(stmm_table * table)105 stmm_clean (stmm_table *table)
106 {
107 int i;
108 // clean the bins
109 for (i = 0; i < table->num_bins; i++)
110 table->bins[i] = NULL;
111 // reset the parameters
112 table->num_entries = 0;
113 // restart the memory manager
114 Extra_MmFixedRestart ((Extra_MmFixed_t *)table->pMemMan);
115 }
116
117
118 #define PTR_NOT_EQUAL(table, ptr, user_key)\
119 (ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
120
121 #define FIND_ENTRY(table, hash_val, key, ptr, last) \
122 (last) = &(table)->bins[hash_val];\
123 (ptr) = *(last);\
124 while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
125 (last) = &(ptr)->next; (ptr) = *(last);\
126 }\
127 if ((ptr) != NULL && (table)->reorder_flag) {\
128 *(last) = (ptr)->next;\
129 (ptr)->next = (table)->bins[hash_val];\
130 (table)->bins[hash_val] = (ptr);\
131 }
132
133 int
stmm_lookup(stmm_table * table,char * key,char ** value)134 stmm_lookup (stmm_table *table, char *key, char **value)
135 {
136 int hash_val;
137 stmm_table_entry *ptr, **last;
138
139 hash_val = do_hash (key, table);
140
141 FIND_ENTRY (table, hash_val, key, ptr, last);
142
143 if (ptr == NULL) {
144 return 0;
145 }
146 else {
147 if (value != NULL)
148 {
149 *value = ptr->record;
150 }
151 return 1;
152 }
153 }
154
155 int
stmm_lookup_int(stmm_table * table,char * key,int * value)156 stmm_lookup_int (stmm_table *table, char *key, int *value)
157 {
158 int hash_val;
159 stmm_table_entry *ptr, **last;
160
161 hash_val = do_hash (key, table);
162
163 FIND_ENTRY (table, hash_val, key, ptr, last);
164
165 if (ptr == NULL) {
166 return 0;
167 }
168 else {
169 if (value != 0)
170 {
171 *value = (long) ptr->record;
172 }
173 return 1;
174 }
175 }
176
177 // This macro contained a line
178 // new = ABC_ALLOC(stmm_table_entry, 1);
179 // which was modified by alanmi
180
181
182 /* This macro does not check if memory allocation fails. Use at you own risk */
183 #define ADD_DIRECT(table, key, value, hash_val, new)\
184 {\
185 if (table->num_entries/table->num_bins >= table->max_density) {\
186 rehash(table);\
187 hash_val = do_hash(key,table);\
188 }\
189 \
190 new = (stmm_table_entry *)Extra_MmFixedEntryFetch( (Extra_MmFixed_t *)table->pMemMan );\
191 \
192 new->key = key;\
193 new->record = value;\
194 new->next = table->bins[hash_val];\
195 table->bins[hash_val] = new;\
196 table->num_entries++;\
197 }
198
199 int
stmm_insert(stmm_table * table,char * key,char * value)200 stmm_insert (stmm_table *table, char *key, char *value)
201 {
202 int hash_val;
203 stmm_table_entry *newEntry;
204 stmm_table_entry *ptr, **last;
205
206 hash_val = do_hash (key, table);
207
208 FIND_ENTRY (table, hash_val, key, ptr, last);
209
210 if (ptr == NULL) {
211 if (table->num_entries / table->num_bins >= table->max_density) {
212 if (rehash (table) == STMM_OUT_OF_MEM) {
213 return STMM_OUT_OF_MEM;
214 }
215 hash_val = do_hash (key, table);
216 }
217
218 // newEntry = ABC_ALLOC( stmm_table_entry, 1 );
219 newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
220 if (newEntry == NULL) {
221 return STMM_OUT_OF_MEM;
222 }
223
224 newEntry->key = key;
225 newEntry->record = value;
226 newEntry->next = table->bins[hash_val];
227 table->bins[hash_val] = newEntry;
228 table->num_entries++;
229 return 0;
230 }
231 else {
232 ptr->record = value;
233 return 1;
234 }
235 }
236
237 int
stmm_add_direct(stmm_table * table,char * key,char * value)238 stmm_add_direct (stmm_table *table, char *key, char *value)
239 {
240 int hash_val;
241 stmm_table_entry *newEntry;
242
243 hash_val = do_hash (key, table);
244 if (table->num_entries / table->num_bins >= table->max_density) {
245 if (rehash (table) == STMM_OUT_OF_MEM) {
246 return STMM_OUT_OF_MEM;
247 }
248 }
249 hash_val = do_hash (key, table);
250
251 // newEntry = ABC_ALLOC( stmm_table_entry, 1 );
252 newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
253 if (newEntry == NULL) {
254 return STMM_OUT_OF_MEM;
255 }
256
257 newEntry->key = key;
258 newEntry->record = value;
259 newEntry->next = table->bins[hash_val];
260 table->bins[hash_val] = newEntry;
261 table->num_entries++;
262 return 1;
263 }
264
265 int
stmm_find_or_add(stmm_table * table,char * key,char *** slot)266 stmm_find_or_add (stmm_table *table, char *key, char ***slot)
267 {
268 int hash_val;
269 stmm_table_entry *newEntry, *ptr, **last;
270
271 hash_val = do_hash (key, table);
272
273 FIND_ENTRY (table, hash_val, key, ptr, last);
274
275 if (ptr == NULL) {
276 if (table->num_entries / table->num_bins >= table->max_density) {
277 if (rehash (table) == STMM_OUT_OF_MEM) {
278 return STMM_OUT_OF_MEM;
279 }
280 hash_val = do_hash (key, table);
281 }
282
283 // newEntry = ABC_ALLOC( stmm_table_entry, 1 );
284 newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
285 if (newEntry == NULL) {
286 return STMM_OUT_OF_MEM;
287 }
288
289 newEntry->key = key;
290 newEntry->record = (char *) 0;
291 newEntry->next = table->bins[hash_val];
292 table->bins[hash_val] = newEntry;
293 table->num_entries++;
294 if (slot != NULL)
295 *slot = &newEntry->record;
296 return 0;
297 }
298 else {
299 if (slot != NULL)
300 *slot = &ptr->record;
301 return 1;
302 }
303 }
304
305 int
stmm_find(stmm_table * table,char * key,char *** slot)306 stmm_find (stmm_table *table, char *key, char ***slot)
307 {
308 int hash_val;
309 stmm_table_entry *ptr, **last;
310
311 hash_val = do_hash (key, table);
312
313 FIND_ENTRY (table, hash_val, key, ptr, last);
314
315 if (ptr == NULL) {
316 return 0;
317 }
318 else {
319 if (slot != NULL)
320 {
321 *slot = &ptr->record;
322 }
323 return 1;
324 }
325 }
326
327 static int
rehash(stmm_table * table)328 rehash (stmm_table *table)
329 {
330 stmm_table_entry *ptr, *next, **old_bins;
331 int i, old_num_bins, hash_val, old_num_entries;
332
333 /* save old values */
334 old_bins = table->bins;
335 old_num_bins = table->num_bins;
336 old_num_entries = table->num_entries;
337
338 /* rehash */
339 table->num_bins = (int) (table->grow_factor * old_num_bins);
340 if (table->num_bins % 2 == 0) {
341 table->num_bins += 1;
342 }
343 table->num_entries = 0;
344 table->bins = ABC_ALLOC(stmm_table_entry *, table->num_bins);
345 if (table->bins == NULL) {
346 table->bins = old_bins;
347 table->num_bins = old_num_bins;
348 table->num_entries = old_num_entries;
349 return STMM_OUT_OF_MEM;
350 }
351 /* initialize */
352 for (i = 0; i < table->num_bins; i++) {
353 table->bins[i] = 0;
354 }
355
356 /* copy data over */
357 for (i = 0; i < old_num_bins; i++) {
358 ptr = old_bins[i];
359 while (ptr != NULL) {
360 next = ptr->next;
361 hash_val = do_hash (ptr->key, table);
362 ptr->next = table->bins[hash_val];
363 table->bins[hash_val] = ptr;
364 table->num_entries++;
365 ptr = next;
366 }
367 }
368 ABC_FREE(old_bins);
369
370 return 1;
371 }
372
373 stmm_table *
stmm_copy(stmm_table * old_table)374 stmm_copy (stmm_table *old_table)
375 {
376 stmm_table *newEntry_table;
377 stmm_table_entry *ptr, /* *newEntryptr, *next, */ *newEntry;
378 int i, /*j, */ num_bins = old_table->num_bins;
379
380 newEntry_table = ABC_ALLOC(stmm_table, 1);
381 if (newEntry_table == NULL) {
382 return NULL;
383 }
384
385 *newEntry_table = *old_table;
386 newEntry_table->bins = ABC_ALLOC(stmm_table_entry *, num_bins);
387 if (newEntry_table->bins == NULL) {
388 ABC_FREE(newEntry_table);
389 return NULL;
390 }
391
392 // allocate the memory manager for the newEntry table
393 newEntry_table->pMemMan = Extra_MmFixedStart (sizeof (stmm_table_entry));
394
395 for (i = 0; i < num_bins; i++) {
396 newEntry_table->bins[i] = NULL;
397 ptr = old_table->bins[i];
398 while (ptr != NULL) {
399 // newEntry = ABC_ALLOC( stmm_table_entry, 1 );
400 newEntry = (stmm_table_entry *)Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)newEntry_table->pMemMan);
401 if (newEntry == NULL) {
402 /*
403 for ( j = 0; j <= i; j++ )
404 {
405 newEntryptr = newEntry_table->bins[j];
406 while ( newEntryptr != NULL )
407 {
408 next = newEntryptr->next;
409 ABC_FREE( newEntryptr );
410 newEntryptr = next;
411 }
412 }
413 */
414 Extra_MmFixedStop ((Extra_MmFixed_t *)newEntry_table->pMemMan);
415
416 ABC_FREE(newEntry_table->bins);
417 ABC_FREE(newEntry_table);
418 return NULL;
419 }
420 *newEntry = *ptr;
421 newEntry->next = newEntry_table->bins[i];
422 newEntry_table->bins[i] = newEntry;
423 ptr = ptr->next;
424 }
425 }
426 return newEntry_table;
427 }
428
429 int
stmm_delete(stmm_table * table,char ** keyp,char ** value)430 stmm_delete (stmm_table *table, char **keyp, char **value)
431 {
432 int hash_val;
433 char *key = *keyp;
434 stmm_table_entry *ptr, **last;
435
436 hash_val = do_hash (key, table);
437
438 FIND_ENTRY (table, hash_val, key, ptr, last);
439
440 if (ptr == NULL) {
441 return 0;
442 }
443
444 *last = ptr->next;
445 if (value != NULL)
446 *value = ptr->record;
447 *keyp = ptr->key;
448 // ABC_FREE( ptr );
449 Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
450
451 table->num_entries--;
452 return 1;
453 }
454
455 int
stmm_delete_int(stmm_table * table,long * keyp,char ** value)456 stmm_delete_int (stmm_table *table, long *keyp, char **value)
457 {
458 int hash_val;
459 char *key = (char *) *keyp;
460 stmm_table_entry *ptr, **last;
461
462 hash_val = do_hash (key, table);
463
464 FIND_ENTRY (table, hash_val, key, ptr, last);
465
466 if (ptr == NULL) {
467 return 0;
468 }
469
470 *last = ptr->next;
471 if (value != NULL)
472 *value = ptr->record;
473 *keyp = (long) ptr->key;
474 // ABC_FREE( ptr );
475 Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
476
477 table->num_entries--;
478 return 1;
479 }
480
481 int
stmm_foreach(stmm_table * table,enum stmm_retval (* func)(char *,char *,char *),char * arg)482 stmm_foreach (stmm_table *table, enum stmm_retval (*func) (char *, char *, char *), char *arg)
483 {
484 stmm_table_entry *ptr, **last;
485 enum stmm_retval retval;
486 int i;
487
488 for (i = 0; i < table->num_bins; i++) {
489 last = &table->bins[i];
490 ptr = *last;
491 while (ptr != NULL) {
492 retval = (*func) (ptr->key, ptr->record, arg);
493 switch (retval) {
494 case STMM_CONTINUE:
495 last = &ptr->next;
496 ptr = *last;
497 break;
498 case STMM_STOP:
499 return 0;
500 case STMM_DELETE:
501 *last = ptr->next;
502 table->num_entries--; /* cstevens@ic */
503 // ABC_FREE( ptr );
504 Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
505
506 ptr = *last;
507 }
508 }
509 }
510 return 1;
511 }
512
513 int
stmm_strhash(const char * string,int modulus)514 stmm_strhash (const char *string, int modulus)
515 {
516 int val = 0;
517 int c;
518
519 while ((c = *string++) != '\0') {
520 val = val * 997 + c;
521 }
522
523 return ((val < 0) ? -val : val) % modulus;
524 }
525
526 int
stmm_numhash(const char * x,int size)527 stmm_numhash (const char *x, int size)
528 {
529 return STMM_NUMHASH (x, size);
530 }
531
532 int
stmm_ptrhash(const char * x,int size)533 stmm_ptrhash (const char *x, int size)
534 {
535 return STMM_PTRHASH (x, size);
536 }
537
538 int
stmm_numcmp(const char * x,const char * y)539 stmm_numcmp (const char *x, const char *y)
540 {
541 return STMM_NUMCMP (x, y);
542 }
543
544 int
stmm_ptrcmp(const char * x,const char * y)545 stmm_ptrcmp (const char *x, const char *y)
546 {
547 return STMM_NUMCMP (x, y);
548 }
549
550 stmm_generator *
stmm_init_gen(stmm_table * table)551 stmm_init_gen (stmm_table *table)
552 {
553 stmm_generator *gen;
554
555 gen = ABC_ALLOC(stmm_generator, 1);
556 if (gen == NULL) {
557 return NULL;
558 }
559 gen->table = table;
560 gen->entry = NULL;
561 gen->index = 0;
562 return gen;
563 }
564
565
566 int
stmm_gen(stmm_generator * gen,char ** key_p,char ** value_p)567 stmm_gen (stmm_generator *gen, char **key_p, char **value_p)
568 {
569 int i;
570
571 if (gen->entry == NULL) {
572 /* try to find next entry */
573 for (i = gen->index; i < gen->table->num_bins; i++) {
574 if (gen->table->bins[i] != NULL) {
575 gen->index = i + 1;
576 gen->entry = gen->table->bins[i];
577 break;
578 }
579 }
580 if (gen->entry == NULL) {
581 return 0; /* that's all folks ! */
582 }
583 }
584 *key_p = gen->entry->key;
585 if (value_p != 0) {
586 *value_p = gen->entry->record;
587 }
588 gen->entry = gen->entry->next;
589 return 1;
590 }
591
592
593 int
stmm_gen_int(stmm_generator * gen,char ** key_p,long * value_p)594 stmm_gen_int (stmm_generator *gen, char **key_p, long *value_p)
595 {
596 int i;
597
598 if (gen->entry == NULL) {
599 /* try to find next entry */
600 for (i = gen->index; i < gen->table->num_bins; i++) {
601 if (gen->table->bins[i] != NULL) {
602 gen->index = i + 1;
603 gen->entry = gen->table->bins[i];
604 break;
605 }
606 }
607 if (gen->entry == NULL) {
608 return 0; /* that's all folks ! */
609 }
610 }
611 *key_p = gen->entry->key;
612 if (value_p != 0)
613 {
614 *value_p = (long) gen->entry->record;
615 }
616 gen->entry = gen->entry->next;
617 return 1;
618 }
619
620
621 void
stmm_free_gen(stmm_generator * gen)622 stmm_free_gen (stmm_generator *gen)
623 {
624 ABC_FREE(gen);
625 }
626 ABC_NAMESPACE_IMPL_END
627
628