stmm.c 14.4 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10
/*
 * Revision Control Information
 *
 * /projects/hsis/CVS/utilities/st/st.c,v
 * serdar
 * 1.1
 * 1993/07/29 01:00:13
 *
 */
#include <stdio.h>
11
#include "misc/extra/extra.h"
Alan Mishchenko committed
12
#include "stmm.h"
Alan Mishchenko committed
13

14 15 16
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
17
#define STMM_NUMCMP(x,y) ((x) != (y))
18
#define STMM_NUMHASH(x,size) (Abc_AbsInt((long)x)%(size))
Alan Mishchenko committed
19 20
//#define STMM_PTRHASH(x,size) ((int)((ABC_PTRUINT_T)(x)>>2)%size) //  64-bit bug fix 9/17/2007
#define STMM_PTRHASH(x,size) ((int)(((ABC_PTRUINT_T)(x)>>2)%size))
Alan Mishchenko committed
21 22 23 24 25 26 27 28 29 30
#define EQUAL(func, x, y) \
    ((((func) == stmm_numcmp) || ((func) == stmm_ptrcmp)) ?\
      (STMM_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))


#define do_hash(key, table)\
    ((table->hash == stmm_ptrhash) ? STMM_PTRHASH((key),(table)->num_bins) :\
     (table->hash == stmm_numhash) ? STMM_NUMHASH((key), (table)->num_bins) :\
     (*table->hash)((key), (table)->num_bins))

31 32
static int rehash (stmm_table *table);
//int stmm_numhash (), stmm_ptrhash (), stmm_numcmp (), stmm_ptrcmp ();
Alan Mishchenko committed
33 34

stmm_table *
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)
Alan Mishchenko committed
36 37
{
    int i;
38
    stmm_table *newTable;
Alan Mishchenko committed
39

40 41
    newTable = ABC_ALLOC(stmm_table, 1);
    if (newTable == NULL) {
Alan Mishchenko committed
42
    return NULL;
Alan Mishchenko committed
43
    }
44 45 46 47 48 49
    newTable->compare = compare;
    newTable->hash = hash;
    newTable->num_entries = 0;
    newTable->max_density = density;
    newTable->grow_factor = grow_factor;
    newTable->reorder_flag = reorder_flag;
Alan Mishchenko committed
50 51 52
    if (size <= 0) {
    size = 1;
    }
53 54 55 56
    newTable->num_bins = size;
    newTable->bins = ABC_ALLOC(stmm_table_entry *, size);
    if (newTable->bins == NULL) {
    ABC_FREE(newTable);
Alan Mishchenko committed
57
    return NULL;
Alan Mishchenko committed
58 59
    }
    for (i = 0; i < size; i++) {
60
    newTable->bins[i] = 0;
Alan Mishchenko committed
61 62 63
    }

    // added by alanmi
64 65
    newTable->pMemMan = Extra_MmFixedStart(sizeof (stmm_table_entry));
    return newTable;
Alan Mishchenko committed
66 67 68
}

stmm_table *
69
stmm_init_table (stmm_compare_func_type compare, stmm_hash_func_type hash)
Alan Mishchenko committed
70 71 72 73 74 75 76 77 78
{
    return stmm_init_table_with_params (compare, hash,
                    STMM_DEFAULT_INIT_TABLE_SIZE,
                    STMM_DEFAULT_MAX_DENSITY,
                    STMM_DEFAULT_GROW_FACTOR,
                    STMM_DEFAULT_REORDER_FLAG);
}

