DIRECTORY
RefTab,
RefTabBackdoor,
RefTabPrivate,
Rope USING [Equal],
RopeHash USING [FromRope];

RefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
IMPORTS Rope, RopeHash
EXPORTS RefTab, RefTabBackdoor = { OPEN RefTab, RefTabPrivate;

Impl: TYPE ~ REF RefTabImplRep;
RefTabImplRep: PUBLIC TYPE = RefTabPrivate.RefTabImplRep;
EqualRope: PUBLIC EqualProc ~ {
RETURN [Rope.Equal[s1: NARROW[key1], s2: NARROW[key2], case: TRUE]];
};

EqualRopeCaseless: PUBLIC EqualProc ~ {
RETURN [Rope.Equal[s1: NARROW[key1], s2: NARROW[key2], case: FALSE]];
};

HashRope: PUBLIC HashProc ~ {
RETURN [RopeHash.FromRope[rope: NARROW[key], case: TRUE]];
};

HashRopeCaseless: PUBLIC HashProc ~ {
RETURN [RopeHash.FromRope[rope: NARROW[key], case: FALSE]];
};

minMod: SeqIndex = 2;

Create: PUBLIC PROC [mod: SeqIndex ¬ 17, equal: EqualProc ¬ NIL, hash: HashProc ¬ NIL] RETURNS [Ref] =  {
seqLen: SeqIndex ~ MAX[mod, minMod];
impl: Impl ~ NEW [RefTabImplRep ¬ [
hash: hash, equal: equal,
size: 0, sizeLimit: seqLen, inhibitCount: 0,
data: NEW [Seq[seqLen]]
]];
RETURN [NEW [RefTabRep ¬ [impl: impl]]];
};

GetSize: PUBLIC ENTRY PROC [x: Ref] RETURNS [INT] = {
impl: Impl ~ x.impl;
RETURN [impl.size];
};

ComputeIndex: PROC [impl: Impl, key: Key] RETURNS [SeqIndex] = INLINE {
IF impl.hash=NIL THEN RETURN [LOOPHOLE[key, CARD32] MOD impl.data.max];
RETURN [impl.hash[key] MOD impl.data.max];
};

Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
impl: Impl ~ x.impl;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 
THEN RETURN [TRUE, node.val];
node ¬ node.next;
ENDLOOP;
RETURN [FALSE, NIL];
};

UnmonitoredFetch: PUBLIC PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
impl: Impl ~ x.impl;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 
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;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 
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;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 
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;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 
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;
index: SeqIndex ¬ ComputeIndex[impl, key];
node: Node ¬ impl.data[index];
lag: Node ¬ NIL;
WHILE node # NIL DO
IF key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key]) 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;
};

UnmonitoredPairs: PUBLIC PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL] = {
data: REF Seq ~ x.impl.data;
node: Node _ NIL;
index: CARDINAL _ 0;
DO
[node, index] _ UnmonitoredGetNext[data, node, index];
IF node = NIL THEN EXIT;
IF action[node.key, node.val] THEN RETURN [TRUE];
ENDLOOP;
RETURN[FALSE]};

