RopeFileImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Russ Atkinson, March 13, 1985 6:42:16 pm PST
Paul Rovner, December 14, 1983 11:31 am
DIRECTORY
FS USING [defaultStreamOptions, GetName, nullOpenFile, OpenFile, OpenFileFromStream, StreamOpen, StreamOptions],
IO USING [Close, GetBlock, GetLength, SetIndex, STREAM],
PrincOpsUtils USING [ByteBlt],
Process USING [Detach],
RopeFile USING [],
Rope USING [AppendCharsType, FetchType, MakeRope, MapType, NewText, ROPE, Text],
SafeStorage USING [CantEstablishFinalization, EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ, ReEstablishFinalization];
RopeFileImpl:
CEDAR MONITOR
LOCKS handle USING handle: Handle
IMPORTS FS, IO, PrincOpsUtils, Process, Rope, SafeStorage
EXPORTS RopeFile
SHARES Rope
= BEGIN
T Y P E S
ROPE: TYPE = Rope.ROPE;
STREAM: TYPE = IO.STREAM;
Handle: TYPE = REF RopeFileRep;
RopeFileRep:
TYPE =
MONITORED
RECORD [
lockChange: CONDITION,
next: Handle ← NIL,
file: STREAM ← NIL,
offset: INT ← 0,
locked: BOOL ← FALSE,
bufSize: NAT ← 0,
data: SEQUENCE buffers: NAT OF Buf];
Buf: TYPE = REF BufRec;
BufRec: TYPE = RECORD [start: INT, len: NAT, text: REF TEXT];
useByteBlt:
BOOL ←
TRUE;
This boolean is here to enable speed trials
pagesPerFileBuffer: NAT ← 2;
numberOfFilebuffers: NAT ← 2;
AcquireLock:
ENTRY
PROC [handle: Handle] =
INLINE {
WHILE handle.locked DO WAIT handle.lockChange; ENDLOOP;
handle.locked ← TRUE;
};
ReleaseLock:
ENTRY
PROC [handle: Handle] =
INLINE {
IF NOT handle.locked THEN ERROR;
handle.locked ← FALSE;
BROADCAST handle.lockChange;
};
Create:
PUBLIC
PROC [name:
ROPE, start:
INT ← 0, len:
INT ←
LAST[
INT], bufSize:
INT ← 512, buffers:
NAT ← 4, raw:
BOOL ←
TRUE]
RETURNS [rope:
ROPE] = {
options: FS.StreamOptions ← FS.defaultStreamOptions;
stream: STREAM ← NIL;
IF raw
THEN
this makes the rope include the formatting information
options[tiogaRead] ← FALSE;
stream ←
FS.StreamOpen[
fileName: name,
accessOptions: $read,
streamOptions: options,
streamBufferParms: [vmPagesPerBuffer: pagesPerFileBuffer, nBuffers: numberOfFilebuffers]];
RETURN [FromStream[stream, start, len, bufSize, buffers]];
};
FromStream:
PUBLIC
PROC [stream:
STREAM, start:
INT ← 0, len:
INT ←
LAST[
INT], bufSize:
INT ← 512, buffers:
NAT ← 4]
RETURNS [rope:
ROPE] = {
handle: Handle ← NIL;
filesize: INT ← 0;
bestBuffers: INT ← 0;
IF start < 0 THEN start ← 0;
IF len <= 0 THEN RETURN [NIL];
filesize ← IO.GetLength[stream];
IF len = LAST[INT] OR start+len > filesize THEN len ← filesize - start;
IO.SetIndex[stream, start];
IF buffers = 0 THEN buffers ← 1;
IF bufSize < 64 THEN bufSize ← 64;
IF bufSize > 16*1024 THEN bufSize ← 16*1024;
bestBuffers ← (len + bufSize - 1) / bufSize;
IF bestBuffers < buffers THEN buffers ← bestBuffers;
IF len < 16*1024
AND len <= (buffers * bufSize)
THEN
TRUSTED {
text: Rope.Text ← Rope.NewText[len];
[] ← IO.GetBlock[stream, LOOPHOLE[text], 0, len];
IO.Close[stream];
RETURN [text];
};
handle ← NEW[RopeFileRep[buffers]];
handle.bufSize ← bufSize;
handle.file ← stream;
handle.offset ← start;
FOR i:
NAT
IN [0..buffers)
DO
handle[i] ← NEW[BufRec ← [start: 0, len: 0, text: NEW[TEXT[bufSize]]]];
ENDLOOP;
rope ← Rope.MakeRope[handle, len, MyFetch, MyMap, MyAppendChars];
splice this ropeFile onto the global list
AcquireLock[dummyRopeFile];
handle.next ← dummyRopeFile.next;
dummyRopeFile.next ← handle;
ropesOutstanding ← ropesOutstanding + 1;
SafeStorage.EnableFinalization[handle];
ReleaseLock[dummyRopeFile];
};
MyFetch: Rope.FetchType = {
[data: REF, index: INT] RETURNS [CHAR]
handle: Handle = NARROW[data];
last: NAT = handle.buffers-1;
c: CHAR;
IF handle.file = NIL THEN ERROR;
AcquireLock[handle];
index ← index + handle.offset;
FOR i:
NAT
IN [0..last]
DO
buf: Buf ← handle[i];
delta: INT ← index - buf.start;
SELECT
TRUE
FROM
delta >= 0
AND delta < buf.len => {
this buffer contains the character range
};
i < last =>
we have not come to the last buffer
LOOP;
ENDCASE => {
need to swap in new buffer
length: NAT ← handle.bufSize;
start: INT = index - (delta ← index MOD length);
IO.SetIndex[handle.file, start];
length ← IO.GetBlock[handle.file, buf.text, 0, length];
IF length = 0 THEN {ReleaseLock[handle]; ERROR};
buf.start ← start;
buf.len ← length;
};
IF i # 0
THEN {
swap to speed searches
handle[i] ← handle[i-1];
handle[i-1] ← buf;
};
c ← buf.text[delta];
EXIT;
ENDLOOP;
ReleaseLock[handle];
RETURN [c];
};
MyMap: Rope.MapType =
TRUSTED {
[base: REF, start, len: INT, action: ActionType] RETURNS [quit: BOOL ← FALSE]
handle: Handle ← NARROW[base];
last: NAT = handle.buffers-1;
IF handle.file = NIL THEN ERROR;
start ← start + handle.offset;
WHILE len > 0
DO
buf: Buf ← NIL;
delta: INT ← 0;
subLen: NAT = 32;
string: STRING ← [subLen];
pos: NAT ← delta;
spos: NAT ← 0;
chars: NAT ← 0;
AcquireLock[handle];
FOR i:
NAT
IN [0..last]
DO
buf ← handle[i];
delta ← start - buf.start;
SELECT
TRUE
FROM
delta >= 0
AND delta < buf.len => {
this buffer contains the character range
};
i < last =>
we have not come to the last buffer
LOOP;
ENDCASE => {
need to swap in new buffer
length: NAT ← handle.bufSize;
bpos: INT = start - (delta ← start MOD length);
IO.SetIndex[handle.file, bpos];
length ← IO.GetBlock[handle.file, buf.text, 0, length];
IF length = 0 THEN {ReleaseLock[handle]; ERROR};
buf.start ← bpos;
buf.len ← length;
};
IF i # 0
THEN {
swap to speed searches
handle[i] ← handle[i-1];
handle[i-1] ← buf;
};
EXIT;
ENDLOOP;
At this point we have found a good buffer, so we snatch a sub-buffer from it
pos ← delta;
chars ← MIN[buf.len-pos, subLen];
IF len < chars THEN chars ← len;
FOR j:
NAT
IN [0..chars)
DO
string[j] ← buf.text[pos+j];
ENDLOOP;
we will not touch the buffer until the next time around (if any)
ReleaseLock[handle];
Now yield all of the chars in the sub-buffer
FOR j:
NAT
IN [0..chars)
DO
IF action[string[j]] THEN RETURN [TRUE];
ENDLOOP;
len ← len - chars;
start ← start + chars;
ENDLOOP;
RETURN [FALSE];
};
SubstrCreate:
PUBLIC
PROC [name:
ROPE, start:
INT ← 0, len:
INT ←
LAST[
INT]]
RETURNS [rope:
ROPE] = {
RETURN [Create[name, start, len]];
};
SimpleCreate:
PUBLIC
PROC [name:
ROPE]
RETURNS [rope:
ROPE] = {
RETURN [Create[name]];
};
FileFromRope:
PUBLIC
PROC [rope:
ROPE]
RETURNS [
FS.OpenFile ←
FS.nullOpenFile] =
TRUSTED {
Returns the file (if any) used by the given rope.
WITH r: rope
SELECT
FROM
node =>
WITH r: r
SELECT
FROM
object =>
WITH r.base
SELECT
FROM
h: Handle => RETURN [FS.OpenFileFromStream[h.file]];
ENDCASE;
ENDCASE;
ENDCASE;
};
AddrOfChars:
PROC [refText:
REF
TEXT]
RETURNS [
LONG
POINTER] =
TRUSTED
INLINE {
RETURN [LOOPHOLE[refText, LONG POINTER] + SIZE[TEXT[0]] ];
};
MyAppendChars: Rope.AppendCharsType =
TRUSTED {
[buffer: REF TEXT, data: REF, start: INT, len: INT] RETURNS [charsMoved: NAT];
Appends characters from the given rope (which need not be a RopeFile rope) onto the specified buffer. The move will stop at the end of the specified subrope OR end of the rope OR the end of the buffer. It is the user's responsibility to determine if enough characters have been moved. A BoundsFault will occur if start NOT IN [0..rope.Length[]].
WITH data
SELECT
FROM
handle: Handle => {
Our special case
last: NAT = handle.buffers-1;
bPos: NAT ← buffer.length;
bLim: NAT = buffer.maxLength;
bRem: NAT = bLim-bPos;
rem: INT ← len-start;
IF bRem < len THEN len ← bRem;
charsMoved ← len;
buffer.length ← bPos;
IF handle.file = NIL THEN ERROR;
start ← start + handle.offset;
WHILE len > 0
DO
buf: Buf ← NIL;
delta: INT ← 0;
pos: NAT ← delta;
spos,chars: NAT ← 0;
AcquireLock[handle];
FOR i:
NAT
IN [0..last]
DO
buf ← handle[i];
delta ← start - buf.start;
SELECT
TRUE
FROM
delta >= 0
AND delta < buf.len => {
this buffer contains the character range
};
i < last =>
we have not come to the last buffer
LOOP;
ENDCASE => {
need to swap in new buffer
length: NAT ← handle.bufSize;
bpos: INT = start - (delta ← start MOD length);
IO.SetIndex[handle.file, bpos];
length ← IO.GetBlock[handle.file, buf.text, 0, length];
IF length = 0 THEN {ReleaseLock[handle]; ERROR};
buf.start ← bpos;
buf.len ← length;
};
IF i # 0
THEN {
swap to speed searches
handle[i] ← handle[i-1];
handle[i-1] ← buf;
};
EXIT;
ENDLOOP;
At this point we have found the right buffer, so move chars.
pos ← delta;
chars ← buf.len-pos;
IF len < chars THEN chars ← len;
IF chars > 4
AND useByteBlt
THEN
The setup time is worth while to get better throughput
[] ← PrincOpsUtils.ByteBlt[
to: [AddrOfChars[buffer], bPos, bPos+chars],
from: [AddrOfChars[buf.text], pos, pos+chars]]
ELSE
The setup time probably dwarfs the following loop
FOR j:
NAT
IN [0..chars)
DO
buffer[bPos+j] ← buf.text[pos+j];
ENDLOOP;
We will not touch the buffer until the next time around (if any).
ReleaseLock[handle];
len ← len - chars;
start ← start + chars;
bPos ← bPos + chars;
ENDLOOP;
RETURN;
};
ENDCASE => ERROR;
};
RopeFileFinalizer:
PROC = {
This procedure closes the files associated with rope files as part of finalizing the ropes in question. We have to be quite careful to lock things properly, which is why there is a dummyRopeFile. The dummyRopeFile is used to hold on to the ropes created by Create, and to synchronize insertinon of new rope files and deletion of old rope files. Remember: paranoia pays!
DO
ref: REF ← NIL;
ref ← SafeStorage.FQNext[fq]; -- genuflect three times to the GC's conservative scanner
WITH ref
SELECT
FROM
rf: Handle => {
note: always use the following order in acquiring/releasing locks
lag: Handle ← dummyRopeFile;
found: BOOL ← FALSE;
IF rf = dummyRopeFile THEN LOOP;
AcquireLock[dummyRopeFile];
AcquireLock[rf];
FOR each: Handle ← dummyRopeFile.next, each.next
WHILE each #
NIL
DO
IF each = rf
THEN {
splice out this file
lag.next ← each.next;
found ← TRUE;
EXIT;
};
lag ← each;
ENDLOOP;
IF found
AND rf.file #
NIL
THEN {
Only close the file if it is on the list AND has been opened. This makes us insensitive to multiple occurences of rope files on the finalization queue.
ENABLE UNWIND => {ReleaseLock[rf]; ReleaseLock[dummyRopeFile]};
IO.Close[rf.file];
rf.file ← NIL;
ropesOutstanding ← ropesOutstanding - 1;
};
ReleaseLock[rf];
ReleaseLock[dummyRopeFile];
};
ENDCASE;
ENDLOOP;
};
FilesOnQueue:
PROC
RETURNS [nameList:
LIST
OF
ROPE ←
NIL] = {
Useful little crock for debugging
AcquireLock[dummyRopeFile];
FOR each: Handle ← dummyRopeFile.next, each.next
WHILE each #
NIL
DO
name: ROPE ← "NIL file!?!?!?!?";
stream: STREAM = each.file;
IF stream #
NIL
THEN
name ← FS.GetName[FS.OpenFileFromStream[stream]].fullFName;
nameList ← CONS[name, nameList];
ENDLOOP;
ReleaseLock[dummyRopeFile];
};
FinalizationProblem: SIGNAL = CODE;
dummyRopeFile: Handle ← NIL; -- for synchronization
ropesOutstanding: INT ← 0; -- protected by lock
fq: SafeStorage.FinalizationQueue = SafeStorage.NewFQ[32]; -- for finalization
TRUSTED {
ok: BOOL ← TRUE;
SafeStorage.EstablishFinalization[
CODE[RopeFileRep], 1, fq
! SafeStorage.CantEstablishFinalization => {ok ← FALSE; CONTINUE}];
IF
NOT ok
THEN {
ok ← TRUE;
SafeStorage.ReEstablishFinalization[
CODE[RopeFileRep], 1, fq
! SafeStorage.CantEstablishFinalization => {ok ← FALSE; CONTINUE}];
IF NOT ok THEN SIGNAL FinalizationProblem;
};
dummyRopeFile ← NEW[RopeFileRep];
Process.Detach[FORK RopeFileFinalizer[]];
};