'   Symbol table module for the basic compiler. Contains public procedures for
' adding, removing and searching of symbols in the symbol table.
' Symbols are uniquely identified by their name, in the form of a string, and
' the scope in which they are declared, in the form of an integer.
'   The symbol table has been implemented as a hash table, for very fast
' finding of searched symbols.
'   The table is used in a stack like manner: when a structure in
' which symbols can be defined of different scope then the scope of the
' structure itself (e.g. procedures) is left, the symbols defined in it, must
' be removed from the symbol table. Since these symbols were the last to be
' declared, and the first to be removed, we have a LIFO : Last In, First Out.

' FINDING A SYMBOL:
'   When identifying a token, only the name is known, while the scope is
' _never_ known. The language defines that the symbol that is most local (and
' thus has the least scope) is always used. Thus, the symbol found in the
' table during SEARCHING must be the one with the same name and the _least
' scope_ that can be found.
' This is done by the procedure IdentifyToken that takes a name as input only.
' IdentifyToken calls SearchSymbol with an increasing scope accompanying the
' name, until a symbol is found. This is the symbol with the least scope
' possible.

' ADDING A SYMBOL:
'   When adding a symbol, it's name, scope and class are always known, since
' adding is done in the parsing stage.
' All symbols with the same name in different scopes, must belong to the same
' class.
' Before adding, the identifier (name) is tested on belonging to a reserved
' name (class KeyWordNm, OperatorNm).
' If so, it cannot be added to the table, and an error code is returned.

' *** WARNING *** This implementation is only suitable as long as we have a
' one-pass compiler, since symbols are defined by their name and scope, i.e.
' "depth" of usage, and not also by the whole structure of the tree above
' them.
'
' Modified by Marcel Smolenaars from:
'   WORDHASH.BAS v1.10 By Rich Geldreich 1992

'$INCLUDE: 'incsym.bi'
'$INCLUDE: 'incerror.bi'

CONST TRUE = -1, FALSE = 0

DIM sym AS STRING
DIM scope AS INTEGER
DIM m AS INTEGER
DIM n AS INTEGER

SymTableSize = 23

RANDOMIZE TIMER
SCREEN 0
WIDTH , 50

OPEN "hashbas.faq" FOR INPUT AS 1

 FOR n = 1 TO 20
     GOSUB GetSym
     m = AddSymbol(sym, scope, 0, 0)
     GOSUB PrintInfo
     IF EOF(1) THEN PRINT "Reached end of file...": END
     SLEEP
 NEXT
 'PRINT "Mean Tries needed:"; TotTries / n

CLOSE 1


END

GetSym:
     DO
        LINE INPUT #1, sym
        sym = UCASE$(LTRIM$(RTRIM$(MID$(sym, RND * LEN(sym) + 1))))
        sym = LEFT$(sym, INSTR(sym, " ")) 'LEN(Sym)     'get a "random" string from a file
     LOOP UNTIL LEN(sym)
RETURN

PrintInfo:
     LOCATE , 1: PRINT n;
     LOCATE , 5: PRINT sym;
     LOCATE , 15: PRINT m; TotSymbols, " Table usage:";
     PRINT USING "##.##"; 100 * TotSymbols / (SymTableSize + 1);
     PRINT "%"
     'PRINT "Tries :"; Collisions + 1
     'TotTries = TotTries + Collisions + 1
RETURN

