JaMDictImpl.mesa
Original version by Martin Newell, January 1979
Bill Paxton, 29-Jan-82 15:44:13
Doug Wyatt, 21-Oct-81 17:21:22
Russ Atkinson, July 22, 1983 6:10 pm
Administers dictionaries in VM. A dictionary is a type of Object, however additional information is held in a DictDesc, which also lives in VM. A Dictionary is a set of <key,value> tuples, in which both key and value are Objects (key is not necessarily a string).
Present implementation:
Dictionary is allocated as a contiguous vector of <object,object> tuples
Hash coding is used to access tuples
Dictionary stack is cached with single level cache.
DIRECTORY
JaMBasic USING [Object, Tuple],
JaMDict USING [DD, freeHash, Hash, Loc, locNIL, Slot, slotNIL],
JaMInternal USING [Cache, CacheRecord, Frame, HashSequence, TupleSequence],
JaMOps
USING
[AGet, APut, Assert, Bug, Compare, Empty, Equal, Error, ForEachFrame, ForEachFrameExcept, Full, Install, InstallReason, KeyName, limitchk, MakeName, MarkLoop, nullOb, Pop, PopCardinal, PopDict, Push, PushBoolean, PushCardinal, PushInteger, RegisterExplicit, RegisterInternal, StackForAll, TopDict, typechk, UnmarkLoop],
JaMStorage USING [Zone],
JaMVM USING [AllocArray, AllocDict, GetDict, GetTuple, PutDict, PutTuple];
JaMDictImpl:
PROGRAM
IMPORTS JaMDict, JaMOps, JaMStorage, JaMVM
EXPORTS JaMDict, JaMOps = {
OPEN VM:JaMVM, JaMOps, JaMDict, JaMInternal, JaMBasic;
Types and constants
nullTuple: Tuple = [nullOb,nullOb];
nullDict: dict Object = [L,dict[NIL]];
maxlenLimit: CARDINAL = 20000; -- maximum maxlen for a dictionary
maxattLimit: CARDINAL = 1000; -- maximum number of attached dictionaries
initCacheSize: CARDINAL = 67;
GLOBALS
zone: UNCOUNTED ZONE = JaMStorage.Zone[];
undefkey,dictfull,attachmentcycle,notattached,dictundflw,dictovrflw: name Object;
dfacmd,afacmd: command Object;
Low level dictionary operations
AGetDict:
PROC[array: array Object, i:
CARDINAL]
RETURNS[dict Object] = {
ob: Object ← AGet[array,i];
WITH ob:ob
SELECT
FROM dict =>
RETURN[ob];
ENDCASE => ERROR Bug;
};
LookUpDict:
PUBLIC
PROC[dd:
POINTER
TO
READONLY
DD,
hash: CARDINAL, key: Object] RETURNS[BOOLEAN,Slot] = {
Looks in dictionary for object with key, hashed to hash.
If found then returns [TRUE, where it is]
else returns [FALSE, where it would go or slotNIL if no room]
slot: Slot ← dd.beg + LONG[hash MOD dd.size]*SIZE[Tuple];
IF key.type = null THEN ERROR Error[typechk]; -- better not allow this for a key
THROUGH[0..dd.size)
DO
tuple: Tuple ← VM.GetTuple[slot];
IF Equal[tuple.key,key] THEN RETURN[TRUE,slot]; -- found a match
IF tuple.key.type = null
THEN
-- found an empty slot
RETURN[FALSE,IF dd.curlen<dd.maxlen THEN slot ELSE slotNIL];
slot ← slot + SIZE[Tuple]; IF slot=dd.end THEN slot ← dd.beg; -- wrap around
ENDLOOP;
ERROR Bug; -- no empty slots
};
InsertInDict:
PUBLIC
PROC[dd:
POINTER
TO
DD,
hash: CARDINAL, tuple: Tuple, slot: Slot] = {
IF slot=slotNIL
THEN { known:
BOOLEAN;
GrowDict[dd]; -- grow the dictionary, if possible
[known,slot] ← LookUpDict[dd,hash,tuple.key]; -- try again for a slot
Assert[NOT known]; -- shouldn't be there
IF slot=slotNIL THEN ERROR Error[dictfull]; -- still no room
};
VM.PutTuple[slot,tuple]; dd.curlen ← dd.curlen + 1;
};
GrowDict:
PROC[olddd:
POINTER
TO
DD] = {
oldmax: CARDINAL ← olddd.maxlen;
IF oldmax < maxlenLimit
THEN {
newmax: CARDINAL ← oldmax + MIN[MAX[10,oldmax/2],maxlenLimit-oldmax];
newdict: dict Object ← Dict[newmax];
newdd: DD ← VM.GetDict[newdict];
slot: Slot ← olddd.beg;
THROUGH[0..olddd.size)
DO
tuple: Tuple ← VM.GetTuple[slot];
IF tuple.key.type#null
THEN {
hash: CARDINAL ← Hash[tuple.key];
known: BOOLEAN; newslot: Slot;
[known,newslot] ← LookUpDict[@newdd,hash,tuple.key];
Assert[(NOT known) AND newslot#slotNIL];
VM.PutTuple[newslot,tuple]; newdd.curlen ← newdd.curlen + 1 };
slot ← slot + SIZE[Tuple];
ENDLOOP;
Assert[slot=olddd.end AND newdd.curlen=olddd.curlen];
newdd.curatt ← olddd.curatt; newdd.attach ← olddd.attach;
olddd^ ← newdd };
};
FindInDict:
PROC[dict: dict Object, hash:
CARDINAL, key: Object]
RETURNS[known: BOOLEAN, slot: Slot, where: dict Object] = {
Looks in dictionary for object with key, hashed to hash.
Will check in attached dictionaries also.
If found then returns [TRUE, where it is, which dict]
else returns [FALSE, where it would go or locNIL if no room, dict]
dd: DD ← VM.GetDict[dict];
[known,slot] ← LookUpDict[@dd,hash,key];
IF known THEN RETURN[TRUE,slot,dict] -- found it in dict
ELSE {
-- check attachments
FOR i:
CARDINAL
IN[0..dd.curatt)
DO
-- try most recently attached first
adict: dict Object ← AGetDict[dd.attach,i]; aslot: Slot;
[known, aslot, where] ← FindInDict[adict,hash,key];
IF known THEN RETURN[TRUE,aslot,where];
ENDLOOP;
};
RETURN[FALSE,slot,dict];
};
EnterInDict:
PROC[dict: dict Object, hash:
CARDINAL, tuple: Tuple] = {
dd: DD ← VM.GetDict[dict];
known: BOOLEAN; slot: Slot;
[known,slot] ← LookUpDict[@dd,hash,tuple.key];
IF known THEN VM.PutTuple[slot,tuple]
ELSE { InsertInDict[@dd,hash,tuple,slot]; VM.PutDict[dict,dd] };
};
DeleteInDict:
PROC[dict: dict Object, hash:
CARDINAL, key: Object]
RETURNS[
BOOLEAN] = {
dd: DD ← VM.GetDict[dict];
known: BOOLEAN; slot: Slot;
[known,slot] ← LookUpDict[@dd,hash,key];
IF known THEN VM.PutTuple[slot,nullTuple] ELSE RETURN[FALSE];
Rehash entries beyond this one since they may be result of collisions
THROUGH [0..dd.size)
DO
tuple: Tuple; newslot: Slot;
slot ← slot + SIZE[Tuple]; IF slot=dd.end THEN slot ← dd.beg; -- wrap around
tuple ← VM.GetTuple[slot];
IF tuple.key.type=null THEN EXIT; -- empty slot
[known,newslot] ← LookUpDict[@dd,Hash[tuple.key],tuple.key];
IF known THEN Assert[newslot=slot]
ELSE { VM.PutTuple[newslot,tuple]; VM.PutTuple[slot,nullTuple] };
REPEAT FINISHED => ERROR Bug; -- no empty slots
ENDLOOP;
dd.curlen ← dd.curlen - 1;
VM.PutDict[dict,dd]; RETURN[TRUE];
};
ClearDict:
PROC[dict: dict Object] = {
dd: DD ← VM.GetDict[dict];
slot: Slot ← dd.beg;
THROUGH[0..dd.size)
DO
VM.PutTuple[slot,nullTuple]; slot ← slot + SIZE[Tuple];
ENDLOOP;
Assert[slot=dd.end];
dd.curlen ← 0; VM.PutDict[dict,dd];
};
Cache operations
LookUpCache:
PROC[cache: Cache, hash:
CARDINAL, key: Object]
RETURNS[
BOOLEAN,Loc] = {
Looks in dictionary cache for object with key, hashed to hash.
If found then returns [TRUE, where it is]
else returns [FALSE, where it would go or locNIL if no room]
loc: Loc ← hash MOD cache.size;
cache.probes ← cache.probes + 1;
THROUGH[0..cache.size)
DO
h: CARDINAL ← cache.hash[loc];
IF h=hash
THEN {
k: Object ← cache.table[loc].key; -- compare keys
IF Equal[k,key] THEN { cache.hits ← cache.hits + 1; RETURN[TRUE,loc] };
}
ELSE
IF h=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
};
InsertInCache:
PROC[cache: Cache, hash:
CARDINAL, tuple: Tuple, loc: Loc] = {
IF loc = locNIL THEN { ClearCache[cache]; loc ← hash MOD cache.size };
cache.hash[loc] ← hash; cache.table[loc] ← tuple;
cache.curlen ← cache.curlen + 1;
};
EnterInCache:
PROC[cache: Cache, hash:
CARDINAL, tuple: Tuple] = {
known: BOOLEAN; loc: Loc;
[known,loc] ← LookUpCache[cache,hash,tuple.key];
IF known THEN cache.table[loc].value ← tuple.value
ELSE InsertInCache[cache,hash,tuple,loc];
};
DeleteInCache:
PROC[cache: Cache, hash:
CARDINAL, key: Object] = {
known: BOOLEAN; loc: Loc;
[known,loc] ← LookUpCache[cache,hash,key];
IF known THEN { cache.hash[loc] ← 0; cache.table[loc] ← nullTuple };
};
ClearCache:
PROC[cache: Cache] = {
FOR loc: Loc IN[0..cache.size) DO cache.hash[loc] ← freeHash ENDLOOP;
cache.curlen ← 0; cache.clears ← cache.clears + 1;
};
NewCache:
PUBLIC
PROC
RETURNS[Cache] = {
n: CARDINAL = initCacheSize;
hash: LONG POINTER TO HashSequence ← zone.NEW[HashSequence[n]];
table: LONG POINTER TO TupleSequence ← zone.NEW[TupleSequence[n]];
cache: Cache ← zone.
NEW[CacheRecord ← [curlen: 0, maxlen: (n/3)*2, size: n,
hash: hash, table: table, clears: 0, probes: 0, hits: 0]];
FOR i: CARDINAL IN[0..n) DO hash[i] ← freeHash ENDLOOP;
RETURN[cache];
};
FreeCache:
PUBLIC
PROC[cache: Cache] = {
zone.FREE[@cache.hash];
zone.FREE[@cache.table];
zone.FREE[@cache];
};
CREATION
Dict:
PUBLIC
PROC[maxlen:
CARDINAL]
RETURNS[dict Object] = {
Return a new dictionary for up to maxlen tuples
IF maxlen<=maxlenLimit
THEN {
size: CARDINAL ← maxlen + maxlen/2 + 1;
dict: dict Object ← VM.AllocDict[size];
dd: DD ← VM.GetDict[dict];
slot: Slot ← dd.beg;
THROUGH[0..size)
DO
VM.PutTuple[slot,nullTuple]; slot ← slot + SIZE[Tuple];
ENDLOOP;
Assert[slot=dd.end];
dd.maxlen ← maxlen; dd.curlen ← 0;
VM.PutDict[dict,dd]; RETURN[dict] }
ELSE ERROR Error[limitchk];
};
ATTRIBUTES
DictLength:
PUBLIC
PROC[dict: dict Object]
RETURNS[
CARDINAL] = {
Return current number of entries in dictionary dict
dd: DD ← VM.GetDict[dict]; RETURN[dd.curlen];
};
DictMaxLen:
PUBLIC
PROC[dict: dict Object]
RETURNS[
CARDINAL] = {
Return maximum allowable length of dictionary dict
dd: DD ← VM.GetDict[dict]; RETURN[dd.maxlen];
};
ACCESS
Known:
PUBLIC
PROC[dict: dict Object, key: Object]
RETURNS[
BOOLEAN] = {
name: Object ← KeyName[key];
hash: CARDINAL ← Hash[name];
dd: DD ← VM.GetDict[dict];
known: BOOLEAN; [known,] ← LookUpDict[@dd,hash,name];
RETURN[known];
};
Where:
PUBLIC
PROC [frame: Frame, key: Object]
RETURNS[
BOOLEAN,dict Object] = {
name: Object ← KeyName[key];
hash: CARDINAL ← Hash[name];
known: BOOLEAN; slot: Slot; dict: dict Object;
Find:
PROC[ob: Object]
RETURNS[
BOOLEAN] = {
WITH ob:ob
SELECT
FROM
dict => [known, slot, dict] ← FindInDict[ob, hash, name];
ENDCASE => ERROR Error[typechk];
RETURN[known] };
IF StackForAll[frame.dictstk, Find]
THEN {
EnterInCache[frame.cache,hash,VM.GetTuple[slot]]; -- put in cache, anticipating a Get
RETURN[TRUE,dict] }
ELSE RETURN[FALSE,nullDict];
};
Get:
PUBLIC
PROC[dict: dict Object, key: Object]
RETURNS[Object] = {
Generates undefkey:
known: BOOLEAN; value: Object;
[known,value] ← TryToGet[dict,key];
IF known THEN RETURN[value]
ELSE ERROR Error[undefkey];
};
TryToGet:
PUBLIC
PROC[dict: dict Object, key: Object]
RETURNS[
BOOLEAN,Object] = {
name: Object ← KeyName[key];
hash: CARDINAL ← Hash[name];
dd: DD ← VM.GetDict[dict];
known: BOOLEAN; slot: Slot;
[known,slot] ← LookUpDict[@dd,hash,name];
IF known THEN RETURN[TRUE,VM.GetTuple[slot].value]
ELSE RETURN[FALSE,nullOb];
};
Put:
PUBLIC
PROC[dict: dict Object, key, value: Object] = {
Generates dictfull:
tuple: Tuple ← [KeyName[key],value];
hash: CARDINAL ← Hash[tuple.key];
Delete: PROC[f: Frame] = { DeleteInCache[f.cache,hash,tuple.key] };
EnterInDict[dict,hash,tuple];
ForEachFrame[Delete]; -- in case dict is on stack
};
Def:
PUBLIC
PROC[frame: Frame, key, value: Object] = {
Enters <key,value> into dictionary on top of dictstk,
Generates dictfull:
dict: dict Object = TopDict[frame.dictstk];
tuple: Tuple ← [KeyName[key],value];
hash: CARDINAL ← Hash[tuple.key];
Delete: PROC[f: Frame] = { DeleteInCache[f.cache,hash,tuple.key] };
EnterInDict[dict,hash,tuple];
EnterInCache[frame.cache,hash,tuple]; -- insert in this frame's cache
ForEachFrameExcept[frame,Delete]; -- in case dict is on stack
};
Load:
PUBLIC
PROC[frame: Frame, key: Object]
RETURNS[Object] = {
known: BOOLEAN; value: Object;
[known,value] ← TryToLoad[frame,key];
IF known THEN RETURN[value] ELSE ERROR Error[undefkey];
};
TryToLoad:
PUBLIC
PROC[frame: Frame, key: Object]
RETURNS[
BOOLEAN,Object] = {
Return value looked up in highest dictionary having key in dictstk,
searching attached dictionaries if necessary
cache: Cache ← frame.cache;
name: Object ← KeyName[key];
hash: CARDINAL ← Hash[name];
known: BOOLEAN; loc: Loc; dict: dict Object; slot: Slot;
Find:
PROC[ob: Object]
RETURNS[
BOOLEAN] = {
WITH ob:ob
SELECT
FROM
dict => [known,slot,dict] ← FindInDict[ob,hash,name];
ENDCASE => ERROR Error[typechk];
RETURN[known] };
[known,loc] ← LookUpCache[cache,hash,name]; -- try the cache first
IF known THEN RETURN[TRUE,cache.table[loc].value]; -- found it! (this should be common)
Not in cache, must search dictionary stack
known ← StackForAll[frame.dictstk, Find];
IF known
THEN { tuple: Tuple ←
VM.GetTuple[slot];
InsertInCache[cache,hash,tuple,loc]; RETURN[TRUE,tuple.value] }
ELSE RETURN[FALSE,nullOb];
};
Store:
PUBLIC
PROC[frame: Frame, key, value: Object] = {
Enters <key,value> into highest dictionary having key in dictstk,
or into dict on top of dictstk if key not found.
Generates dictfull:
tuple: Tuple ← [KeyName[key],value];
hash: CARDINAL ← Hash[tuple.key];
known: BOOLEAN; dict: dict Object; slot: Slot;
Find:
PROC[ob: Object]
RETURNS[
BOOLEAN] = {
WITH ob:ob
SELECT
FROM
dict => [known,slot,dict] ← FindInDict[ob,hash,tuple.key];
ENDCASE => ERROR Error[typechk];
RETURN[known] };
IF StackForAll[frame.dictstk, Find] THEN VM.PutTuple[slot,tuple]
ELSE EnterInDict[TopDict[frame.dictstk],hash,tuple];
EnterInCache[frame.cache,hash,tuple]; -- update cache
};
Del:
PUBLIC
PROC[dict: dict Object, key: Object] = {
Deletes object key from dictionary
Generates undefkey if object not found:
name: Object ← KeyName[key];
hash: CARDINAL ← Hash[name];
Delete: PROC[f: Frame] = { DeleteInCache[f.cache,hash,name] };
IF NOT DeleteInDict[dict,hash,name] THEN ERROR Error[undefkey];
ForEachFrame[Delete]; -- in case dict is on stack
};
ClrDict:
PUBLIC
PROC[dict: dict Object] = {
Deletes all objects from dictionary dict
ClearDict[dict];
ClearAllCaches[]; -- in case dict is on stack
};
ClearAllCaches:
PROC = {
Clear: PROC[f: Frame] = { ClearCache[f.cache] };
ForEachFrame[Clear]; -- in case dict is on stack
};
AttachDict:
PUBLIC
PROC[dict, adict: dict Object] = {
attach adict to dict
Generates attachmentcycle
IF AttachmentPath[adict,dict] THEN ERROR Error[attachmentcycle]
ELSE {
oldatt,newatt: array Object;
dd: DD ← VM.GetDict[dict];
oldatt ← dd.attach;
FOR i:
CARDINAL
IN[0..dd.curatt)
DO
IF AGetDict[oldatt,i] = adict THEN RETURN; -- already attached
ENDLOOP;
IF dd.curatt<oldatt.length
THEN newatt ← oldatt
ELSE { max:
CARDINAL ← oldatt.length;
IF NOT max<maxattLimit THEN ERROR Error[limitchk]; -- too many attachments
max ← max + MIN[MAX[8,max/2],maxattLimit-max];
dd.attach ← newatt ← VM.AllocArray[max] };
FOR i:
CARDINAL
DECREASING
IN[0..dd.curatt)
DO
APut[newatt,i+1,AGetDict[oldatt,i]]; -- move everybody up
ENDLOOP;
APut[newatt,0,adict]; -- plug in the new one
dd.curatt ← dd.curatt + 1; VM.PutDict[dict,dd]; -- update descriptor
};
ClearAllCaches[]; -- in case dict is on stack
};
AttachmentPath:
PROC[dict1, dict2: dict Object]
RETURNS[
BOOLEAN] = {
returns TRUE iff there is an attachment path from dict1 to dict2
IF dict1 = dict2 THEN RETURN[TRUE]
ELSE { dd:
DD ←
VM.GetDict[dict1];
FOR i:
CARDINAL
IN[0..dd.curatt)
DO
IF AttachmentPath[AGetDict[dd.attach,i],dict2] THEN RETURN[TRUE];
ENDLOOP };
RETURN[FALSE];
};
DetachDict:
PUBLIC
PROC[dict, adict: dict Object] = {
detach adict from dict
Generates notattached
dd: DD ← VM.GetDict[dict];
FOR i:
CARDINAL
IN[0..dd.curatt)
DO
IF AGetDict[dd.attach,i]=adict
THEN {
dd.curatt ← dd.curatt - 1;
FOR j:
CARDINAL
IN[i..dd.curatt)
DO
APut[dd.attach,j,AGetDict[dd.attach,j+1]]; -- close up the gap
ENDLOOP;
VM.PutDict[dict,dd]; -- update descriptor
ClearAllCaches[]; -- in case dict is on stack
RETURN };
ENDLOOP;
ERROR Error[notattached]; -- didn't find it
};
DetachAll:
PUBLIC
PROC[dict: dict Object] = {
Detaches all attached dictionaries
dd: DD ← VM.GetDict[dict]; dd.curatt ← 0; VM.PutDict[dict,dd];
ClearAllCaches[]; -- in case dict is on stack
};
Begin:
PUBLIC
PROC[frame: Frame, dict: dict Object] = {
IF Full[frame.dictstk] THEN ERROR Error[dictovrflw];
Push[frame.dictstk,dict]; ClearCache[frame.cache];
};
End:
PUBLIC
PROC[frame: Frame] = {
ob: Object ← Pop[frame.dictstk]; Assert[ob.type=dict];
IF Empty[frame.dictstk]
THEN {
-- disallow popping .sysdict
Push[frame.dictstk,ob]; ERROR Error[dictundflw] };
ClearCache[frame.cache];
};
*** JaM INTRINSICS ***
JDict:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (maxLength)
Returns opstk: (new dictionary to hold up to maxLength objects)
maxlen: CARDINAL ← PopCardinal[frame.opstk];
dict: dict Object ← Dict[maxlen];
Push[frame.opstk,dict];
};
JMaxLength:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary)
Returns opstk: (maximum number of objects in dictionary)
dict: dict Object ← PopDict[frame.opstk];
maxlen: CARDINAL ← DictMaxLen[dict];
PushCardinal[frame.opstk,maxlen];
};
JKnown:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary, key)
Returns opstk: (boolean)
key: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
PushBoolean[frame.opstk,Known[dict,key]];
};
JWhere:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (key),
dictstk: a dictionary stack
Returns opstk: (dictionary(iff key known), boolean("known"))
dictstk: unchanged
key: Object ← Pop[frame.opstk];
known: BOOLEAN;
dict: dict Object;
[known, dict] ← Where[frame,key];
IF known THEN Push[frame.opstk,dict];
PushBoolean[frame.opstk,known];
};
JGet:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary, key)
Returns opstk: (value looked up in dictionary)
key: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
value: Object ← Get[dict,key];
Push[frame.opstk,value];
};
JPut:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary, key, value)
Enters <key,value> into dictionary
Returns opstk: ()
No indication of whether an object with that key already existed.
value: Object ← Pop[frame.opstk];
key: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
Put[dict, key, value];
};
JDef:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (key, value), dictstk: (dictionary)
Enters <key,value> into dictionary
Returns opstk: (), dictstk: (dictionary)
No indication of whether an object with that key already existed.
value: Object ← Pop[frame.opstk];
key: Object ← Pop[frame.opstk];
Def[frame, key, value];
};
JLoad:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (key), dictstk: a dictionary stack
Returns opstk: (value looked up in highest dictionary having key in dictstk),
dictstk: unchanged
key: Object ← Pop[frame.opstk];
value: Object ← Load[frame, key];
Push[frame.opstk,value];
};
JStore:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (key, value), dictstk: a dictionary stack
Enters <key,value> into highest dictionary having key in dictstk,
or into dict on top of dictstk
Returns opstk: (), dictstk: unchanged
value: Object ← Pop[frame.opstk];
key: Object ← Pop[frame.opstk];
Store[frame, key, value];
};
JDel:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary, key)
Deletes object key from dictionary
Returns opstk: ()
key: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
Del[dict, key];
};
JClrDict:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary)
Deletes all objects from dictionary
Returns opstk: ()
dict: dict Object ← PopDict[frame.opstk];
ClrDict[dict];
};
JBegin:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary), dictstk: ()
Returns opstk: (), dictstk: (dictionary)
dict: dict Object ← PopDict[frame.opstk];
Begin[frame,dict];
};
JEnd:
PUBLIC
PROC[frame: Frame] = {
Expects dictstk: (dictionary)
Returns dictstk: ()
End[frame];
};
NextTuple:
PROC[dict: dict Object, old: Loc]
RETURNS[key, value: Object, new: Loc] = {
Increments old to location of next non-null tuple and returns new location
together with the key and object of the tuple
Initial call should have old=locNIL
Returns new=locNIL if no more tuples
Normal enumeration is not used because of way JaM control works
dd: DD ← VM.GetDict[dict]; slot: Slot;
IF old=locNIL THEN { new ← 0; slot ← dd.beg }
ELSE { new ← old + 1; slot ← dd.beg + LONG[new]*SIZE[Tuple] };
WHILE new<dd.size
DO
tuple: Tuple ← VM.GetTuple[slot];
IF tuple.key.type # null THEN RETURN[tuple.key,tuple.value,new];
new ← new + 1; slot ← slot + SIZE[Tuple];
ENDLOOP;
Assert[slot=dd.end]; RETURN[nullOb,nullOb,locNIL];
};
JDictForall:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary)(object)
For each tuple in dictionary put (key)(value) onto opstk and execute object
Returns opstk: ()
ob: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
save them on exec stack
MarkLoop[frame];
Push[frame.execstk, dict];
Push[frame.execstk, ob];
prime state
PushCardinal[frame.execstk, locNIL];
start it
DFAProc[frame];
};
DFAProc:
PROC[frame: Frame] = {
oldloc: Loc ← PopCardinal[frame.execstk];
ob: Object ← Pop[frame.execstk];
dict: dict Object ← TopDict[frame.execstk];
key, value: Object; newloc: Loc;
get tuple onto opstk
[key, value, newloc] ← NextTuple[dict, oldloc];
IF newloc = locNIL
THEN {
[] ← PopDict[frame.execstk]; -- remove dict
UnmarkLoop[frame]; -- remove mark
RETURN };
set up opstk
Push[frame.opstk, key];
Push[frame.opstk, value];
set up execstk
Push[frame.execstk, ob];
PushInteger[frame.execstk, newloc];
Push[frame.execstk, dfacmd];
Push[frame.execstk, ob];
and let it happen
};
JCurDict:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (), dictstk: (dictionary)
Returns opstk: (dictionary), dictstk: (dictionary)
dict: dict Object ← TopDict[frame.dictstk];
Push[frame.opstk, dict];
};
JAttachDict:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary1) (dictionary2)
Returns opstk: ()
Generates attachmentcycle
dict2: dict Object ← PopDict[frame.opstk];
dict1: dict Object ← PopDict[frame.opstk];
AttachDict[dict1, dict2];
};
JDetachDict:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary1) (dictionary2)
detach dict2 from dict1
Returns opstk: ()
Generates notattached
dict2: dict Object ← PopDict[frame.opstk];
dict1: dict Object ← PopDict[frame.opstk];
DetachDict[dict1, dict2];
};
JAttachedForall:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary1) (object)
For each dictionary2 attached to dictionary1
put dictionary2 onto opstk and execute object
Returns opstk: ()
ob: Object ← Pop[frame.opstk];
dict: dict Object ← PopDict[frame.opstk];
dd: DD ← VM.GetDict[dict];
IF dd.curatt = 0 THEN RETURN;
save them on exec stack
MarkLoop[frame];
Push[frame.execstk,dict];
Push[frame.execstk,ob];
prime state
PushInteger[frame.execstk, 0];
start it
AFAProc[frame];
};
AFAProc:
PROC[frame: Frame] = {
i: CARDINAL ← PopCardinal[frame.execstk];
ob: Object ← Pop[frame.execstk];
dict: dict Object ← PopDict[frame.execstk];
dd: DD ← VM.GetDict[dict];
IF i<dd.curatt
THEN {
adict: dict Object ← AGetDict[dd.attach,i];
set up opstk
Push[frame.opstk, adict];
set up execstk
Push[frame.execstk, ob];
PushInteger[frame.execstk, i + 1];
Push[frame.execstk, afacmd];
Push[frame.execstk, ob];
and let it happen
}
ELSE {
[] ← PopDict[frame.execstk]; -- remove dict
UnmarkLoop[frame];
};
};
JDetachAll:
PUBLIC
PROC[frame: Frame] = {
Expects opstk: (dictionary)
Detaches all attached dictionaries
Returns opstk: ()
dict: dict Object ← PopDict[frame.opstk];
DetachAll[dict];
};
JClrDictCache:
PUBLIC
PROC[frame: Frame] = {
ClearCache[frame.cache];
};
JDictCacheStats:
PUBLIC
PROC[frame: Frame] = {
cache: Cache ← frame.cache;
PushInteger[frame.opstk, cache.clears];
PushInteger[frame.opstk, cache.probes];
PushInteger[frame.opstk, cache.hits];
};
JResetDictCacheStats:
PUBLIC
PROC[frame: Frame] = {
cache: Cache ← frame.cache;
cache.clears ← cache.probes ← cache.hits ← 0;
};
initialization
InstallDict:
PROC[why: InstallReason, frame: Frame] = {
SELECT why
FROM
register => {
Dictionary commands
undefkey ← MakeName[".undefkey"L];
dictfull ← MakeName[".dictfull"L];
attachmentcycle ← MakeName[".attachmentcycle"L];
notattached ← MakeName[".notattached"L];
dictundflw ← MakeName[".dictundflw"L];
dictovrflw ← MakeName[".dictovrflw"L];
dfacmd ← RegisterInternal["@dictforall"L, DFAProc];
afacmd ← RegisterInternal["@attachedforall"L, AFAProc];
RegisterExplicit[frame, ".dict"L, JDict];
RegisterExplicit[frame, ".maxlength"L, JMaxLength];
RegisterExplicit[frame, ".known"L, JKnown];
RegisterExplicit[frame, ".where"L, JWhere];
RegisterExplicit[frame, ".get"L, JGet];
RegisterExplicit[frame, ".put"L, JPut];
RegisterExplicit[frame, ".def"L, JDef];
RegisterExplicit[frame, ".load"L, JLoad];
RegisterExplicit[frame, ".store"L, JStore];
RegisterExplicit[frame, ".del"L, JDel];
RegisterExplicit[frame, ".clrdict"L, JClrDict];
RegisterExplicit[frame, ".begin"L, JBegin];
RegisterExplicit[frame, ".end"L, JEnd];
RegisterExplicit[frame, ".dictforall"L, JDictForall];
RegisterExplicit[frame, ".curdict"L, JCurDict];
RegisterExplicit[frame, ".attachdict"L, JAttachDict];
RegisterExplicit[frame, ".detachdict"L, JDetachDict];
RegisterExplicit[frame, ".attachedforall"L, JAttachedForall];
RegisterExplicit[frame, ".detachall"L, JDetachAll];
RegisterExplicit[frame, ".clrdictcache"L, JClrDictCache];
RegisterExplicit[frame, ".dictcachestats"L, JDictCacheStats];
RegisterExplicit[frame, ".resetdictcachestats"L, JResetDictCacheStats];
};
ENDCASE;
};
Install[InstallDict];
}.
Paxton December 12, 1980 5:25
PM
added attached dictionaries
Paxton December 14, 1980 10:31
AM
added CacheHash array and automatic growth for full dictionaries
Paxton January 8, 1981 9:34
AM
add MakeName and StringForName; change Hash and Match.
Wyatt 16-Apr-81 0:16:54
Pilot conversion
use String instead of StringDefs
Wyatt 7-May-81 11:34:07
use hash field for NameStrings
Wyatt 29-Aug-81 22:32:37
rewrite