source: rtems/cpukit/httpd/sym.c @ 9b05600

/*
 * 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;
}

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