DIRECTORY Basics USING [BITSHIFT], Intervals; IntervalsImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Basics EXPORTS Intervals = BEGIN OPEN Intervals; Hash: PROC [table: Table, interval: Interval] RETURNS [hash: NAT _ 0]= { range: Interval _ table.range; buckets: NAT _ (table.data.hashSize+1)/2; min: NAT _ ((interval.min - range.min) * buckets) / (range.max + 1 - range.min); max: NAT _ ((interval.max - range.min) * buckets) / (range.max + 1 - range.min); IF min<0 OR max>=buckets THEN ERROR; -- ERROR probably due to an interval outside the table range UNTIL min=max DO hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; hash _ hash + min; }; Create: PUBLIC PROC [range: Interval, valueInterval: ValueIntervalProc, userData: REF _ NIL, logHashSize: NAT _ 2] RETURNS [Table] = { data: REF TableData _ NEW [TableData[Basics.BITSHIFT[value: 1, count: logHashSize]-1]]; RETURN [NEW [TableRec _ [ range: range, size: 0, valueInterval: valueInterval, userData: userData, effectiveRange: empty, leafBuckets: 0, data: data ]]]; }; ReHash: PROC [table: Table] = { oldData: REF TableData _ table.data; newData: REF TableData _ NEW [TableData[oldData.hashSize*2+1]]; table.data _ newData; table.effectiveRange _ empty; table.leafBuckets _ 0; FOR i: NAT IN [0 .. oldData.hashSize) DO FOR values: LIST OF Value _ oldData[i], values.rest WHILE values#NIL DO interval: Interval _ table.valueInterval[table, values.first]; hash: NAT _ Hash [table, interval]; IF newData[hash]=NIL THEN table.leafBuckets _ table.leafBuckets+1; table.effectiveRange _ Union[interval, table.effectiveRange]; newData[hash] _ CONS [values.first, newData[hash]]; ENDLOOP; ENDLOOP; }; Insert: PUBLIC ENTRY PROC [table: Table, value: Value] = { ENABLE UNWIND => NULL; interval: Interval _ table.valueInterval[table, value]; hash: NAT _ Hash [table, interval]; table.size _ table.size + 1; IF table.data[hash]=NIL THEN table.leafBuckets _ table.leafBuckets+1; table.effectiveRange _ Union[interval, table.effectiveRange]; table.data[hash] _ CONS [value, table.data[hash]]; IF table.leafBuckets * 2 > table.data.hashSize THEN ReHash[table]; }; Delete: PUBLIC ENTRY PROC [table: Table, value: Value] = { ENABLE UNWIND => NULL; interval: Interval _ table.valueInterval[table, value]; hash: NAT _ Hash [table, interval]; Delq: PROC [values: LIST OF Value] RETURNS [LIST OF Value] = { IF values=NIL THEN RETURN [NIL]; IF values.first=value THEN { table.size _ table.size - 1; table.effectiveRange _ universe; RETURN [Delq[values.rest]]; }; values.rest _ Delq[values.rest]; RETURN [values]; }; IF table.data[hash]=NIL THEN RETURN; table.data[hash] _ Delq[table.data[hash]]; IF table.data[hash]=NIL THEN table.leafBuckets _ table.leafBuckets-1; }; Enumerate: PUBLIC PROC [table: Table, action: PROC [Table, Value] RETURNS [BOOLEAN _ FALSE], interval: Interval _ universe] RETURNS [BOOLEAN] = { data: REF TableData _ table.data; -- stored in the local frame to avoid concurrent inconsistencies range: Interval _ table.range; -- stored in the local frame to avoid concurrent inconsistencies effectiveRange: Interval _ table.effectiveRange; buckets: NAT _ (data.hashSize+1)/2; hash: NAT _ 0; clipped: Interval _ [MAX [interval.min, range.min, effectiveRange.min], MIN [interval.max, range.max, effectiveRange.max]]; min, max: NAT; IF clipped.min>clipped.max THEN RETURN [FALSE]; -- empty interval min _ ((clipped.min - range.min) * buckets) / (range.max + 1 - range.min); max _ ((clipped.max - range.min) * buckets) / (range.max + 1 - range.min); IF min<0 OR max>=buckets THEN ERROR; -- bug in the implementation WHILE buckets>0 DO FOR i: NAT IN [hash+min .. hash+max] DO FOR values: LIST OF Value _ data[i], values.rest WHILE values#NIL DO IF Overlap[table.valueInterval[table, values.first], clipped] AND action[table, values.first] THEN RETURN [TRUE]; ENDLOOP; ENDLOOP; hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; RETURN [FALSE]; }; EffectiveRange: PUBLIC INTERNAL PROC [table: Table] RETURNS [effectiveRange: Interval _ empty] = { ComputeEffectiveRange: PROC [table: Table, value: Value] RETURNS [BOOL _ FALSE] = { effectiveRange _ Union[table.valueInterval[table, value], effectiveRange]; }; IF table.effectiveRange#universe THEN RETURN [table.effectiveRange]; [] _ Enumerate[table, ComputeEffectiveRange]; table.effectiveRange _ effectiveRange; }; Union: PUBLIC PROC [interval1, interval2: Interval] RETURNS [Interval] = { RETURN [[MIN [interval1.min, interval2.min], MAX [interval1.max, interval2.max]]]; }; Overlap: PUBLIC PROC [interval1, interval2: Interval] RETURNS [BOOL] = { RETURN [(interval1.min<=interval2.max) AND (interval2.min<=interval1.max)]; }; END. ΔIntervalsImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reversed. Created by Bertrand Serlet, November 16, 1985 7:22:05 pm PST Bertrand Serlet, March 13, 1986 2:12:46 pm PST ΚΎ– "cedar" style˜codešœ™Kšœ Οmœ1™˜>Kšœžœ˜#Kšžœžœžœ)˜BKšœ=˜=Kšœžœ˜3Kšžœ˜—Kšžœ˜—K˜—K˜šŸœžœžœžœ!˜:Kšžœžœžœ˜Kšœ7˜7Kšœžœ˜#Kšœ˜Kšžœžœžœ)˜EKšœ=˜=Kšœžœ˜2Kšžœ-žœ˜BK˜—K˜šŸœžœžœžœ!˜:Kšžœžœžœ˜Kšœ7˜7Kšœžœ˜#šŸœžœ žœžœžœžœžœ ˜>Kš žœžœžœžœžœ˜ šžœžœ˜Kšœ˜Kšœ!˜!Kšžœ˜Kšœ˜—Kšœ!žœ ˜1K˜—Kšžœžœžœžœ˜$Kšœ*˜*Kšžœžœžœ)˜EK˜—K˜šŸ œžœžœžœžœžœžœ"žœžœ˜‘Kšœžœ @˜bKšœ @˜_Kšœ0˜0Kšœ žœ˜#Kšœžœ˜Kšœžœ0žœ0˜{Kšœ žœ˜Kš žœžœžœžœ ˜AKšœJ˜JKšœJ˜JKš žœžœžœžœ ˜Ašžœ žœ˜šžœžœžœžœ˜(š žœ žœžœžœžœž˜Dšžœ<žœ˜^Kšžœžœžœ˜—Kšžœ˜—Kšžœ˜—Kšœ.˜.Kšœ˜Kšžœ˜—Kšžœžœ˜K˜—K˜š Ÿœžœžœžœžœ'˜bš Ÿœžœžœžœžœ˜SKšœJ˜JK˜—Kšžœžœžœ˜DKšœ-˜-Kšœ&˜&K˜K™—šŸœžœžœ"žœ˜JKšžœžœ!žœ"˜RK˜—š Ÿœžœžœ"žœžœ˜HKšžœ!žœ!˜KK˜—K˜Kšžœ˜K˜K˜K˜——…—€