atom.c

cg编译器

    }
    return 0;
} // GrowAtomTable

/*
 * lReverse() - Reverse the bottom 20 bits of a 32 bit int.
 *
 */

static int lReverse(int fval)
{
    unsigned int in = fval;
    int result = 0, cnt = 0;

    while(in) {
        result <<= 1;
        result |= in&1;
        in >>= 1;
        cnt++;
    }

    // Don't use all 31 bits.  One million atoms is plenty and sometimes the
    // upper bits are used for other things.

    if (cnt < 20)
        result <<= 20 - cnt;
    return result;
} // lReverse

/*
 * AllocateAtom() - Allocate a new atom.  Associated with the "undefined" value of -1.
 *
 */

static int AllocateAtom(AtomTable *atable)
{
    if (atable->nextFree >= atable->size)
        GrowAtomTable(atable, atable->nextFree*2);
    atable->amap[atable->nextFree] = -1;
    atable->arev[atable->nextFree] = lReverse(atable->nextFree);
    atable->nextFree++;
    return atable->nextFree - 1;
} // AllocateAtom

/*
 * SetAtomValue() - Allocate a new atom associated with "hashindex".
 *
 */

static void SetAtomValue(AtomTable *atable, int atomnumber, int hashindex)
{
    atable->amap[atomnumber] = atable->htable.entry[hashindex].index;
    atable->htable.entry[hashindex].value = atomnumber;
} // SetAtomValue

/*
 * FindHashLoc() - Find the hash location for this string.  Return -1 it hash table is full.
 *
 */

static int FindHashLoc(AtomTable *atable, const char *s)
{
    int hashloc, hashdelta, count;
    int FoundEmptySlot = 0;
    int collision[HASH_TABLE_MAX_COLLISIONS + 1];

    hashloc = HashString(s) % atable->htable.size;
    if (!Empty(&atable->htable, hashloc)) {
        if (Match(&atable->htable, &atable->stable, s, hashloc))
            return hashloc;
        collision[0] = hashloc;
        hashdelta = HashString2(s);
        count = 0;
        while (count < HASH_TABLE_MAX_COLLISIONS) {
            hashloc = ((hashloc + hashdelta) & 0x7fffffff) % atable->htable.size;
            if (!Empty(&atable->htable, hashloc)) {
                if (Match(&atable->htable, &atable->stable, s, hashloc)) {
                    return hashloc;
                }
            } else {
                FoundEmptySlot = 1;
                break;
            }
            count++;
            collision[count] = hashloc;
        }

        if (!FoundEmptySlot) {
            if (Cg->options.DumpAtomTable) {
                int ii;
                printf("*** Hash faild with more than %d collisions.  Must increase hash table size. ***\n",
                       HASH_TABLE_MAX_COLLISIONS);
                printf("*** New string \"%s\", hash=%04x, delta=%04x.\n", s, collision[0], hashdelta);
                for (ii = 0; ii <= HASH_TABLE_MAX_COLLISIONS; ii++)
                    printf("*** Collides on try %d at hash entry %04x with \"%s\"\n",
                           ii + 1, collision[ii], GetAtomString(atable, atable->htable.entry[collision[ii]].value));
            }
            return -1;
        } else {
            atable->htable.counts[count]++;
        }
    }
    return hashloc;
} // FindHashLoc

/*
 * IncreaseHashTableSize()
 *
 */

static int IncreaseHashTableSize(AtomTable *atable)
{
    int ii, strloc, oldhashloc, value, size;
    AtomTable oldtable;
    char *s;

    // Save the old atom table and create a new one:

    oldtable = *atable;
    size = oldtable.htable.size*2 + 1;
    if (!InitAtomTable(atable, size))
        return 0;

    // Add all the existing values to the new atom table preserving their atom values:

    for (ii = atable->nextFree; ii < oldtable.nextFree; ii++) {
        strloc = oldtable.amap[ii];
        s = &oldtable.stable.strings[strloc];
        oldhashloc = FindHashLoc(&oldtable, s);
        assert(oldhashloc >= 0);
        value = oldtable.htable.entry[oldhashloc].value;
        AddAtomFixed(atable, s, value);
    }
    FreeAtomTable(&oldtable);
    return 1;
} // IncreaseHashTableSize

/*
 * LookUpAddStringHash() - Lookup a string in the hash table.  If it's not there, add it and
 *        initialize the atom value in the hash table to 0.  Return the hash table index.
 */

static int LookUpAddStringHash(AtomTable *atable, const char *s)
{
    int hashloc, strloc;

    while(1) {
        hashloc = FindHashLoc(atable, s);
        if (hashloc >= 0)
            break;
        IncreaseHashTableSize(atable);
    }

    if (Empty(&atable->htable, hashloc)) {
        atable->htable.entries++;
        strloc = AddString(&atable->stable, s);
        atable->htable.entry[hashloc].index = strloc;
        atable->htable.entry[hashloc].value = 0;
    }
    return hashloc;
} // LookUpAddStringHash

/*
 * LookUpAddString() - Lookup a string in the hash table.  If it's not there, add it and
 *        initialize the atom value in the hash table to the next atom number.
 *        Return the atom value of string.
 */