UnmonitoredGetNext: PROC [data: REF Seq, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
IF node = NIL
THEN index _ data.max
ELSE {
node _ node.next;
IF node # NIL THEN RETURN [node, index];
};
WHILE index > 0 DO
index _ index - 1;
node _ data[index];
IF node # NIL THEN RETURN [node, index];
ENDLOOP;
RETURN [NIL, 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;
index: SeqIndex ¬ ComputeIndex[impl, key];
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 (impl.equal#NIL AND impl.equal[key, node.key]) 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[RefTabImplRep ¬ 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[RefTabRep ¬ [impl: newImpl]]];
};
ReHash: INTERNAL PROC [impl: Impl] = {
oldData: REF Seq = impl.data;
newData: REF Seq;
seek: CARDINAL = impl.data.max * 2;
newPTI: CARDINAL ¬ 0;
newMod: CARDINAL ¬ highPrime;
IF seek >= highPrime
THEN newPTI ¬ PrimeTableSize-1
ELSE DO
newMod ¬ primeTable[newPTI];
IF newMod >= seek THEN EXIT;
newPTI ¬ newPTI+1;
ENDLOOP;
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 ¬ ComputeIndex[impl, cur.key];
next ¬ cur.next;
cur.next ¬ newData[index];
newData[index] ¬ cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
};

PrimeTableSize: NAT = 14;
highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749;
primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [
00002,  00005,  00011,  00023,  00053,  00113,  00251,  00509,  01019,  02039,  04079,  08179,  16369,  highPrime];

}.
Ψ
RefTabImpl.mesa
Copyright Σ 1985, 1987, 1988, 1990, 1992 by Xerox Corporation.  All rights reserved.
RefTabImpl => HashTableImpl by Bertrand Serlet, July 24, 1985
Last Edited by Bertrand Serlet, August 12, 1985 7:06:47 pm PDT
Last Edited by Widom, July 25, 1985 4:46:10 pm PDT
Spreitzer, January 10, 1992 9:51 am PST
HashTableImpl => RefTabImpl by Doug Wyatt, January 7, 1987
Russ Atkinson (RRA) July 10, 1990 9:11 am PDT
Doug Wyatt, February 4, 1987 2:57:57 pm PST
Carl Hauser, June 21, 1988 10:29:56 pm PDT
Michael Plass, February 21, 1992 5:30 pm PST
Willie-s, March 3, 1992 12:40 pm PST
Hash/Equal functions
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.

Carl Hauser, January 14, 1988 3:11:35 pm PST
prepare for Portable Cedar
changes to: DIRECTORY folded RefTabExtras, Munch made identity function for Portable Cedar (32 bit machines).

Κ
•NewlineDelimiter

–
(cedarcode) style™
headš
œ™Icodešœ
Οe
œI™TLš
œ=™=Lš
œ>™>L™2L™'Lš
œ:™:L™-Lš
œ+™+L™*L™,L™$—˜š
Οk	˜	Lš
œ˜L˜Lš
œ˜Lšœžœ	˜Lšœ	žœ˜L˜——š
Οn
œžœ
žœ
žœžœ˜.Lšžœ˜Lšžœžœ˜>L˜Lšœžœžœ˜Lšœžœ
žœ˜9—™šŸ	œžœ˜Lšžœžœžœžœ˜DL˜L˜—šŸœžœ˜'Lšžœžœžœžœ˜EL˜L˜—šŸœžœ
˜Lšžœžœ
žœ˜:L˜L˜—šŸœžœ
˜%Lšžœžœ
žœ˜;L˜L˜——š
œ™L˜L˜šŸœžœ
žœ)žœžœžœ˜iLšœžœ˜$šœ
žœ˜#Lš
œ˜Lš
œ,˜,Lšœžœ˜Lš
œ˜—Lšžœžœ˜(Lš
œ˜—L˜šŸœžœ
žœ
žœ
žœžœ˜5L˜Lšžœ
˜Lš
œ˜L˜—šŸœžœžœžœ˜GLšžœžœ
žœ
žœžœžœžœ˜GLšžœžœ˜*L˜—L˜šŸœžœ
žœ
žœžœ	žœ˜OL˜L˜*L˜šžœžœ
ž˜šžœžœ
žœ
žœ˜BLšžœ
žœžœ˜—L˜Lšžœ
˜—Lšžœžœžœ˜Lš
œ˜L˜—š
Ÿœžœ
žœžœ	žœ˜TL˜L˜*L˜šžœžœ
ž˜šžœžœ
žœ
žœ˜BLšžœ
žœžœ˜—L˜Lšžœ
˜—Lšžœžœžœ˜Lš
œ˜L˜—šŸœžœ
žœ
žœžœžœ˜JL˜L˜*L˜šžœžœ
ž˜šžœžœ
žœ
žœ˜BLšžœžœžœ˜%—L˜Lšžœ
˜—Lšžœžœ˜Lš
œ˜L˜—šŸœžœ
žœ
žœžœžœ˜HL˜L˜*L˜šžœžœ
ž˜šžœžœ
žœ
žœ˜BLšžœžœžœ˜&—L˜Lšžœ
˜—Lšœžœ9˜OLšžœ.žœžœ˜\Lšžœžœ˜Lš
œ˜L˜—šŸœžœ
žœ
žœžœžœ˜IL˜L˜*L˜šžœžœ
ž˜šžœžœ
žœ
žœ˜BLšžœ
žœžœ˜—L˜Lšžœ
˜—Lšœžœ9˜OLšžœ.žœžœ˜\Lšžœžœ˜Lš
œ˜L˜—šŸœžœ
žœ
žœžœžœ˜?L˜L˜*L˜Lšœžœ
˜šžœžœ
ž˜š
žœžœ
žœ
žœžœ˜HLšžœžœ
žœžœ˜IL˜Lšžœžœ˜Lš
œ˜—L˜L˜Lšžœ
˜—Lšžœžœ˜Lš
œ˜L˜—šŸœžœ
žœ
žœ
˜%L˜Lš
žœ
žœžœžœ
žœ
˜DL˜Lš
œ˜L˜—š
Ÿœžœ
žœ"žœžœ˜WLšœžœ˜Lšœ
žœ
˜Lšœžœ˜š
ž˜Lš
œ6˜6Lšžœžœ
žœ
žœ
˜Lšžœžœ
žœžœ˜1Lšžœ
˜—Lšžœ
žœ˜L˜—šŸœžœžœžœžœžœ˜bšžœž˜
Lšžœ˜šžœ˜L˜Lšžœžœ
žœ
žœ˜(L˜——šžœž˜Lš
œ˜Lš
œ˜Lšžœžœ
žœ
žœ˜(Lšžœ
˜—Lšžœžœ˜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™—šœžœžœ	žœ
žœ)žœ™hL™—šŸœžœ
žœ
žœ-˜FLš
œη
™η
Lšžœ
žœžœ
˜šžœ
žœ
žœ˜L˜L˜*L˜L˜Lšœžœ
˜L˜Lšœžœ
˜šžœžœ
ž˜L˜š
žœžœ
žœ
žœžœ˜HLšœžœ˜#šžœž˜š
œ˜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š
žœžœžœ
žœžœ˜DL˜Lšœžœ˜(šžœ
žœž˜(Lšœ
žœ
˜šžœžœžœ
ž˜3L˜.L˜L˜L˜Lšžœ
˜—Lšžœžœ
žœ
žœ
˜Lšžœ
˜—L˜L˜—šœžœ˜Lšœžœžœ˜/—šœžœžœ
žœ˜7Lš
œs˜s—L˜Lš
œ˜—™,L™LšœΟr	œ‘œ=™m—L™—…— 1ό