
DIRECTORY
Checksum, Card4Tab, Card4TabPrivate;
Card4TabImpl: CEDAR MONITOR
LOCKS x USING x: Ref
IMPORTS Checksum
EXPORTS Card4Tab
= { OPEN Card4Tab, Card4TabPrivate;

Impl: TYPE ~ REF Card4TabImplRep;
Card4TabImplRep: PUBLIC TYPE = Card4TabPrivate.Card4TabImplRep;
minMod: SeqIndex = 2;

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

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

Hash: PROC [impl: Impl, key: Key] RETURNS [CARDINAL] ~ TRUSTED INLINE {
IF impl.hash#NIL THEN RETURN impl.hash[key];
RETURN [Checksum.ComputeChecksum[0, BITS[Key]/BITS[CARD16], LONG[@key]]]};

Equal: PROC [impl: Impl, key: Key, node: Node] RETURNS [BOOL]
~ INLINE {RETURN [key=node.key OR (impl.equal#NIL AND impl.equal[key, node.key])]};

Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
impl: Impl ~ x.impl;
index: SeqIndex м Hash[impl, key] MOD impl.data.max;
node: Node м impl.data[index];
WHILE node # NIL DO
IF Equal[impl, key, node] 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;
node: Node м impl.data[Hash[impl, key] MOD impl.data.max];
WHILE node # NIL DO
IF Equal[impl, key, node] 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 ~ Hash[impl, key] MOD impl.data.max;
node: Node м impl.data[index];
WHILE node # NIL DO
IF Equal[impl, key, node] 
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 ~ Hash[impl, key] MOD impl.data.max;
node: Node м impl.data[index];
WHILE node # NIL DO
IF Equal[impl, key, node] 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 ~ Hash[impl, key] MOD impl.data.max;
node: Node м impl.data[index];
lag: Node м NIL;
WHILE node # NIL DO
IF Equal[impl, key, node] 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;
index: SeqIndex м Hash[impl, key] 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 Equal[impl, key, node] 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;
none => NULL;
ENDCASE => ERROR;
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];
};
none, delete => NULL;
ENDCASE => ERROR;
};
};

Copy: PUBLIC ENTRY PROC [x: Ref] RETURNS [Ref] = {
impl: Impl = x.impl;
oldData: REF Seq = impl.data;
max: CARDINAL = oldData.max;
newImpl: Impl = NEW[Card4TabImplRep м 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[Card4TabRep м [impl: newImpl]]];
};
ReHash: INTERNAL PROC [impl: Impl] = {
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 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 ~ Hash[impl, cur.key] MOD newMod;
next м cur.next;
cur.next м newData[index];
newData[index] м cur;
ENDLOOP;
IF next # NIL THEN ERROR;
ENDLOOP;
};

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

}.
  ╚  
Card4TabImpl.mesa
Copyright ╙ 1987, 1988, 1990, 1992 by Xerox Corporation.  All rights reserved.
For Portable Cedar
Russ Atkinson (RRA) July 10, 1990 8:56 am PDT
Doug Wyatt, January 22, 1987 11:04:21 am PST
Carl Hauser, January 14, 1988 2:41:46 pm PST
Last tweaked by Mike Spreitzer on October 17, 1990 4:40 pm PDT
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 2:40:13 pm PST
changes for Portable Cedar
changes to: Hash made a no-op for 32 bit machines.  It was an XOR of the two halves of the word.  Allows for potentially larger tables.

