RopeReaderMiscImpl.mesa
written by Bill Paxton, January 1981
last edit by Paxton, February 7, 1983 9:34 am
last edit by McGregor, June 10, 1982 3:18 pm
Last Edited by: Maxwell, January 5, 1983 12:07 pm
Last Edited by: Plass, March 7, 1983 2:27 pm
DIRECTORY
RopeReader,
RopeFrom,
Rope,
RopeInline,
Environment,
Space;
RopeReaderMiscImpl:
CEDAR MONITOR
IMPORTS RopeReader, Rope, RopeInline, RopeFrom, Space --, RTTypesBasic, Process
EXPORTS RopeReader
SHARES RopeReader, Rope =
BEGIN OPEN RopeReader, RopeInline;
EqSubstrs:
PUBLIC
PROC [r1,r2:
ROPE, start1,start2,len: Offset, rdr1,rdr2: Ref ←
NIL]
RETURNS [eq: BOOLEAN] = {
-- uses readers rdr1 and rdr2 to read ropes r1 and r2 to test for equality
-- returns TRUE if r1 is same as len chars of r2 starting at start
free1, free2: BOOLEAN ← FALSE;
size1: Offset ← InlineSize[r1];
size2: Offset ← InlineSize[r2];
start1 ← MIN[start1,size1];
start2 ← MIN[start2,size2];
IF len=MaxLen THEN { IF (len ← size1-start1) # size2-start2 THEN RETURN [FALSE] }
ELSE IF start1+len > size1 THEN RETURN [FALSE]
ELSE IF start2+len > size2 THEN RETURN [FALSE];
IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
SetPosition[rdr1,r1,start1];
SetPosition[rdr2,r2,start2];
eq ← TRUE;
WHILE len > 0
DO
num: NAT ← Short[MIN[len,LAST[NAT]]]; -- loop on NAT instead of Offset
len ← len-num;
THROUGH [0..num)
DO
IF Get[rdr1]#Get[rdr2] THEN { eq ← FALSE; GOTO Finis };
ENDLOOP;
REPEAT Finis => NULL;
ENDLOOP;
IF free1 THEN FreeRopeReader[rdr1];
IF free2 THEN FreeRopeReader[rdr2] };
CompareSubstrs:
PUBLIC
PROC [
r1, r2: ROPE, start1, len1, start2, len2: Offset,
rdr1, rdr2: Ref ← NIL, case: BOOLEAN ← TRUE]
RETURNS [result: Environment.Comparison] = {
-- uses readers rdr1 and rdr2 to compare ropes r1 and r2
-- if ~case then all characters forced lowercase for comparison
Lower:
PROC [c:
CHARACTER]
RETURNS [
CHARACTER] =
INLINE {
RETURN [
IF c
NOT
IN ['A..'Z]
THEN c
ELSE
LOOPHOLE[LOOPHOLE[c,CARDINAL]+40B,CHARACTER]] };
size1: Offset ← InlineSize[r1];
size2: Offset ← InlineSize[r2];
rem, rem1, rem2: Offset;
free1, free2: BOOLEAN ← FALSE;
rem1 ← IF start1 > size1 THEN 0 ELSE size1-start1;
rem2 ← IF start2 > size2 THEN 0 ELSE size2-start2;
IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
len1 ← MIN[len1,rem1]; len2 ← MIN[len2,rem2]; rem ← MIN[len1,len2];
SetPosition[rdr1,r1,start1];
SetPosition[rdr2,r2,start2];
result ← equal;
WHILE rem > 0
DO
num: NAT ← Short[MIN[rem,LAST[NAT]]];
rem ← rem-num;
THROUGH [0..num)
DO
c1: CHARACTER ← Get[rdr1];
c2: CHARACTER ← Get[rdr2];
IF ~case THEN { c1 ← Lower[c1]; c2 ← Lower[c2] };
SELECT c1
FROM
< c2 => { result ← less; GOTO Finis };
> c2 => { result ← greater; GOTO Finis };
ENDCASE;
ENDLOOP;
REPEAT Finis => NULL;
ENDLOOP;
IF free1 THEN FreeRopeReader[rdr1];
IF free2 THEN FreeRopeReader[rdr2];
RETURN [
IF result # equal
THEN result
ELSE
SELECT
TRUE
FROM
len1 < len2 => less,
len1 > len2 => greater,
ENDCASE => equal] };
-- implementation of ropes using character arrays
CList: TYPE = REF CListBody;
CListBody: TYPE = RECORD [chars: Chars, space: Space.Handle, next: CList];
charsList: CList ← NIL;
numCharsArrays: INT ← 0; -- number allocated
CharsRope:
PUBLIC
ENTRY
PROC [
chars: Chars, space: Space.Handle ← Space.nullHandle]
RETURNS [ROPE] = TRUSTED {
ENABLE UNWIND => NULL;
FOR lst:CList ← charsList, lst.next UNTIL lst=NIL DO
IF lst.chars = chars THEN {
IF lst.space = Space.nullHandle THEN lst.space ← space
ELSE IF space # Space.nullHandle THEN ERROR;
EXIT };
REPEAT FINISHED => {
charsList ← RopeFrom.qZone.NEW[CListBody ← [chars,space,charsList]];
numCharsArrays ← numCharsArrays+1 };
ENDLOOP;
RETURN [RopeFrom.qZone.
NEW[Tobject ← [node[object[
charsPerArray,LOOPHOLE[chars],CharsFetch,CharsMap,NIL]]]]] };
spacesFinalized: INT ← 0;
CharsFinalizer: PROC [charsFQ: RTTypesBasic.FinalizationQueue] = TRUSTED {
DO
chars: REF CharsArray = NARROW[RTTypesBasic.FQNext[charsFQ]];
space: Space.Handle = RemoveFromCList[chars];
IF space # Space.nullHandle THEN {
spacesFinalized ← spacesFinalized+1;
Space.Unmap[space]; Space.Map[space, Space.defaultWindow] };
ENDLOOP };
charsFinalized: INT ← 0;
RemoveFromCList: ENTRY PROC [chars: Chars] RETURNS [space: Space.Handle] = {
ENABLE UNWIND => NULL;
lst, prev: CList;
charsFinalized ← charsFinalized+1;
IF (lst𡤌harsList)=NIL THEN RETURN [Space.nullHandle];
IF lst.chars = chars THEN {
lst.chars ← NIL; charsList ← lst.next; lst.next ← NIL; RETURN [lst.space] };
DO
prev ← lst;
IF (lst ← lst.next)=NIL THEN RETURN [Space.nullHandle];
IF lst.chars = chars THEN {
lst.chars ← NIL; prev.next ← lst.next; lst.next ← NIL; RETURN [lst.space] };
ENDLOOP };
countCList: INT ← 0; -- set by calling CountCList
CountCList: ENTRY PROC = {
ENABLE UNWIND => NULL;
countCList← 0;
FOR lst:CList ← charsList, lst.next UNTIL lst=NIL DO
countCList ← countCList+1; ENDLOOP };
CharsFetch:
SAFE
PROC [data:
REF, index: Offset]
RETURNS [c:
CHAR] =
TRUSTED {
WITH data
SELECT
FROM
x: Chars => RETURN[x[Short[index]]];
ENDCASE => ERROR Rope.NoRope };
CharsMap:
SAFE
PROC
[base: REF, start,len: Offset, action: PROC [CHAR] RETURNS [BOOLEAN]]
RETURNS [BOOLEAN] = TRUSTED {
WITH base
SELECT
FROM
x: Chars => {
st: NAT ← Short[start];
FOR i:
NAT
IN [st..st+Short[len])
DO
IF action[x[i]] THEN RETURN [TRUE];
ENDLOOP };
ENDCASE => ERROR Rope.NoRope;
RETURN [FALSE] };
-- ***** rope reader cache
Create: PUBLIC PROC RETURNS [Ref] = { RETURN[RopeFrom.qZone.NEW[Body]] };
roperdr1, roperdr2, roperdr3: Ref; -- shared rope readers
GetRopeReader:
PUBLIC
ENTRY
PROC
RETURNS [reader: Ref] = {
IF roperdr3 # NIL THEN { reader ← roperdr3; roperdr3 ← NIL }
ELSE IF roperdr2 # NIL THEN { reader ← roperdr2; roperdr2 ← NIL }
ELSE IF roperdr1 # NIL THEN { reader ← roperdr1; roperdr1 ← NIL }
ELSE reader ← Create[] };
FreeRopeReader:
PUBLIC
ENTRY
PROC [reader: Ref] = {
SetPosition[reader, NIL];
reader.charForEndOfRope ← FALSE;
IF roperdr3 = reader OR roperdr2 = reader OR roperdr1 = reader THEN ERROR;
IF roperdr3 = NIL THEN roperdr3 ← reader
ELSE IF roperdr2 = NIL THEN roperdr2 ← reader
ELSE IF roperdr1 = NIL THEN roperdr1 ← reader };
-- ***** Initialization
charsFQ: RTTypesBasic.FinalizationQueue = RTTypesBasic.NewFQ[]; -- for CharsArrays
StartRopeReaderMisc:
PUBLIC
PROC =
TRUSTED {
RTTypesBasic.EstablishFinalization[CODE[CharsArray],1,charsFQ];
Process.Detach[FORK CharsFinalizer[charsFQ]]
};
END.