void
79
stmm_free_table (stmm_table *table)
Alan Mishchenko committed
80 81
{
/*
82
    stmm_table_entry *ptr, *next;
Alan Mishchenko committed
83 84 85 86
    int i;
    for ( i = 0; i < table->num_bins; i++ )
    {
        ptr = table->bins[i];
Alan Mishchenko committed
87
        while ( ptr != NULL )
Alan Mishchenko committed
88 89
        {
            next = ptr->next;
Alan Mishchenko committed
90
            ABC_FREE( ptr );
Alan Mishchenko committed
91 92 93 94 95 96 97
            ptr = next;
        }
    }
*/
    // no need to deallocate entries because they are in the memory manager now
    // added by alanmi
    if ( table->pMemMan )
98
        Extra_MmFixedStop ((Extra_MmFixed_t *)table->pMemMan);
99 100
    ABC_FREE(table->bins);
    ABC_FREE(table);
Alan Mishchenko committed
101 102 103 104
}

// this function recycles all the bins
void
105
stmm_clean (stmm_table *table)
Alan Mishchenko committed
106 107 108 109 110 111 112 113
{
    int i;
    // clean the bins
    for (i = 0; i < table->num_bins; i++)
        table->bins[i] = NULL;
    // reset the parameters
    table->num_entries = 0;
    // restart the memory manager
114
    Extra_MmFixedRestart ((Extra_MmFixed_t *)table->pMemMan);
Alan Mishchenko committed
115 116 117 118
}


#define PTR_NOT_EQUAL(table, ptr, user_key)\
Alan Mishchenko committed
119
(ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
Alan Mishchenko committed
120 121 122 123 124 125 126

#define FIND_ENTRY(table, hash_val, key, ptr, last) \
    (last) = &(table)->bins[hash_val];\
    (ptr) = *(last);\
    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
    (last) = &(ptr)->next; (ptr) = *(last);\
    }\
Alan Mishchenko committed
127
    if ((ptr) != NULL && (table)->reorder_flag) {\
Alan Mishchenko committed
128 129 130 131 132 133
    *(last) = (ptr)->next;\
    (ptr)->next = (table)->bins[hash_val];\
    (table)->bins[hash_val] = (ptr);\
    }

int
134
stmm_lookup (stmm_table *table, char *key, char **value)
Alan Mishchenko committed
135 136
{
    int hash_val;
137
    stmm_table_entry *ptr, **last;
Alan Mishchenko committed
138 139 140 141 142

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
143
    if (ptr == NULL) {
Alan Mishchenko committed
144 145 146
    return 0;
    }
    else {
Alan Mishchenko committed
147
    if (value != NULL)
Alan Mishchenko committed
148 149 150 151 152 153 154 155
    {
        *value = ptr->record;
    }
    return 1;
    }
}

int
156
stmm_lookup_int (stmm_table *table, char *key, int *value)
Alan Mishchenko committed
157 158
{
    int hash_val;
159
    stmm_table_entry *ptr, **last;
Alan Mishchenko committed
160 161 162 163 164

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
165
    if (ptr == NULL) {
Alan Mishchenko committed
166 167 168
    return 0;
    }
    else {
Alan Mishchenko committed
169
    if (value != 0)
Alan Mishchenko committed
170 171 172 173 174 175 176 177
    {
        *value = (long) ptr->record;
    }
    return 1;
    }
}

// This macro contained a line
Alan Mishchenko committed
178
//    new = ABC_ALLOC(stmm_table_entry, 1);
Alan Mishchenko committed
179 180 181 182 183 184 185 186 187 188 189
// which was modified by alanmi


/* This macro does not check if memory allocation fails. Use at you own risk */
#define ADD_DIRECT(table, key, value, hash_val, new)\
{\
    if (table->num_entries/table->num_bins >= table->max_density) {\
    rehash(table);\
    hash_val = do_hash(key,table);\
    }\
    \
190
    new = (stmm_table_entry *)Extra_MmFixedEntryFetch( (Extra_MmFixed_t *)table->pMemMan );\
Alan Mishchenko committed
191 192 193 194 195 196 197 198 199
    \
    new->key = key;\
    new->record = value;\
    new->next = table->bins[hash_val];\
    table->bins[hash_val] = new;\
    table->num_entries++;\
}

