AtomImpl.Mesa. Implements basic atom and property list operations. Resides in boot file. Rest of procedures in Atom interface are exported by AtomImpl.
Last Modified On January 17, 1983 1:38 pm by Warren Teitelman
Last Modified On September 19, 1983 8:48 pm by Paul Rovner
Last Edited by: Levin, September 20, 1983 3:34 pm
DIRECTORY
Atom USING [PropList, DottedPairNode],
AtomPrivate USING [AtomRec],
PrincOpsUtils USING [BITSHIFT],
Rope USING [ROPE, Text, FromChar, InlineFlatten, NewText, FromRefText],
SafeStorageOps USING [AcquireBasicLiterals],
SafeStorage USING [GetPermanentZone]
AtomImpl: CEDAR MONITOR -- protects the ATOM dictionary and all PropLists
IMPORTS PrincOpsUtils, Rope, SafeStorageOps, SafeStorage
EXPORTS Atom, AtomPrivate
SHARES Rope
= BEGIN
Constants
HashSize: INTEGER = 4093; -- prime;
Types, Errors, Global Variables
PropList: TYPE = Atom.PropList;
String: TYPE = LONG POINTER TO READONLY TEXT;
AtomRec: TYPE = AtomPrivate.AtomRec;
RefAtomRec:
TYPE =
REF AtomRec;
bridge from opaque ATOM to concrete as defined in AtomPrivate
AtomDictionaryIndex: TYPE = [0..HashSize);
AAtomDict: TYPE = ARRAY AtomDictionaryIndex OF RefAtomRec;
ComparisonOutcome: TYPE = {less, greater, equal};
atomZone: ZONE = SafeStorage.GetPermanentZone[];
atomDictionary: REF AAtomDict ← atomZone.NEW[AAtomDict ← ALL[NIL]];
NILNotAnAtom: PUBLIC ERROR = CODE;
emptyAtom: ATOM;
Creating Atoms
EmptyAtom: PUBLIC PROC RETURNS[ATOM] = {RETURN[emptyAtom]};
MakeAtom:
PUBLIC
PROC [pName: Rope.
ROPE]
RETURNS[
ATOM] =
TRUSTED {
t: Rope.Text = Rope.InlineFlatten[pName];
this, prev: RefAtomRec;
hash: AtomDictionaryIndex;
l: CARDINAL;
IF t = NIL THEN RETURN[EmptyAtom[]];
l ← t.length;
IF l
MOD 2 = 1
-- fill residue char with 0
THEN {
w: CARDINAL ← PrincOpsUtils.BITSHIFT[LOOPHOLE[t[l-1], UNSPECIFIED], 8];
p: LONG POINTER TO CARDINAL;
l ← l + 1;
p ← LOOPHOLE[t, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]] + l/2 - 1;
IF p^ # w THEN p^ ← w};
[this, prev, hash] ← LookUpAtom[t];
IF this # NIL THEN RETURN[LOOPHOLE[this]];
here if not found. Make a new ATOM.
this ← atomZone.NEW[AtomRec ← [pName: t]];
InsertAtom[atom: this, prev: prev, hash: hash];
RETURN[LOOPHOLE[this]];
};
exported to AtomPrivate
UnsafeMakeAtom:
PUBLIC
PROC[pName: String]
RETURNS[
ATOM] =
TRUSTED{
this, prev: RefAtomRec;
hash: AtomDictionaryIndex;
l: CARDINAL;
oddLength: BOOLEAN ← FALSE;
rt: Rope.Text;
IF pName = NIL THEN RETURN[NIL];
l ← pName.length;
IF l
MOD 2 = 1
-- fill residue char with 0 (NOTE violation of READONLY!!!)
THEN {
w: CARDINAL = PrincOpsUtils.BITSHIFT[LOOPHOLE[pName[l-1], UNSPECIFIED], 8];
p: LONG POINTER TO CARDINAL;
oddLength ← TRUE;
l ← l + 1;
p ← LOOPHOLE[pName + SIZE[TEXT[0]] + l/2 - 1];
IF p^ # w THEN p^ ← w -- NOTE violation of READONLY!!!
};
[this, prev, hash] ← LookUpAtom[LOOPHOLE[pName, Rope.Text]];
IF this # NIL THEN RETURN[LOOPHOLE[this]];
here if not found. Make a new ATOM.
rt ← Rope.NewText[l];
rt.length ← pName.length;
FOR i: CARDINAL IN [0..pName.length) DO rt[i] ← pName[i] ENDLOOP;
IF oddLength THEN {rt.length ← l; rt[l-1] ← LOOPHOLE[0]; rt.length ← l-1};
this ← atomZone.NEW[AtomRec ← [pName: rt]];
InsertAtom[atom: this, prev: prev, hash: hash];
RETURN[LOOPHOLE[this]]};
MakeAtomFromChar:
PUBLIC
PROC [char:
CHARACTER]
RETURNS[
ATOM] =
TRUSTED {
RETURN[MakeAtom[Rope.FromChar[char]]];
};
MakeAtomFromRefText:
PUBLIC
PROC [rt:
REF
READONLY
TEXT]
RETURNS[
ATOM] =
TRUSTED {
this, prev: RefAtomRec;
hash: AtomDictionaryIndex;
l: CARDINAL;
IF rt = NIL THEN RETURN[EmptyAtom[]];
l ← rt.length;
IF l
MOD 2 = 1
-- fill residue char with 0
THEN {
w: CARDINAL ← PrincOpsUtils.BITSHIFT[LOOPHOLE[rt[l-1], UNSPECIFIED], 8];
p: LONG POINTER TO CARDINAL;
old: CARDINAL;
oldSaved: BOOL ← FALSE;
l ← l + 1;
p ← LOOPHOLE[rt, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]] + l/2 - 1;
IF p^ # w THEN {old ← p^; p^ ← w; oldSaved ← TRUE};
[this, prev, hash] ← LookUpAtom[LOOPHOLE[rt, Rope.Text]];
IF oldSaved THEN p^ ← old;
}
ELSE [this, prev, hash] ← LookUpAtom[LOOPHOLE[rt, Rope.Text]];
IF this # NIL THEN RETURN[LOOPHOLE[this]];
here if not found. Make a new ATOM.
this ← atomZone.NEW[AtomRec ← [pName: Rope.FromRefText[rt]]];
InsertAtom[atom: this, prev: prev, hash: hash];
RETURN[LOOPHOLE[this, ATOM]];
};
ATOMToAtom:
PROC [atom:
ATOM]
RETURNS [RefAtomRec] =
TRUSTED
INLINE {
RETURN[LOOPHOLE[atom, RefAtomRec]];
};
ATOMToPropList:
PROC [atom:
ATOM]
RETURNS [PropList] =
INLINE {
RETURN[NARROW[ATOMToAtom[atom].propList, PropList]];
};
property list operations (for atoms and types)
property lists are alists, rather than list of ref any, so that the property list functions do not have to check the type of each entry to make sure it is a dotted pair. When automatic narrowing arrives, then maybe want to just make property list a list of typed objects.
GetPropertyList:
PUBLIC
PROC [atom:
ATOM]
RETURNS[PropList] = {
RETURN[
IF atom =
NIL
THEN
NIL
ELSE ATOMToPropList[atom]];
treat NIL as an atom for purposes of GetProp
};
PutProp:
PUBLIC
PROC [atom:
ATOM, prop:
REF
ANY, val:
REF
ANY] = {
IF atom = NIL THEN ERROR NILNotAnAtom;
ATOMToAtom[atom].propList
← PutPropOnList[propList: ATOMToPropList[atom], prop: prop, val: val];
};
PutPropOnList:
PUBLIC
ENTRY
PROC [propList: PropList, prop:
REF
ANY, val:
REF
ANY]
RETURNS[PropList] = {
ENABLE UNWIND => NULL;
lst: PropList ← propList;
lst1: PropList ← NIL;
UNTIL lst =
NIL
DO
IF lst.first.key = prop
THEN
BEGIN
lst.first.val ← val;
RETURN[propList];
END;
lst1 ← lst;
lst ← lst.rest;
ENDLOOP;
prop not found on property list
lst ← CONS[NEW[Atom.DottedPairNode ← [key: prop, val: val]], NIL];
IF lst1 =
NIL
THEN
RETURN[lst]
ELSE IF lst1.rest = NIL THEN {lst1.rest ← lst; RETURN[propList]} -- add at end --
ELSE ERROR ; -- shouldnt happen
}; -- of PutPropOnList
GetProp:
PUBLIC
PROC [atom:
ATOM, prop:
REF
ANY]
RETURNS[
REF
ANY] = {
IF atom = NIL THEN RETURN[NIL] -- treat NIL as an atom for purposes of GetProp
ELSE RETURN[GetPropFromList[propList: ATOMToPropList[atom], prop: prop]];
};
GetPropFromList:
PUBLIC
ENTRY
PROC [propList: PropList, prop:
REF
ANY]
RETURNS[
REF
ANY] = {
ENABLE UNWIND => NULL;
FOR lst: PropList ← propList, lst.rest
UNTIL lst =
NIL
DO
IF lst.first.key = prop THEN RETURN[lst.first.val];
ENDLOOP;
RETURN[NIL];
};
RemProp:
PUBLIC
PROC [atom:
ATOM, prop:
REF
ANY] = {
IF atom = NIL THEN RETURN;
ATOMToAtom[atom].propList ← RemPropFromList[ATOMToPropList[atom], prop];
};
RemPropFromList:
PUBLIC
ENTRY
PROC [propList: PropList, prop:
REF
ANY]
RETURNS[PropList] = {
ENABLE UNWIND => NULL;
lst, lst1: PropList ← NIL;
lst ← propList;
UNTIL lst =
NIL
DO
IF lst.first.key = prop
THEN
{IF lst1 = NIL THEN RETURN[lst.rest]
ELSE {lst1.rest ← lst.rest; RETURN[propList]};
};
lst1 ← lst;
lst←lst.rest;
ENDLOOP;
RETURN[propList];
};
GetPName:
PUBLIC
PROC [atom:
ATOM]
RETURNS [pName: Rope.Text] = {
IF atom = NIL THEN ERROR NILNotAnAtom;
RETURN[ATOMToAtom[atom].pName];
};
MapAtoms:
PUBLIC
PROC [proc:
PROC[atom:
ATOM]] =
TRUSTED {
proc1:
PROC [atm:
ATOM]
RETURNS[stop:
BOOLEAN] =
CHECKED {
proc[atm];
RETURN[FALSE];
}; -- of proc1
[] ← FindAtom[proc: proc1];
};
FindAtom:
PUBLIC
PROC [proc:
PROC[atom:
ATOM]
RETURNS[stop:
BOOL]]
RETURNS[ATOM--NIL if was not stopped--] = {
FOR atom:
ATOM ← Next[
NIL], Next[atom]
UNTIL atom =
NIL
DO IF proc[atom] THEN RETURN[atom] ENDLOOP;
RETURN[NIL]};
Next: ENTRY PROC[atom: ATOM ← NIL] RETURNS[ATOM] =
TRUSTED INLINE{
a: RefAtomRec = LOOPHOLE[atom];
IF a # NIL AND a.link # NIL THEN RETURN[a.link];
FOR adi:
CARDINAL ← (
IF a =
NIL
THEN 0
ELSE (Hash[
LOOPHOLE[a.pName]] + 1)), adi + 1
UNTIL adi = HashSize
DO IF atomDictionary[adi] # NIL THEN RETURN[LOOPHOLE[atomDictionary[adi]]];
ENDLOOP;
RETURN[NIL]};
returns [NIL, ptr to last atom, hash index] if not found
LookUpAtom:
ENTRY
PROC[s: Rope.Text]
RETURNS[atom: RefAtomRec, prev: RefAtomRec, hash: AtomDictionaryIndex] =
TRUSTED INLINE {
prev ← NIL;
hash ← Hash[s];
FOR atom ← atomDictionary[hash],
LOOPHOLE[atom.link]
UNTIL atom =
NIL
DO
SELECT CompareStrings[s, atom.pName]
FROM
equal => RETURN;
greater => {atom ← NIL; EXIT};
ENDCASE;
prev ← atom;
ENDLOOP};
InsertAtom: ENTRY PROC[atom: RefAtomRec, prev: RefAtomRec, hash: AtomDictionaryIndex] =
TRUSTED INLINE {
IF prev =
NIL
THEN {atom.link ← LOOPHOLE[atomDictionary[hash]]; atomDictionary[hash] ← atom}
ELSE {atom.link ← prev.link; prev.link ← LOOPHOLE[atom]}};
CompareStrings:
INTERNAL
PROC[leftString, rightString: Rope.Text]
RETURNS[ComparisonOutcome] =
TRUSTED INLINE {
lLength: CARDINAL = (leftString.length+1)/2;
rLength: CARDINAL = (rightString.length+1)/2;
lp: LONG POINTER TO CARDINAL = LOOPHOLE[leftString, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]];
rp: LONG POINTER TO CARDINAL = LOOPHOLE[rightString, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]];
FOR i:
CARDINAL
IN [0..
MIN[lLength, rLength])
DO
lw: CARDINAL = (lp + i)^;
rw: CARDINAL = (rp + i)^;
IF lw < rw THEN RETURN[less] ELSE IF lw > rw THEN RETURN[greater];
ENDLOOP;
RETURN
[
IF lLength = rLength
THEN equal
ELSE IF lLength < rLength THEN less ELSE greater]};
stolen from TexHash.mesa
Hash: INTERNAL PROC[s: Rope.Text] RETURNS[AtomDictionaryIndex] =
INLINE {
acc: CARDINAL ← 0;
FOR i:
CARDINAL
IN [0..
MIN[7, s.length])
DO acc ← 7*acc+LOOPHOLE[s[i], CARDINAL] ENDLOOP;
RETURN[acc MOD HashSize]};
START HERE
TRUSTED{SafeStorageOps.AcquireBasicLiterals[CODE[AtomRec]]};
emptyAtom ← MakeAtom[""];
END.