src/misc/st/stmm.c File Reference

#include <stdio.h>
#include "extra.h"
#include "stmm.h"

Include dependency graph for stmm.c:

Go to the source code of this file.

Defines
#define	STMM_NUMCMP(x, y)   ((x) != (y))
#define	STMM_NUMHASH(x, size)   (ABS((long)x)%(size))
#define	STMM_PTRHASH(x, size)   ((int)(((unsigned long)(x)>>2)%size))
#define	EQUAL(func, x, y)
#define	do_hash(key, table)
#define	PTR_NOT_EQUAL(table, ptr, user_key)   (ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
#define	FIND_ENTRY(table, hash_val, key, ptr, last)
#define	ADD_DIRECT(table, key, value, hash_val, new)
Functions
static int	rehash ()
int	stmm_numhash ()
int	stmm_ptrhash ()
int	stmm_numcmp ()
int	stmm_ptrcmp ()
stmm_table *	stmm_init_table_with_params (int(*)() compare, int(*)() hash, int size, int density, double grow_factor, int reorder_flag)
stmm_table *	stmm_init_table (int(*)() compare, int(*)() hash)
void	stmm_free_table (stmm_table *table)
void	stmm_clean (stmm_table *table)
int	stmm_lookup (stmm_table *table, char *key, char **value)
int	stmm_lookup_int (stmm_table *table, char *key, int *value)
int	stmm_insert (stmm_table *table, char *key, char *value)
int	stmm_add_direct (stmm_table *table, char *key, char *value)
int	stmm_find_or_add (stmm_table *table, char *key, char ***slot)
int	stmm_find (stmm_table *table, char *key, char ***slot)
static int	rehash (stmm_table *table)
stmm_table *	stmm_copy (stmm_table *old_table)
int	stmm_delete (stmm_table *table, char **keyp, char **value)
int	stmm_delete_int (stmm_table *table, long *keyp, char **value)
int	stmm_foreach (stmm_table *table, enum stmm_retval(*)() func, char *arg)
int	stmm_strhash (char *string, int modulus)
int	stmm_numhash (char *x, int size)
int	stmm_ptrhash (char *x, int size)
int	stmm_numcmp (char *x, char *y)
int	stmm_ptrcmp (char *x, char *y)
stmm_generator *	stmm_init_gen (stmm_table *table)
int	stmm_gen (stmm_generator *gen, char **key_p, char **value_p)
int	stmm_gen_int (stmm_generator *gen, char **key_p, long *value_p)
void	stmm_free_gen (stmm_generator *gen)

---

Define Documentation

#define ADD_DIRECT	(	table,
		key,
		value,
		hash_val,
		new		)

Value:

{\
    if (table->num_entries/table->num_bins >= table->max_density) {\
        rehash(table);\
        hash_val = do_hash(key,table);\
    }\
    \
    new = (stmm_table_entry *)Extra_MmFixedEntryFetch( table->pMemMan );\
    \
    new->key = key;\
    new->record = value;\
    new->next = table->bins[hash_val];\
    table->bins[hash_val] = new;\
    table->num_entries++;\
}

Definition at line 201 of file stmm.c.

#define do_hash	(	key,
		table		)

Value:

((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))

Definition at line 27 of file stmm.c.

#define EQUAL	(	func,
		x,
		y		)

Value:

((((func) == stmm_numcmp) || ((func) == stmm_ptrcmp)) ?\
      (STMM_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))

Definition at line 22 of file stmm.c.

#define FIND_ENTRY	(	table,
		hash_val,
		key,
		ptr,
		last		)

Value:

(last) = &(table)->bins[hash_val];\
    (ptr) = *(last);\
    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
        (last) = &(ptr)->next; (ptr) = *(last);\
    }\
    if ((ptr) != NULL && (table)->reorder_flag) {\
        *(last) = (ptr)->next;\
        (ptr)->next = (table)->bins[hash_val];\
        (table)->bins[hash_val] = (ptr);\
    }

