Subversion Repositories openrisc_2011-10-31

/*

 * sym.c -- Symbol Table module

 *

 * Copyright (c) GoAhead Software Inc., 1995-1999. All Rights Reserved.

 *

 * See the file "license.txt" for usage and redistribution license requirements

 */

/******************************** Description *********************************/

/*

 *      This module implements a highly efficient generic symbol table with

 *      update and access routines.  Symbols are simple character strings and

 *      the values they take can be flexible types as defined by value_t.

 *      This modules allows multiple symbol tables to be created.

 */

/********************************* Includes ***********************************/

#if UEMF

        #include        "uemf.h"

#else

        #include        "basic/basicInternal.h"

#endif

/********************************* Defines ************************************/

typedef struct {                                                /* Symbol table descriptor */

        int             inuse;                                          /* Is this entry in use */

        int             hash_size;                                      /* Size of the table below */

        sym_t   **hash_table;                           /* Allocated at run time */

} sym_tabent_t;

/********************************* Globals ************************************/

static sym_tabent_t             **sym;                  /* List of symbol tables */

static int                              sym_max;                /* One past the max symbol table */

static int              htIndex;                                /* Current location in table */

static sym_t*   next;                                   /* Next symbol in iteration */

/**************************** Forward Declarations ****************************/

static int              hashIndex(sym_tabent_t *tp, char_t *name);

static sym_t    *hash(sym_tabent_t *tp, char_t *name);

static int              calc_prime(int size);

/*********************************** Code *************************************/

/*

 *      Create a symbol table.

 */

sym_fd_t symOpen(int hash_size)

{

        sym_fd_t                sd;

        sym_tabent_t    *tp;

        a_assert(hash_size > 2);

/*

 *      Create a new handle for this symbol table

 */

        if ((sd = hAlloc((void***) &sym)) < 0) {

                return -1;

        }

/*

 *      Create a new symbol table structure and zero

 */

        if ((tp = (sym_tabent_t*) balloc(B_L, sizeof(sym_tabent_t))) == NULL) {

                sym_max = hFree((void***) &sym, sd);

                return -1;

        }

        memset(tp, 0, sizeof(sym_tabent_t));

        if (sd >= sym_max) {

                sym_max = sd + 1;

        }

        a_assert(0 <= sd && sd < sym_max);

        sym[sd] = tp;

/*

 *      Now create the hash table for fast indexing.

 */

        tp->hash_size = calc_prime(hash_size);

        tp->hash_table = (sym_t**) balloc(B_L, tp->hash_size * sizeof(sym_t*));

        a_assert(tp->hash_table);

        memset(tp->hash_table, 0, tp->hash_size * sizeof(sym_t*));

        return sd;

}

/******************************************************************************/

/*

 *      Close this symbol table. Call a cleanup function to allow the caller

 *      to free resources associated with each symbol table entry.

 */

void symClose(sym_fd_t sd, void (*cleanup)(sym_t *symp))

{

        sym_tabent_t    *tp;

        sym_t                   *sp, *forw;

        int                     i;

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

/*

 *      Free all symbols in the hash table, then the hash table itself.

 */

        for (i = 0; i < tp->hash_size; i++) {

                for (sp = tp->hash_table[i]; sp; sp = forw) {

                        forw = sp->forw;

                        if (cleanup) {

                                (*cleanup)(sp);

                        }

                        valueFree(&sp->name);

                        bfree(B_L, (void*) sp);

                        sp = forw;

                }

        }

        bfree(B_L, (void*) tp->hash_table);

        sym_max = hFree((void***) &sym, sd);

        bfree(B_L, (void*) tp);

}

/******************************************************************************/

/*

 *      Default callback for freeing the value.

 */

void symFreeVar(sym_t* sp)

{

        valueFree(&sp->content);

}

/******************************************************************************/

/*

 *      Return the first symbol in the hashtable if there is one. This call is used

 *      as the first step in traversing the table. A call to symFirst should be

 *      followed by calls to symNext to get all the rest of the entries.

 */

sym_t* symFirst(sym_fd_t sd)

{

        sym_tabent_t    *tp;

        sym_t                   *sp, *forw;

        int                     i;

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

/*

 *      Find the first symbol in the hashtable and return a pointer to it.

 */

        for (i = 0; i < tp->hash_size; i++) {

                for (sp = tp->hash_table[i]; sp; sp = forw) {

                        forw = sp->forw;

                        if (forw == NULL) {

                                htIndex = i + 1;

                                next = tp->hash_table[htIndex];

                        } else {

                                htIndex = i;

                                next = forw;

                        }

                        return sp;

                }

        }

        return NULL;

}

/******************************************************************************/

/*

 *      Return the next symbol in the hashtable if there is one. See symFirst.

 */

sym_t* symNext(sym_fd_t sd)

{

        sym_tabent_t    *tp;

        sym_t                   *sp, *forw;

        int                     i;

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

/*

 *      Find the first symbol in the hashtable and return a pointer to it.

 */

        for (i = htIndex; i < tp->hash_size; i++) {

                for (sp = next; sp; sp = forw) {

                        forw = sp->forw;

                        if (forw == NULL) {

                                htIndex = i + 1;

                                next = tp->hash_table[htIndex];

                        } else {

                                htIndex = i;

                                next = forw;

                        }

                        return sp;

                }

                next = tp->hash_table[i + 1];

        }

        return NULL;

}

/******************************************************************************/

/*

 *      Lookup a symbol and return a pointer to the symbol entry. If not present

 *      then return a NULL.

 */

sym_t *symLookup(sym_fd_t sd, char_t *name)

