// ResistSym.bcpl -- symbol table management

// Last modified November 6, 1979  3:05 PM

external
[
// outgoing procedures
CreateSymbolTable; EnumerateSymbolTable; MustLookupSymbol
LookupSymbol; DefineSymbol; InsertSymbol; LookupOrDefineSymbol
SymbolsObject; SymbolsString; SymbolsType
ObjectsSymbol; ObjectsString; ObjectsLength; ObjectsType

// incoming procedures
Allocate; Zero; MoveBlock; CallSwat
]

// ---------------------------------------------------------------------------
structure String: [ length byte; char↑1,1 byte ]
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
structure ST:	// Symbol Table
// ---------------------------------------------------------------------------
[
lenHT word
zone word
numSymbols word
hashTable↑0,0 word
]

// ---------------------------------------------------------------------------
structure ObjHdr:
// ---------------------------------------------------------------------------
[
length bit 6	// length of object
objOffset bit 5	// offset of object relative to symbol
type bit 5	// type of object
]

// ---------------------------------------------------------------------------
structure Symbol:
// ---------------------------------------------------------------------------
[
next word
string @String
objHdr @ObjHdr
// object
]

manifest objOffset1 = (offset Symbol.string + size ObjHdr)/16 +1

// ---------------------------------------------------------------------------
let CreateSymbolTable(lenHT, zone) = valof
// ---------------------------------------------------------------------------
// Creates symbol table with hash table length lenHT, allocating it from zone,
// and returns a pointer to it.  All symbols subsequently inserted into
// the table will also be allocated from zone.
[
let lenST = (offset ST.hashTable↑lenHT)/16
let st = Allocate(zone, lenST)
Zero(st, lenST)
st>>ST.lenHT = lenHT
st>>ST.zone = zone
resultis st
]

// ---------------------------------------------------------------------------
and EnumerateSymbolTable(st, type, Proc, arg) be
// ---------------------------------------------------------------------------
// Calls Proc(object, arg) for each symbol of type type in st.
[
for hash = 0 to st>>ST.lenHT-1 do
   [
   let symbol = st>>ST.hashTable↑hash
   while symbol ne 0 do
      [
      let object = SymbolsObject(symbol)
      if type eq (object-1)>>ObjHdr.type then Proc(object, arg)
      symbol = symbol>>Symbol.next
      ]
   ]
]

// ---------------------------------------------------------------------------
and LookupOrDefineSymbol(st, string, type, object, lenObject;
    numargs na) = valof
// ---------------------------------------------------------------------------
// Looks up string in st and defines a symbol for it if not already present.
[
let symbol = LookupSymbol(st, string)
if symbol ne 0 resultis symbol
resultis InsertSymbol(st, string, type, object, (na ge 5? lenObject, 0))
]

// ---------------------------------------------------------------------------
and MustLookupSymbol(st, string) = valof
// ---------------------------------------------------------------------------
// Looks up string in st and returns pointer to symbol.
// Calls Swat if not found.
[
let symbol = LookupSymbol(st, string)
if symbol eq 0 then CallSwat("Symbol not found: ", string)
resultis symbol
]

// ---------------------------------------------------------------------------
and LookupSymbol(st, string) = valof
// ---------------------------------------------------------------------------
// Looks up string in st and returns pointer to symbol.
// Returns zero if not found.
[
let symbol = st>>ST.hashTable↑(Hash(st, string))
while symbol ne 0 do
   [
   if valof
      [
      if string>>String.length ne symbol>>Symbol.string.length resultis false
      for i = 1 to string>>String.length do
         if string>>String.char↑i ne symbol>>Symbol.string.char↑i then
            resultis false
      resultis true
      ] resultis symbol
   symbol = symbol>>Symbol.next
   ]
resultis 0
]

// ---------------------------------------------------------------------------
and DefineSymbol(st, string, type, object, lenObject; numargs na) = valof
// ---------------------------------------------------------------------------
// Inserts string into st as a symbol of type type,
// along with a copy of object whose length
// is lenObject, and returns a pointer to the symbol.
// Calls Swat if the symbol is already defined.
[
if LookupSymbol(st, string) ne 0 then
   CallSwat("Symbol already defined: ", string)
resultis InsertSymbol(st, string, type, object, (na ge 5? lenObject, 0))
]

// ---------------------------------------------------------------------------
and InsertSymbol(st, string, type, object, lenObject; numargs na) = valof
// ---------------------------------------------------------------------------
// Inserts string into st as a symbol of type type,
// along with a copy of object whose length
// is lenObject, and returns a pointer to the symbol.
// Makes no check for duplicate definitions.
[
if na ls 5 then lenObject = 0
let objOffset = objOffset1 + string>>String.length rshift 1
let symbol = Allocate(st>>ST.zone, objOffset + lenObject)
let hash = Hash(st, string)
symbol>>Symbol.next = st>>ST.hashTable↑hash
st>>ST.hashTable↑hash = symbol
MoveBlock(lv symbol>>Symbol.string, string, string>>String.length rshift 1 +1)
let objHdr = symbol+objOffset-1
objHdr>>ObjHdr.length = lenObject
objHdr>>ObjHdr.objOffset = objOffset
objHdr>>ObjHdr.type = type
MoveBlock(symbol+objOffset, object, lenObject)
st>>ST.numSymbols = st>>ST.numSymbols+1
resultis symbol
]

// ---------------------------------------------------------------------------
and SymbolsString(symbol) = lv symbol>>Symbol.string
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and SymbolsObject(symbol) =
// ---------------------------------------------------------------------------
    symbol + objOffset1 + symbol>>Symbol.string.length rshift 1

// ---------------------------------------------------------------------------
and SymbolsType(symbol) = (SymbolsObject(symbol)-1)>>ObjHdr.type
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and ObjectsSymbol(object) = object - (object-1)>>ObjHdr.objOffset
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and ObjectsString(object) = SymbolsString(ObjectsSymbol(object))
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and ObjectsLength(object) = (object-1)>>ObjHdr.length
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and ObjectsType(object) = (object-1)>>ObjHdr.type
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
and Hash(st, string) = valof
// ---------------------------------------------------------------------------
[
let hash = 0
for i = 1 to string>>String.length do
   hash = AccumulateHash(hash, string>>String.char↑i)
resultis hash rem st>>ST.lenHT
]

// ---------------------------------------------------------------------------
and AccumulateHash(hash, char) = valof
// ---------------------------------------------------------------------------
// hash ← (2*(hash+char)) mod (2↑15-1)
[
AccumulateHash = table
   [
   123120B	// addzl 1 0
   105142B	// movol 0 1 szc
   121620B	//  inczr 1 0
     1401B	// jmp 1 3
   ]
resultis AccumulateHash(hash, char)
]