<> <> <> <> <> <> <> <> <> <> DIRECTORY DBCommon, DBStorage, DBStorageConcrete, DBIndexFilePage USING[CreateIndexKey, FreeKey, GreaterEq, Key, LessEq], DBIndex, DBIndexScan, DBSegment USING [SegmentIDFromDBPage, SegmentIDFromSegment]; DBIndexScanImpl: CEDAR PROGRAM IMPORTS DBIndexFilePage, DBSegment EXPORTS DBStorage, DBIndexScan = BEGIN OPEN DBIndexFilePage; <> IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject; IndexScanHandle: TYPE = REF IndexScanObject; <> PriorityScanList: IndexScanHandle; 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 FreeKey[y.lowerBound]; FreeKey[y.upperBound]; 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 { FreeKey[s.lowerBound]; FreeKey[s.upperBound]; 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: CreateIndexKey[y.lowerBound], upperBound: CreateIndexKey[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; 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 DBIndexFilePageImpl.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 <>