IntervalsImpl.mesa
Copyright © 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
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.