CardTabImpl.mesa
Copyright Ó 1987, 1988, 1990, 1991, 1992 by Xerox Corporation. All rights reserved.
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
Willie-s, March 3, 1992 12:46 pm PST
CardTabImpl:
CEDAR
MONITOR
LOCKS x USING x: Ref
EXPORTS CardTab, CardTabBackdoor
= { OPEN CardTab, CardTabPrivate;
Impl: TYPE ~ REF CardTabImplRep;
CardTabImplRep: PUBLIC TYPE = CardTabPrivate.CardTabImplRep;
Public operations
minMod: SeqIndex = 2;
Create:
PUBLIC
PROC [mod: SeqIndex]
RETURNS [Ref] = {
seqLen: SeqIndex ~ MAX[mod, minMod];
impl: Impl ~
NEW [CardTabImplRep ¬ [
size: 0, sizeLimit: seqLen, inhibitCount: 0,
data: NEW [Seq[seqLen]]
]];
RETURN [NEW [CardTabRep ¬ [impl: impl]]];
};
GetSize:
PUBLIC
ENTRY
PROC [x: Ref]
RETURNS [
INT] = {
impl: Impl ~ x.impl;
RETURN [impl.size];
};
Hash:
PROC [key:
CARD32]
RETURNS [
CARD32] =
INLINE {
reduce the number of bits in the key to something reasonable for a MOD operation.
on a 32 bit machine this can be a no-op
RETURN[key]
};
Fetch:
PUBLIC
ENTRY
PROC [x: Ref, key: Key]
RETURNS [found:
BOOL, val: Val] = {
impl: Impl ~ x.impl;
index: SeqIndex ¬ Hash[key] MOD impl.data.max;
node: Node ¬ impl.data[index];
WHILE node #
NIL
DO
IF 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;
data: REF Seq ~ impl.data;
index: SeqIndex ← Hash[key] MOD data.max;
node: Node ← data[index];
WHILE node #
NIL
DO
IF 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;
node: Node ¬ impl.data[Hash[key] MOD impl.data.max];
WHILE node #
NIL
DO
IF 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 ~ Hash[key] MOD impl.data.max;
node: Node ¬ impl.data[index];
WHILE node #
NIL
DO
IF 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 ~ Hash[key] MOD impl.data.max;
node: Node ¬ impl.data[index];
WHILE node #
NIL
DO
IF 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 ~ Hash[key] MOD impl.data.max;
node: Node ¬ impl.data[index];
lag: Node ¬ NIL;
WHILE node #
NIL
DO
IF 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;
};
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];
};
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[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 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] = {
... atomically copies the table.
impl: Impl = x.impl;
oldData: REF Seq = impl.data;
max: CARDINAL = oldData.max;
newImpl: Impl = NEW[CardTabImplRep ¬ 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[CardTabRep ¬ [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[cur.key] 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];
}.