Э╩
е  ХNewlineDelimiter
Ц(cedarcode) styleЩ headЪЬЩIcodeЪЬ
╧eЬCЩNLЪ╨blЩLЩ-LЩ,LЩ,LЩ>ЧШ Ъ╧k	Ш	LЪЬ$Ш$ЧЧЪ╧nЬЯЬЯШLЪЯЬЯЬШLЪЯЬ	ШLЪЯЬ	ШLЪЬЯЬШ#LШ LЪЬЯЬЯЬШ!LЪЬЯЬЯЬ#Ш?ЧЪЬЩLШLШ ЪаЬЯЬЯЬ3ЯЬШXLЪЬЯЬШ$ЪЬЯЬШ%LЪЬШLЪЬ,Ш,LЪЬЯЬШLЪЬШЧLЪЯЬЯЬШ*LЪЬШЧLШ ЪаЬЯЬЯЬЯЬ
ЯЬЯЬШ5LШLЪЯЬШLЪЬШLШ ЧЪаЬЯЬЯЬЯЬЯЬЯЬШGLЪЯЬЯЬЯЬЯЬШ,LЪ
ЯЬЯЬЯЬЯЬЯЬ
ШJLШ ЧЪаЬЯЬ$ЯЬЯЬШ=LЪЬЯЬЯЬЯЬЯЬЯЬШSLШ ЧЪаЬЯЬЯЬЯЬЯЬ	ЯЬШOLШLЪЬ"ЯЬШ4LШЪЯЬЯЬЯШLЪЯЬЯЬЯЬЯЬШ7LШLЪЯЬШЧLЪЯЬЯЬЯЬШLЪЬШLШ ЧЪаЬЯЬЯЬЯЬЯЬЯЬШJLШLЪЬ'ЯЬШ:ЪЯЬЯЬЯШЪЯЬЯЬШ LШLЪЯЬЯЬШLЪЬШЧLШLЪЯЬШЧLЪЯЬЯЬШLЪЬШLШ ЧЪаЬЯЬЯЬЯЬЯЬЯЬШHLШLЪЬ"ЯЬШ4LШЪЯЬЯЬЯШЪЯЬШLЪЯЬЯЬЯЬШ&ЧLШLЪЯЬШЧLЪЬЯЬ9ШOЪЯЬ.ЯЬЯШNLЪЬШЧLЪЯЬЯЬШLЪЬШLШ ЧЪаЬЯЬЯЬЯЬЯЬЯЬШILШLЪЬ"ЯЬШ4LШЪЯЬЯЬЯШLЪЯЬЯЬЯЬЯЬШ.LШLЪЯЬШЧLЪЬЯЬ9ШOLЪЯЬ.ЯЬЯЬШ\LЪЯЬЯЬШLЪЬШLШ ЧЪаЬЯЬЯЬЯЬЯЬЯЬШ?LШLЪЬ"ЯЬШ4LШLЪЬЯЬШЪЯЬЯЬЯШЪЯЬЯЬШ LЪЯЬЯЬЯЬЯЬШ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Щ ЧЪЬЯЩЪЬЯЬ	ЯЬЩLЪЯЬ)ЯЬЩ5ЧLЩ ЧЪаЬЯЬЯЬЯЬ-ШFLЪЬчЩчLЪЯЬЯЬЯЬШЪЯЬ
ЯЬЯЬШLШLЪЬ"ЯЬШ4LШLШLЪЬЯЬШLШLЪЬЯЬШЪЯЬЯЬЯШLШЪЯЬЯЬШ LЪЬЯЬШ#ЪЯЬЯШЪЬШLЪЯЬЯЬЯЬЯЬШ?LШLШЧLШLЪЬЯЬШLЪЯЬЯЬШЧLЪЯЬШLШЧLШLШLЪЯЬШЧLЪЬЯЬЯЬШЪЯЬЯШЪЬ
Ш
LЪЬЯЬ-ШCЪЯЬ.ЯЬЯШNLЪЬШЧLЪЬШЧ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Ъ
ЯЬЯЬЯЬЯЬЯЬШbLШLЪ
ЯЬЯЬЯЬЯЬЯЬШDLШLЪЬЯЬШ(ЪЯЬЯЬЯШ(LЪЬЯЬШЪЯЬЯЬЯЬЯШ3LЪЬ&ЯЬШ1LШLШLШLЪЯЬШЧLЪЯЬЯЬЯЬЯЬШLЪЯЬШЧLШЧLШ LЪЬЯЬШЪЬЯЬЯЬЯЬШ7LЪЬvШvЧLШ LЪЬШЧЩ,LЩLЪЬ╧rЬwЩЗЧLЩ Ч ЕЧ    @  (н  