-- ScriptHashImpl.mesa - last edit by
-- Sweet, 10-Aug-82 10:58:25
-- Karlton, 11-Aug-82 13:56:36
-- Mitchell, October 12, 1982 3:22 pm

DIRECTORY
Environment USING [wordsPerPage],
Inline USING [BITAND, BITXOR, LongCOPY, LowHalf],
UnsafeStorage USING [NewUObject],
ScriptHash USING [Hash, nullHash, nullVal, Val],
RefText USING [Append, Equal];

ScriptHashImpl: PROGRAM IMPORTS Inline, MSegment, String EXPORTS ScriptHash =
BEGIN OPEN ScriptHash;

HashVec: TYPE = RECORD [vec: SEQUENCE COMPUTED CARDINAL OF Hash];

Object: PUBLIC TYPE = RECORD [
caseHeed: BOOLEAN,
buckets: [1..128],
data: Base,
nextAvail: Hash,
nPages: CARDINAL,
z: UNCOUNTED ZONE];

Handle: TYPE = LONG POINTER TO Object;

Base: TYPE = LONG BASE POINTER TO HashVec;
Hash: PUBLIC TYPE = Base RELATIVE ORDERED POINTER TO HashBlock;

HashBlock: TYPE = RECORD [
next: Hash,
value: ScriptHash.Val,
string: StringBody];

PagesForWords: PRIVATE PROC [w: CARDINAL] RETURNS [p: CARDINAL] =
BEGIN
lc: LONG CARDINAL = LONG[w] + (Environment.wordsPerPage-1);
RETURN [Inline.LowHalf[lc / Environment.wordsPerPage]];
END;

NewEntry: PRIVATE PROCEDURE [h: Handle, s: REF TEXT, next: Hash]
RETURNS [hash: Hash] =
BEGIN
w: CARDINAL = SIZE[HashBlock] + (s.length+1)/2;
IF LOOPHOLE[h.nextAvail+w, CARDINAL] > h.nPages*Environment.wordsPerPage THEN
BEGIN -- make more space
np, nw: CARDINAL;
oldData: LONG POINTER ← h.data;
np ← h.nPages + PagesForWords[w];
nw ← LOOPHOLE[h.nextAvail];
h.data ← MSegment.Address[MSegment.Create[pages: np, release: []]];
Inline.LongCOPY[
from:oldData,
to: h.data,
nwords: nw];
MSegment.Delete[MSegment.AddresstoSegment[oldData]];
END;
hash ← h.nextAvail; h.nextAvail ← h.nextAvail+w;
h.data[hash] ← [
next: next, value: NULL,
string: [length: 0, maxlength: s.length, text:] ];
RefText.Append[@h.data[hash].string, s];
END;

HashFn: PRIVATE PROCEDURE [h: Handle, s: REF TEXT] RETURNS [[0..128)] =
BEGIN -- computes the hash index for string s
CharBits: PROCEDURE [CHARACTER, WORD] RETURNS [WORD] =
LOOPHOLE[Inline.BITAND];
Mask: WORD = 337B;  -- masks out ASCII case shifts
n: CARDINAL = s.length;
v: WORD;
v ← CharBits[s[0], Mask]*177B + CharBits[s[n-1], Mask];
RETURN [Inline.BITXOR[v, n*17B] MOD h.buckets]
END;

Lookup: PUBLIC PROCEDURE [h: Handle, s: REF TEXT] RETURNS [hash: Hash] =
BEGIN
i: [0..128) ← HashFn[h, s];
hash ← h.data.vec[i];
WHILE hash # nullHash DO
IF RefText.Equal[s1: s, s2: @h.data[hash].string, case: h.caseHeed] THEN EXIT;
hash ← h.data[hash].next;
ENDLOOP;
END;

Enter: PUBLIC PROCEDURE [h: Handle, s: REF TEXT, val: Val]
RETURNS [hash: Hash] =
BEGIN
i: [0..128) ← HashFn[h, s];
hash ← h.data.vec[i];
WHILE hash # nullHash DO
IF RefText.Equal[s1: s, s2: @h.data[hash].string, case: h.caseHeed] THEN EXIT;
hash ← h.data[hash].next;
ENDLOOP;
IF hash = nullHash THEN {
hash ← NewEntry[h, s, h.data.vec[i]]; h.data.vec[i] ← hash};
h.data[hash].value ← val;
END;

GetId: PUBLIC PROC [h: Handle, hash: Hash] RETURNS [s: REF TEXT] =
BEGIN
s ← RefText.New[h.data[hash].string.length];
String.AppendString[s, @h.data[hash].string];
END;

AppendId: PUBLIC PROC [h: Handle, s: REF TEXT, hash: Hash] =
BEGIN
String.AppendString[s, @h.data[hash].string];
END;

Enumerate: PUBLIC PROC [
h: Handle,
action: PROC [hash: Hash] RETURNS [done: BOOLEAN]]
RETURNS [hash: Hash] =
BEGIN
hash ← LOOPHOLE[h.buckets * SIZE[Hash]];
UNTIL hash = h.nextAvail DO
IF action[hash] THEN RETURN;
hash ← hash + SIZE[HashBlock] + (h.data[hash].string.length+1)/2;
ENDLOOP;
RETURN [nullHash];
END;

SetValue: PUBLIC PROC [h: Handle, hash: Hash, val: Val] = {
h.data[hash].value ← val};

Value: PUBLIC PROC [h: Handle, hash: Hash] RETURNS [Val] = {
RETURN [h.data[hash].value]};

ValueForString: PUBLIC PROC [h: Handle, s: REF TEXT] RETURNS [Val] = {
hash: Hash = Lookup[h, s];
IF hash = nullHash THEN RETURN[nullVal];
RETURN[h.data[hash].value]};

Create: PUBLIC PROC [z: UNCOUNTED ZONE, buckets: [1..128], expItems, aveItemSize: CARDINAL, caseHeed: BOOLEAN]
RETURNS [h: Handle] = {
np: CARDINAL = PagesForWords[
buckets * SIZE[Hash] + expItems * (SIZE[HashBlock] + (aveItemSize+1)/2)];
data: Base = UnsafeStorage.NewUObject[size: np*Environment.wordsPerPage, zone: z];
h ← NEW[Object ← [
nPages: np, caseHeed: caseHeed, buckets: buckets,
data: data, nextAvail: LOOPHOLE[buckets*SIZE[Hash], z: z]]];
FOR i: CARDINAL IN [0..buckets) DO data.vec[i] ← nullHash; ENDLOOP;
};

Destroy: PUBLIC PROC [h: Handle] = {FREE[h]};

END.