FUNCTION AddSymbol% (sym AS STRING, symScope AS INTEGER, class AS INTEGER, id AS INTEGER)
  DIM n AS INTEGER, l AS INTEGER, p AS INTEGER
  DIM Offset AS INTEGER, KeyNum AS INTEGER

    '** Calculate the first KeyNum
    KeyNum = GetSymKey(sym)

    '** adjust the KeyNum so it's within the table
    KeyNum = ABS(KeyNum) MOD SymTableSize

    '** calculate an offset for retries
    IF KeyNum = 0 THEN
        Offset = 1
    ELSE
        Offset = SymTableSize - KeyNum
    END IF

    '** main loop of hashing
    DO
        '** is this entry empty?
        IF SymTable(KeyNum).used = 0 THEN
            'add symbol to the hash table
            SymTable(KeyNum).used = TRUE
            SymTable(KeyNum).nm = sym
            SymTable(KeyNum).nmlen = LEN(sym)
            SymTable(KeyNum).scope = symScope
            SymTable(KeyNum).class = class
            SymTable(KeyNum).id = id
            TotSymbols = TotSymbols + 1
            IF TotSymbols = SymTableSize THEN
               FatalErr "Too many symbols. Symbol table is full."
            END IF
            AddSymbol = KeyNum
            EXIT FUNCTION
       
        ELSE
           
            '** Check if symbol already in symbol table
            n = SymTable(KeyNum).nmlen
            IF n = LEN(sym) AND symScope = SymTable(KeyNum).scope AND LEFT$(SymTable(KeyNum).nm, n) = sym THEN
               FatalErr "Symbol " + sym + " already exists in this scope."

            ELSEIF n = LEN(sym) AND SymTable(KeyNum).class <> class AND LEFT$(SymTable(KeyNum).nm, n) = sym THEN
               'same name used, but with a different class: illegal
               FatalErr "Symbol " + sym + " is assigned a different class in another scope. The same identifiers in different scopes must always belong to the same class."
           
            '** collision -> adjust the KeyNum and try again
            ELSE
                KeyNum = KeyNum - Offset
                IF KeyNum < 0 THEN     'wrap back the KeyNum if it's <0
                   KeyNum = KeyNum + SymTableSize
                END IF
            END IF
       
        END IF

    LOOP
   
END FUNCTION

SUB DelSymbol (Idx AS INTEGER)

    IF SymTable(Idx).used = 0 THEN
       FatalErr "Symbol not used. Illogical deletion request."
    END IF
    SymTable(Idx).used = 0
    TotSymbols = TotSymbols - 1

END SUB

DEFINT A-Z
FUNCTION funFirstPrime (threshold)

tp30 = INT((threshold * 1.3) + .5)
IF tp30 / 2 = tp30 \ 2 THEN
    tp30 = tp30 + 1
END IF
c = tp30 - 2
IF c < 1 THEN
    c = 1
END IF
t2 = threshold * 2
DO
    c = c + 2
    FOR z = 3 TO SQR(c)
        ind = TRUE
        IF c / z = c \ z THEN
            ind = FALSE
            EXIT FOR
        END IF
    NEXT z
    IF ind THEN
        IF (c - 3) / 4 = INT((c - 3) / 4) OR c > t2 THEN
            funFirstPrime = c
            EXIT DO
        END IF
    END IF
LOOP
END FUNCTION

DEFSNG A-Z
FUNCTION GetSymKey% (sym AS STRING)
  DIM KeyNum AS INTEGER
  DIM n AS INTEGER
  DIM mem AS INTEGER
  DIM p AS INTEGER

  '** Calculate the first KeyNum
  DEF SEG = SSEG(sym)
  mem = SADD(sym)
  FOR n = 1 TO LEN(sym)
      p = PEEK(mem)
      KeyNum = KeyNum + p * n
      mem = mem + 1
  NEXT
  DEF SEG

  '** adjust the KeyNum so it's within the table
  GetSymKey = ABS(KeyNum) MOD SymTableSize
  'ABS(KeyNum + SymScope) MOD SymTableSize
  
END FUNCTION

FUNCTION GetSymName$ (sym AS INTEGER)

    GetSymName = LEFT$(SymTable(sym).nm, SymTable(sym).nmlen)

END FUNCTION

FUNCTION SearchSymbol% (sym AS STRING, symScope AS INTEGER, BYVAL KeyNum AS INTEGER)
  DIM n AS INTEGER, l AS INTEGER, p AS INTEGER
  DIM Offset AS INTEGER

    '** calculate an offset for retries
    IF KeyNum = 0 THEN
        Offset = 1
    ELSE
        Offset = SymTableSize - KeyNum
    END IF

    '** main loop of hashing
    DO
        '** is this entry empty?
        IF SymTable(KeyNum).used = 0 THEN

           ' symbol table search failed: symbol was not found
           SearchSymbol = -1
           EXIT FUNCTION

        ELSE

            '** Check if this is symbol we're looking for.
           n = SymTable(KeyNum).nmlen
           IF n = LEN(sym) AND symScope = SymTable(KeyNum).scope AND LEFT$(SymTable(KeyNum).nm, n) = sym THEN
               
              SearchSymbol = KeyNum    ' Found symbol !
              EXIT FUNCTION            ' Return symbol table index.

           '** collision -> adjust the KeyNum and try again
           ELSE
               KeyNum = KeyNum - Offset
               IF KeyNum < 0 THEN     'wrap back the KeyNum if it's <0
                  KeyNum = KeyNum + SymTableSize
               END IF
           END IF

        END IF

    LOOP

END FUNCTION

