DIRECTORY AllocatorOps USING [permanentPageZone], Basics USING [bytesPerWord, BITAND, BITSHIFT, LowHalf], BrandXSymbolDefs USING [PreDefinedSEI], BrandYSymbolDefs USING [PreDefinedSEI], Checksum USING [ComputeChecksum], RCMap USING [Index], RCMapOps USING [Initialize], RTSymbolDefs USING [SymbolIndex, nullSymbolIndex], RTTypesBasicPrivate USING [FindSTI, InitialSTIRangeSize, LOOPHOLEDRMapStiStd, LOOPHOLEDTMapStiStd, PTypeDesc, RMapTiTd, STDesc, SymbolTableIndex, TMapStiStd, TMapTiTd, TypeDesc, UniqueTypeFinger], SafeStorage USING [TypeIndex, Type, nullType, anyType, lastPredefinedTypeIndex], StorageTraps USING [], TimeStamp USING [Null], TypeHash USING [TypeKey, nullKey, WordPerKey], TypeStrings USING [Code, TypeString], UnsafeStorage USING [GetSystemUZone], VM USING [AddressForPageNumber, Allocate]; TypesBasicImpl: MONITOR IMPORTS AllocatorOps, Basics, Checksum, RTTypesBasicPrivate, RCMapOps, UnsafeStorage, VM EXPORTS RTTypesBasicPrivate, SafeStorage, StorageTraps, TypeHash = BEGIN OPEN bx: BrandXSymbolDefs, by: BrandYSymbolDefs, RTSymbolDefs, RTTypesBasicPrivate, RTTypesBasicPrivate, RTTypesBasicPrivate, SafeStorage, TypeHash, TypeStrings; TypeKey: TYPE = TypeHash.TypeKey; nullKey: TypeKey = TypeHash.nullKey; KeyPtr: TYPE = LONG POINTER TO TypeKey; InitialTiRangeSize: CARDINAL = 10000B; InitialUTFRangeSize: CARDINAL = 10000B; InitialTsRangeSize: CARDINAL = 4000B; rcMapBasePages: CARDINAL = 30; uz: UNCOUNTED ZONE _ UnsafeStorage.GetSystemUZone[]; lastTypeIndex: TypeIndex _ lastPredefinedTypeIndex; nullTD: TypeDesc _ [utf: [umid: TimeStamp.Null, seIndex: nullSymbolIndex], symbolAccess: [], myType: nullType, typekey: nullKey]; atomRecType: Type _ nullType; atomRecString: TypeString _ NIL; atomRecKey: TypeKey; MapTiTd: PUBLIC TMapTiTd; -- table: TypeIndex -> PTypeDesc TMapTsTdl: TYPE = RECORD[SEQUENCE length: CARDINAL OF PTypeDesc]; MapTsTdl: LONG POINTER TO TMapTsTdl; TMapUTFTi: TYPE = RECORD[SEQUENCE length: CARDINAL OF TypeIndex]; MapUTFTi: LONG POINTER TO TMapUTFTi; MapStiStd: PUBLIC TMapStiStd; -- EXTREMELY delicate initialization. WATCH OUT. InvalidType: PUBLIC ERROR[type: Type] = CODE; NarrowFault: PUBLIC ERROR = CODE; NarrowRefFault: PUBLIC ERROR[ref: REF ANY, targetType: Type] = CODE; TooManyTypes: ERROR = CODE; EquivalentTypes: PUBLIC SAFE PROC [t1, t2: Type] RETURNS [BOOL] = TRUSTED { IF t1 = t2 THEN RETURN [TRUE]; RETURN [GetCanonicalType[t1] = GetCanonicalType[t2]]; }; GetCanonicalType: PUBLIC ENTRY SAFE PROC [t: Type] RETURNS [Type] = TRUSTED { ENABLE UNWIND => NULL; RETURN [DoGetCanonicalType[t]]; }; NotifyAtomRecType: PUBLIC PROC [type: Type] = { atomRecType _ type}; GetLastTypeIndex: PUBLIC PROC RETURNS [ans: TypeIndex _ lastTypeIndex] = {}; CheckForNarrowRefFault: PUBLIC PROC [ref: REF, targetType: Type] RETURNS [REF _ NIL] = { IF ref # NIL THEN ERROR NarrowRefFault[ref: ref, targetType: targetType]; }; GetMapTiTd: PUBLIC PROC RETURNS [ans: LONG POINTER TO RMapTiTd _ MapTiTd] = {}; Enter: PUBLIC ENTRY PROC [inner: PROC] = { ENABLE UNWIND => NULL; inner[]; }; AcquireTypeForLoader: PUBLIC ENTRY PROC [ utf: UniqueTypeFinger, std: STDesc, sei: SymbolIndex, ts: TypeString, rcmi: RCMap.Index, canonicalize: BOOL _ FALSE, initializing: BOOL _ FALSE] RETURNS [Type] = { ENABLE UNWIND => NULL; ptd: PTypeDesc; IF canonicalize THEN ptd _ FindCanonicalPTD[ts] ELSE ptd _ FindPTD[utf, ts]; IF ptd # NIL THEN RETURN [ptd.myType]; RETURN [MakeNewType[utf, std, sei, ts, rcmi, canonicalize, initializing]]; }; FindCanonicalPTD: PUBLIC INTERNAL PROC [ts: TypeString] RETURNS [ptd: PTypeDesc] = { tk: TypeKey = TypeStrHash[ts]; IF EqualKey[tk, nullKey] THEN ERROR; ptd _ FindCanonicalPTDFromKey[tk]; }; MakeNewType: PUBLIC INTERNAL PROC [utf: UniqueTypeFinger, std: STDesc, sei: SymbolIndex, ts: TypeString, rcmx: RCMap.Index, canonicalize: BOOL _ FALSE, initializing: BOOL _ FALSE, type: Type _ nullType] RETURNS [Type] = { ptd: PTypeDesc; tk: TypeKey = TypeStrHash[ts]; sti: SymbolTableIndex; IF type = nullType THEN type _ [NewTypeIndex[utf]]; sti _ IF (WITH sei SELECT FROM t: SymbolIndex.x => LOOPHOLE[t.e, CARDINAL] IN bx.PreDefinedSEI, t: SymbolIndex.y => LOOPHOLE[t.e, CARDINAL] IN by.PreDefinedSEI, ENDCASE => ERROR) AND MapStiStd[1] # NIL THEN 1 ELSE FindSTI[std, initializing]; MapTiTd[type] _ ptd _ uz.NEW [TypeDesc _ [rcmx: rcmx, equivalentType: nullType, utf: utf, symbolAccess: [sti: sti, sei: sei], myType: type, typekey: tk] ]; IF canonicalize THEN { ptd.equivalentType _ type; EnterNewCanonicalType[ptd]} ELSE ptd.equivalentType _ DoGetCanonicalType[type]; RETURN [type]; }; DoGetCanonicalType: INTERNAL PROC [t: Type] RETURNS [Type] = { cptd, ptd: PTypeDesc; IF t <= anyType THEN RETURN [t]; ptd _ MapTiTd[t]; IF ptd.equivalentType # nullType THEN RETURN [ptd.equivalentType]; cptd _ FindCanonicalPTDFromKey[ptd.typekey]; IF cptd = NIL THEN { ptd.equivalentType _ t; EnterNewCanonicalType[ptd]; RETURN [t]; } ELSE { ptd.equivalentType _ cptd.equivalentType; ptd.extension _ cptd.extension; -- there can't be one already RETURN [ptd.equivalentType]; }; }; EnterNewCanonicalType: INTERNAL PROC [ptd: PTypeDesc] = { probe: CARDINAL = ptd.typekey[0] MOD InitialTsRangeSize; ptd.next _ MapTsTdl[probe]; MapTsTdl[probe] _ ptd; }; NewTypeIndex: INTERNAL PROC [utf: UniqueTypeFinger] RETURNS [typeIndex: TypeIndex] = { utfProbe: CARDINAL; nLooks: CARDINAL _ 0; lastTypeIndex _ (typeIndex _ lastTypeIndex + 1); IF lastTypeIndex = InitialTiRangeSize OR lastTypeIndex = LAST[TypeIndex] THEN ERROR TooManyTypes; FOR utfProbe _ FirstUTFProbe[utf], NextUTFProbe[utfProbe] UNTIL MapUTFTi[utfProbe] = nullType DO IF (nLooks _ nLooks + 1) > MapUTFTi.length THEN ERROR TooManyTypes; ENDLOOP; MapUTFTi[utfProbe] _ typeIndex; }; EstablishAtomRecUTF: INTERNAL PROC [utf: UniqueTypeFinger] = { utfProbe: CARDINAL; nLooks: CARDINAL _ 0; FOR utfProbe _ FirstUTFProbe[utf], NextUTFProbe[utfProbe] UNTIL MapUTFTi[utfProbe] = nullType DO IF (nLooks _ nLooks + 1) > MapUTFTi.length THEN ERROR TooManyTypes; ENDLOOP; MapUTFTi[utfProbe] _ atomRecType; MapTiTd[LOOPHOLE[atomRecType]].utf _ utf; }; FindCanonicalPTDFromKey: INTERNAL PROC [tk: TypeKey] RETURNS [ptd: PTypeDesc] = { IF tk = atomRecKey THEN { IF atomRecType = nullType THEN ERROR; ptd _ MapTiTd[atomRecType]} ELSE ptd _ FindEQVTypeFromKey[tk]; }; FindEQVTypeFromKey: INTERNAL PROC [tk: TypeKey] RETURNS [PTypeDesc] = { start: CARDINAL _ tk[0] MOD InitialTsRangeSize; FOR candidate: PTypeDesc _ MapTsTdl[start], candidate.next UNTIL candidate = NIL DO IF EqualKey[tk, candidate.typekey] THEN RETURN [candidate]; ENDLOOP; RETURN [NIL]; }; FindPTD: PUBLIC INTERNAL PROC [utf: UniqueTypeFinger, ts: TypeString _ NIL] RETURNS [ptd: PTypeDesc] = { utfProbe: CARDINAL; nLooks: CARDINAL _ 0; FOR typeIndex: TypeIndex _ MapUTFTi[utfProbe _ FirstUTFProbe[utf]], MapUTFTi[utfProbe _ NextUTFProbe[utfProbe]] UNTIL Type[typeIndex] = nullType DO IF MapTiTd[typeIndex].utf = utf THEN RETURN [MapTiTd[typeIndex]]; IF (nLooks _ nLooks + 1) > MapUTFTi.length THEN ERROR TooManyTypes; ENDLOOP; IF ts # NIL AND IsAtomRecTS[ts] THEN { IF atomRecType = nullType THEN ERROR; EstablishAtomRecUTF[utf]; RETURN [MapTiTd[atomRecType]]; } ELSE RETURN [NIL]; }; IsAtomRecTS: INTERNAL PROC [ts: TypeString] RETURNS [BOOL] = { RETURN [ts.length = 1 AND ts[0] = LOOPHOLE[TypeStrings.Code[atomRec]]]; }; EqualKey: PROC [key1, key2: TypeKey] RETURNS [ans: BOOL _ TRUE] = { FOR i: CARDINAL IN [0..WordPerKey) DO IF key1[i] # key2[i] THEN RETURN [FALSE]; ENDLOOP; }; FirstUTFProbe: INTERNAL PROC [utf: UniqueTypeFinger] RETURNS [CARDINAL] = INLINE { RETURN [Basics.BITAND[ Basics.BITSHIFT[Basics.LowHalf[utf.umid.time] + LOOPHOLE[utf.seIndex, CARDINAL], 2], MapUTFTi.length-1]]; }; NextUTFProbe: INTERNAL PROC [probe: CARDINAL] RETURNS [CARDINAL] = INLINE { RETURN [Basics.BITAND[probe + 1, MapUTFTi.length-1]]; }; KeyAsChars: TYPE = PACKED ARRAY [0 .. CharsPerKey) OF CHAR; WordsPerKey: CARDINAL = SIZE[TypeKey]; CharsPerKey: CARDINAL = Basics.bytesPerWord*WordsPerKey; KeyAsCharsPtr: TYPE = LONG POINTER TO KeyAsChars; DoubleKey: TYPE = RECORD [key1: TypeKey, key2: TypeKey]; EndBytes: TYPE = PACKED ARRAY [0..Basics.bytesPerWord) OF CHAR; EndBytesPtr: TYPE = LONG POINTER TO EndBytes; TypeStrHash: PUBLIC PROC [ts: TypeString] RETURNS [key: TypeKey _ nullKey] = { chars: CARDINAL _ ts.length; ptr: LONG POINTER TO CARDINAL _ LOOPHOLE[ts+SIZE[StringBody]]; double: DoubleKey _ [nullKey, nullKey]; pos: CARDINAL _ 0; double.key1[0] _ chars+1; WHILE chars >= Basics.bytesPerWord DO mod: [0..WordsPerKey) _ pos MOD WordsPerKey; double.key2[mod] _ (ptr+pos)^; pos _ pos + SIZE[CARDINAL]; double.key1[mod] _ Checksum.ComputeChecksum[pos, WordsPerKey+1, @double.key1[mod]]; chars _ chars - Basics.bytesPerWord; ENDLOOP; IF chars # 0 THEN { endBytesPtr: EndBytesPtr _ LOOPHOLE[ptr+pos]; endBytes: EndBytes _ ALL[0C]; mod: [0..WordsPerKey) _ pos MOD WordsPerKey; FOR i: NAT IN [0..chars) DO endBytes[i] _ endBytesPtr[i]; ENDLOOP; double.key2[mod] _ LOOPHOLE[endBytes]; double.key1[mod] _ Checksum.ComputeChecksum[pos+1, WordsPerKey+1, @double+(pos MOD WordsPerKey)]; }; key _ double.key1; IF key[0] = 0 AND key[1] = 0 AND key[2] = 0 AND key[3] = 0 THEN { key[0] _ chars+1; }; }; LOOPHOLE[MapStiStd, LOOPHOLEDTMapStiStd] -- until the sun comes up. _ AllocatorOps.permanentPageZone.NEW[LOOPHOLEDRMapStiStd[InitialSTIRangeSize]]; FOR i: CARDINAL IN [0..InitialSTIRangeSize) DO LOOPHOLE[MapStiStd, LOOPHOLEDTMapStiStd][i] _ NIL; ENDLOOP; MapTiTd _ LOOPHOLE[AllocatorOps.permanentPageZone.NEW[RMapTiTd[InitialTiRangeSize]]]; FOR i: CARDINAL IN [0..InitialTiRangeSize) DO MapTiTd[i] _ NIL ENDLOOP; MapTiTd[nullType] _ @nullTD; atomRecString _ LOOPHOLE[AllocatorOps.permanentPageZone.NEW[TEXT[1]]]; atomRecString.length _ 1; atomRecString[0] _ LOOPHOLE[TypeStrings.Code[atomRec]]; atomRecKey _ TypeStrHash[atomRecString]; MapUTFTi _ LOOPHOLE[AllocatorOps.permanentPageZone.NEW[TMapUTFTi[InitialUTFRangeSize]]]; FOR i: CARDINAL IN [0..InitialUTFRangeSize) DO MapUTFTi[i] _ nullType ENDLOOP; MapTsTdl _ LOOPHOLE[AllocatorOps.permanentPageZone.NEW[TMapTsTdl[InitialTsRangeSize]]]; FOR i: CARDINAL IN [0..InitialTsRangeSize) DO MapTsTdl[i] _ NIL ENDLOOP; RCMapOps.Initialize [LOOPHOLE [VM.AddressForPageNumber[VM.Allocate[count: rcMapBasePages, in64K: TRUE].page]], rcMapBasePages ]; END. CHANGE LOG nTypesBasicImpl.mesa Copyright c 1984, 1985 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) October 29, 1985 11:25:28 am PST Types Constants a power of 2, divisible by PageSize (for MapTiTd) a power of 2, divisible by PageSize (for MapUTFTi) a power of 2, divisible by PageSize (for MapTsTdl) Variables TypeMap stuff hash map: TypeStructure -> PTypeDesc hash map: UniqueTypeFinger -> TypeIndex ERRORs PUBLIC procedures BEWARE NOTE don't microcode this without changing InternalGetCanonicalReferentType The Atom pkg is ready Use by CedarProbe This procedure value goes into SD and used by NARROW std identifies original source symbolStamp, bcd and sgi for a symbol seg that contains below sei (entry may be copied and relocated). *********************************** PRIVATE procedures *********************************** BEWARE NOTE don't microcode this without changing InternalGetCanonicalReferentType here to "canonicalize" t t would have been canonicalized here if utf is not yet registered It would be nice to double the size and chek; get a new hash table; rehash; release old table and try again. Someday we may extend the table instead of producing an error. keep track of the canonical types. The representation is a hash map: TypeStructure -> PTypeDesc It would be nice to double the size and chek; get a new hash table; rehash; release old table and try again. Stolen from TexHash.mesa Type Hashing (formerly in TypeHashImpl) TypeStrings is of type LONG STRING. Don't ever return a null type key! ***************************** M O D U L E I N I T I A L I Z A T I O N S T A R T S H E R E Changed by Koo on June 28, 1984 3:45:57 pm PDT: Changes are done throughout to reflect the change of the definition of TypeDesc in RTTypesBasicPrivate. One significant change is when canonicalization is performed; now it is done when a new type is entered into MapTiTd. Κ[˜codešœ™Kšœ Οmœ7™BK™4K™—šΟk ˜ Kšœ žœ˜'Kšœžœžœžœ ˜7Kšœžœ˜'Kšœžœ˜'Kšœ žœ˜!Kšœžœ ˜Kšœ žœ˜Kšœ žœ ˜2Kšœžœ«˜ΔKšœ žœ?˜PKšœ žœ˜Kšœ žœ˜Kšœ žœ ˜.Kšœ žœ˜%Kšœžœ˜%Kšžœžœ"˜*K˜—headšœž˜KšžœOž˜XKšžœ:˜AKšœžœžœ˜©K˜—™K™šœ žœ˜!Kšœ$˜$—Kš œžœžœžœžœ ˜'K˜—šœ ™ K™šœžœ ˜&Kšœ1™1—šœžœ ˜'Kšœ2™2—šœžœ ˜'Kšœ2™2—Kšœžœ˜—K˜šœ ™ K™Kšœž œžœ"˜4K˜3Kšœ˜K˜Kšœžœ˜ Kšœ˜—K˜šœ ™ K™Kšœ žœ Οc ˜:Kš œ žœžœžœ žœžœ ˜Ašœ žœžœžœ ˜$Kšœ$™$—Kš œ žœžœžœ žœžœ ˜Ašœ žœžœžœ ˜$Kšœ'™'—Kšœ žœŸ0˜O—K˜šœ™Kšœ žœžœžœ˜-Kšœ žœžœžœ˜!Kš œžœžœžœžœžœ˜DKšœžœžœ˜—K˜Kšœ™K˜šΟnœžœžœžœžœžœžœ˜KKšžœ žœžœžœ˜Kšžœ/˜5Kšœ˜K˜—š œžœžœžœžœ žœ žœ˜MKšœR™RKšžœžœžœ˜Kšžœ˜Kšœ˜K˜—KšŸ™Kš œžœžœ&˜DK˜KšŸ™Kš œžœžœžœ(˜MK˜š œžœžœžœžœžœžœ˜XKšœ!Ÿ™4Kšžœžœžœžœ2˜IKšœ˜K˜—Kš  œžœžœžœžœžœžœ˜PK˜Kš œžœžœžœ žœžœžœžœ ˜MK˜š œžœžœžœjžœžœžœžœžœ ˜ΞKšœ…™…Kšžœžœžœ˜K˜Kšžœžœžœ˜LKšžœžœžœžœ˜&KšžœD˜JKšœ˜K˜—š  œžœžœžœžœ˜TKšœ˜Kšžœžœžœ˜$Kšœ"˜"K˜—K™Kšœ#™#Kšœ™Kšœ#™#K˜š  œžœžœžœižœžœžœžœžœ ˜ήKšœ˜K˜K˜Kšžœžœ˜3šœžœžœžœžœžœžœžœ'žœžœžœžœžœžœž˜ΙKšžœ˜Kšžœ˜ —Kšœžœ˜5šœ˜K˜ K˜#K˜ Kšœ˜—šžœ ˜šžœ˜Kšœ˜Kšœ˜—Kšžœ/˜3—Kšžœ˜Kšœ˜—K˜š œžœžœ žœ ˜?KšœR™RKšœ˜Kšžœžœžœ˜ K˜Kšžœžœžœ˜BK˜Kšœ™Kšœ,˜,šžœž˜ šžœ˜Kšœ˜Kšœ˜Kšžœ˜ Kšœ˜—šžœ˜Kšœ)˜)Kšœ!Ÿ˜>Kšœ™Kšžœ˜Kšœ˜——šœ˜K˜——š œžœžœ˜:Kšœžœžœ˜8K˜K˜˜K˜——š  œžœžœžœ˜VKšœ!™!Kšœ žœ˜Kšœžœ˜K˜0šžœ$žœžœ žœ˜NKšžœ˜—šžœ6žœž˜`Kšžœ)žœžœ˜CKšœl™lKšžœ˜—K˜K˜K˜—š œžœžœ˜?Kšœ žœ˜Kšœžœ˜šžœ6žœž˜`šžœ)žœžœ˜CKšœ>™>—Kšžœ˜—Kšœ*žœ˜KKšœ˜K˜—Kšœ_™_K˜š œžœžœžœ˜Qšžœ˜šžœ˜Kšžœžœžœ˜&Kšœ˜—Kšžœ˜"—K˜K˜—š œžœžœžœ˜GKšœžœ žœ˜/šžœ8žœ žœž˜SKšžœ!žœžœ ˜;Kšžœ˜—Kšžœžœ˜ šœ˜K˜——š  œžœžœžœ*žœžœ˜hKšœ žœ˜Kšœžœ˜šžœnžœž˜”Kšžœž œ˜AKšžœ)žœžœ˜DKšœl™lKšžœ˜—šžœžœžœ˜šžœ˜Kšžœžœžœ˜%Kšœ˜Kšžœ˜Kšœ˜—Kšžœžœžœ˜—Kšœ˜—K˜Kšœ™K˜š   œžœžœžœžœ˜>Kšžœžœ žœ˜GKšœ˜—š  œžœžœžœžœ˜Cšžœžœžœž˜%Kšžœžœžœžœ˜)Kšžœ˜—K˜K˜—š   œžœžœžœžœžœ˜Ršžœ žœ˜Kšœžœ!žœžœ˜TKšœ˜—šœ˜K˜——š  œžœžœ žœžœžœžœ˜KKšžœ žœ ˜5Kšœ˜K˜—™'K˜š œ žœž œžœžœ˜;K˜Kšœ žœžœ ˜&Kšœ žœ#˜8Kš œžœžœžœžœ ˜1K˜Kšœ žœžœ ˜8K˜Kš œ žœžœžœžœžœ˜?Kš œ žœžœžœžœ ˜-K˜—šΠbn œžœžœžœ˜NKšœžœžœ™#Kšœžœ ˜Kš œžœžœžœžœžœžœ˜>Kšœ'˜'Kšœžœ˜K˜Kšœ˜K˜šžœž˜%Kšœžœ ˜,Kšœ˜Kšœ žœžœ˜KšœS˜SKšœ$˜$Kšžœ˜K˜—šžœ žœ˜Kšœžœ ˜-Kšœžœ˜Kšœžœ ˜,šžœžœžœ ž˜Kšœ˜Kšžœ˜—Kšœžœ ˜&šœ˜Kšœ<žœ˜N—K˜K˜—Kšœ˜K˜š žœ žœ žœ žœ žœ˜AKšœ"™"Kšœ˜K˜—K˜Kšœ˜——K˜Kšœ™K˜KšœA™A˜šžœ"Ÿ˜DKšœ!žœ+˜O—šžœžœžœž˜.Kšœžœ&žœ˜3Kšœžœ˜ K˜—Kšœ žœ žœ ˜UKš žœžœžœžœžœžœ˜GK˜K˜Kšœžœ žœžœ˜FKšœ˜Kšœžœ˜7Kšœ(˜(K˜šœ ˜ Kšžœ žœ"˜M—Kš žœžœžœžœžœ˜NK˜Kšœ žœ žœ!˜WKš žœžœžœžœžœžœ˜HK˜šœ˜šœž˜ Kšœžœžœ(žœ ˜PKšœ˜—Kšœ˜K˜——Kšžœ˜K˜šžœž˜ K˜™/Kšœή™ή———…—(`>)