[_CDCSL_93-16_]<1>Cedar>release>HashTables>Card2TabImpl.mesa

Card2TabImpl.mesa

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:39 pm PDT

DIRECTORY

Checksum, Card2Tab, Card2TabPrivate;

Card2TabImpl: CEDAR MONITOR

LOCKS x USING x: Ref

IMPORTS Checksum

EXPORTS Card2Tab

= { OPEN Card2Tab, Card2TabPrivate;

Impl: TYPE ~ REF Card2TabImplRep;

Card2TabImplRep: PUBLIC TYPE = Card2TabPrivate.Card2TabImplRep;

Public operations

minMod: SeqIndex = 2;

Create: PUBLIC PROC [mod: SeqIndex, equal: EqualProc, hash: HashProc] RETURNS [Ref] = {

seqLen: SeqIndex ~ MAX[mod, minMod];

impl: Impl ~ NEW [Card2TabImplRep ¬ [

hash: hash, equal: equal,

size: 0, sizeLimit: seqLen, inhibitCount: 0,

data: NEW [Seq[seqLen]]

]];

RETURN [NEW [Card2TabRep ¬ [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;

[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];

};

UpdateOperation: TYPE = {none, store, delete};

UpdateAction: TYPE

= PROC [found: BOOL, val: Val]

RETURNS [op: UpdateOperation ← none, new: Val ← NIL];

Update: PUBLIC ENTRY PROC [x: Ref, key: Key, action: UpdateAction] = {

... 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.

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] = {

... atomically copies the table.

impl: Impl = x.impl;

oldData: REF Seq = impl.data;

max: CARDINAL = oldData.max;

newImpl: Impl = NEW[Card2TabImplRep ¬ 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[Card2TabRep ¬ [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];

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.