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
DBIndexScanImpl:
CEDAR
PROGRAM
IMPORTS
DBIndexFilePage, DBSegment
EXPORTS
DBStorage,
DBIndexScan
= BEGIN OPEN DBIndexFilePage;
Types
IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject;
IndexScanHandle: TYPE = REF IndexScanObject;
global vars
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;
now PriorityScanList points to a free object.
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] =
Maintains the LIFO queue
BEGIN
temp: IndexScanHandle;
s.free ← TRUE;
IF s.front = s THEN RETURN;
remove it from the list
s.front.back ← s.back;
s.back.front ← s.front;
put it in front of PriorityScanList
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.
If there is a IndexScanHandle, change values.
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] =
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
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.
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