// symtab5-s.txt
//    symbol table implementation with one hash table
//    read som3-j-explain for detail


// structure of symbol table is two arrays of (name,attr)
//    name points to string, never be deleted
//    attr points to (type,ref,arity,lv)

// interface:
//    install string  -- search and insert string in symname
//                    -- return index to table, if new attr=0
//
//    enterLocal idx  -- error if duplicate
//    enterGlobal idx type ref
//    clearLocal
//    init_symtab
//    searchref ref   -- search by ref, ret idx, 0 not found

// pass the test  27 December 2004

enum
	1009 tablesize	  // a prime number
enum
	100 localsize

to init_symtab =
	symname = array tablesize
	symattr = array tablesize
	localvar = array localsize
	lv = 0
	freetuple = NIL

// access function by hash key

to getName a = symname[a]
to getAttr a = symattr[a]
to getType a = M[symattr[a]]
to getRef a = M[symattr[a]+1]
to getArity a = M[symattr[a]+2]
to getLv a = M[symattr[a]+3]

to setName a nm = symname[a] = nm
to setAttr a v = symattr[a] = v
to setType a v = M[symattr[a]] = v
to setRef a v = M[symattr[a]+1] = v
to setArity a v = M[symattr[a]+2] = v
to setLv a v = M[symattr[a]+3] = v

// access to tuple, use type as next field

to getNext a = M[a]
to setNext a v = M[a] = v

to newtuple | a =
	if freetuple == NIL
		a = array 4		// tuple (type,ref,arity,lv)
	else
		a = freetuple
		freetuple = getNext a
	M[a] = 0			// init to all 0
	M[a+1] = 0
	M[a+2] = 0
	M[a+3] = 0
	a

to hash s1 | i v a =
	i = 0
	v = 0
	a = s1[i]
	while a != 0
		v = v + a	// add all int
		i = i + 1
		a = s1[i]
	if (v < 0)	v = 0 - v
	v % tablesize

to dumpSym | i nm =
	prints "symbol table" nl
	for i 0 tablesize-1
		nm = getName i
		if nm != 0
			prints nm space
			if (getAttr i) != 0
				print (getType i) space
				print (getRef i)
			nl

to dumpLocal | i nm =
	prints "local symbol" nl
	for i 0 tablesize-1
		nm = getName i
		if nm != 0
			if (getAttr i) == 0
				prints nm
			else if (getType i) == tyLOCAL
				prints nm space
				print (getRef i)
			nl

// hash with linear probe
//   if new, insert name, return index
to install s1 | key i nm =
	key = hash s1
	i = key
	while 1
		nm = getName i
		if nm == 0		// not found, insert name
			nm = array ((strlen s1) + 1)
			strcpy nm s1
			setName i nm
			setAttr i 0
			i break
		if streq  nm s1
			i break		// return idx, found
		i = (i+1) % tablesize
		if i == key		// wrap around
			seterror "symbol table full" // impossible case

// must install name-string first to get idx
to enterLocal idx | nm =
	localvar[lv] = idx		// record localvar
	lv = lv + 1
	if lv >= localsize
		seterror "local sym overflow"

	if (getAttr idx) == 0		// new local
		setAttr idx newtuple
	else
		if (getType idx) == tyGVAR	// shadow gvar
			ref = getRef idx
			setArity idx tyGVAR		// move (type,ref) ->
			setLv idx ref
		else
			dumpLocal
			seterror "duplicate local"
	setType idx tyLOCAL
	setRef idx lv

// free pure local
to clearLocal | i idx type a =
	for i 0 lv-1
		idx = localvar[i]
		if (getType idx) != tyLOCAL  // impossible case
			seterror "wrong type in local sym"
		type = getArity idx
		if type == 0			// pure local
			a = getAttr idx
			setAttr idx 0
			setNext a freetuple	// free tuple
			freetuple = a
		else
			setType idx type	// move <- (arity,lv)
			setRef idx (getLv idx)
			setArity idx 0		// clear to 0
			setLv idx 0
	lv = 0

// must install name-string first to get idx
to enterGlobal idx type ref =
	if (getAttr idx) == 0
		setAttr idx newtuple
	setType idx type
	setRef idx ref

// search by ref, ret index, -1 not found
to searchref ref | i =
	for i 0 tablesize-1
		if (getAttr i) != 0
			if (getRef i) == ref
				break
	if (i < tablesize) i else 0-1

// End
