DIRECTORY DBCommon, DBSegment, DBStorage, DBStorageConcrete, DBStorageTuple, DBIndexPage, DBIndex, DBIndexScan, IO; DBIndexScanImpl: CEDAR PROGRAM IMPORTS DBCommon, DBIndexPage, DBSegment, DBStorageTuple, IO EXPORTS DBStorage, DBIndexScan = BEGIN OPEN DBIndexPage; IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject; IndexScanHandle: TYPE = REF IndexScanObject; RealIndexHandle: TYPE = DBIndex.RealIndexHandle; IndexObject: TYPE = DBIndex.IndexObject; PriorityScanList: IndexScanHandle; PriorityHandleList: RealIndexHandle; FinalizeIndexHandle: PUBLIC PROC [s: DBCommon.Segment] = BEGIN i: RealIndexHandle; FOR i _ PriorityHandleList, i.back UNTIL i.back = PriorityHandleList DO IF DBSegment.SegmentFromTID[i.tid] = s THEN { IF i.free AND i.depth # 0 THEN ERROR; i.free _ TRUE; i.depth _ 0 }; ENDLOOP; END; CreateNewRealIndexHandle: PUBLIC PROC [tid: DBCommon.TID] = BEGIN q: RealIndexHandle; IF PriorityHandleList.front.free THEN BEGIN PriorityHandleList _ PriorityHandleList.front; GOTO Initialize END ELSE BEGIN q _ NEW[IndexObject]; q.front _ PriorityHandleList.front; q.back _ PriorityHandleList; PriorityHandleList.front.back _ q; PriorityHandleList.front _ q; PriorityHandleList _ q; GOTO Initialize END; EXITS Initialize => { PriorityHandleList^ _ [tid, Segment[tid], DBCommon.NullDBPage, NIL, 0, PriorityHandleList.front, PriorityHandleList.back, FALSE]}; END; GetOldRealIndexHandle: PUBLIC PROC [x: DBStorage.IndexHandle] RETURNS [RealIndexHandle] = BEGIN q: RealIndexHandle _ PriorityHandleList; tid: DBCommon.TID _ DBStorageTuple.TIDOfTuple[x]; DO IF q.free THEN GOTO NotFound; IF q.tid = tid THEN { IF q = PriorityHandleList THEN GOTO Found; q.front.back _ q.back; q.back.front _ q.front; q.front _ PriorityHandleList.front; PriorityHandleList.front.back _ q; PriorityHandleList.front _ q; q.back _ PriorityHandleList; PriorityHandleList _ q; GOTO Found}; q _ q.back; IF q = PriorityHandleList THEN GOTO NotFound; REPEAT Found => {RETURN[q]}; NotFound => { ttr: DBIndexPage.TupleTree _ NEW[DBIndexPage.TupleTreeRecord]; CreateNewRealIndexHandle[tid]; DBIndexPage.ReadIndexObject[x, ttr]; PriorityHandleList.rootDB _ ttr.rootPA; PriorityHandleList.depth _ ttr.depth; RETURN[PriorityHandleList]}; ENDLOOP; END; DestroyIndexHandle: PUBLIC PROC [q: RealIndexHandle] = BEGIN IF q.front = q THEN -- there is only on item NULL ELSE IF q = PriorityHandleList THEN PriorityHandleList _ PriorityHandleList.back ELSE BEGIN q.front.back _ q.back; q.back.front _ q.front; q.front _ PriorityHandleList.front; q.back _ PriorityHandleList; q.front.back _ q; PriorityHandleList.front _ q END; q.free _ TRUE; END; DeleteHandle: PUBLIC PROC [q: RealIndexHandle] = BEGIN IF q.front = q THEN -- there is only on item NULL ELSE IF q = PriorityHandleList THEN PriorityHandleList _ PriorityHandleList.back ELSE BEGIN q.front.back _ q.back; q.back.front _ q.front; q.front _ PriorityHandleList.front; q.back _ PriorityHandleList; q.front.back _ q; PriorityHandleList.front _ q END; q.rootDB _ DBCommon.NullDBPage; q.root _ NIL; q.depth _ 0; q.free _ TRUE; END; Segment: PROC [tid: DBCommon.TID] RETURNS [DBCommon.DBPage] = BEGIN page: DBCommon.DBPage = DBCommon.DecomposeTID[tid].page; RETURN[DBSegment.SegmentIDFromDBPage[page]] END; PrintHandle: PROC = { q: RealIndexHandle _ PriorityHandleList; DO DBCommon.GetDebugStream[].PutF["tid: %12bB, rootDB: %12bB, depth: %bB, %s*n", IO.card[q.tid], IO.card[q.rootDB], IO.card[q.depth], IO.rope[IF q.free THEN "free" ELSE "not free"]]; q _ q.back; IF q=PriorityHandleList THEN EXIT; ENDLOOP; }; CloseScanIndex: PUBLIC PROC [x: DBStorage.IndexScanHandle] = BEGIN y: IndexScanHandle; TRUSTED { y _ LOOPHOLE[x, IndexScanHandle] }; IF y.tree=NIL THEN RETURN; -- Already freed or transaction closed IF y.front = y THEN NULL ELSE IF y = PriorityScanList THEN PriorityScanList _ PriorityScanList.back ELSE { y.front.back _ y.back; y.back.front _ y.front; y.front _ PriorityScanList.front; y.back _ PriorityScanList; y.front.back _ y; PriorityScanList.front _ y}; y.free _ TRUE; END; InitScan: PUBLIC PROC = BEGIN PriorityScanList _ NEW[IndexScanObject]; PriorityScanList.front _ PriorityScanList.back _ PriorityScanList; PriorityScanList.free _ TRUE; END; FreeScan: PUBLIC PROC [seg: DBCommon.Segment] = BEGIN s: IndexScanHandle; segID: DBCommon.SegmentID _ DBSegment.SegmentIDFromSegment[seg]; FreeOne: PROC = BEGIN IF DBSegment.SegmentIDFromDBPage[s.this] = segID THEN { s.tree _ NIL; s.this_ DBCommon.NullDBPage; IF NOT s.free THEN { s.lowerBound_ NIL; s.upperBound_ NIL }; s.free_ TRUE }; END; FOR s _ PriorityScanList, s.back UNTIL s.back = PriorityScanList DO FreeOne[]; REPEAT FINISHED => FreeOne[]; ENDLOOP; END; CreateScanHandle: PUBLIC PROC [r: DBIndex.RealIndexHandle, y: DBStorage.Selection, start: DBStorage.FirstLast, page: DBCommon.DBPage, index: CARDINAL] RETURNS [DBStorage.IndexScanHandle] = BEGIN IF NOT PriorityScanList.front.free THEN { temp: IndexScanHandle _ NEW[IndexScanObject]; temp.front _ PriorityScanList.front; temp.back _ PriorityScanList; PriorityScanList.front.back _ temp; PriorityScanList.front _ temp; PriorityScanList _ temp} ELSE PriorityScanList _ PriorityScanList.front; PriorityScanList^ _ [front: PriorityScanList.front, back: PriorityScanList.back, tree: r, this: page, index: index, free: FALSE, start: start, lowerBound: y.lowerBound, upperBound: y.upperBound, includeLowerBound: y.includeLowerBound, includeUpperBound: y.includeUpperBound, lowerBoundInfinity: y.lowerBoundInfinity, upperBoundInfinity: y.upperBoundInfinity]; TRUSTED {RETURN[LOOPHOLE[PriorityScanList, DBStorage.IndexScanHandle]]}; END; FreeScanHandle: PUBLIC PROC [s: IndexScanHandle] = BEGIN temp: IndexScanHandle; s.free _ TRUE; IF s.front = s THEN RETURN; s.front.back _ s.back; s.back.front _ s.front; temp _ PriorityScanList.front; temp.back _ s; s.front _ temp; PriorityScanList.front _ s; s.back _ PriorityScanList; END; ManipulateScanIndex: PUBLIC PROC [ page: DBIndex.Page, after: CARDINAL, f: PROC [IndexScanHandle]] = BEGIN db: DBCommon.DBPage _ page.db; temp: IndexScanHandle _ PriorityScanList; UNTIL temp.free DO IF temp.this = db AND temp.index >= after THEN f[temp]; temp _ temp.back; IF temp = PriorityScanList THEN RETURN; ENDLOOP; END; PutScanIndex: PUBLIC PROC[r: DBIndex.RealIndexHandle, p: DBIndex.Page] = BEGIN temp: IndexScanHandle _ PriorityScanList; UNTIL temp.free DO IF temp.tree=r THEN { temp.this _ p.db; IF temp.start=First THEN IF temp.lowerBoundInfinity THEN temp.index _ 0 ELSE IF temp.includeLowerBound THEN IF LessEq[temp.lowerBound, Key[p,0]] THEN temp.index _ 0 ELSE temp.index _ 1 ELSE temp.index _ 1 ELSE IF temp.upperBoundInfinity THEN temp.index _ 1 ELSE IF temp.includeUpperBound THEN IF GreaterEq[temp.upperBound, Key[p,0]] THEN temp.index _ 1 ELSE temp.index _ 0 ELSE temp.index _ 0}; temp _ temp.back; IF temp=PriorityScanList THEN RETURN ENDLOOP; END; ScanForNullTree: PUBLIC PROC [q: DBIndex.RealIndexHandle] = BEGIN temp: IndexScanHandle _ PriorityScanList; UNTIL temp.free DO IF temp.tree=q THEN { temp.this _ DBCommon.NullDBPage; temp.index _ 0}; temp _ temp.back; IF temp=PriorityScanList THEN RETURN ENDLOOP; END; PriorityHandleList _ NEW[IndexObject]; PriorityHandleList.front _ PriorityHandleList.back _ PriorityHandleList; PriorityHandleList.free _ TRUE; END. Change Log Added PutScanIndex and ScanForNullTree Suzuki: November 24, 1980 11:01 AM Alloc storage from DBHeapStorage; use Inline; define FreeIndexKey MBrown: February 27, 1981 6:26 PM CopyIndexKey -> CreateIndexKey. Cattell: June 20, 1982 6:41 pm Removed FreeIndexKey defined by Mark above, we should call DBIndexPageImpl.FreeKey instead to centralize this. No longer need DBHeapStorage or Inline as a result. Cattell: August 19, 1982 7:39 pm Re-organization of DBIndex level Cattell: September 21, 1982 9:56 pm Changed by Willie-Sue on February 18, 1985 pFile: DBIndexScanImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Implements: DBIndexScan Created by: Suzuki, November 20, 1980 10:29 AM Last edited by: Suzuki, November 20, 1980 10:29 AM MBrown, February 27, 1981 9:41 PM Cattell, September 21, 1982 9:58 pm Willie-Sue, February 18, 1985 1:45:10 pm PST Widom, September 4, 1985 9:19:41 pm PDT Donahue, May 22, 1986 1:25:03 pm PDT Types global vars this points to a ring buffer of RealIndexHandle's. They form a LRU list, with PriorityHandleList pointing to the most recently used Index and the next one is PriorityHandleList.back, ...back. If what PriorityHandleList points to is free, then everything on the ring buffer is free. If there is any free Index, PriorityHandleList.front points to a free Index. IndexHandle manipulation Creates a RealIndexHandle at the head of LRU queue, and set tid. Returns the actual index handle out of the tuple level's tuple that represents it. put it at the front of PriorityHandleList Deallocates the IndexObject. The real one, not the tuple level's. Doesn't actually free any storage to system, just marks it free. Deallocates the IndexObject Returns the segment in which "tid" exists now PriorityScanList points to a free object. Maintains the LIFO queue remove it from the list put it in front of PriorityScanList "r" was an empty tree, and just became to have one entry. "p" points to the first page. If there is a IndexScanHandle, change values. The tree pointed to by q because empty. Change all the IndexRealHandle so that if they point to this index, their page fields are Null made Cedar, added tioga formatting Κ Š˜šœ™Icodešœ Οmœ1™<—Jšœ™Jšœ0™0Jšœ™Jšœ#™#Jšœ"™"šœ$™$K™,K™'K™$—˜šΟk ˜ J˜ J˜ J˜ J˜J˜Jšœ ˜ J˜Jšœ ˜ Jšœ˜J˜——šœžœž˜Jšžœ2ž˜J˜J˜$Jšœ(˜(Jšœ%˜%Jšžœ˜——Jšžœ˜—Jšžœ˜J˜—šŸœžœžœ˜6JšœB™BJšœA™AJšž˜šžœ žœΟc˜,Jšž˜—šž˜Jšžœžœ-˜Kšž˜Jšž˜J˜J˜Jšœ#˜#Jšœ˜J˜Jšœ˜Jšžœ˜——Jšœ žœ˜Jšžœ˜J˜—šŸ œžœžœ˜0Jšœ™Jšž˜šžœ žœ ˜,Jšž˜—šž˜Jšžœžœ-˜Kšž˜Jšž˜J˜J˜Jšœ#˜#Jšœ˜J˜Jšœ˜Jšžœ˜——J˜Jšœ žœ˜ J˜ Jšœ žœ˜Jšžœ˜J˜—š Ÿœžœžœžœž˜CJšœ)™)Jšœ8˜8Jšžœ%˜+Jšžœ˜J˜—šŸ œžœ˜Jšœ(˜(šž˜˜NJšžœžœžœžœžœžœžœ˜e—J˜ Jšžœžœžœ˜"—Jšžœ˜J˜J˜—šŸœžœžœ!˜