Definition at line 133 of file stmm.c.

#define PTR_NOT_EQUAL	(	table,
		ptr,
		user_key		)	(ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))

Definition at line 130 of file stmm.c.

#define STMM_NUMCMP	(	x,
		y		)	((x) != (y))

Definition at line 18 of file stmm.c.

#define STMM_NUMHASH	(	x,
		size		)	(ABS((long)x)%(size))

Definition at line 19 of file stmm.c.

#define STMM_PTRHASH	(	x,
		size		)	((int)(((unsigned long)(x)>>2)%size))

Definition at line 21 of file stmm.c.

---

Function Documentation

static int rehash

(

stmm_table *

table

)

[static]

Definition at line 358 of file stmm.c.

{
    register stmm_table_entry *ptr, *next, **old_bins;
    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;
    table->bins = ALLOC (stmm_table_entry *, table->num_bins);
    if (table->bins == NULL) {
        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];
        while (ptr != NULL) {
            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;
        }
    }
    FREE (old_bins);

    return 1;
}

static int rehash

(

)

[static]

int stmm_add_direct	(	stmm_table *	table,
		char *	key,
		char *	value
	)

Definition at line 259 of file stmm.c.

{
    int hash_val;
    stmm_table_entry *new;

    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);

//      new = ALLOC( stmm_table_entry, 1 );
    new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
    if (new == NULL) {
        return STMM_OUT_OF_MEM;
    }

    new->key = key;
    new->record = value;
    new->next = table->bins[hash_val];
    table->bins[hash_val] = new;
    table->num_entries++;
    return 1;
}

void stmm_clean

(

stmm_table *

table

)

Definition at line 116 of file stmm.c.

{
    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
    Extra_MmFixedRestart (table->pMemMan);
}

stmm_table* stmm_copy

(

stmm_table *

old_table

)

Definition at line 405 of file stmm.c.

{
    stmm_table *new_table;
    stmm_table_entry *ptr, /* *newptr, *next, */ *new;
    int i, /*j, */ num_bins = old_table->num_bins;

    new_table = ALLOC (stmm_table, 1);
    if (new_table == NULL) {
        return NULL;
    }

    *new_table = *old_table;
    new_table->bins = ALLOC (stmm_table_entry *, num_bins);
    if (new_table->bins == NULL) {
        FREE (new_table);
        return NULL;
    }

    // allocate the memory manager for the new table
    new_table->pMemMan =
        Extra_MmFixedStart (sizeof (stmm_table_entry));

    for (i = 0; i < num_bins; i++) {
        new_table->bins[i] = NULL;
        ptr = old_table->bins[i];
        while (ptr != NULL) {
//                      new = ALLOC( stmm_table_entry, 1 );
            new =
                (stmm_table_entry *) Extra_MmFixedEntryFetch (new_table->
                                                            pMemMan);

            if (new == NULL) {
/*
                                for ( j = 0; j <= i; j++ )
                                {
                                        newptr = new_table->bins[j];
                                        while ( newptr != NULL )
                                        {
                                                next = newptr->next;
                                                FREE( newptr );
                                                newptr = next;
                                        }
                                }
*/
                Extra_MmFixedStop (new_table->pMemMan);

                FREE (new_table->bins);
                FREE (new_table);
                return NULL;
            }
            *new = *ptr;
            new->next = new_table->bins[i];
            new_table->bins[i] = new;
            ptr = ptr->next;
        }
    }
    return new_table;
}

int stmm_delete	(	stmm_table *	table,
		char **	keyp,
		char **	value
	)

Definition at line 466 of file stmm.c.

{
    int hash_val;
    char *key = *keyp;
    register stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        return 0;
    }

    *last = ptr->next;
    if (value != NULL)
         *value = ptr->record;
    *keyp = ptr->key;
//      FREE( ptr );
    Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);

    table->num_entries--;
    return 1;
}