int LookUpAddString(AtomTable *atable, const char *s)
{
    int hashindex, atom;

    hashindex = LookUpAddStringHash(atable, s);
    atom = atable->htable.entry[hashindex].value;
    if (atom == 0) {
        atom = AllocateAtom(atable);
        SetAtomValue(atable, atom, hashindex);
    }
    return atom;
} // LookUpAddString

/*
 * GetAtomString()
 *
 */

const char *GetAtomString(AtomTable *atable, int atom)
{
    int soffset;

    if (atom > 0 && atom < atable->nextFree) {
        soffset = atable->amap[atom];
        if (soffset > 0 && soffset < atable->stable.nextFree) {
            return &atable->stable.strings[soffset];
        } else {
            return "<internal error: bad soffset>";
        }
    } else {
        if (atom == 0) {
            return "<null atom>";
        } else {
            if (atom == EOF) {
                return "<EOF>";
            } else {
                return "<invalid atom>";
            }
        }
    }
} // GetAtomString

/*
 * GetReversedAtom()
 *
 */

int GetReversedAtom(AtomTable *atable, int atom)
{
    if (atom > 0 && atom < atable->nextFree) {
        return atable->arev[atom];
    } else {
        return 0;
    }
} // GetReversedAtom

/*
 * AddAtom() - Add a string to the atom, hash and string tables if it isn't already there.
 *         Return it's atom index.
 */

int AddAtom(AtomTable *atable, const char *s)
{
    int atom;

    atom = LookUpAddString(atable, s);
    return atom;
} // AddAtom

/*
 * AddAtomFixed() - Add an atom to the hash and string tables if it isn't already there.
 *         Assign it the atom value of "atom".
 */

static int AddAtomFixed(AtomTable *atable, const char *s, int atom)
{
    int hashindex, lsize;

    hashindex = LookUpAddStringHash(atable, s);
    if (atable->nextFree >= atable->size || atom >= atable->size) {
        lsize = atable->size*2;
        if (lsize <= atom)
            lsize = atom + 1;
        GrowAtomTable(atable, lsize);
    }
    atable->amap[atom] = atable->htable.entry[hashindex].index;
    atable->htable.entry[hashindex].value = atom;
    //if (atom >= atable->nextFree)
    //    atable->nextFree = atom + 1;
    while (atom >= atable->nextFree) {
        atable->arev[atable->nextFree] = lReverse(atable->nextFree);
        atable->nextFree++;
    }
    return atom;
} // AddAtomFixed

/*
 * InitAtomTable() - Initialize the atom table.
 *
 */

int InitAtomTable(AtomTable *atable, int htsize)
{
    int ii;

    htsize = htsize <= 0 ? INIT_HASH_TABLE_SIZE : htsize;
    if (!InitStringTable(&atable->stable))
        return 0;
    if (!InitHashTable(&atable->htable, htsize))
        return 0;

    atable->nextFree = 0;
    atable->amap = NULL;
    atable->size = 0;
    GrowAtomTable(atable, INIT_ATOM_TABLE_SIZE);
    if (!atable->amap)
        return 0;

    // Initialize lower part of atom table to "<undefined>" atom:

    AddAtomFixed(atable, "<undefined>", 0);
    for (ii = 0; ii < FIRST_USER_TOKEN_SY; ii++)
        atable->amap[ii] = atable->amap[0];

    // Add single character tokens to the atom table:

    {
        const char *s = "~!@%^&*()-+=|,.<>/?;:[]{}";
        char t[2];

        t[1] = '\0';
        while (*s) {
            t[0] = *s;
            AddAtomFixed(atable, t, s[0]);
            s++;
        }
    }

    // Add multiple character scanner tokens and reserved words:

    for (ii = 0; ii < sizeof(tokens)/sizeof(tokens[0]); ii++)
        AddAtomFixed(atable, tokens[ii].str, tokens[ii].val);

    // Add error symbol if running in error mode:

    if (Cg->options.ErrorMode)
        AddAtomFixed(atable, "error", ERROR_SY);

    AddAtom(atable, "<*** end fixed atoms ***>");

    return 1;
} // InitAtomTable

///////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////// Debug Printing Functions: //////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////

/*
 * PrintAtomTable()
 *
 */

void PrintAtomTable(AtomTable *atable)
{
    int ii;

    for (ii = 0; ii < atable->nextFree; ii++) {
        printf("%d: \"%s\"\n", ii, &atable->stable.strings[atable->amap[ii]]);
    }
    printf("Hash table: size=%d, entries=%d, collisions=",
           atable->htable.size, atable->htable.entries);
    for (ii = 0; ii < HASH_TABLE_MAX_COLLISIONS; ii++)
        printf(" %d", atable->htable.counts[ii]);
    printf("\n");
} // PrintAtomTable

/*
 * FreeAtomTable() - Free the atom table and associated memory
 *
 */

void FreeAtomTable(AtomTable *atable)
{
    FreeStringTable(&atable->stable);
    FreeHashTable(&atable->htable);
    if (atable->amap)
        free(atable->amap);
    if (atable->arev)
        free(atable->arev);
    atable->amap = NULL;
    atable->arev = NULL;
    atable->nextFree = 0;
    atable->size = 0;
} // FreeAtomTable

///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////// End of atom.c ///////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////