YggLogMapImpl.mesa
Copyright Ó 1985, 1988 by Xerox Corporation. All rights reserved.
Last edited by
Taft on November 19, 1982 5:59 pm
Kolling on January 30, 1984 3:13 pm
MBrown on January 30, 1984 9:20:26 pm PST
Hauser, March 27, 1985 10:49:29 am PST
Carl Hauser, February 24, 1987 4:55:01 pm PST
Bob Hagmann May 9, 1988 1:38:31 pm PDT
DIRECTORY
YggEnvironment
USING[PageCount, PageNumber, PageRun],
YggInternal
USING[Document, LogRecordID, TransHandle],
Basics
USING[CompareInt],
YggDIDMap
USING[ClearLogMapHandle, Document, VerifyLogMapHandle],
YggLogMap
USING[CheckOutOption, CallingErrorType, FileDescription, Location, MappedPageRun],
YggLogMapPrivate
USING[IntentionObject, Intention],
RedBlackTree
USING[Compare, Create, Delete, GetKey, Insert, Lookup, LookupLargest, LookupNextLarger,
LookupNextSmaller, LookupSmallest, Node, Table],
YggTransactionMap
USING[IsCommitted];
YggLogMapImpl: CEDAR MONITOR LOCKS logMapHandle USING logMapHandle: LogMap
IMPORTS Basics, YggDIDMap, RedBlackTree, YggTransactionMap
EXPORTS YggInternal, YggLogMap =
BEGIN
LogMap: TYPE = REF LogMapRep;
LogMapRep: PUBLIC TYPE = MONITORED RECORD[
createTrans: YggInternal.TransHandle,
deleteTrans: YggInternal.TransHandle,
sizeUncommitted: YggEnvironment.PageCount,
sizeUncommittedTrans: YggInternal.TransHandle,
sizeCommitted: YggEnvironment.PageCount,
highWaterMarkCommitted: YggEnvironment.PageCount,
intentionsTable: RedBlackTree.Table,
rbKeyRef should be initialized at creation to refer to an YggEnvironment.PageNumber object. It is used thereafter for the key parameter to RedBlackTree routines, called from YggFilePageMgrMainImpl. This avoids allocating an object to get a reference each time such a call is made.
rbKeyRef: REF YggEnvironment.PageNumber
];
Error: PUBLIC --CALLING-- ERROR [error: YggLogMap.CallingErrorType] = CODE;
fatal errors:
ProbableLockingFailure: --CALLING-- ERROR = CODE;
Horrible: --CALLING-- ERROR = CODE;
DescribeFile: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] RETURNS
[fileDesc: YggLogMap.FileDescription] =
BEGIN -- non-fatal errors: none.
MonitoredDescribeFile: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
fileDesc.registered ← TRUE;
fileDesc.created ← trans = logMapHandle.createTrans;
fileDesc.deleted ← trans = logMapHandle.deleteTrans;
TRUSTED BEGIN fileDesc.exists ← (
((fileDesc.created) OR (logMapHandle.createTrans = NIL) OR
(YggTransactionMap.IsCommitted[logMapHandle.createTrans]))
AND NOT ((fileDesc.deleted) OR ((logMapHandle.deleteTrans # NIL) AND
(YggTransactionMap.IsCommitted[logMapHandle.deleteTrans])))); END;
fileDesc.sizeChanged ← trans = logMapHandle.sizeUncommittedTrans;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle # NIL
THEN MonitoredDescribeFile[logMapHandle]
ELSE fileDesc.registered ← FALSE;
END;
A fatal error is raised if the LogMapRep createTrans field is not NIL.
RegisterCreate: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] =
BEGIN -- non-fatal errors: none.
MonitoredRegisterCreate: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
IF logMapHandle.createTrans # NIL THEN RETURN WITH ERROR ProbableLockingFailure;
logMapHandle.createTrans ← trans;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
MonitoredRegisterCreate[logMapHandle];
END;
A fatal error is raised if the LogMapRep deleteTrans field is not NIL.
RegisterDelete: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] =
BEGIN -- non-fatal errors: none.
MonitoredRegisterDelete: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
IF logMapHandle.deleteTrans # NIL THEN RETURN WITH ERROR ProbableLockingFailure;
logMapHandle.deleteTrans ← trans;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
MonitoredRegisterDelete[logMapHandle];
END;
Remembers the uncommitted size of the file and which trans is setting it. If trans # NIL and the previous trans that set the uncommitted size # NIL and these transactions do not match, a fatal error is raised.
SetUncommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, size:
YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredSetUncommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
IF ((logMapHandle.sizeUncommittedTrans = NIL) OR
(trans = NIL) OR
(trans = logMapHandle.sizeUncommittedTrans))
THEN BEGIN logMapHandle.sizeUncommittedTrans ← trans;
logMapHandle.sizeUncommitted ← size;
END
ELSE RETURN WITH ERROR ProbableLockingFailure;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
MonitoredSetUncommittedSize[logMapHandle];
END;
Returns the uncommitted size (LAST[PageCount] if it has never been set). If the previous trans that set the uncommitted size # NIL and if trans does not match the previous trans, then if the previous trans is committed a fatal error is raised else LAST[PageCount] is returned.
GetUncommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle]
RETURNS[size: YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredGetUncommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
IF ((trans # logMapHandle.sizeUncommittedTrans) AND
(logMapHandle.sizeUncommittedTrans # NIL))
THEN TRUSTED BEGIN
IF YggTransactionMap.IsCommitted[logMapHandle.sizeUncommittedTrans]
THEN RETURN WITH ERROR ProbableLockingFailure
ELSE size ← LAST[YggEnvironment.PageCount];
END
ELSE size ← logMapHandle.sizeUncommitted;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]];
MonitoredGetUncommittedSize[logMapHandle];
END;
Remembers the committed size of the file.
SetCommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document, size: YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredSetCommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
logMapHandle.sizeCommitted ← size;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
MonitoredSetCommittedSize[logMapHandle];
END;
Returns the committed size of the file (LAST[PageCount] if it has never been set).
GetCommittedSize: PUBLIC PROCEDURE[file: YggInternal.Document] RETURNS[size: YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredGetCommittedSize: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
size ← logMapHandle.sizeCommitted;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]];
MonitoredGetCommittedSize[logMapHandle];
END;
Remembers the committed high water mark for the file.
SetCommittedHighWaterMark: PUBLIC PROCEDURE[file: YggInternal.Document, highWaterMark:
YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredSetCommittedHighWaterMark: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
logMapHandle.highWaterMarkCommitted ← highWaterMark;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
MonitoredSetCommittedHighWaterMark[logMapHandle];
END;
Returns the committed high water mark for the file (LAST[PageCount] if it has never been set).
GetCommittedHighWaterMark: PUBLIC PROCEDURE[file: YggInternal.Document] RETURNS
[highWaterMark: YggEnvironment.PageCount] =
BEGIN -- non-fatal errors: none.
MonitoredGetCommittedHighWaterMark: ENTRY PROCEDURE[logMapHandle: LogMap] = INLINE
BEGIN -- non-fatal errors: none.
highWaterMark ← logMapHandle.highWaterMarkCommitted;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle = NIL THEN RETURN[LAST[YggEnvironment.PageCount]];
MonitoredGetCommittedHighWaterMark[logMapHandle];
END;
For file pages, the LogMap remembers only the LogRecordID for the data written, rather than the actual data; it is the client's responsibility to subsequently read the log, if necessary.
Registers a logged write of the pages identified by <file, pageRun> for transaction trans, identified in the log by logRecordID. The log record contains exactly this pageRun. If writes are already registered for any of those pages by the same transaction, the old writes are forgotten. If writes are already registered for a different transaction, a fatal error is raised.
RegisterPages: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, pageRun:
YggEnvironment.PageRun, logRecordID: YggInternal.LogRecordID] =
BEGIN -- non-fatal errors: none.
MonitoredRegisterPages: ENTRY PROCEDURE[logMapHandle: LogMap] =
BEGIN -- non-fatal errors: none.
currentFirstPage: YggEnvironment.PageNumber ← pageRun.firstPage;
currentCount: INT ← pageRun.count;
int: YggLogMapPrivate.Intention ← RBTLookupNextSmaller[logMapHandle,
currentFirstPage];
IF ((int # NIL) AND
(int.pageRun.firstPage + int.pageRun.count > currentFirstPage))
THEN -- fission off the higher part.
BEGIN
higherPartInt: YggLogMapPrivate.Intention ← NEW[YggLogMapPrivate.IntentionObject ←
[int.trans, [currentFirstPage, int.pageRun.count - (currentFirstPage -
int.pageRun.firstPage)], int.logRecordID, FALSE, , , ]];
RBTInsert[logMapHandle, higherPartInt,
higherPartInt.pageRun.firstPage];
int.pageRun.count ← int.pageRun.count - higherPartInt.pageRun.count;
int ← higherPartInt;
END
ELSE int ← RBTLookup[logMapHandle, currentFirstPage];
DO -- on entry int starts at currentFirstPage or is NIL if nothing starts there.
IF int = NIL
THEN BEGIN
overlap: BOOLEAN;
newInt: YggLogMapPrivate.Intention;
int ← RBTLookupNextLarger[logMapHandle, currentFirstPage];
overlap ← ((int # NIL) AND (int.pageRun.firstPage < currentFirstPage +
currentCount));
newInt ← NEW[YggLogMapPrivate.IntentionObject ← [trans, [currentFirstPage,
(IF overlap THEN int.pageRun.firstPage - currentFirstPage ELSE
currentCount)], logRecordID, FALSE, , , ]]; -- newInt starts at currentFirstPage.
RBTInsert[logMapHandle, newInt, newInt.pageRun.firstPage];
IF NOT overlap THEN EXIT;
currentCount ← currentCount - newInt.pageRun.count;
currentFirstPage ← int.pageRun.firstPage;
END;
here int starts at (possibly changed) currentFirstPage.
IF ((int.trans # trans) OR (int.checkedOut))
THEN RETURN WITH ERROR ProbableLockingFailure;
IF int.pageRun.count > currentCount
THEN BEGIN -- fission off the higher part.
higherPartInt: YggLogMapPrivate.Intention ← NEW[YggLogMapPrivate.IntentionObject ←
[trans, [currentFirstPage + currentCount, int.pageRun.count - currentCount],
int.logRecordID, FALSE, , , ]];
RBTInsert[logMapHandle, higherPartInt,
higherPartInt.pageRun.firstPage];
int.pageRun.count ← currentCount;
END;
int.logRecordID ← logRecordID;
IF (currentCount ← currentCount - int.pageRun.count) = 0 THEN EXIT;
currentFirstPage ← currentFirstPage + int.pageRun.count;
int ← RBTLookup[logMapHandle, currentFirstPage];
ENDLOOP;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, TRUE];
TRUSTED BEGIN IF YggTransactionMap.IsCommitted[trans] THEN ERROR Horrible; END;
MonitoredRegisterPages[logMapHandle];
END;
Forgets registered writes for the specified pageRun. If the <file, pageRun> does not exactly match a checked out entry in the LogMap, a fatal error is raised.
UnregisterPages: PUBLIC PROCEDURE[file: YggInternal.Document, pageRun: YggEnvironment.PageRun] =
BEGIN -- non-fatal errors: none.
MonitoredUnregisterPages: ENTRY PROCEDURE[logMapHandle: LogMap] =
BEGIN -- non-fatal errors: none.
intention: YggLogMapPrivate.Intention ← RBTLookup[logMapHandle, pageRun.firstPage];
IF ((intention = NIL) OR (NOT intention.checkedOut) OR (intention.pageRun.count # pageRun.count))
THEN RETURN WITH ERROR Horrible;
[] ← RBTDelete[logMapHandle, pageRun.firstPage];
BROADCAST IntentionFreed;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle = NIL THEN ERROR Horrible;
MonitoredUnregisterPages[logMapHandle];
END;
IntentionFreed: CONDITION;
A caller who checks out an entry is required to carry out the operation described by that entry and then Unregister the entry from the YggLogMap before proceeding further. Checking out an entry prevents other clients from checking out the same entry. If the entry is already checked out, the checkOut option waits until that entry has been unregistered (or, more likely, on something less specific) and then tries again.
Returns a MappedPageRun describing the initial interval of pageRun. If the YggLogMap knows the size of the file as seen by this transaction (precisely, if SetUncommittedSize has been done by this trans or, failing that, if SetCommittedSize has been done), exceedsFileSize is errored if any part of the pageRun is past the eof. No checking is done to see if the file exists. If the initial interval of pageRun is not represented in the YggLogMap or if it is represented but for an uncommitted different transaction, returns location = base. Otherwise, handles the CheckOutOption, and if it doesn't have to wait and retry, returns location = log and a MappedPageRun log field containing the data which describes the initial interval. The pageRun describes the initial interval available.
LocatePages: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle, pageRun:
YggEnvironment.PageRun, checkOut: YggLogMap.CheckOutOption] RETURNS[mappedPageRun:
YggLogMap.MappedPageRun] =
BEGIN -- non-fatal errors: Error[exceedsFileSize].
MonitoredLocatePages: ENTRY PROCEDURE[logMapHandle: LogMap]
RETURNS[mappedPageRun: YggLogMap.MappedPageRun] =
BEGIN -- non-fatal errors: Error[exceedsFileSize].
int: YggLogMapPrivate.Intention;
currentCount: INT;
DO
IF pageRun.firstPage + pageRun.count > (IF logMapHandle.sizeUncommittedTrans = trans
THEN logMapHandle.sizeUncommitted ELSE logMapHandle.sizeCommitted)
THEN RETURN WITH ERROR Error[exceedsFileSize];
int ← RBTLookup[logMapHandle, pageRun.firstPage];
IF (int # NIL)
THEN currentCount ← MIN[pageRun.count, int.pageRun.count]
ELSE BEGIN
int ← RBTLookupNextSmaller[logMapHandle, pageRun.firstPage];
IF ((int # NIL) AND (int.pageRun.firstPage + int.pageRun.count >
pageRun.firstPage))
THEN currentCount ← MIN[int.pageRun.firstPage + int.pageRun.count,
pageRun.firstPage + pageRun.count] - pageRun.firstPage
ELSE BEGIN
int ← RBTLookupNextLarger[logMapHandle,
pageRun.firstPage];
IF int # NIL
THEN BEGIN
currentCount ← IF int.pageRun.firstPage < pageRun.firstPage +
pageRun.count
THEN int.pageRun.firstPage - pageRun.firstPage
ELSE pageRun.count;
int ← NIL;
END
ELSE currentCount ← pageRun.count;
END;
END;
TRUSTED BEGIN IF ((int = NIL) OR
((int.trans # trans) AND (NOT YggTransactionMap.IsCommitted[int.trans])))
THEN RETURN[[[pageRun.firstPage, currentCount], base[]]]; END;
IF int.trans = trans
THEN RETURN[[[pageRun.firstPage, currentCount], log[int.logRecordID, int.pageRun,
FALSE]]];
IF checkOut = checkOut
THEN BEGIN
IF int.checkedOut
THEN BEGIN WAIT IntentionFreed; LOOP; END
ELSE int.checkedOut ← TRUE;
END;
RETURN[[[pageRun.firstPage,
currentCount], log[int.logRecordID, int.pageRun, (checkOut = checkOut)]]];
ENDLOOP;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle = NIL THEN RETURN[[pageRun, base[]]];
RETURN[MonitoredLocatePages[logMapHandle]];
END;
Looks for registered writes for this trans in file. If there is an unchecked out one, checks it out, and returns it. Otherwise, if the only ones it can find are ones which have already been checked out, it waits until they all go away. When unable to find any, returns found = FALSE.
LocateAnyPagesForTrans: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle]
RETURNS[found: BOOLEAN, logRecordID: YggInternal.LogRecordID, logMapPageRun: YggEnvironment.PageRun] =
BEGIN -- non-fatal errors: none.
MonitoredLocateAnyPagesForTrans: ENTRY PROCEDURE[logMapHandle: LogMap] =
BEGIN -- non-fatal errors: none.
FOR intention: YggLogMapPrivate.Intention ← RBTLookupSmallest[logMapHandle],
RBTLookupNextLarger[logMapHandle, intention.pageRun.firstPage]
UNTIL intention = NIL
DO
IF ((intention.trans = trans) AND (NOT intention.checkedOut))
THEN BEGIN
found ← TRUE;
intention.checkedOut ← TRUE;
logRecordID ← intention.logRecordID;
logMapPageRun ← intention.pageRun;
RETURN;
END;
ENDLOOP;
DO
FOR intention: YggLogMapPrivate.Intention ← RBTLookupSmallest[logMapHandle],
RBTLookupNextLarger[logMapHandle, intention.pageRun.firstPage]
UNTIL intention = NIL
DO
IF intention.trans = trans
THEN BEGIN
IF (NOT intention.checkedOut) THEN RETURN WITH ERROR Horrible;
WAIT IntentionFreed;
EXIT;
END;
REPEAT FINISHED => GOTO allDone;
ENDLOOP;
REPEAT allDone => NULL;
ENDLOOP;
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
found ← FALSE;
IF logMapHandle # NIL THEN MonitoredLocateAnyPagesForTrans[logMapHandle];
END;
Removes from the YggLogMap all information that was set by transaction trans for this file. If fields that were associated with this trans will persist, they are set to their default initial values. If the intentionsTable becomes empty and no trans fields in the LogMapRep contain references to other transactions, the LogMapRep is thrown away.
UnregisterTrans: PUBLIC PROCEDURE[file: YggInternal.Document, trans: YggInternal.TransHandle] =
BEGIN -- non-fatal errors: none.
MonitoredUnregisterTrans: ENTRY PROCEDURE[logMapHandle: LogMap] =
BEGIN -- non-fatal errors: none.
ClearTransFromLogMapHandle: INTERNAL PROCEDURE RETURNS[LogMap] =
BEGIN -- non system fatal errors: none.
FOR intention: YggLogMapPrivate.Intention ←
RBTLookupSmallest[logMapHandle],
RBTLookupNextLarger[logMapHandle,
intention.pageRun.firstPage]
UNTIL intention = NIL
DO
IF intention.trans = trans
THEN BEGIN
IF intention.checkedOut THEN RETURN WITH ERROR Horrible;
[] ← RBTDelete[logMapHandle,
intention.pageRun.firstPage];
END;
ENDLOOP;
IF logMapHandle.createTrans = trans THEN logMapHandle.createTrans ← NIL;
IF logMapHandle.deleteTrans = trans THEN logMapHandle.deleteTrans ← NIL;
IF logMapHandle.sizeUncommittedTrans = trans
THEN BEGIN logMapHandle.sizeUncommittedTrans ← NIL;
logMapHandle.sizeUncommitted ← LAST[YggEnvironment.PageCount];
END;
IF ((RBTLookupSmallest[logMapHandle] = NIL) AND
(logMapHandle.createTrans = NIL) AND
(logMapHandle.deleteTrans = NIL) AND
(logMapHandle.sizeUncommittedTrans = NIL) )
THEN RETURN[NIL]
ELSE RETURN[logMapHandle];
END;
YggDIDMap.ClearLogMapHandle[file, ClearTransFromLogMapHandle];
END;
logMapHandle: LogMap ← GetOrReportOnLogMapHandle[file, FALSE];
IF logMapHandle # NIL THEN MonitoredUnregisterTrans[logMapHandle];
END;
utility routines:
GetKeyProc: RedBlackTree.GetKey -- PROC [data: UserData] RETURNS [Key]
= {
RETURN[ data ];
};
CompareProc: RedBlackTree.Compare -- PROC [k: Key, data: UserData] RETURNS [Basics.Comparison]
= {
dataIntention: YggLogMapPrivate.Intention = NARROW[ data ];
WITH k SELECT FROM
pnRef: REF YggEnvironment.PageNumber => RETURN[Basics.CompareInt[pnRef^, dataIntention.pageRun.firstPage]];
keyIntention: YggLogMapPrivate.Intention => RETURN[Basics.CompareInt[keyIntention.pageRun.firstPage, dataIntention.pageRun.firstPage]];
ENDCASE => ERROR;
};
If create is FALSE and the logMapHandle doesn't exist, will return NIL.
GetOrReportOnLogMapHandle: PROCEDURE[fileHandle: YggDIDMap.Document, create: BOOLEAN]
RETURNS[logMapHandle: LogMap] =
BEGIN -- non system fatal errors: none.
CreateLogMapHandle: PROCEDURE RETURNS[logMapHandle: LogMap] =
BEGIN -- non system fatal errors: none.
logMapHandle ← IF create
THEN NEW[LogMapRep ← [
createTrans: NIL,
deleteTrans: NIL,
sizeUncommitted: LAST[YggEnvironment.PageCount],
sizeUncommittedTrans: NIL,
sizeCommitted: LAST[YggEnvironment.PageCount],
highWaterMarkCommitted: LAST[YggEnvironment.PageCount],
intentionsTable: RedBlackTree.Create[getKey: GetKeyProc, compare: CompareProc],
rbKeyRef: NEW[YggEnvironment.PageNumber ← 0]]
]
ELSE NIL;
END;
logMapHandle ← YggDIDMap.VerifyLogMapHandle[fileHandle, CreateLogMapHandle];
END;
A thin interface over RedBlackTree handling the coercions.
RBTLookupProc: TYPE = PROCEDURE[ logMapHandle: LogMap, key: YggEnvironment.PageNumber ] RETURNS [YggLogMapPrivate.Intention];
RBTLookup: INTERNAL RBTLookupProc = {
logMapHandle.rbKeyRef^ ← key;
RETURN[ NARROW[RedBlackTree.Lookup[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ];
};
RBTLookupNextLarger: INTERNAL RBTLookupProc = {
logMapHandle.rbKeyRef^ ← key;
RETURN[ NARROW[RedBlackTree.LookupNextLarger[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ];
};
RBTLookupNextSmaller: INTERNAL RBTLookupProc = {
logMapHandle.rbKeyRef^ ← key;
RETURN[ NARROW[RedBlackTree.LookupNextSmaller[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef]] ];
};
RBTLookupLargest: INTERNAL PROCEDURE[ logMapHandle: LogMap ] RETURNS [YggLogMapPrivate.Intention] = {
RETURN[ NARROW[RedBlackTree.LookupLargest[ logMapHandle.intentionsTable]] ];
};
RBTLookupSmallest: INTERNAL PROCEDURE[ logMapHandle: LogMap ] RETURNS [YggLogMapPrivate.Intention] = {
RETURN[ NARROW[RedBlackTree.LookupSmallest[ logMapHandle.intentionsTable ]] ];
};
RBTDelete: INTERNAL PROCEDURE[ logMapHandle: LogMap, key: YggEnvironment.PageNumber ] RETURNS [YggLogMapPrivate.Intention] = {
n: RedBlackTree.Node;
logMapHandle.rbKeyRef^ ← key;
n ← RedBlackTree.Delete[ logMapHandle.intentionsTable, logMapHandle.rbKeyRef];
RETURN[ IF n=NIL THEN NIL ELSE NARROW[n.data] ];
};
RBTInsert: INTERNAL PROCEDURE[ logMapHandle: LogMap, refChunk: YggLogMapPrivate.Intention, key: YggEnvironment.PageNumber ] = {
logMapHandle.rbKeyRef^ ← key;
RedBlackTree.Insert[ logMapHandle.intentionsTable, refChunk, logMapHandle.rbKeyRef ];
};
main line code:
END.
Hauser: March 1, 1985: Nodified. Removed check for AlreadySet leader page handle.
Hauser, March 8, 1985 10:54:42 am PST
Added copyright