DIRECTORY AllocatorOps USING[permanentPageZone], BrandXSymbolDefs USING[PreDefinedSEI], BrandYSymbolDefs USING[PreDefinedSEI], Basics USING[BITAND, BITSHIFT, LowHalf], RCMap USING[Index], RCMapOps USING[Initialize], RTSymbolDefs USING[SymbolIndex, nullSymbolIndex], RTTypesBasicPrivate USING [FindSTI, UniqueTypeFinger, STDesc, TMapStiStd, SymbolTableIndex, LOOPHOLEDTMapStiStd, LOOPHOLEDRMapStiStd, TypeDesc, TMapTiTd, PTypeDesc, RMapTiTd], RTTypesBasicPrivateChanges USING [InitialSTIRangeSize], SafeStorage USING[TypeIndex, Type, nullType, anyType, lastPredefinedTypeIndex], StorageTraps USING[], TimeStamp USING[Null], TypeHash USING [TypeKey, nullKey, TypeStrHash, WordPerKey], TypeStrings USING[Code, TypeString], UnsafeStorage USING[GetSystemUZone], VM USING[AddressForPageNumber, Allocate]; TypesBasicImpl: MONITOR -- protects data structures for runtime types IMPORTS AllocatorOps, Basics, RTTypesBasicPrivate, RCMapOps, TypeHash, UnsafeStorage, VM EXPORTS RTTypesBasicPrivate, SafeStorage, StorageTraps = BEGIN OPEN bx: BrandXSymbolDefs, by: BrandYSymbolDefs, RTSymbolDefs, RTTypesBasicPrivate, RTTypesBasicPrivate, RTTypesBasicPrivateChanges, SafeStorage, TypeHash, TypeStrings; InitialTiRangeSize: CARDINAL = 10000B; -- a power of 2, divisible by PageSize (for MapTiTd) InitialUTFRangeSize: CARDINAL = 10000B; -- a power of 2, divisible by PageSize (for MapUTFTi) InitialTsRangeSize: CARDINAL = 4000B; -- a power of 2, divisible by PageSize (for MapTsTdl) 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; 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[BOOLEAN] = 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 ANY, targetType: Type] RETURNS[REF ANY] = { IF ref = NIL THEN RETURN[NIL] ELSE 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: BOOLEAN _ FALSE, initializing: BOOL _ FALSE] RETURNS[Type] = { ENABLE UNWIND => NULL; ptd: PTypeDesc; IF canonicalize THEN ptd _ FindCanonicalPTD[ts] ELSE ptd _ FindPTD[utf, ts]; RETURN[IF ptd # NIL THEN ptd.myType ELSE MakeNewType[utf, std, sei, ts, rcmi, canonicalize, initializing] ]; }; CopyString: PROC[s: LONG STRING] RETURNS[ns: LONG STRING] = { ns _ LOOPHOLE[uz.NEW[TEXT[s.length]]]; AppendString[to: ns, from: s]; }; AppendString: PROC [to: LONG STRING, from: LONG STRING] = { i, j, n: CARDINAL; IF to = NIL OR from = NIL THEN RETURN; IF from.length + to.length > to.maxlength THEN ERROR; n _ MIN[from.length, LOOPHOLE[to.maxlength - to.length, CARDINAL]]; i _ to.length; j _ 0; WHILE j < n DO to[i] _ from[j]; i _ i + 1; j _ j + 1; ENDLOOP; to.length _ i; }; EqualStrings: PROC[s1, s2: LONG STRING] RETURNS [ans: BOOL _ TRUE] = { IF s1 = NIL AND s2 = NIL THEN RETURN[TRUE]; IF s1 = NIL OR s2 = NIL OR s1.length # s2.length THEN RETURN[FALSE]; FOR i: CARDINAL IN [0..s1.length) DO IF s1[i] # s2[i] THEN RETURN[FALSE]; ENDLOOP; }; MakeNewType: PUBLIC INTERNAL PROC[utf: UniqueTypeFinger, std: STDesc, sei: SymbolIndex, ts: TypeString, rcmx: RCMap.Index, canonicalize: BOOLEAN _ FALSE, initializing: BOOLEAN _ 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, ts]; } ELSE ptd.equivalentType _ DoGetCanonicalType[type, ts]; RETURN[type]; }; DoGetCanonicalType: INTERNAL PROC[t: Type, ts: TypeString _ ""] RETURNS[Type] = { cptd, ptd: PTypeDesc; IF t <= anyType THEN RETURN[t]; ptd _ MapTiTd[t]; IF ptd.equivalentType # nullType THEN RETURN[ptd.equivalentType]; cptd _ FindCanonicalPTD[ts]; IF cptd = NIL THEN { ptd.equivalentType _ t; EnterNewCanonicalType[ptd, ts]; 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, ts: TypeString] = { probe: CARDINAL = TsHash[ts]; 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; }; FindCanonicalPTD: PUBLIC INTERNAL PROC[ts: TypeString] RETURNS[ptd: PTypeDesc] = { IF IsAtomRecTS[ts] THEN { IF atomRecType = nullType THEN ERROR; ptd _ MapTiTd[atomRecType]; } ELSE ptd _ FindEQVType[ts]; }; FindEQVType: INTERNAL PROC[ts: TypeString] RETURNS[PTypeDesc] = { key: TypeKey = TypeStrHash [ts]; FOR candidate: PTypeDesc _ MapTsTdl[TsHash[ts]], candidate.next UNTIL candidate = NIL DO IF EqualKey[key, 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]; }; TsHash: INTERNAL PROC[ts: TypeString] RETURNS[CARDINAL] = INLINE { acc: CARDINAL _ 0; FOR i: CARDINAL IN [0..MIN[7, ts.length]) DO acc _ 7*acc+LOOPHOLE[ts[i], CARDINAL]; ENDLOOP; RETURN[acc MOD InitialTsRangeSize]; }; EqualTS: INTERNAL PROC[ts1, ts2: TypeString] RETURNS[ans: BOOLEAN _ TRUE] = INLINE { RETURN[EqualStrings[ts1, ts2]] }; IsAtomRecTS: INTERNAL PROC[ts: TypeString] RETURNS[BOOLEAN] = { RETURN[ts.length = 1 AND ts[0] = LOOPHOLE[TypeStrings.Code[atomRec]]]; }; EqualKey: PROC [key1, key2: TypeKey] RETURNS [ans: BOOLEAN _ 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[LOOPHOLE[Basics.LowHalf[utf.umid.time], CARDINAL] + LOOPHOLE[utf.seIndex, CARDINAL], 2], MapUTFTi.length-1] ] }; NextUTFProbe: INTERNAL PROC[probe: CARDINAL] RETURNS[CARDINAL] = INLINE { RETURN[Basics.BITAND[probe + 1, MapUTFTi.length-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; 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 ^///users/koo.pa/TypesBasicImplExtra.mesa Last Modified by Richard Koo on June 28, 1984 3:51:32 pm PDT Constants -- Variables -- 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. It would be nice to double the size and chek; get a new hash table; rehash; release old table and try again. 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 ***************************** 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. Ê/˜šœ(™(Jšœ>™>J™—šÏk ˜ Jšœ œ˜&Jšœœ˜&Jšœœ˜&Jšœœœœ ˜(Jšœœ˜Jšœ œ ˜Jšœ œ˜1šœ˜Jšœ•˜•—Jšœœ˜7Jšœ œ>˜OJšœ œ˜Jšœ œ˜Jšœ œ-˜;Jšœ œ˜$Jšœœ˜$Jšœœ!˜)J˜—šœœÏc-˜FJšœO˜Xšœ0˜7J˜——šœœœ¤˜°J˜—Jšœ ™ Jšœœ ž4˜\Jšœœ ž5˜^Jšœœ ž5˜\Jšœœ˜J˜Jšœ ™ Jšœ œœ"˜4J˜3Jšœ˜J˜J˜Jšœ œ ž ˜:Jš œ œœœ œœ ˜Ašœ œœœ ˜$Jšœ$™$—Jš œ œœœ œœ ˜Ašœ œœœ ˜$Jšœ'™'J˜—Jšœ œž0˜OJ˜Jšœ™Jšœ œœœ˜-Jšœ œœœ˜!Jš œœœœœœ˜DJšœœœ˜J˜J˜Jšœ™J˜šÏnœœœœœœœ˜LJšœ œœœ˜Jšœ.˜4Jšœ˜J˜—JšœR™RšŸœœœœœ œ œ˜KJšœœœ˜Jšœ˜Jšœ˜J˜—Jšž™JšŸœœœ%˜CJ˜Jšž™JšŸœœœœ'˜LJ˜Jšœ!ž™4š Ÿœœœœœ˜Dšœœœ˜Jš œœœœœ˜Jšœœ2˜<—Jšœ˜J˜—JšŸ œœœœœœœ˜PJ˜JšŸœœœœœœœœ ˜LJ˜šŸœœœ˜'˜˜ Jšœ+™+Jšœ*™*Jšœ.™.—J˜J˜J˜Jšœœœ˜Jšœœœ˜—šœ ˜Jšœœœ˜J˜šœœ˜Jšœ˜—Jšœ˜š œœœœ œ˜)Jšœ@˜@—Jšœ˜—šœ˜J˜——J™Jšœ#™#Jšœ™Jšœ#™#J˜šŸ œœœœœœœ˜=Jšœœœœ ˜&J˜J˜J˜—š Ÿ œœœœœœ˜;Jšœ œ˜Jš œœœœœœ˜&Jšœ(œœ˜5Jšœœœœ˜CJ˜J˜Jšœœ(œ˜>J˜J˜J˜—šŸ œœ œœœœœ˜FJšœœœœœœœ˜+Jšœœœœœœœœ˜DJšœœœœœœœœœ˜RJ˜J˜—šŸ œœœœ˜8J˜ J˜J˜J˜Jšœœœ˜Jšœœœ˜J˜šœ ˜Jšœ˜—˜!J˜Jšœœ˜3šœœœœ˜Jšœœœœ˜CJšœœœœ˜CJšœœœœ˜*Jšœœ˜Jšœœ˜!—Jšœœ˜5šœ)˜)˜J˜0J˜Jšœ˜——J˜ šœœ˜Jšœ˜Jšœ˜—šœ˜Jšœ2˜2—Jšœ˜ Jšœ˜——J˜JšœR™RšŸœœœœ ˜RJšœ˜Jšœœœ˜J˜Jšœœœ˜AJ˜Jšœ™Jšœ˜šœœœ˜Jšœ˜Jšœ˜Jšœ˜ —Jšœ˜šœ˜Jšœ)˜)Jšœ!ž˜>Jšœ™Jšœ˜—Jšœ˜šœ˜˜J˜———šŸœœœ%˜IJšœœ˜J˜J˜˜J˜Jšœ!™!——šŸ œœœœ˜TJšœ œ˜Jšœœ˜J˜0šœ$œœ œ˜NJšœ˜—šœ8˜;Jšœ˜&Jšœ)œœ˜CJšœl™lJšœ˜—J˜J˜J˜—šŸœœœ˜>Jšœ œ˜Jšœœ˜šœ7˜:šœ˜&Jšœ)œœ˜CJšœl™l—Jšœ˜—Jšœ*œ˜KJšœ˜J˜—Jšœ_™_J˜š Ÿœœœœœ˜Ršœœ˜Jšœœœ˜&Jšœ˜—šœœ˜Jšœ˜—J˜J˜—šŸ œœœœ˜AJšœ!˜!šœ=œ ˜UJš œœ"œœ œ˜F—Jšœœ˜ šœ˜J˜——š Ÿœœœœ)œ˜Jšœ˜Jšœ œ˜Jšœœ˜šœA˜DJšœ,œ˜Ošœ˜$Jšœ˜—Jšœ)œœ˜DJšœl™lJšœ˜—šœœœœ˜&Jšœœœ˜%Jšœ˜Jšœ˜—Jšœœœœ˜—Jšœ˜—J˜Jšœ™š Ÿœœœœœœ˜BJšœœ˜š œœœœ˜,Jšœ œœ˜&Jšœ˜—Jšœœ˜#šœ˜J˜——š Ÿœœœœœœ˜KJšœœœ˜+—J˜š Ÿ œœœœœ˜?Jšœœ œ˜FJšœ˜—š Ÿœœœœœ˜Fšœœœ˜%Jšœœœœ˜)Jšœ˜—J˜J˜—š Ÿ œœœœœœ˜Pšœ˜Jš œœœœ œ˜QJšœœœ˜