DIRECTORY DBCommon USING[DBPage, NullDBPage, CacheHandle, TID, ConsTID, InternalError], DBSegment USING[ReadPage, UnlockPage], DBStorage USING[TupleHandle, FirstLast], DBStorageConcrete USING[TuplesetScanObject], DBStorageField USING[TuplesetFieldHandle], DBStoragePage, DBStoragePrivate USING[GetNWordBase], DBStorageTuple USING[ConsTupleObject, IsValidTuple, TIDOfTuple], DBStorageTuplesetScan USING[]; DBStorageTuplesetScanImpl: CEDAR PROGRAM IMPORTS DBCommon, DBSegment, DBStorageField, DBStoragePrivate, DBStoragePage, DBStorageTuple EXPORTS DBStorage, DBStorageTuplesetScan = BEGIN OPEN DBCommon, DBStorageTuple; TuplesetScanObject: PUBLIC TYPE = DBStorageConcrete.TuplesetScanObject; TuplesetScanHandle: TYPE = REF TuplesetScanObject; activeTuplesetScanList: TuplesetScanHandle; Init: PUBLIC PROC = { activeTuplesetScanList _ NEW[TuplesetScanObject _ [tupleset: NIL]]; tempTuplesetScanHandle _ NEW[TuplesetScanObject _ [tupleset: NIL]]; }; OpenScanTupleset: PUBLIC PROC [x: DBStorage.TupleHandle, 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] }; tempTuplesetScanHandle: TuplesetScanHandle; EmptyTupleSet: PUBLIC PROC [x: DBStorage.TupleHandle] RETURNS[yes: BOOL] = { tempTuplesetScanHandle.tupleset _ x; tempTuplesetScanHandle.position _ beforeFirst; SetInitialPage[tempTuplesetScanHandle]; NewPage[tempTuplesetScanHandle, forward]; yes _ tempTuplesetScanHandle.position = afterLast; IF tempTuplesetScanHandle.position = middle THEN DBSegment.UnlockPage[tempTuplesetScanHandle.pageHint] }; FirstTuple: PUBLIC PROC [x: DBStorage.TupleHandle] RETURNS[tuple: DBStorage.TupleHandle] = { tempTuplesetScanHandle.tupleset _ x; tempTuplesetScanHandle.position _ beforeFirst; SetInitialPage[tempTuplesetScanHandle]; tuple _ NextScanTupleset[tempTuplesetScanHandle]; IF tempTuplesetScanHandle.position = middle THEN DBSegment.UnlockPage[tempTuplesetScanHandle.pageHint] }; 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 DBCommon.InternalError; -- InvalidTuplesetScan ENDCASE => ERROR; ENDLOOP; FOR slotI: CARDINAL IN [scan.slotIndex + 1 .. DBStoragePage.HighSlotIndexOfPage[scan.pagePtr]] DO IF DBStoragePage.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 _ DBStoragePage.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 DBCommon.InternalError; -- InvalidTuplesetScan ENDCASE => ERROR; ENDLOOP; FOR slotI: CARDINAL DECREASING IN (DBStoragePage.TSDictSlotIndex .. MIN[scan.slotIndex, DBStoragePage.HighSlotIndexOfPage[scan.pagePtr]] ] DO IF DBStoragePage.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 _ DBStoragePage.EntryFromIndex[scan.pagePtr, scan.localTuplesetID].prev; }; DBSegment.UnlockPage[scan.pageHint]; NewPage[scan, backward]; };--FINISHED ENDLOOP; ENDLOOP; };--PrevScanTupleset SetInitialPage: PROC [scan: TuplesetScanHandle] = TRUSTED { tsObjPtr: LONG POINTER TO DBStoragePage.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 { 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 => DBStoragePage.TSDictSlotIndex, backward => LAST[CARDINAL],--larger than the number of slots on a page ENDCASE => ERROR; [scan.pageHint, scan.pagePtr] _ DBSegment.ReadPage[scan.page, NIL]; DBStoragePage.AssertPageIsTuplePage[scan.pagePtr]; [scan.localTuplesetID, tsIsInDict] _ DBStoragePage.GetIndex[scan.pagePtr, TIDOfTuple[scan.tupleset]]; IF ~tsIsInDict THEN ERROR DBCommon.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 DBCommon.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 { IF DBStorageTuple.TIDOfTuple[scan.tupleset] = tsID THEN { scan.page _ nextDBPage; DBSegment.UnlockPage[scan.pageHint]; NewPage[scan, forward]; } ELSE { 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 Changed by MBrown on June 20, 1980 4:26 PM Changed by MBrown on July 9, 1980 6:25 PM Changed by MBrown on July 9, 1980 11:40 PM Changed by MBrown on July 11, 1980 2:47 PM Changed by MBrown on July 22, 1980 2:28 PM Changed by MBrown on August 1, 1980 10:59 PM Changed by MBrown on August 3, 1980 1:24 AM Changed by MBrown on August 4, 1980 10:34 PM Changed by MBrown on August 6, 1980 9:34 PM Changed by MBrown on September 12, 1980 2:09 PM Changed by MBrown on November 12, 1980 4:11 PM Changed by MBrown on December 11, 1980 2:39 PM Changed by MBrown on February 27, 1981 4:09 PM Changed by MBrown on 17-Jun-81 11:06:35 Changed by MBrown on December 2, 1982 3:05 pm Changed by Willie-Sue on February 15, 1985 ΤFile: DBStorageTuplesetScanImpl.mesa Copyright c 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, May 23, 1986 10:01:00 am PDT Types exported to DBStorage Module global state 1st item on list is a permanent header node Initializes scan.page. scan.position indicates where to start; middle is not allowed! Called from: NextScanTupleset, PrevScanTupleset. 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. scan is on the affected page; is it on the deleted tupleset? yes, move scan to start of nextDBPage (which may be NullDBPage) no, but adjust localTuplesetID if required Moved code from StorageImplC in process of introducing opaque types. Added explicit management of free TuplesetScanObjects. Implemented NoticeDeletion; still need to make other changes relating to bidirectional scans. 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). Fixed some glitches caused by the late-evening coding above. TuplesetObject was changed, causing change here. Also converted to use GetNWordBase instead of ReadNWord. 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! 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). Added NoticeCloseDatabase. 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. Added Finalize. 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. 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. Use zone for storage allocation. 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. Implement CallAfterFinishTransaction (new segment scheme). made Cedar, added tioga formatting Κ Α˜šœ$™$Jšœ Οmœ1™<—Jšœ=™=Jšœ™Jšœ"™"Jšœ#™#Jšœ-™-™#Icode™%—˜šΟk ˜ Jšœ žœ"žœ˜MJšœ žœ˜&Jšœ žœ˜(Jšœžœ˜,Jšœžœ˜*Jšœ˜Jšœžœ˜%Jšœžœ,˜@Jšœžœ˜J˜J˜——šœžœž˜(šž˜Jšœ ˜ Jšœ ˜ J˜J˜Jšœ˜J˜—Jšžœ!˜(J˜Jšœž˜J˜Jšžœ˜J˜J˜Jšœ™J˜Jšœžœžœ(˜GJšœžœžœ˜2J˜Jšœ™J˜˜+Jšœ+™+J˜—šΟnœžœžœ˜Jšœžœ!žœ˜CJšœžœ!žœ˜CJ˜J˜—šŸœžœžœ7žœ˜uJšœžœ%˜E˜Jšžœžœ*žœžœ˜L—J˜*J˜%Jšžœ ˜J˜—Jšœ+˜+J˜š Ÿ œžœžœžœžœ˜LJšœ$˜$Jšœ.˜.Jšœ'˜'Jšœ)˜)Jšœ2˜2šžœ)˜+Jšžœ9˜=——J˜šŸ œžœžœžœ"˜\Jšœ$˜$Jšœ.˜.Jšœ'˜'Jšœ1˜1šžœ)˜+Jšžœ9˜=——J˜šŸœžœžœžœ˜[Jš žœžœžœžœžœΟc˜4šž !˜#šžœž˜šžœž˜Jšœ@ ˜^Jšœ žœžœ˜Jšœ žœ ˜?—Jšžœžœ˜—Jšžœ˜šžœžœžœIž˜aJšžœFžœžœ ˜\—šž˜šœ ˜ ˜J˜J—J˜Jšžœ ˜—Jšœ  ˜ šžœ ˜JšžœW˜^J˜$J˜—Jšœ  ˜ —Jšžœ˜Jšžœ˜—Jšœ ˜—J˜šŸœžœžœ˜8šžœ˜#Jš žœžœžœžœžœ ˜4šž !˜#šžœž˜šžœž˜Jšœžœžœ˜Jšœ= ˜YJšœ žœ ˜?—Jšžœžœ˜—Jšžœ˜šžœžœž œžœ"˜CšžœDž˜IJšžœFžœžœ ˜\——šž˜šœ ˜ ˜J˜J—J˜Jšžœ ˜—Jšœ  ˜ šžœ ˜šžœ˜ JšœU˜U—J˜$J˜—Jšœ  ˜ —Jšžœ˜—Jšžœ˜—Jšœ ˜—J˜šŸœžœžœ˜;JšœV™VJšœ0™0Jšœ žœžœžœ˜7Jšœ ˜ ˜J˜S—šœ žœž˜%J˜(J˜&—Jšžœžœ˜J˜ Jšœ ˜—J˜Jšœžœ˜,J˜šŸœžœ:žœ˜PJšœκ™κšžœžœ˜ šœžœ ž˜%J˜J˜Jšžœžœ˜——šžœ˜Jšœ žœ˜šœžœ ž˜&Jšœ)˜)Jšœ žœžœ +˜FJšžœžœ˜—Jšœ>žœ˜CJ˜2˜$Jšœ@˜@—Jšžœ žœžœ ˜LJ˜—Jšœ ˜Jšœ  ˜ —J˜šŸœžœžœ˜=Jšžœžœ%˜CJšžœE˜Hšžœ žœž˜Jšžœžœ)žœžœ˜P—šž˜Jšžœžœ ˜C—Jšžœ˜J˜Jšœžœ˜Jšœžœ˜Jšœ ˜—J˜šŸœžœžœ˜.J˜3šžœžœž˜J˜#šžœžœ)žœ˜5J˜Jšœ žœ˜Jšœ žœ˜Jšœžœ˜#J˜—Jšžœ ˜Jšžœ˜—J˜J˜—šŸœžœžœ˜Jšœžœ žœ˜GJšžœB˜Ešžœžœž˜šžœžœžœ˜7Jšœ<™<šžœ1žœ˜9Jšœ?™?J˜J˜$J˜—šžœ˜Jšœ*™*šžœ"ž˜(J˜0——Jšœ ˜—Jšœ ˜—Jšžœ˜Jšœ ˜—J˜—Jšžœ ˜J˜J˜Jšžœž˜ J˜Jšœ*ž˜,JšœD™DJ˜Jšœ)ž˜+Jšœ6™6J˜Jšœ(ž˜*Jšœ]™]J˜Jšœ)ž˜+Jšœ\™\JšœZ™ZJšœS™SJ˜Jšœ)ž˜+Jšœ<™