{

        sym_tabent_t    *tp;

        sym_t                   *sp;

        char_t                  *cp;

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

        if (name == NULL || *name == '\0') {

                return NULL;

        }

/*

 *      Do an initial hash and then follow the link chain to find the right entry

 */

        for (sp = hash(tp, name); sp; sp = sp->forw) {

                cp = sp->name.value.string;

                if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {

                        break;

                }

        }

        return sp;

}

/******************************************************************************/

/*

 *      Enter a symbol into the table.  If already there, update its value.

 *      Always succeeds if memory available.

 */

sym_t *symEnter(sym_fd_t sd, char_t *name, value_t v, int arg)

{

        sym_tabent_t    *tp;

        sym_t                   *sp, *last;

        char_t                  *cp;

        int                             hindex;

        a_assert(name && *name);

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

/*

 *      Calculate the first daisy-chain from the hash table.  If non-zero, then

 *      we have daisy-chain, so scan it and look for the symbol.

 */

        last = NULL;

        hindex = hashIndex(tp, name);

        if ((sp = tp->hash_table[hindex]) != NULL) {

                for (; sp; sp = sp->forw) {

                        cp = sp->name.value.string;

                        if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {

                                break;

                        }

                        last = sp;

                }

                if (sp) {

/*

 *                      Found, so update the value

 *                      If the caller stores handles which require freeing, they

 *                      will be lost here. It is the callers responsibility to free

 *                      resources before overwriting existing contents. We will here

 *                      free allocated strings which occur due to value_instring().

 *                      We should consider providing the cleanup function on the open rather

 *                      than the close and then we could call it here and solve the problem.

 */

                        if (sp->content.valid) {

                                valueFree(&sp->content);

                        }

                        sp->content = v;

                        sp->arg = arg;

                        return sp;

                }

/*

 *              Not found so allocate and append to the daisy-chain

 */

                sp = (sym_t*) balloc(B_L, sizeof(sym_t));

                if (sp == NULL) {

                        return NULL;

                }

                sp->name = valueString(name, VALUE_ALLOCATE);

                sp->content = v;

                sp->forw = (sym_t*) NULL;

                sp->arg = arg;

                last->forw = sp;

        } else {

/*

 *              Daisy chain is empty so we need to start the chain

 */

                sp = (sym_t*) balloc(B_L, sizeof(sym_t));

                if (sp == NULL) {

                        return NULL;

                }

                tp->hash_table[hindex] = sp;

                tp->hash_table[hashIndex(tp, name)] = sp;

                sp->forw = (sym_t*) NULL;

                sp->content = v;

                sp->arg = arg;

                sp->name = valueString(name, VALUE_ALLOCATE);

        }

        return sp;

}

/******************************************************************************/

/*

 *      Delete a symbol from a table

 */

int symDelete(sym_fd_t sd, char_t *name)

{

        sym_tabent_t    *tp;

        sym_t                   *sp, *last;

        char_t                  *cp;

        int                             hindex;

        a_assert(name && *name);

        a_assert(0 <= sd && sd < sym_max);

        tp = sym[sd];

        a_assert(tp);

/*

 *      Calculate the first daisy-chain from the hash table.  If non-zero, then

 *      we have daisy-chain, so scan it and look for the symbol.

 */

        last = NULL;

        hindex = hashIndex(tp, name);

        if ((sp = tp->hash_table[hindex]) != NULL) {

                for ( ; sp; sp = sp->forw) {

                        cp = sp->name.value.string;

                        if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {

                                break;

                        }

                        last = sp;

                }

        }

        if (sp == (sym_t*) NULL) {                              /* Not Found */

                return -1;

        }

/*

 *      Unlink and free the symbol. Last will be set if the element to be deleted

 *      is not first in the chain.

 */

        if (last) {

                last->forw = sp->forw;

        } else {

                tp->hash_table[hindex] = sp->forw;

        }

        valueFree(&sp->name);

        bfree(B_L, (void*) sp);

        return 0;

}

/******************************************************************************/

/*

 *      Hash a symbol and return a pointer to the hash daisy-chain list

 *      All symbols reside on the chain (ie. none stored in the hash table itself)

 */

static sym_t *hash(sym_tabent_t *tp, char_t *name)

{

        a_assert(tp);

        return tp->hash_table[hashIndex(tp, name)];

}

/******************************************************************************/

/*

 *      Compute the hash function and return an index into the hash table

 *      We use a basic additive function that is then made modulo the size of the

 *      table.

 */

static int hashIndex(sym_tabent_t *tp, char_t *name)

{

        unsigned int    sum;

        int                     i;

        a_assert(tp);

/*

 *      Add in each character shifted up progressively by 7 bits. The shift

 *      amount is rounded so as to not shift too far.  It thus cycles with each

 *      new cycle placing character shifted up by one bit.

 */

        i = 0;

        sum = 0;

        while (*name) {

                sum += (((int) *name++) << i);

                i = (i + 7) % (BITS(int) - BITSPERBYTE);

        }

        return sum % tp->hash_size;

}

/******************************************************************************/

/*

 *      Check if this number is a prime

 */

static int is_prime(int n)

{

        int     i;

        a_assert(n > 0);

        for (i = 2; i < n; i++) {

                if (n % i == 0) {

                        return 0;

                }

        }

        return 1;

}

/******************************************************************************/

/*

 *      Calculate the largest prime smaller than size.

 */

static int calc_prime(int size)

{

        int count;

        a_assert(size > 0);

        for (count = size; count > 0; count--) {

                if (is_prime(count)) {

                        return count;

                }

        }

        return 1;

}

/******************************************************************************/