int stmm_delete_int	(	stmm_table *	table,
		long *	keyp,
		char **	value
	)

Definition at line 495 of file stmm.c.

{
    int hash_val;
    char *key = (char *) *keyp;
    register stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        return 0;
    }

    *last = ptr->next;
    if (value != NULL)
         *value = ptr->record;
    *keyp = (long) ptr->key;
//      FREE( ptr );
    Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);

    table->num_entries--;
    return 1;
}

int stmm_find	(	stmm_table *	table,
		char *	key,
		char ***	slot
	)

Definition at line 333 of file stmm.c.

{
    int hash_val;
    stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        return 0;
    }
    else {
        if (slot != NULL)
        {
            *slot = &ptr->record;
        }
        return 1;
    }
}

int stmm_find_or_add	(	stmm_table *	table,
		char *	key,
		char ***	slot
	)

Definition at line 290 of file stmm.c.

{
    int hash_val;
    stmm_table_entry *new, *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        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);
        }

        // new = ALLOC( stmm_table_entry, 1 );
        new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
        if (new == NULL) {
            return STMM_OUT_OF_MEM;
        }

        new->key = key;
        new->record = (char *) 0;
        new->next = table->bins[hash_val];
        table->bins[hash_val] = new;
        table->num_entries++;
        if (slot != NULL)
             *slot = &new->record;
        return 0;
    }
    else {
        if (slot != NULL)
             *slot = &ptr->record;
        return 1;
    }
}

int stmm_foreach	(	stmm_table *	table,
		enum stmm_retval (*) ()	func,
		char *	arg
	)

Definition at line 524 of file stmm.c.

{
    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;
        while (ptr != NULL) {
            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;
                table->num_entries--;   /* cstevens@ic */
//                              FREE( ptr );
                Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);

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

void stmm_free_gen

(

stmm_generator *

gen

)

Definition at line 684 of file stmm.c.

{
    FREE (gen);
}

void stmm_free_table

(

stmm_table *

table

)

Definition at line 89 of file stmm.c.

{
/*
        register stmm_table_entry *ptr, *next;
        int i;
        for ( i = 0; i < table->num_bins; i++ )
        {
                ptr = table->bins[i];
                while ( ptr != NULL )
                {
                        next = ptr->next;
                        FREE( ptr );
                        ptr = next;
                }
        }
*/
    // no need to deallocate entries because they are in the memory manager now
    // added by alanmi
    if ( table->pMemMan )
        Extra_MmFixedStop (table->pMemMan);
    FREE (table->bins);
    FREE (table);
}

int stmm_gen	(	stmm_generator *	gen,
		char **	key_p,
		char **	value_p
	)

Definition at line 623 of file stmm.c.

{
    register int i;

    if (gen->entry == NULL) {
        /* try to find next entry */
        for (i = gen->index; i < gen->table->num_bins; i++) {
            if (gen->table->bins[i] != NULL) {
                gen->index = i + 1;
                gen->entry = gen->table->bins[i];
                break;
            }
        }
        if (gen->entry == NULL) {
            return 0;           /* that's all folks ! */
        }
    }
    *key_p = gen->entry->key;
    if (value_p != 0) {
        *value_p = gen->entry->record;
    }
    gen->entry = gen->entry->next;
    return 1;
}

int stmm_gen_int	(	stmm_generator *	gen,
		char **	key_p,
		long *	value_p
	)

Definition at line 653 of file stmm.c.

{
    register int i;

    if (gen->entry == NULL) {
        /* try to find next entry */
        for (i = gen->index; i < gen->table->num_bins; i++) {
            if (gen->table->bins[i] != NULL) {
                gen->index = i + 1;
                gen->entry = gen->table->bins[i];
                break;
            }
        }
        if (gen->entry == NULL) {
            return 0;           /* that's all folks ! */
        }
    }
    *key_p = gen->entry->key;
    if (value_p != 0)
    {
        *value_p = (long) gen->entry->record;
    }
    gen->entry = gen->entry->next;
    return 1;
}

stmm_generator* stmm_init_gen

(

stmm_table *

table

)

Definition at line 606 of file stmm.c.

{
    stmm_generator *gen;

    gen = ALLOC (stmm_generator, 1);
    if (gen == NULL) {
        return NULL;
    }
    gen->table = table;
    gen->entry = NULL;
    gen->index = 0;
    return gen;
}

stmm_table* stmm_init_table	(	int (*) ()	compare,
		int (*) ()	hash
	)

Definition at line 77 of file stmm.c.

{
    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);
}

