JaMNameImpl.mesa
Written by Bill Paxton, January 1981
Bill Paxton, 14-Jan-82 14:32:53
Russ Atkinson, July 22, 1983 6:38 pm
Administers names
DIRECTORY
JaMBasic USING [NameID, NameIndex, Object, Tag, Tuple],
JaMDict USING [DD, freeHash, HashString, HashText, InsertInDict, LookUpDict, Slot],
JaMInternal USING [Frame],
JaMOps
USING
[ACopy, Assert, Bug, Error, Install, InstallReason, limitchk, MakeName, MakeString, root, SCopy, Text],
JaMStorage USING [Zone],
JaMVM
USING
[AllocString, GetChar, GetDict, GetElem, GetText, GetTuple, PutDict, PutElem, PutRoot, PutText],
PrincOpsUtils USING [LongCOPY];
JaMNameImpl:
MONITOR
IMPORTS JaMDict, JaMOps, JaMStorage, JaMVM, PrincOpsUtils
EXPORTS JaMOps = {
OPEN VM:JaMVM, JaMOps, JaMDict, JaMInternal, JaMBasic;
Types and Constants
nullID: NameID = [FALSE,LAST[NameIndex]];
NameCache: TYPE = LONG POINTER TO NameCacheRecord;
NameCacheRecord:
TYPE =
RECORD [
curlen,maxlen: CARDINAL,
clears, probes, hits: LONG INTEGER,
table: SEQUENCE size: CARDINAL OF Entry
];
Entry: TYPE = RECORD[text: Text, hash: CARDINAL, id: NameID];
initialCacheSize: CARDINAL = 67;
locNIL: CARDINAL = LAST[CARDINAL];
maxNameLength: CARDINAL = 20;
Globals
zone: UNCOUNTED ZONE = JaMStorage.Zone[];
unknownname: name Object;
cache: NameCache ← NIL;
scratch: string Object;
Also part of the monitor: root.nameDict, root.nameArray, root.nameCount
Private operations (should be called with the monitor locked)
InitCache:
PROC[size:
CARDINAL] = {
Assert[cache=NIL];
cache ← zone.
NEW[NameCacheRecord[size] ← [curlen: 0, maxlen: (size/3)*2,
clears: 0, probes: 0, hits: 0, table: ]];
FOR i:
CARDINAL
IN[0..size)
DO
text: Text ← zone.NEW[StringBody[maxNameLength]];
cache[i] ← [text,freeHash,nullID];
ENDLOOP;
};
FreeCache:
PROC = {
Assert[cache#NIL];
FOR i:
CARDINAL
IN[0..cache.size)
DO
zone.FREE[@cache[i].text];
ENDLOOP;
zone.FREE[@cache];
};
LookUpName:
PROC[text: Text, hash:
CARDINAL]
RETURNS[
BOOLEAN,
CARDINAL] = {
loc: CARDINAL ← hash MOD cache.size;
cache.probes ← cache.probes + 1;
THROUGH[0..cache.size)
DO
entry: Entry ← cache[loc];
IF entry.hash=hash
AND EQText[entry.text,text]
THEN {
cache.hits ← cache.hits + 1; RETURN[TRUE,loc] }
ELSE
IF entry.hash=freeHash
THEN
RETURN[FALSE,IF cache.curlen<cache.maxlen THEN loc ELSE locNIL];
loc ← loc + 1; IF loc=cache.size THEN loc ← 0; -- wrap around
ENDLOOP;
ERROR Bug; -- no free slots
};
InsertName:
PROC[text: Text, hash:
CARDINAL, id: NameID, loc:
CARDINAL] = {
len: CARDINAL ← text.length;
entry: Entry;
IF loc = locNIL THEN { ClearCache[]; loc ← hash MOD cache.size };
entry ← cache[loc]; entry.hash ← hash; entry.id ← id;
Assert[len<=entry.text.maxlength]; entry.text.length ← len;
PrincOpsUtils.LongCOPY[from: @text.text, to: @entry.text.text, nwords: (len+1)/2];
cache[loc] ← entry; cache.curlen ← cache.curlen + 1;
};
ClearCache:
PROC = {
FOR loc:
CARDINAL
IN[0..cache.size)
DO
entry: Entry ← cache[loc];
entry.hash ← freeHash; entry.id ← nullID;
entry.text.length ← 0; cache[loc] ← entry;
ENDLOOP;
cache.curlen ← 0; cache.clears ← cache.clears + 1;
};
StringToID:
PROC[string: string Object, hash:
CARDINAL]
RETURNS[NameID] = {
dict: dict Object ← root.nameDict;
dd: DD ← VM.GetDict[dict];
known: BOOLEAN; slot: Slot;
tuple: Tuple; id: NameID;
[known,slot] ← LookUpDict[@dd,hash,string];
IF known
THEN {
-- found it in the name dictionary
tuple ← VM.GetTuple[slot];
WITH ob:tuple.value
SELECT
FROM name => id ← ob.id;
ENDCASE => ERROR Bug }
ELSE {
-- not found, must create a new Name
array: array Object ← root.nameArray;
index: CARDINAL ← root.nameCount;
firstchar: CHARACTER ← 0C;
IF index>LAST[NameIndex] THEN ERROR Error[limitchk];
Assert[dd.curlen=index];
string ← SCopy[string]; -- copy the string
IF string.length>0 THEN firstchar ← VM.GetChar[string,0];
id ← [local: (firstchar=':), index: index];
tuple ← [string,[X,name[id]]];
InsertInDict[@dd,hash,tuple,slot]; VM.PutDict[dict,dd];
IF
NOT index<array.length
THEN
array ← root.nameArray ← ACopy[array,array.length/2];
VM.PutElem[array,index,string];
root.nameCount ← index + 1; VM.PutRoot[root];
};
RETURN[id];
};
Name operations
NameToString:
PUBLIC
ENTRY
PROC[name: name Object]
RETURNS[string Object] = {
ENABLE UNWIND => NULL;
index: CARDINAL ← name.id.index;
count: CARDINAL ← root.nameCount;
IF index<count
THEN {
array: array Object ← root.nameArray; ob: Object;
Assert[index<array.length];
ob ← VM.GetElem[array,index]; ob.tag ← name.tag;
WITH ob:ob
SELECT
FROM string =>
RETURN[ob];
ENDCASE => ERROR Bug }
ELSE ERROR Error[unknownname];
};
NameLength:
PUBLIC
PROC[name: name Object]
RETURNS[
CARDINAL] = {
RETURN[NameToString[name].length] };
StringToName:
PUBLIC
ENTRY
PROC[string: string Object, text: Text ←
NIL]
RETURNS[name Object] = {
ENABLE UNWIND => NULL;
mytext: STRING ← [maxNameLength];
hash: CARDINAL; known: BOOLEAN; loc: CARDINAL; id: NameID;
IF text=
NIL
AND string.length<=maxNameLength
THEN {
text ← mytext; VM.GetText[string,text] };
IF text=NIL THEN { hash ← HashString[string]; known ← FALSE }
ELSE { hash ← HashText[text]; [known,loc] ← LookUpName[text,hash] };
IF known THEN id ← cache[loc].id -- found it in the cache
ELSE {
id ← StringToID[string,hash]; -- look in the dictionary, enter if necessary
IF text#NIL THEN InsertName[text,hash,id,loc]; -- enter in cache
};
RETURN[[string.tag,name[id]]];
};
CreateName:
PUBLIC
ENTRY
PROC[text: Text, tag: Tag ←
X]
RETURNS[name: name Object, known: BOOLEAN] = {
hash: CARDINAL ← HashText[text];
loc: CARDINAL; id: NameID;
[known,loc] ← LookUpName[text,hash];
IF known THEN id ← cache[loc].id
ELSE {
string: string Object ← scratch; -- use scratch string if possible
IF text.length<=string.length
THEN {
string.length ← text.length; VM.PutText[string,text] }
ELSE { string ← MakeString[text]; text ← NIL };
id ← StringToID[string,hash]; -- look in the dictionary, enter if necessary
IF text#NIL THEN InsertName[text,hash,id,loc]; -- enter in cache
};
name ← [tag,name[id]];
};
EQText:
PROC[a,b: Text]
RETURNS[
BOOLEAN] =
INLINE {
RETURN[IF a.length=b.length THEN EqualText[a,b] ELSE FALSE] };
EqualText:
PROC[a,b: Text]
RETURNS[
BOOLEAN] = {
IF a.length#b.length THEN RETURN[FALSE];
FOR i:
CARDINAL
IN[0..a.length)
DO
IF a[i]#b[i] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE] };
Initialization
InstallName:
PROC[why: InstallReason, frame: Frame] = {
SELECT why
FROM
init => InitCache[initialCacheSize];
free => FreeCache[];
register => {
unknownname ← MakeName[".unknownname"L];
scratch ← VM.AllocString[maxNameLength];
};
ENDCASE;
};
Install[InstallName];
}.