File: DBStorageTuplesetScanImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
This module exports tupleset scan-related stuff to DBStorage.
Last edited by:
MBrown on December 2, 1982 3:20 pm
Cattell on November 2, 1983 3:18 pm
Willie-Sue, February 15, 1985 12:48:55 pm PST
Widom, July 16, 1985 5:11:03 pm PDT
Donahue, September 5, 1985 4:19:00 pm PDT
DIRECTORY
DB USING [InternalError],
DBCommon USING[DBPage, NullDBPage, CacheHandle],
DBSegment USING[ReadPage, UnlockPage],
DBStorage USING[TupleHandle, FirstLast],
DBStorageConcrete USING[TuplesetScanObject],
DBStorageField USING[TuplesetFieldHandle],
DBStoragePagetags USING[AssertPageIsTuplePage],
DBStoragePrivate USING[GetNWordBase],
DBStorageTID USING[TID, ConsTID],
DBStorageTSDict USING[GetIndex, EntryFromIndex, TSDictSlotIndex],
DBStorageTuple USING[ConsTupleObject, IsValidTuple, TIDOfTuple],
DBStorageTupleset USING[TuplesetObject],
DBStorageTuplesetScan USING[],
DBStorageVec USING[VecPage, TypeOfSlot, HighSlotIndexOfPage];
DBStorageTuplesetScanImpl:
CEDAR
PROGRAM
IMPORTS
DB,
DBSegment,
DBStorageField,
DBStoragePrivate,
DBStoragePagetags,
DBStorageTID,
DBStorageVec,
DBStorageTuple,
DBStorageTSDict
EXPORTS
DBStorage,
DBStorageTuplesetScan
= BEGIN
OPEN DBCommon, DBStorageTID, DBStorageTuple;
Types exported to DBStorage
TuplesetScanObject: PUBLIC TYPE = DBStorageConcrete.TuplesetScanObject;
TuplesetScanHandle: TYPE = REF TuplesetScanObject;
Module global state
activeTuplesetScanList: TuplesetScanHandle;
1st item on list is a permanent header node
Init:
PUBLIC
PROC = {
activeTuplesetScanList ← NEW[TuplesetScanObject ← [tupleset: NIL]];
};
OpenScanTupleset:
PUBLIC
PROC [
x: DBStorage.TupleHandle--tupleset--, start: DBStorage.FirstLast]
RETURNS [TuplesetScanHandle] = {
result: TuplesetScanHandle = NEW[TuplesetScanObject ← [tupleset: x]];
result.position ←
SELECT start FROM First => beforeFirst, Last => afterLast, ENDCASE => ERROR;
result.link ← activeTuplesetScanList.link;
activeTuplesetScanList.link ← result;
RETURN[result] };
NextScanTupleset:
PUBLIC
PROC [scan: TuplesetScanHandle]
RETURNS [DBStorage.TupleHandle] = {
IF scan=NIL THEN RETURN[NIL]; -- convenience feature
DO
--loop to simulate tail-recursion
WHILE scan.position # middle
DO
SELECT scan.position
FROM
beforeFirst => {SetInitialPage[scan]; NewPage[scan, forward]};--makes position # beforeFirst
afterLast => RETURN[NIL];
invalid => ERROR DB.InternalError; -- InvalidTuplesetScan
ENDCASE => ERROR;
ENDLOOP;
FOR slotI:
CARDINAL
IN [scan.slotIndex + 1 .. DBStorageVec.HighSlotIndexOfPage[scan.pagePtr]]
DO
IF DBStorageVec.TypeOfSlot[scan.pagePtr, slotI] = scan.localTuplesetID THEN GOTO FoundNext;
REPEAT
FoundNext => {
--return the tuple
result: DBStorage.TupleHandle ←
ConsTupleObject[tid: ConsTID[scan.page, slotI], cacheHint: scan.pageHint];
scan.slotIndex ← slotI;
RETURN[result];
};--FoundNext
FINISHED => {
--try next page
TRUSTED {
scan.page ← DBStorageTSDict.EntryFromIndex[scan.pagePtr, scan.localTuplesetID].next;
};
DBSegment.UnlockPage[scan.pageHint];
NewPage[scan, forward];
};--FINISHED
ENDLOOP;
ENDLOOP;
};--NextScanTupleset
PrevScanTupleset:
PUBLIC
PROC [scan: TuplesetScanHandle]
RETURNS [DBStorage.TupleHandle] = {
IF scan=NIL THEN RETURN[NIL]; -- convenience feature
DO
--loop to simulate tail-recursion
WHILE scan.position # middle
DO
SELECT scan.position
FROM
beforeFirst => RETURN[NIL];
afterLast => {SetInitialPage[scan]; NewPage[scan, backward]};--makes position # afterLast
invalid => ERROR DB.InternalError; -- InvalidTuplesetScan
ENDCASE => ERROR;
ENDLOOP;
FOR slotI:
CARDINAL
DECREASING
IN (DBStorageTSDict.TSDictSlotIndex ..
MIN[scan.slotIndex, DBStorageVec.HighSlotIndexOfPage[scan.pagePtr]] ]
DO
IF DBStorageVec.TypeOfSlot[scan.pagePtr, slotI] = scan.localTuplesetID THEN GOTO FoundNext;
REPEAT
FoundNext => {
--return the tuple
result: DBStorage.TupleHandle ←
ConsTupleObject[tid: ConsTID[scan.page, slotI], cacheHint: scan.pageHint];
scan.slotIndex ← slotI - 1;
RETURN[result];
};--FoundNext
FINISHED => {
--try next page
TRUSTED {
scan.page ← DBStorageTSDict.EntryFromIndex[scan.pagePtr, scan.localTuplesetID].prev;
};
DBSegment.UnlockPage[scan.pageHint];
NewPage[scan, backward];
};--FINISHED
ENDLOOP;
ENDLOOP;
};--PrevScanTupleset
SetInitialPage:
PROC [scan: TuplesetScanHandle] =
TRUSTED {
Initializes scan.page. scan.position indicates where to start; middle is not allowed!
Called from: NextScanTupleset, PrevScanTupleset.
tsObjPtr: LONG POINTER TO DBStorageTupleset.TuplesetObject;
cacheHint: DBCommon.CacheHandle;
[tsObjPtr, cacheHint] ←
DBStoragePrivate.GetNWordBase[scan.tupleset, DBStorageField.TuplesetFieldHandle[]];
scan.page ←
SELECT scan.position
FROM
beforeFirst => tsObjPtr.searchList.next,
afterLast => tsObjPtr.searchList.prev,
ENDCASE => ERROR;
DBSegment.UnlockPage[cacheHint];
};--SetInitialPage
ForwardBackward: TYPE = {forward, backward};
NewPage:
PROC [scan: TuplesetScanHandle, direction: ForwardBackward] =
TRUSTED {
Makes scan consistent with a new value of page. The new page represents a movement in the
indicated direction. Current page, if any, should already have been unlocked.
Called from: NextScanTupleset, PrevScanTupleset, NoticeDeletion.
IF scan.page = NullDBPage
THEN {
scan.position ←
SELECT direction
FROM
forward => afterLast,
backward => beforeFirst,
ENDCASE => ERROR; }
ELSE {
tsIsInDict: BOOLEAN;
scan.slotIndex ←
SELECT direction
FROM
forward => DBStorageTSDict.TSDictSlotIndex,
backward => LAST[CARDINAL],--larger than the number of slots on a page
ENDCASE => ERROR;
[scan.pageHint, scan.pagePtr] ← DBSegment.ReadPage[scan.page, NIL];
DBStoragePagetags.AssertPageIsTuplePage[scan.pagePtr];
[scan.localTuplesetID, tsIsInDict] ←
DBStorageTSDict.GetIndex[scan.pagePtr, TIDOfTuple[scan.tupleset]];
IF ~tsIsInDict THEN ERROR DB.InternalError; --[BadTuplesetSearchList];
scan.position ← middle;
};--IF
};--NewPage
CloseScanTupleset:
PUBLIC
PROC [scan: TuplesetScanHandle] = {
IF scan.position = middle THEN DBSegment.UnlockPage[scan.pageHint];
FOR scanPred: TuplesetScanHandle ← activeTuplesetScanList, scanPred.link
UNTIL scanPred =
NIL
DO
IF scanPred.link = scan THEN {scanPred.link ← scan.link; scan.link ← NIL; EXIT};
REPEAT
FINISHED => ERROR DB.InternalError; --[TuplesetScanNotFound];
ENDLOOP;
scan.position ← invalid;
scan.pageHint ← NIL;
scan.tupleset ← NIL;
};--CloseScanTupleset
CallAfterFinishTransaction:
PUBLIC
PROC [] = {
rPrev: TuplesetScanHandle ← activeTuplesetScanList;
UNTIL rPrev.link =
NIL
DO
r: TuplesetScanHandle ← rPrev.link;
IF
NOT DBStorageTuple.IsValidTuple[r.tupleset]
THEN {
r.position ← invalid;
r.pageHint ← NIL;
r.tupleset ← NIL;
rPrev.link ← r.link; r.link ← NIL;
}
ELSE rPrev ← r;
ENDLOOP;
};
NoticeDeletion:
PUBLIC
PROC [
dbPage: DBPage, tsID: TID, localTSID: CARDINAL, nextDBPage: DBPage] = {
FOR scan: TuplesetScanHandle ← activeTuplesetScanList.link, scan.link
UNTIL scan=
NIL
DO
IF scan.position = middle
AND scan.page = dbPage
THEN {
scan is on the affected page; is it on the deleted tupleset?
IF DBStorageTuple.TIDOfTuple[scan.tupleset] = tsID
THEN {
yes, move scan to start of nextDBPage (which may be NullDBPage)
scan.page ← nextDBPage;
DBSegment.UnlockPage[scan.pageHint];
NewPage[scan, forward]; }
ELSE {
no, but adjust localTuplesetID if required
IF scan.localTuplesetID > localTSID
THEN
scan.localTuplesetID ← scan.localTuplesetID - 1;
};--IF
};--IF
ENDLOOP;
};--NoticeDeletion
END.--DBStorageTuplesetScanImpl
CHANGE LOG
Created by MBrown on June 14, 1980 12:26 PM
Moved code from StorageImplC in process of introducing opaque types.
Changed by MBrown on June 20, 1980 4:26 PM
Added explicit management of free TuplesetScanObjects.
Changed by MBrown on July 9, 1980 6:25 PM
Implemented NoticeDeletion; still need to make other changes relating to bidirectional scans.
Changed by MBrown on July 9, 1980 11:40 PM
Finished revision for bidirectional scans (major rewrite). We may want to have this module
export TupleObject later, so that it can read the tid. Also needed: an internal ReadNWord
routine that allocates no storage (just returns long pointer to locked cache page).
Changed by MBrown on July 11, 1980 2:47 PM
Fixed some glitches caused by the late-evening coding above.
Changed by MBrown on July 22, 1980 2:28 PM
TuplesetObject was changed, causing change here. Also converted to use GetNWordBase instead
of ReadNWord.
Changed by MBrown on August 1, 1980 10:59 PM
Bug: NextScanTupleset (also PrevScanTupleset) failed on empty tupleset. My comment in the
code made an assertion that wasn't true. Replacing an IF by a WHILE solved the problem!
Changed by MBrown on August 3, 1980 1:24 AM
Bug: CloseScanTupleset failed to free scan.tupleset (the old version did free it, but in
adding the code to remove scan from the active list, I deleted the freeing operaton).
Changed by MBrown on August 4, 1980 10:34 PM
Added NoticeCloseDatabase.
Changed by MBrown on August 6, 1980 9:34 PM
NoticeCloseDatabase now invalidates all scans on the active list, but does not delete them.
A CloseScan on an invalid object removes it from the list. BadOperation may be resumed when
raised from this proc.
Changed by MBrown on September 12, 1980 2:09 PM
Added Finalize.
Changed by MBrown on November 12, 1980 4:11 PM
In NoticeCloseDatabase, set activeTuplesetScanList.link ← NIL after deallocation.
This is a hack; it leaves garbage around, and doing a CloseScanTupleset on a
deleted scan will cause InternalBug[TuplesetScanNotFound] to be generated.
Changed by MBrown on December 11, 1980 2:39 PM
Undid the above hack, and modified Finalize to not raise any signals. Made NextScanTupleset
and PrevScanTupleset ERROR BadOperation[InvalidTuplesetScan] when invoked on a tupleset scan with
p.position = invalid.
Changed by MBrown on February 27, 1981 4:09 PM
Use zone for storage allocation.
Changed by MBrown on 17-Jun-81 11:06:35
Use counted zone for storage allocation. No longer need to copy the tupleset tuple.
Retain Alloc and Free procs for TuplesetScanObjects, in case we need to economize on
allocations later.
Changed by MBrown on December 2, 1982 3:05 pm
Implement CallAfterFinishTransaction (new segment scheme).
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting