DBIndexScanImpl:
CEDAR
PROGRAM
IMPORTS DBCommon, DBIndexPage, DBSegment, DBStorageTuple, IO
EXPORTS DBStorage, DBIndexScan
= BEGIN OPEN DBIndexPage;
Types
IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject;
IndexScanHandle: TYPE = REF IndexScanObject;
RealIndexHandle: TYPE = DBIndex.RealIndexHandle;
IndexObject: TYPE = DBIndex.IndexObject;
global vars
PriorityScanList: IndexScanHandle;
PriorityHandleList: RealIndexHandle;
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.
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;
IndexHandle manipulation
CreateNewRealIndexHandle:
PUBLIC
PROC [tid: DBCommon.
TID] =
Creates a RealIndexHandle at the head of LRU queue, and set 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] =
Returns the actual index handle out of the tuple level's tuple that represents it.
BEGIN
q: RealIndexHandle ← PriorityHandleList;
tid: DBCommon.TID ← DBStorageTuple.TIDOfTuple[x];
DO
IF q.free THEN GOTO NotFound;
IF q.tid = tid
THEN {
put it at the front of PriorityHandleList
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] =
Deallocates the IndexObject. The real one, not the tuple level's.
Doesn't actually free any storage to system, just marks it free.
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] =
Deallocates the IndexObject
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
Returns the segment in which "tid" exists
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;
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: 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] =
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;
PriorityHandleList ← NEW[IndexObject];
PriorityHandleList.front ← PriorityHandleList.back ← PriorityHandleList;
PriorityHandleList.free ← TRUE;
END.