-- 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. "J&&p