int
200
stmm_insert (stmm_table *table, char *key, char *value)
Alan Mishchenko committed
201 202
{
    int hash_val;
203
    stmm_table_entry *newEntry;
204
    stmm_table_entry *ptr, **last;
Alan Mishchenko committed
205 206 207 208 209

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
210
    if (ptr == NULL) {
Alan Mishchenko committed
211 212 213 214 215 216 217
    if (table->num_entries / table->num_bins >= table->max_density) {
        if (rehash (table) == STMM_OUT_OF_MEM) {
        return STMM_OUT_OF_MEM;
        }
        hash_val = do_hash (key, table);
    }

218
//              newEntry = ABC_ALLOC( stmm_table_entry, 1 );
219
    newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
220
    if (newEntry == NULL) {
Alan Mishchenko committed
221 222 223
        return STMM_OUT_OF_MEM;
    }

224 225 226 227
    newEntry->key = key;
    newEntry->record = value;
    newEntry->next = table->bins[hash_val];
    table->bins[hash_val] = newEntry;
Alan Mishchenko committed
228 229 230 231 232 233 234 235 236 237
    table->num_entries++;
    return 0;
    }
    else {
    ptr->record = value;
    return 1;
    }
}

int
238
stmm_add_direct (stmm_table *table, char *key, char *value)
Alan Mishchenko committed
239 240
{
    int hash_val;
241
    stmm_table_entry *newEntry;
Alan Mishchenko committed
242 243 244 245 246 247 248 249 250

    hash_val = do_hash (key, table);
    if (table->num_entries / table->num_bins >= table->max_density) {
    if (rehash (table) == STMM_OUT_OF_MEM) {
        return STMM_OUT_OF_MEM;
    }
    }
    hash_val = do_hash (key, table);

251
//      newEntry = ABC_ALLOC( stmm_table_entry, 1 );
252
    newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
253
    if (newEntry == NULL) {
Alan Mishchenko committed
254 255 256
    return STMM_OUT_OF_MEM;
    }

257 258 259 260
    newEntry->key = key;
    newEntry->record = value;
    newEntry->next = table->bins[hash_val];
    table->bins[hash_val] = newEntry;
Alan Mishchenko committed
261 262 263 264 265
    table->num_entries++;
    return 1;
}

int
266
stmm_find_or_add (stmm_table *table, char *key, char ***slot)
Alan Mishchenko committed
267 268
{
    int hash_val;
269
    stmm_table_entry *newEntry, *ptr, **last;
Alan Mishchenko committed
270 271 272 273 274

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
275
    if (ptr == NULL) {
Alan Mishchenko committed
276 277 278 279 280 281 282
    if (table->num_entries / table->num_bins >= table->max_density) {
        if (rehash (table) == STMM_OUT_OF_MEM) {
        return STMM_OUT_OF_MEM;
        }
        hash_val = do_hash (key, table);
    }

283
    // newEntry = ABC_ALLOC( stmm_table_entry, 1 );
284
    newEntry = (stmm_table_entry *) Extra_MmFixedEntryFetch ((Extra_MmFixed_t *)table->pMemMan);
285
    if (newEntry == NULL) {
Alan Mishchenko committed
286 287 288
        return STMM_OUT_OF_MEM;
    }

289 290 291 292
    newEntry->key = key;
    newEntry->record = (char *) 0;
    newEntry->next = table->bins[hash_val];
    table->bins[hash_val] = newEntry;
Alan Mishchenko committed
293
    table->num_entries++;
Alan Mishchenko committed
294
    if (slot != NULL)
295
         *slot = &newEntry->record;
Alan Mishchenko committed
296 297 298
    return 0;
    }
    else {
Alan Mishchenko committed
299
    if (slot != NULL)
Alan Mishchenko committed
300 301 302 303 304 305
         *slot = &ptr->record;
    return 1;
    }
}

