Dictionary operations
DictImpl: TYPE ~ REF DictImplRep;
DictImplRep:
PUBLIC
TYPE ~
RECORD [
length: INT,
data: SEQUENCE maxLength: NAT OF DictNode
];
DictNode: TYPE ~ REF DictNodeRep;
DictNodeRep:
TYPE ~
RECORD [key: Any, val: Any, next: DictNode];
Hash:
PROC [key: Key]
RETURNS [
CARDINAL] ~ {
HashProc: TYPE = PROC [key: Key] RETURNS [CARDINAL];
Munch: PROC [CARD32] RETURNS [CARD16] ~ TRUSTED MACHINE CODE { PrincOps.zXOR };
hash: CARD ← 0;
WITH v: x.val
SELECT
FROM
name => hash ← LOOPHOLE[x.ref];
integer => hash ← LOOPHOLE[v.int];
string => RETURN [Hash[NameFromAny[x]]];
real => --don't try: reals with different bit patterns may be equal!--
boolean => hash ← ORD[v.bool];
operator, array, file, dict, font => hash ← LOOPHOLE[x.ref];
ENDCASE => hash ← 42;
RETURN [Munch[hash]];
};
DictCreate:
PUBLIC
PROC [size:
INT]
RETURNS [Dict] ~ {
IF size<0 THEN ERROR Error[rangecheck]
ELSE IF size>NAT.LAST THEN ERROR Error[limitcheck]
ELSE {
impl: DictImpl ~ NEW[DictImplRep[size]];
ref: DictRef ~ NEW[DictRep ← [access: unlimited, impl: impl]];
impl.length ← 0;
RETURN[[executable: FALSE, ref: ref]];
};
};
DictLength: PUBLIC PROC [dict: Dict] RETURNS [INT] ~ {
RETURN [dict.ref.length];
};
DictMaxLength: PUBLIC PROC [dict: Dict] RETURNS [INT] ~ {
base: DictBase ~ dict.base;
IF base.access<readOnly THEN ERROR Error[invalidaccess];
RETURN [base.maxLength];
};
DictFetch:
PROC [dict: Dict, key: Any]
RETURNS [found:
BOOL, val: Any] ~ {
ERROR;
};
DictGet: PUBLIC PROC [dict: Dict, key: Any] RETURNS [Any] ~ {
WITH RefTab.Fetch[dict.table, key].val SELECT FROM
val: Any => RETURN [val];
ENDCASE => RETURN [NIL];
};
DictPut: PUBLIC PROC [dict: Dict, key: Any, val: Any] ~ {
length: INT ~ DictLength[dict];
IF NOT length<dict.maxlength THEN ERROR Error[dictfull];
[] ← RefTab.Store[dict.table, key, val];
};
Known: PUBLIC PROC [dict: Dict, key: Any] RETURNS [BOOL] ~ {
RETURN [RefTab.Fetch[dict.table, key].found];
};
DStack: TYPE ~ REF DStackRep;
DStackRep:
PUBLIC
TYPE ~
RECORD [
count: ArrayIndex,
size: ArrayIndex,
array: DArrayRef
];
DArrayRef: TYPE ~ REF DArrayRep;
DArrayRep:
TYPE ~
RECORD [
SEQUENCE size: ArrayIndex
OF Dict];
Begin:
PUBLIC
PROC [self: Root, dict: Dict] ~ {
dstack: DStack ~ self.dstack;
IF NOT dstack.count<dstack.size THEN ERROR Error[dictstackoverflow];
dstack.array[dstack.count] ← dict;
dstack.count ← dstack.count+1;
};
End:
PUBLIC
PROC [self: Root] ~ {
dstack: DStack ~ self.dstack;
IF NOT dstack.count>2 THEN ERROR Error[dictstackunderflow];
dstack.count ← dstack.count-1;
};
CurrentDict:
PUBLIC
PROC [self: Root]
RETURNS [Dict] ~ {
dstack: DStack ~ self.dstack;
IF NOT dstack.count>0 THEN ERROR Bug; -- should always be >=2
RETURN [dstack.array[dstack.count-1]];
};
CountDictStack:
PROC [self: Root]
RETURNS [
INT] ~ {
dstack: DStack ~ self.dstack;
RETURN [dstack.count];
};
dictstack:
PROC [self: Root] ~ {
dstack: DStack ~ self.dstack;
array: Array ~ PopArray[self];
subarray: Array ~ ArrayGetInterval[array, 0, dstack.count];
IF subarray.access<unlimited THEN ERROR Error[invalidaccess];
FOR i: ArrayIndex
IN [0..dstack.count)
DO
dict: Dict ~ dstack.array[i];
ArrayPut[subarray, i, AnyFromDict[dict]];
ENDLOOP;
PushArray[self, subarray];
};
Def:
PUBLIC
PROC [self: Root, key: Any, val: Any] ~ {
DictPut[CurrentDict[self], key, val];
};
nullDict: Dict ← [executable:
FALSE, ref:
NIL];
Where:
PUBLIC
PROC [self: Root, key: Any]
RETURNS [found:
BOOL, where: Dict] ~ {
dstack: DStack ~ self.dstack;
FOR i: ArrayIndex
DECREASING
IN [0..dstack.count)
DO
dict: Dict ~ dstack.array[i];
IF DictFetch[dict, key].found THEN RETURN [TRUE, dict];
ENDLOOP;
RETURN [FALSE, nullDict];
};
Load:
PUBLIC
PROC [self: Root, key: Any]
RETURNS [Any] ~ {
dstack: DStack ~ self.dstack;
FOR i: ArrayIndex
DECREASING
IN [0..dstack.count)
DO
dict: Dict ~ dstack.array[i];
found: BOOL; val: Any;
[found, val] ← DictFetch[dict, key];
IF found THEN RETURN [val];
ENDLOOP;
ERROR Error[undefined];
};
Store:
PUBLIC
PROC [self: Root, key: Any, val: Any] ~ {
found: BOOL; dict: Dict;
[found, dict] ← Where[self, key];
IF found THEN DictPut[dict, key, val] ELSE Def[self, key, val];
};
DictForAll: PUBLIC PROC [dict: Dict, proc: PROC [key: Any, val: Any]] ~ {
action: RefTab.EachPairAction ~ { proc[NARROW[key], NARROW[val]] };
[] ← RefTab.Pairs[dict.table, action];
};
DictCopy:
PUBLIC
PROC [dict1, dict2: Dict]
RETURNS [Dict] ~ {
ERROR;
};