DIRECTORY Rope USING [Equal], RopeHash USING [FromRope, FromRefText], SymTab, SymTabPrivate; SymTabImpl: CEDAR MONITOR LOCKS x USING x: Ref IMPORTS Rope, RopeHash EXPORTS SymTab = { OPEN SymTab, SymTabPrivate; Impl: TYPE ~ REF SymTabImplRep; SymTabImplRep: PUBLIC TYPE = SymTabPrivate.SymTabImplRep; minMod: SeqIndex = 2; Create: PUBLIC PROC [mod: SeqIndex, case: BOOL] RETURNS [Ref] = { seqLen: SeqIndex ~ MAX[mod, minMod]; impl: Impl ~ NEW [SymTabImplRep ¬ [ case: case, size: 0, sizeLimit: seqLen, inhibitCount: 0, data: NEW [Seq[seqLen]] ]]; RETURN [NEW [SymTabRep ¬ [impl: impl]]]; }; GetSize: PUBLIC ENTRY PROC [x: Ref] RETURNS [INT] = { impl: Impl ~ x.impl; RETURN [impl.size]; }; Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = { impl: Impl ~ x.impl; case: BOOL ~ impl.case; index: SeqIndex ¬ RopeHash.FromRope[key, case] MOD impl.data.max; node: Node ¬ impl.data[index]; WHILE node # NIL DO IF key=node.key OR Rope.Equal[key, node.key, case] THEN RETURN [TRUE, node.val]; node ¬ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; FetchText: PUBLIC ENTRY PROC [x: Ref, key: REF READONLY TEXT] RETURNS [found: BOOL, val: Val] = TRUSTED { impl: Impl ~ x.impl; case: BOOL ~ impl.case; hash: CARDINAL ~ (IF case THEN RopeHash.FromRefText[key] ELSE RopeHash.FromRope[LOOPHOLE[key, Key], case]); node: Node ¬ impl.data[hash MOD impl.data.max]; WHILE node # NIL DO IF Rope.Equal[LOOPHOLE[key, Key], node.key, case] THEN RETURN [TRUE, node.val]; node ¬ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; Replace: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { impl: Impl ~ x.impl; case: BOOL ~ impl.case; node: Node ¬ impl.data[RopeHash.FromRope[key, case] MOD impl.data.max]; WHILE node # NIL DO IF key=node.key OR Rope.Equal[key, node.key, case] THEN { node.val ¬ val; RETURN [TRUE]; }; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Store: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { impl: Impl ~ x.impl; case: BOOL ~ impl.case; index: SeqIndex ~ RopeHash.FromRope[key, case] MOD impl.data.max; node: Node ¬ impl.data[index]; WHILE node # NIL DO IF key=node.key OR Rope.Equal[key, node.key, case] THEN {node.val ¬ val; RETURN [FALSE]}; node ¬ node.next; ENDLOOP; impl.data[index] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[index]]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; RETURN [TRUE]; }; Insert: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { impl: Impl ~ x.impl; case: BOOL ~ impl.case; index: SeqIndex ~ RopeHash.FromRope[key, case] MOD impl.data.max; node: Node ¬ impl.data[index]; WHILE node # NIL DO IF key=node.key OR Rope.Equal[key, node.key, case] THEN RETURN [FALSE]; node ¬ node.next; ENDLOOP; impl.data[index] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[index]]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; RETURN [TRUE]; }; Delete: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [BOOL] = { impl: Impl ~ x.impl; case: BOOL ~ impl.case; index: SeqIndex ~ RopeHash.FromRope[key, case] MOD impl.data.max; node: Node ¬ impl.data[index]; lag: Node ¬ NIL; WHILE node # NIL DO IF key=node.key OR Rope.Equal[key, node.key, case] THEN { IF lag = NIL THEN impl.data[index] ¬ node.next ELSE lag.next ¬ node.next; impl.size ¬ impl.size - 1; RETURN [TRUE]; }; lag ¬ node; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Erase: PUBLIC ENTRY PROC [x: Ref] = { impl: Impl ~ x.impl; FOR i: SeqIndex IN [0..impl.data.max) DO impl.data[i] ¬ NIL ENDLOOP; impl.size ¬ 0; }; Pairs: PUBLIC PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL] = { Inhibit: ENTRY PROC [x: Ref] ~ { impl: Impl ~ x.impl; impl.inhibitCount ¬ impl.inhibitCount + 1; }; Release: ENTRY PROC [x: Ref] ~ { impl: Impl ~ x.impl; impl.inhibitCount ¬ impl.inhibitCount - 1; IF impl.inhibitCount#0 THEN RETURN; WHILE impl.size > impl.sizeLimit DO ReHash[impl] ENDLOOP; }; Enumerate: PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL ¬ FALSE] ~ { node: Node ¬ NIL; index: CARDINAL ¬ 0; DO [node, index] ¬ GetNext[x, node, index]; IF node = NIL THEN EXIT; IF action[node.key, node.val] THEN RETURN [TRUE]; ENDLOOP; }; Inhibit[x]; quit ¬ Enumerate[x, action ! UNWIND => Release[x]]; Release[x]; }; GetNext: ENTRY PROC [x: Ref, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = { impl: Impl ~ x.impl; IF node = NIL THEN index ¬ impl.data.max ELSE { node ¬ node.next; IF node # NIL THEN RETURN [node, index]; }; WHILE index > 0 DO index ¬ index - 1; node ¬ impl.data[index]; IF node # NIL THEN RETURN [node, index]; ENDLOOP; RETURN [NIL, 0]; }; Update: PUBLIC ENTRY PROC [x: Ref, key: Key, action: UpdateAction] = { ENABLE UNWIND => NULL; IF action # NIL THEN { impl: Impl ~ x.impl; case: BOOL ~ impl.case; index: SeqIndex ¬ RopeHash.FromRope[key, case] MOD impl.data.max; head: Node ¬ impl.data[index]; node: Node ¬ head; lag: Node ¬ NIL; op: UpdateOperation ¬ none; val: Val ¬ NIL; WHILE node # NIL DO next: Node ¬ node.next; IF key=node.key OR Rope.Equal[key, node.key, case] THEN { [op, val] ¬ action[TRUE, node.val]; SELECT op FROM delete => { IF lag = NIL THEN impl.data[index] ¬ next ELSE lag.next ¬ next; impl.size ¬ impl.size - 1; }; store => node.val ¬ val; ENDCASE; RETURN; }; lag ¬ node; node ¬ next; ENDLOOP; [op, val] ¬ action[FALSE, NIL]; SELECT op FROM store => { impl.data[index] ¬ NEW[NodeRep ¬ [key: key, val: val, next: head]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; }; ENDCASE; }; }; Copy: PUBLIC ENTRY PROC [x: Ref] RETURNS [Ref] = { impl: Impl = x.impl; oldData: REF Seq = impl.data; max: CARDINAL = oldData.max; newImpl: Impl = NEW[SymTabImplRep ¬ impl­]; newData: REF Seq = NEW[Seq[max]]; -- note, all buckets initially NIL newImpl.data ¬ newData; FOR i: NAT IN [0..max) DO oldChain: Node ¬ oldData[i]; IF oldChain # NIL THEN { newTail: Node ¬ NIL; WHILE oldChain # NIL DO new: Node ¬ NEW[NodeRep ¬ [key: oldChain.key, val: oldChain.val, next: NIL]]; IF newTail = NIL THEN newData[i] ¬ new ELSE newTail.next ¬ new; newTail ¬ new; oldChain ¬ oldChain.next; ENDLOOP; }; ENDLOOP; RETURN [NEW[SymTabRep ¬ [impl: newImpl]]]; }; ReHash: INTERNAL PROC [impl: Impl] = { case: BOOL ~ impl.case; oldData: REF Seq = impl.data; newData: REF Seq; seek: CARDINAL = impl.data.max * 2; newPTI, newMod: CARDINAL ¬ 0; IF primeTable[PrimeTableSize-1] > LAST[SeqIndex] THEN ERROR; FOR newPTI ¬ 0, newPTI+1 WHILE newPTI+1 < PrimeTableSize AND primeTable[newPTI] < seek DO NULL ENDLOOP; newMod ¬ primeTable[newPTI]; IF newMod = impl.data.max THEN {impl.sizeLimit ¬ LAST[INT]; RETURN}; impl.sizeLimit ¬ newMod; impl.data ¬ newData ¬ NEW [Seq[newMod]]; FOR i: SeqIndex IN [0 .. oldData.max) DO next: Node ¬ NIL; FOR cur: Node ¬ oldData[i], next WHILE cur # NIL DO index: SeqIndex ~ RopeHash.FromRope[cur.key, case] MOD newMod; next ¬ cur.next; cur.next ¬ newData[index]; newData[index] ¬ cur; ENDLOOP; IF next # NIL THEN ERROR; ENDLOOP; }; PrimeTableSize: NAT = 14; primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [ 00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, 32749]; }. Έ SymTabImpl.mesa Copyright Σ 1985, 1987, 1988, 1990, 1991 by Xerox Corporation. All rights reserved. HashTableImpl => SymTabImpl by Doug Wyatt, January 7, 1987 Russ Atkinson (RRA) July 10, 1990 8:59 am PDT Doug Wyatt, January 22, 1987 11:04:29 am PST Public operations UpdateOperation: TYPE = {none, store, delete}; UpdateAction: TYPE = PROC [found: BOOL, val: Val] RETURNS [op: UpdateOperation _ none, new: Val _ NIL]; ... atomically performs an update action; looks up key and calls action, which returns the desired operation. If op=none, the table is not changed; if op=store, the new value is stored; if op=delete, key is removed from the table. ... atomically copies the table. Κ t•NewlineDelimiter –(cedarcode) style™headšœ™Icodešœ ΟeœI™TLšœ:™:L™-Lšœ,™,—˜šΟk ˜ Lšœžœ ˜Lšœ žœ˜'Lšœ˜Lšœ˜——š Οn œžœžœžœžœ˜.Lšžœ˜Lšžœ žœ˜.L˜Lšœžœžœ˜Lšœžœžœ˜9—šœ™L˜L˜š Ÿœžœžœžœžœ ˜BLšœžœ˜$šœ žœ˜#Lšœ ˜ Lšœ,˜,Lšœžœ˜Lšœ˜—Lšžœžœ˜(Lšœ˜—L˜š Ÿœžœžœžœ žœžœ˜5L˜Lšžœ ˜Lšœ˜L˜—š Ÿœžœžœžœžœ žœ˜OL˜Lšœžœ ˜Lšœ/žœ˜ALšœ˜šžœžœž˜Lš žœžœ žœžœžœ ˜PL˜Lšžœ˜—Lšžœžœžœ˜Lšœ˜L˜—šŸ œžœžœžœžœžœžœžœ žœžœ˜iL˜Lšœžœ ˜Lš œžœžœžœžœžœ˜kLšœžœ˜/šžœžœž˜Lš žœ žœžœžœžœ ˜OL˜Lšžœ˜—Lšžœžœžœ˜Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜JL˜Lšœžœ ˜Lšœ4žœ˜Gšžœžœž˜šžœžœ!žœ˜9Lšœ˜Lšžœžœ˜Lšœ˜—L˜Lšžœ˜—Lšžœžœ˜Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜HL˜Lšœžœ ˜Lšœ/žœ˜ALšœ˜šžœžœž˜šžœžœ!˜3Lšžœžœžœ˜&—L˜Lšžœ˜—Lšœžœ9˜Ošžœ.žœž˜NLšœ ˜ —Lšžœžœ˜Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜IL˜Lšœžœ ˜Lšœ/žœ˜ALšœ˜šžœžœž˜Lš žœžœ!žœžœžœ˜GL˜Lšžœ˜—Lšœžœ9˜OLšžœ.žœžœ˜\Lšžœžœ˜Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜?L˜Lšœžœ ˜Lšœ/žœ˜ALšœ˜Lšœ žœ˜šžœžœž˜šžœžœ!žœ˜9Lšžœžœžœžœ˜ILšœ˜Lšžœžœ˜Lšœ˜—L˜ L˜Lšžœ˜—Lšžœžœ˜Lšœ˜L˜—šŸœžœžœžœ ˜%L˜Lš žœ žœžœžœžœ˜DLšœ˜Lšœ˜L˜—š Ÿœžœžœ"žœžœ˜LšŸœžœžœ ˜ L˜Lšœ*˜*L˜—šŸœžœžœ ˜ L˜Lšœ*˜*Lšžœžœžœ˜#Lšžœžœžœ˜9L˜—š Ÿ œžœ"žœžœžœ˜QLšœ žœ˜Lšœžœ˜šž˜Lšœ(˜(Lšžœžœžœžœ˜Lšžœžœžœžœ˜1Lšžœ˜—L˜—L˜ Lšœžœ˜3L˜ Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜VL˜Lšžœžœžœ˜(šžœ˜L˜Lšžœžœžœžœ˜(L˜—šžœ ž˜Lšœ˜Lšœ˜Lšžœžœžœžœ˜(Lšžœ˜—Lšžœžœ˜L˜L˜—L˜šœžœ™.L™—š œžœžœ žœ žœ)žœ™hL™—šŸœžœžœžœ-˜FLšœη™ηLšžœžœžœ˜šžœ žœžœ˜L˜Lšœžœ ˜Lšœ/žœ˜ALšœ˜Lšœ˜Lšœ žœ˜Lšœ˜Lšœ žœ˜šžœžœž˜Lšœ˜šžœžœ!žœ˜9Lšœžœ ˜#šžœž˜šœ ˜ Lšžœžœžœžœ˜?Lšœ˜L˜—Lšœ˜Lšžœ˜—Lšžœ˜L˜—L˜ Lšœ ˜ Lšžœ˜—Lšœžœžœ˜šžœž˜šœ ˜ Lšœžœ-˜Cšžœ.žœž˜NLšœ ˜ —Lšœ˜—Lšžœ˜—L˜—L˜—L˜š Ÿœžœžœžœ žœ ˜2Lšœ ™ L˜Lšœ žœ˜Lšœžœ˜Lšœžœ˜+Lšœ žœžœ Οc"˜ELšœ˜šžœžœžœ ž˜Lšœ˜šžœ žœžœ˜Lšœžœ˜šžœ žœž˜Lšœ žœ8žœ˜MLšžœ žœžœžœ˜?Lšœ˜Lšœ˜Lšžœ˜—L˜—Lšžœ˜—Lšžœžœ˜*L˜L™—šŸœžœžœ˜&Lšœžœ ˜Lšœ žœ˜Lšœ žœ˜Lšœžœ˜#Lšœžœ˜Lšžœ žœ žœžœ˜L˜L˜L˜Lšžœ˜—Lšžœžœžœžœ˜Lšžœ˜—L˜—L˜Lšœžœ˜šœ žœžœžœ˜7Lšœo˜o—L˜Lšœ˜——…—*<