int
306
stmm_find (stmm_table *table, char *key, char ***slot)
Alan Mishchenko committed
307 308 309 310 311 312 313 314
{
    int hash_val;
    stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
315
    if (ptr == NULL) {
Alan Mishchenko committed
316 317 318
    return 0;
    }
    else {
Alan Mishchenko committed
319
    if (slot != NULL)
Alan Mishchenko committed
320 321 322 323 324 325 326 327
    {
        *slot = &ptr->record;
    }
    return 1;
    }
}

static int
328
rehash (stmm_table *table)
Alan Mishchenko committed
329
{
330
    stmm_table_entry *ptr, *next, **old_bins;
Alan Mishchenko committed
331 332 333 334 335 336 337 338 339 340 341 342 343
    int i, old_num_bins, hash_val, old_num_entries;

    /* save old values */
    old_bins = table->bins;
    old_num_bins = table->num_bins;
    old_num_entries = table->num_entries;

    /* rehash */
    table->num_bins = (int) (table->grow_factor * old_num_bins);
    if (table->num_bins % 2 == 0) {
    table->num_bins += 1;
    }
    table->num_entries = 0;
Alan Mishchenko committed
344
    table->bins = ABC_ALLOC(stmm_table_entry *, table->num_bins);
Alan Mishchenko committed
345
    if (table->bins == NULL) {
Alan Mishchenko committed
346 347 348 349 350 351 352 353 354 355 356 357 358
    table->bins = old_bins;
    table->num_bins = old_num_bins;
    table->num_entries = old_num_entries;
    return STMM_OUT_OF_MEM;
    }
    /* initialize */
    for (i = 0; i < table->num_bins; i++) {
    table->bins[i] = 0;
    }

    /* copy data over */
    for (i = 0; i < old_num_bins; i++) {
    ptr = old_bins[i];
Alan Mishchenko committed
359
    while (ptr != NULL) {
Alan Mishchenko committed
360 361 362 363 364 365 366 367
        next = ptr->next;
        hash_val = do_hash (ptr->key, table);
        ptr->next = table->bins[hash_val];
        table->bins[hash_val] = ptr;
        table->num_entries++;
        ptr = next;
    }
    }
368
    ABC_FREE(old_bins);
Alan Mishchenko committed
369 370 371 372 373

    return 1;
}

stmm_table *
374
stmm_copy (stmm_table *old_table)
Alan Mishchenko committed
375
{
376 377
    stmm_table *newEntry_table;
    stmm_table_entry *ptr, /* *newEntryptr, *next, */ *newEntry;
Alan Mishchenko committed
378 379
    int i, /*j, */ num_bins = old_table->num_bins;

380 381
    newEntry_table = ABC_ALLOC(stmm_table, 1);
    if (newEntry_table == NULL) {
Alan Mishchenko committed
382
    return NULL;
Alan Mishchenko committed
383 384
    }

385 386 387 388
    *newEntry_table = *old_table;
    newEntry_table->bins = ABC_ALLOC(stmm_table_entry *, num_bins);
    if (newEntry_table->bins == NULL) {
    ABC_FREE(newEntry_table);
Alan Mishchenko committed
389
    return NULL;
Alan Mishchenko committed
390 391
    }

392
    // allocate the memory manager for the newEntry table
393
    newEntry_table->pMemMan = Extra_MmFixedStart (sizeof (stmm_table_entry));
Alan Mishchenko committed
394 395

    for (i = 0; i < num_bins; i++) {
396
    newEntry_table->bins[i] = NULL;
Alan Mishchenko committed
397
    ptr = old_table->bins[i];
Alan Mishchenko committed
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) {
Alan Mishchenko committed
402 403 404
/*
                for ( j = 0; j <= i; j++ )
                {
405 406
                    newEntryptr = newEntry_table->bins[j];
                    while ( newEntryptr != NULL )
Alan Mishchenko committed
407
                    {
408 409 410
                        next = newEntryptr->next;
                        ABC_FREE( newEntryptr );
                        newEntryptr = next;
Alan Mishchenko committed
411 412 413
                    }
                }
*/
414
        Extra_MmFixedStop ((Extra_MmFixed_t *)newEntry_table->pMemMan);
Alan Mishchenko committed
415

416 417
        ABC_FREE(newEntry_table->bins);
        ABC_FREE(newEntry_table);
Alan Mishchenko committed
418
        return NULL;
Alan Mishchenko committed
419
        }
420 421 422
        *newEntry = *ptr;
        newEntry->next = newEntry_table->bins[i];
        newEntry_table->bins[i] = newEntry;
Alan Mishchenko committed
423 424 425
        ptr = ptr->next;
    }
    }