stmm_table* stmm_init_table_with_params	(	int (*) ()	compare,
		int (*) ()	hash,
		int	size,
		int	density,
		double	grow_factor,
		int	reorder_flag
	)

Definition at line 36 of file stmm.c.

{
    int i;
    stmm_table *new;

    new = ALLOC (stmm_table, 1);
    if (new == NULL) {
        return NULL;
    }
    new->compare = compare;
    new->hash = hash;
    new->num_entries = 0;
    new->max_density = density;
    new->grow_factor = grow_factor;
    new->reorder_flag = reorder_flag;
    if (size <= 0) {
        size = 1;
    }
    new->num_bins = size;
    new->bins = ALLOC (stmm_table_entry *, size);
    if (new->bins == NULL) {
        FREE (new);
        return NULL;
    }
    for (i = 0; i < size; i++) {
        new->bins[i] = 0;
    }

    // added by alanmi
    new->pMemMan = Extra_MmFixedStart(sizeof (stmm_table_entry));
    return new;
}

int stmm_insert	(	stmm_table *	table,
		char *	key,
		char *	value
	)

Definition at line 218 of file stmm.c.

{
    int hash_val;
    stmm_table_entry *new;
    register stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        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);
        }

//              new = ALLOC( stmm_table_entry, 1 );
        new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
        if (new == NULL) {
            return STMM_OUT_OF_MEM;
        }

        new->key = key;
        new->record = value;
        new->next = table->bins[hash_val];
        table->bins[hash_val] = new;
        table->num_entries++;
        return 0;
    }
    else {
        ptr->record = value;
        return 1;
    }
}

int stmm_lookup	(	stmm_table *	table,
		char *	key,
		char **	value
	)

Definition at line 146 of file stmm.c.

{
    int hash_val;
    register stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        return 0;
    }
    else {
        if (value != NULL)
        {
            *value = ptr->record;
        }
        return 1;
    }
}

int stmm_lookup_int	(	stmm_table *	table,
		char *	key,
		int *	value
	)

Definition at line 171 of file stmm.c.

{
    int hash_val;
    register stmm_table_entry *ptr, **last;

    hash_val = do_hash (key, table);

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

    if (ptr == NULL) {
        return 0;
    }
    else {
        if (value != 0)
        {
            *value = (long) ptr->record;
        }
        return 1;
    }
}

int stmm_numcmp	(	char *	x,
		char *	y
	)

Definition at line 590 of file stmm.c.

{
    return STMM_NUMCMP (x, y);
}

int stmm_numcmp

(

)

int stmm_numhash	(	char *	x,
		int	size
	)

Definition at line 574 of file stmm.c.

{
    return STMM_NUMHASH (x, size);
}

int stmm_numhash

(

)

int stmm_ptrcmp	(	char *	x,
		char *	y
	)

Definition at line 598 of file stmm.c.

{
    return STMM_NUMCMP (x, y);
}

int stmm_ptrcmp

(

)

int stmm_ptrhash	(	char *	x,
		int	size
	)

Definition at line 582 of file stmm.c.

{
    return STMM_PTRHASH (x, size);
}

int stmm_ptrhash

(

)

int stmm_strhash	(	char *	string,
		int	modulus
	)

Definition at line 559 of file stmm.c.

{
    register int val = 0;
    register int c;

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

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