DIRECTORY DBCommon, DBSegment, DBStorage USING[FieldHandle, FirstLast, MaxSystemTupleID, TupleHandle], DBStorageField USING[ CheckFieldHandleType, GroupIDOfField], DBStorageGroup USING[GroupList, GroupListFromTuple, ReadGroupField, WriteGroupField, WriteHeadField, CreateHeadEntry, DestroyHeadEntry], DBStorageConcrete USING[GroupScanObject], DBStorageGroupScan USING[], DBStoragePrivate USING[TupleFromTID], DBStorageTuple USING[ConsTupleObject, EqualTuple, IsValidTuple, InvalidateTuple, NullTupleHandle, PrintTupleObject], IO; DBStorageGroupScanImpl: CEDAR PROGRAM IMPORTS DBCommon, DBSegment, DBStorageField, DBStorageGroup, DBStoragePrivate, DBStorageTuple, IO EXPORTS DBStorage, DBStorageGroupScan = BEGIN OPEN IO, DBStorageGroup, DBStorageTuple; TID: TYPE = DBCommon.TID; NullTID: TID = DBCommon.NullTID; TupleObject: PUBLIC TYPE = DBCommon.TupleObject; TupleHandle: TYPE = REF TupleObject; GroupScanObject: PUBLIC TYPE = DBStorageConcrete.GroupScanObject; GroupScanHandle: TYPE = REF GroupScanObject; activeGroupScanList: GroupScanHandle; nullTupleHandle: TupleHandle; Init: PUBLIC PROC = { activeGroupScanList _ NEW[GroupScanObject _ [tidFieldHandle: NIL, headOfGroup: NIL]]; tempGroupScanHandle _ NEW[GroupScanObject _ [tidFieldHandle: NIL, headOfGroup: NIL]]; nullTupleHandle _ DBStorageTuple.NullTupleHandle[]; }; ReadTID: PUBLIC PROC[x: TupleHandle, f: DBStorage.FieldHandle] RETURNS[TupleHandle] = { RETURN[ReadGroupField[x, f, headTID]]; };--ReadTID WriteTID: PUBLIC PROC[x: TupleHandle, r: GroupScanHandle] = { f: DBStorage.FieldHandle = r.tidFieldHandle; currentValue: TupleHandle = ReadTID[x, f]; IF currentValue # NIL AND r.headOfGroup.tid = currentValue.tid THEN RETURN; -- No-op WriteTIDNil[x, f]; WriteGroupField[x, f, headTID, r.headOfGroup]; SELECT TRUE FROM (r.prevInScan=NIL) AND (r.nextInScan=NIL) => BEGIN --x is only tuple in group CreateHeadEntry[r.headOfGroup, f]; WriteHeadField[r.headOfGroup, f, firstTID, x]; WriteHeadField[r.headOfGroup, f, lastTID, x]; WriteGroupField[x, f, prevTID, nullTupleHandle]; WriteGroupField[x, f, nextTID, nullTupleHandle]; END; (r.prevInScan=NIL) AND (r.nextInScan#NIL) => BEGIN --x is at front of group WriteHeadField[r.headOfGroup, f, firstTID, x]; WriteGroupField[x, f, prevTID, nullTupleHandle]; WriteGroupField[x, f, nextTID, r.nextInScan]; WriteGroupField[r.nextInScan, f, prevTID, x]; END; (r.prevInScan#NIL) AND (r.nextInScan=NIL) => BEGIN --x is at rear of group WriteHeadField[r.headOfGroup, f, lastTID, x]; WriteGroupField[x, f, nextTID, nullTupleHandle]; WriteGroupField[x, f, prevTID, r.prevInScan]; WriteGroupField[r.prevInScan, f, nextTID, x]; END; (r.prevInScan#NIL) AND (r.nextInScan#NIL) => BEGIN --x is in middle of group WriteGroupField[x, f, nextTID, r.nextInScan]; WriteGroupField[r.nextInScan, f, prevTID, x]; WriteGroupField[x, f, prevTID, r.prevInScan]; WriteGroupField[r.prevInScan, f, nextTID, x]; END; ENDCASE => ERROR; BEGIN --fix up active scans that are in identical position to scan (others are unaffected) FOR p: GroupScanHandle _ activeGroupScanList.link, p.link UNTIL p = NIL DO IF (DBStorageField.GroupIDOfField[p.tidFieldHandle] # DBStorageField.GroupIDOfField[r.tidFieldHandle]) OR (~EqualTuple[p.headOfGroup,r.headOfGroup]) OR (~EqualTuple[p.prevInScan,r.prevInScan]) THEN LOOP; p.prevInScan _ x; -- no need for explicit free here anymore ... ENDLOOP; END; };--WriteTID WriteTIDNil: PUBLIC PROC[x: TupleHandle, f: DBStorage.FieldHandle] = { head, prev, next: TupleHandle; head _ ReadGroupField[x, f, headTID]; IF head = NIL THEN RETURN; prev _ ReadGroupField[x, f, prevTID]; next _ ReadGroupField[x, f, nextTID]; WriteGroupField[x, f, headTID, nullTupleHandle]; WriteGroupField[x, f, prevTID, nullTupleHandle]; --redundant WriteGroupField[x, f, nextTID, nullTupleHandle]; --redundant SELECT TRUE FROM (prev=NIL) AND (next=NIL) => BEGIN --x was only tuple in group DestroyHeadEntry[head, f]; END; (prev=NIL) AND (next#NIL) => BEGIN --x was first tuple in group WriteGroupField[next, f, prevTID, nullTupleHandle]; WriteHeadField[head, f, firstTID, next]; END; (prev#NIL) AND (next=NIL) => BEGIN --x was last tuple in group WriteGroupField[prev, f, nextTID, nullTupleHandle]; WriteHeadField[head, f, lastTID, prev]; END; (prev#NIL) AND (next#NIL) => BEGIN --x was in middle of group WriteGroupField[prev, f, nextTID, next]; WriteGroupField[next, f, prevTID, prev]; END; ENDCASE => ERROR; BEGIN --fix up active scans that contain x (others are unaffected) FOR p: GroupScanHandle _ activeGroupScanList.link, p.link UNTIL p = NIL DO IF DBStorageField.GroupIDOfField[p.tidFieldHandle] # DBStorageField.GroupIDOfField[f] THEN LOOP; IF EqualTuple[p.prevInScan,x] THEN p.prevInScan _ prev; IF EqualTuple[p.nextInScan,x] THEN p.nextInScan _ next; ENDLOOP; END; };--WriteTIDNil tempGroupScanHandle: GroupScanHandle; SetTupleField: PUBLIC PROC[x: TupleHandle, f: DBStorage.FieldHandle, val: TupleHandle] = { DBStorageField.CheckFieldHandleType[f, Group]; tempGroupScanHandle.tidFieldHandle _ f; tempGroupScanHandle.headOfGroup _ val; tempGroupScanHandle.prevInScan _ tempGroupScanHandle.nextInScan _ NIL; SetGroupHandle[tempGroupScanHandle, Last]; WriteTID[x, tempGroupScanHandle] }; TupleForField: PUBLIC PROC[x: TupleHandle, f: DBStorage.FieldHandle] RETURNS[handle: TupleHandle] = { DBStorageField.CheckFieldHandleType[f, Group]; tempGroupScanHandle.tidFieldHandle _ f; tempGroupScanHandle.headOfGroup _ x; tempGroupScanHandle.prevInScan _ tempGroupScanHandle.nextInScan _ NIL; SetGroupHandle[tempGroupScanHandle, First]; handle _ NextInGroup[tempGroupScanHandle] }; GetGroupIDs: PUBLIC PROC[x: TupleHandle] RETURNS[LIST OF TupleHandle] = TRUSTED { groupList: LONG DESCRIPTOR FOR DBStorageGroup.GroupList; cacheHint: DBCommon.CacheHandle; result: LIST OF TupleHandle; [groupList,cacheHint] _ GroupListFromTuple[x]; IF LENGTH[groupList] = 0 THEN result _ NIL ELSE { newCons, lastCons: LIST OF TupleHandle; FOR i: CARDINAL IN [0..LENGTH[groupList]) DO newCons _ LIST[ IF groupList[i].groupID <= DBStorage.MaxSystemTupleID THEN DBStoragePrivate.TupleFromTID[groupList[i].groupID] ELSE DBStorageTuple.ConsTupleObject[tid: groupList[i].groupID, cacheHint: NIL]]; IF i = 0 THEN result _ newCons ELSE lastCons.rest _ newCons; lastCons _ newCons; ENDLOOP; };--IF DBSegment.UnlockPage[cacheHint]; RETURN[result]; };--GetGroupIDs SetGroupHandle: PROC[handle: GroupScanHandle, start: DBStorage.FirstLast] = TRUSTED { head: TupleHandle = handle.headOfGroup; field: DBStorage.FieldHandle = handle.tidFieldHandle; groupList: LONG DESCRIPTOR FOR DBStorageGroup.GroupList; cacheHint: DBCommon.CacheHandle; [groupList, cacheHint] _ DBStorageGroup.GroupListFromTuple[head]; IF LENGTH[groupList] # 0 THEN BEGIN FOR i: CARDINAL IN [0..LENGTH[groupList]) DO IF groupList[i].groupID = DBStorageField.GroupIDOfField[field] THEN GOTO FoundIt; REPEAT FoundIt => SELECT start FROM First => handle.nextInScan _ DBStorageTuple.ConsTupleObject[groupList[i].firstTID, NIL]; Last => handle.prevInScan _ DBStorageTuple.ConsTupleObject[groupList[i].lastTID, NIL]; ENDCASE => ERROR; FINISHED => NULL; -- this is ok, the scan is just empty ENDLOOP; END;--IF DBSegment.UnlockPage[cacheHint]; }; OpenScanGroup: PUBLIC PROC[x: TupleHandle, f: DBStorage.FieldHandle, start: DBStorage.FirstLast] RETURNS [result: GroupScanHandle] = TRUSTED { DBStorageField.CheckFieldHandleType[f, Group]; result _ Alloc[f, x]; result.link _ activeGroupScanList.link; activeGroupScanList.link _ result; SetGroupHandle[result, start] };--OpenScanGroup Alloc: PROC[f: DBStorage.FieldHandle, x: TupleHandle] RETURNS [GroupScanHandle] = INLINE { RETURN[NEW[GroupScanObject _ [ tidFieldHandle: f, headOfGroup: x, prevInScan: NIL, nextInScan: NIL, link: NIL]]] }; NextInGroup: PUBLIC PROC[r: GroupScanHandle] RETURNS[TupleHandle] = { result: TupleHandle _ NIL; IF r=NIL THEN RETURN[NIL]; -- convenience feature IF r.tidFieldHandle = NIL THEN ERROR DBCommon.InternalError; -- InvalidGroupScan IF r.nextInScan#NIL THEN { r.prevInScan _ result _ r.nextInScan; r.nextInScan _ DBStorageGroup.ReadGroupField[result, r.tidFieldHandle, nextTID]; };--IF RETURN[result]; };--NextInGroup PrevInGroup: PUBLIC PROC[r: GroupScanHandle] RETURNS[TupleHandle] = { result: TupleHandle _ NIL; IF r=NIL THEN RETURN[NIL]; -- convenience feature IF r.tidFieldHandle = NIL THEN ERROR DBCommon.InternalError; -- InvalidGroupScan IF r.prevInScan # NIL THEN { r.nextInScan _ result _ r.prevInScan; r.prevInScan _ DBStorageGroup.ReadGroupField[result, r.tidFieldHandle, prevTID]; };--IF RETURN[result]; };--PrevInGroup CloseScanGroup: PUBLIC PROC[r: GroupScanHandle] = { FOR scanPred: GroupScanHandle _ activeGroupScanList, scanPred.link UNTIL scanPred=NIL DO IF scanPred.link=r THEN { scanPred.link _ r.link; r.link _ NIL; FreeContents[r]; RETURN; }; REPEAT FINISHED => ERROR DBCommon.InternalError; -- [GroupScanNotFound]; ENDLOOP; };--CloseScanGroup CallAfterFinishTransaction: PUBLIC PROC [] = { rPrev: GroupScanHandle _ activeGroupScanList; UNTIL rPrev.link = NIL DO r: GroupScanHandle _ rPrev.link; IF NOT DBStorageTuple.IsValidTuple[r.headOfGroup] THEN { DBStorageTuple.InvalidateTuple[r.prevInScan]; DBStorageTuple.InvalidateTuple[r.nextInScan]; FreeContents[r]; rPrev.link _ r.link; r.link _ NIL; } ELSE rPrev _ r; ENDLOOP; }; FreeContents: PROC[r: GroupScanHandle] = { r.tidFieldHandle _ NIL; r.headOfGroup _ r.prevInScan _ r.nextInScan _ NIL; };--FreeContents CheckState: PUBLIC PROC[doPrinting: BOOLEAN] = { activeGroupScanListLen: CARDINAL _ 0; FOR r: GroupScanHandle _ activeGroupScanList.link, r.link UNTIL r=NIL DO activeGroupScanListLen _ activeGroupScanListLen + 1; DBStorageField.CheckFieldHandleType[r.tidFieldHandle, Group]; IF r.headOfGroup = NIL THEN ERROR; ENDLOOP; IF doPrinting THEN { DBCommon.GetDebugStream[].PutF["list of active group scans contains %d elements*n", card[activeGroupScanListLen]]; FOR r: GroupScanHandle _ activeGroupScanList, r.link UNTIL r=NIL DO PrintGroupScanObject[r]; ENDLOOP; DBCommon.GetDebugStream[].PutF["*n"]; };--IF };--CheckState PrintGroupScanObject: PROC[scan: GroupScanHandle] = TRUSTED { pscan: POINTER TO GroupScanHandle = @scan; debugStream: IO.STREAM_ DBCommon.GetDebugStream[]; debugStream.PutF["groupScanHdl: %12bB, tidFieldHdl: ", card[LOOPHOLE[pscan, CARDINAL]]]; debugStream.PutF["*n headOfGroup: "]; DBStorageTuple.PrintTupleObject[scan.headOfGroup]; debugStream.PutF["*n prevInScan: "]; DBStorageTuple.PrintTupleObject[scan.prevInScan]; debugStream.PutF["*n nextInScan: "]; DBStorageTuple.PrintTupleObject[scan.nextInScan]; debugStream.PutF["*n"]; };--PrintGroupScanObject END.--DBStorageGroupScanImpl CHANGE LOG Created by MBrown on June 17, 1980 1:00 PM Changed by MBrown on June 20, 1980 4:19 PM Changed by MBrown on July 23, 1980 10:10 PM Changed by MBrown on August 4, 1980 11:50 PM Changed by MBrown on August 20, 1980 9:15 PM Changed by MBrown on September 12, 1980 2:13 PM Changed by MBrown on September 14, 1980 11:27 PM Changed by MBrown on September 26, 1980 12:33 PM Changed by MBrown on November 12, 1980 4:09 PM Changed by MBrown on December 11, 1980 2:26 PM Changed by MBrown on December 20, 1980 6:04 PM Changed by MBrown on February 27, 1981 3:58 PM Changed by MBrown on 9-Jun-81 18:13:50 Changed by Willie-Sue on June 24, 1982 12:19 pm Changed by Willie-Sue on June 30, 1982 4:49 pm Changed by MBrown on November 30, 1982 10:07 pm Changed by Willie-Sue on February 15, 1985 File: DBStorageGroupScanImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. This module exports group-related stuff to DBStorage. Last edited by: MBrown on December 2, 1982 3:17 pm Cattell on November 2, 1983 3:19 pm Willie-Sue on February 15, 1985 12:43:46 pm PST Widom, September 3, 1985 6:28:29 pm PDT Donahue, May 22, 1986 11:44:09 am PDT Type exported to DBStorage Module global state 1st item on list is a permanent header node If x belongs to an f-group, ReadTID returns the head of the group; otherwise it returns NIL. Makes tuple x join the group specified by r at r's current position (i.e. between the tuple just read and the next tuple that would be read by NextInGroup). A NextInGroup following WriteTID returns the tuple following x; a PrevInGroup returns x itself. Note that: (1) if x's field y had a non-NIL value before the WriteTID call, then WriteTID has the effect of deleting x from some group (using WriteTIDNIL below), (2) WriteTID cannot delete a tuple from one group without inserting it into another, so WriteTIDNil below is necessary for that case, and (3) inserting or deleting a tuple from a group requires the storage level to check all outstanding GroupScanHandles to assure that they stay consistent with the deletion. For now, this works only when inserting at the front... p is effectively identical to scan Makes x's TID field point to the null tuple, i.e. removes x from whatever f-group it currently belongs. head is free now prev, next are free now Returns a list containing all GroupIDs g such that z is the head of a g-group. The Tuple level is responsible for mapping from GroupIDs to FieldHandles, so that OpenScanGroup can be called when necessary. Append the cell just created to the list we're growing. Returns a GroupScanHandle positioned before the first (or after the last) tuple of the f-group that has tuple x as head (first or last depending upon the value of start). Returns a non-NIL GroupScanHandle even if there is no group (since the scan handle is the only way to CREATE a group). Returns the tuple x immediately following the position r in a group, and advances r one position. Returns NIL if r was already positioned after the last tuple in the group. Returns the tuple x immediately preceding the position r in a group, and moves r one position backwards. Returns NIL if r was already positioned before the first tuple in the group. Frees all objects that are dependent on r. works even if r is invalid, i.e. FreeContents[r] has been done before. There isn't really much to check, except that the lists are well-formed. if this runs forever, one isn't. DBStorageField.PrintFieldObject[scan.tidFieldHandle]; Moved code here from StorageImplB. Added explicit management of free GroupScanObjects. FirstLast changed from {First, Last} to {first, last}. Added NoticeCloseDatabase. Changed ListofGroupID to ListOfGroupID. Added CheckState. Added Finalize. NullTupleObject went away during Finalize! Now it is kept in the global frame, which requires us to export TupleHandle, etc... Converted to new DBException. In NoticeCloseDatabase, set activeGroupScanList _ NIL after deallocation. This is a hack; it leaves garbage around, and doing a CloseScanGroup on a deleted scan will cause InternalBug[GroupScanNotFound] to be generated. Undid the above hack, and modified Finalize to not raise any signals. Made NextInGroup and PrevInGroup ERROR BadOperation[InvalidGroupScan] when invoked on a group scan with r.tidFieldHandle = NIL. Added cleanup code in NextInGroup and PrevInGroup, to avoid error in finalization. Use zone for storage allocation. Converting to use collectable storage for GroupScanObject, TupleObject. IOStream => IO PrivateIO.DebugStream => DBCommon.GetDebugStream[] Changes for new segment scheme. made Cedar, added tioga formatting Κ G˜šœ!™!Jšœ Οmœ1™<—Jšœ5™5šœ™Jšœ"™"Jšœ#™#Jšœ/™/Jšœ'™'Icode™%—˜šΟk ˜ Jšœ ˜ J˜ Jšœ žœ8˜GJšœžœ(˜<šœžœ@˜TJ˜3—Jšœžœ˜)Jšœžœ˜Jšœžœ˜%šœžœ<˜PJ˜#—Jšžœ˜J˜——šœžœž˜%šž˜J˜ J˜ J˜J˜J˜J˜Jšž˜—šžœ˜&J˜—Jšœžœžœžœ!˜0J˜Jšžœžœ žœ˜Jšœ žœ˜ J˜Jšœ žœžœ˜0Jšœ žœžœ ˜$J˜J˜Jšœ™Jšœžœžœ%˜AJšœžœžœ˜,Ihead1šœ™J˜˜%Jšœ+™+—J˜J˜šΟnœžœžœ˜Jšœžœ$žœžœ˜UJšœžœ$žœžœ˜UJ˜3J˜J˜—šŸœžœžœ*žœ˜Wšœ\™\Jšžœ ˜&JšœΟc ˜ J˜J˜——šŸœžœžœ(˜=Jšœό™όJ™JšœŽ™ŽJ˜,Jšœ*˜*Jš žœžœžœ&žœžœ ˜TJ˜J˜.šžœžœž˜š œžœžœžœžœ ˜MJ˜"J˜.J˜-J˜0J˜0Jšžœ˜—š œžœžœžœžœ ˜KJ˜.J˜0J˜-J˜-Jšžœ˜—š œžœžœžœžœ ˜JJ˜-J˜0J˜-J˜-Jšžœ˜—š œžœžœžœžœ ˜LJ˜-J˜-J˜-J˜-Jšžœ˜——Jšžœžœ˜šžœ T˜Zšžœ7žœžœž˜Jšžœ3˜5Jšœ1ž˜3Jšœ+ž˜-Jšœ)žœžœ˜3—Jšœ"™"Jšœ -˜?—Jšžœ˜—Jšžœ˜Jšœ  ˜ J˜J˜—šŸ œžœžœ.˜FJšœg™gJ˜J˜%Jšžœžœžœžœ˜J˜%J˜%J˜0Jšœ1  ˜J˜Jšžœ˜—š œžœžœžœžœ ˜?J˜3J˜(Jšžœ˜—š œžœžœžœžœ ˜>J˜3J˜'Jšžœ˜—š œžœžœžœžœ ˜=J˜(J˜(Jšžœ˜——Jšžœžœ˜Jšœ™šžœ <˜Bšžœ7žœžœž˜Jšžœ2˜4Jšœ!žœžœ˜+—Jšžœžœ˜7Jšžœžœ˜7—Jšžœ˜—Jšžœ˜Jšœ™Jšœ  ˜J˜J˜—J˜%J˜šŸ œžœžœ@˜ZJ˜.JšœN˜NJšœBžœ˜FJšœ*˜*Jšœ#˜#—J˜šŸ œžœžœ+žœ˜eJ˜.JšœL˜LJšœBžœ˜FJšœ+˜+Jšœ)˜)Jšœ˜—J™šŸ œžœžœžœžœžœžœ˜QJšœΜ™ΜJšœ žœž œžœ˜8Jšœ ˜ Jšœžœžœ ˜J˜.Jšžœžœžœ ž˜*šžœ˜Jšœžœžœ ˜'š žœžœžœžœ ž˜,šœ žœ˜šžœ4ž˜:J˜3—šž˜JšœEžœ˜K——Jšœ7™7Jšžœžœžœ˜