426
    return newEntry_table;
Alan Mishchenko committed
427 428 429
}

int
430
stmm_delete (stmm_table *table, char **keyp, char **value)
Alan Mishchenko committed
431 432 433
{
    int hash_val;
    char *key = *keyp;
434
    stmm_table_entry *ptr, **last;
Alan Mishchenko committed
435 436 437 438 439

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
440
    if (ptr == NULL) {
Alan Mishchenko committed
441 442 443 444
    return 0;
    }

    *last = ptr->next;
Alan Mishchenko committed
445
    if (value != NULL)
Alan Mishchenko committed
446 447
     *value = ptr->record;
    *keyp = ptr->key;
Alan Mishchenko committed
448
//      ABC_FREE( ptr );
449
    Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
Alan Mishchenko committed
450 451 452 453 454 455

    table->num_entries--;
    return 1;
}

int
456
stmm_delete_int (stmm_table *table, long *keyp, char **value)
Alan Mishchenko committed
457 458 459
{
    int hash_val;
    char *key = (char *) *keyp;
460
    stmm_table_entry *ptr, **last;
Alan Mishchenko committed
461 462 463 464 465

    hash_val = do_hash (key, table);

    FIND_ENTRY (table, hash_val, key, ptr, last);

Alan Mishchenko committed
466
    if (ptr == NULL) {
Alan Mishchenko committed
467 468 469 470
    return 0;
    }

    *last = ptr->next;
Alan Mishchenko committed
471
    if (value != NULL)
Alan Mishchenko committed
472 473
     *value = ptr->record;
    *keyp = (long) ptr->key;
Alan Mishchenko committed
474
//      ABC_FREE( ptr );
475
    Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
Alan Mishchenko committed
476 477 478 479 480 481

    table->num_entries--;
    return 1;
}

int
482
stmm_foreach (stmm_table *table, enum stmm_retval (*func) (char *, char *, char *), char *arg)
Alan Mishchenko committed
483 484 485 486 487 488 489 490
{
    stmm_table_entry *ptr, **last;
    enum stmm_retval retval;
    int i;

    for (i = 0; i < table->num_bins; i++) {
    last = &table->bins[i];
    ptr = *last;
Alan Mishchenko committed
491
    while (ptr != NULL) {
Alan Mishchenko committed
492 493 494 495 496 497 498 499 500 501
        retval = (*func) (ptr->key, ptr->record, arg);
        switch (retval) {
        case STMM_CONTINUE:
        last = &ptr->next;
        ptr = *last;
        break;
        case STMM_STOP:
        return 0;
        case STMM_DELETE:
        *last = ptr->next;
502
        table->num_entries--;   /* cstevens@ic */
Alan Mishchenko committed
503
//                              ABC_FREE( ptr );
504
        Extra_MmFixedEntryRecycle ((Extra_MmFixed_t *)table->pMemMan, (char *) ptr);
Alan Mishchenko committed
505 506 507 508 509 510 511 512 513

        ptr = *last;
        }
    }
    }
    return 1;
}

