TypeHashImpl.mesa
Copyright © 1984 by Xerox Corporation. All rights reserved.
Russ Atkinson, October 23, 1984 3:31:01 pm PDT
DIRECTORY
Basics USING[BITAND, BITOR, BITSHIFT, BITXOR],
TypeStrings USING[TypeString],
TypeHash USING [TypeKey, nullKey, WordPerKey];
KeyAsChars:
TYPE =
PACKED ARRAY [0 .. CharsPerKey)
OF
CHAR;
CharsPerKey: CARDINAL = 8;
KeyAsCharsPtr: TYPE = LONG POINTER TO KeyAsChars;
TypeStrHash:
PUBLIC PROCEDURE[ts: TypeString]
RETURNS[key: TypeKey ← nullKey] = {
TypeStrings is of type LONG STRING.
chars: CARDINAL ← ts.length;
keyPtr: KeyPtr ← LOOPHOLE[ts, KeyPtr] + SIZE[StringBody];
AccumKey:
PROC [temp: TypeKey] =
INLINE {
key[0] ← Basics.BITXOR[key[0], temp[0] ];
key[1] ← Basics.BITXOR[key[1], temp[1] ];
key[2] ← Basics.BITXOR[key[2], temp[2] ];
key[3] ← Basics.BITXOR[key[3], temp[3] ];
key[3] ← Basics.BITOR[Basics.BITSHIFT[key[3], 1], Basics.BITSHIFT[key[2], -15] ];
key[2] ← Basics.BITOR[Basics.BITSHIFT[key[2], 1], Basics.BITSHIFT[key[1], -15] ];
key[1] ← Basics.BITOR[Basics.BITSHIFT[key[1], 1], Basics.BITSHIFT[key[0], -15] ];
key[0] ← Basics.BITSHIFT[key[0], 1];
key[0] ← IF Basics.BITAND[key[0], 1] = 1 THEN key[0]-1 ELSE key[0]+1;
};
WHILE chars >= CharsPerKey
DO
temp: TypeKey ← keyPtr^;
AccumKey[temp];
keyPtr ← keyPtr + WordPerKey;
chars ← chars - CharsPerKey;
ENDLOOP;
IF chars # 0
THEN {
charKey: KeyAsChars ← ALL[0C];
charKeyPtr: KeyAsCharsPtr ← LOOPHOLE[keyPtr];
FOR i:
NAT
IN [0..chars)
DO
charKey[i] ← charKeyPtr[i];
ENDLOOP;
AccumKey[LOOPHOLE[charKey]];
};
IF key[0] = 0
AND key[1] = 0
AND key[2] = 0
AND key[3] = 0
THEN {
Don't ever return a null type key!
key[0] ← 1;
};
};