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] = 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 @File: 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 Types global vars 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 ˜ J˜ J˜ J˜Jšœžœ2˜GJ˜J˜ Jšœ žœ-˜