int
514
stmm_strhash (const char *string, int modulus)
Alan Mishchenko committed
515
{
516 517
    int val = 0;
    int c;
Alan Mishchenko committed
518 519 520 521 522 523 524 525 526

    while ((c = *string++) != '\0') {
    val = val * 997 + c;
    }

    return ((val < 0) ? -val : val) % modulus;
}

int
527
stmm_numhash (const char *x, int size)
Alan Mishchenko committed
528 529 530 531 532
{
    return STMM_NUMHASH (x, size);
}

int
533
stmm_ptrhash (const char *x, int size)
Alan Mishchenko committed
534 535 536 537 538
{
    return STMM_PTRHASH (x, size);
}

int
539
stmm_numcmp (const char *x, const char *y)
Alan Mishchenko committed
540 541 542 543 544
{
    return STMM_NUMCMP (x, y);
}

int
545
stmm_ptrcmp (const char *x, const char *y)
Alan Mishchenko committed
546 547 548 549 550
{
    return STMM_NUMCMP (x, y);
}

stmm_generator *
551
stmm_init_gen (stmm_table *table)
Alan Mishchenko committed
552 553 554
{
    stmm_generator *gen;

Alan Mishchenko committed
555
    gen = ABC_ALLOC(stmm_generator, 1);
Alan Mishchenko committed
556 557
    if (gen == NULL) {
    return NULL;
Alan Mishchenko committed
558 559
    }
    gen->table = table;
Alan Mishchenko committed
560
    gen->entry = NULL;
Alan Mishchenko committed
561 562 563 564 565 566
    gen->index = 0;
    return gen;
}


int
567
stmm_gen (stmm_generator *gen, char **key_p, char **value_p)
Alan Mishchenko committed
568
{
569
    int i;
Alan Mishchenko committed
570

Alan Mishchenko committed
571
    if (gen->entry == NULL) {
Alan Mishchenko committed
572 573
    /* try to find next entry */
    for (i = gen->index; i < gen->table->num_bins; i++) {
Alan Mishchenko committed
574
        if (gen->table->bins[i] != NULL) {
Alan Mishchenko committed
575 576 577 578 579
        gen->index = i + 1;
        gen->entry = gen->table->bins[i];
        break;
        }
    }
Alan Mishchenko committed
580
    if (gen->entry == NULL) {
581
        return 0;       /* that's all folks ! */
Alan Mishchenko committed
582 583 584 585 586 587 588 589 590 591 592 593
    }
    }
    *key_p = gen->entry->key;
    if (value_p != 0) {
    *value_p = gen->entry->record;
    }
    gen->entry = gen->entry->next;
    return 1;
}


int
594
stmm_gen_int (stmm_generator *gen, char **key_p, long *value_p)
Alan Mishchenko committed
595
{
596
    int i;
Alan Mishchenko committed
597

Alan Mishchenko committed
598
    if (gen->entry == NULL) {
Alan Mishchenko committed
599 600
    /* try to find next entry */
    for (i = gen->index; i < gen->table->num_bins; i++) {
Alan Mishchenko committed
601
        if (gen->table->bins[i] != NULL) {
Alan Mishchenko committed
602 603 604 605 606
        gen->index = i + 1;
        gen->entry = gen->table->bins[i];
        break;
        }
    }
Alan Mishchenko committed
607
    if (gen->entry == NULL) {
608
        return 0;       /* that's all folks ! */
Alan Mishchenko committed
609 610 611
    }
    }
    *key_p = gen->entry->key;
Alan Mishchenko committed
612
    if (value_p != 0)
Alan Mishchenko committed
613 614 615 616 617 618 619 620 621
    {
    *value_p = (long) gen->entry->record;
    }
    gen->entry = gen->entry->next;
    return 1;
}


void
622
stmm_free_gen (stmm_generator *gen)
Alan Mishchenko committed
623
{
624
    ABC_FREE(gen);
Alan Mishchenko committed
625
}
626 627
ABC_NAMESPACE_IMPL_END