<> <> <> <> <> <> <> <> <> <> <> 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] = <<"r" was an empty tree, and just became to have one entry. "p" points to the first 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 <>