File: DBIndexHandleImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Created by: Suzuki, December 8, 1980 2:19 PM
Last edited by:
Suzuki, December 8, 1980 3:09 PM
MBrown, February 27, 1981 5:31 PM
Cattell, September 15, 1983 4:05 pm
Willie-Sue on February 18, 1985 1:19:53 pm PST
Donahue, November 13, 1985 8:12:51 am PST
DIRECTORY
DBCommon,
DBSegment,
DBStorage,
DBStorageInternal,
DBIndex,
DBIndexHandle,
IO;
DBIndexHandleImpl: CEDAR PROGRAM
IMPORTS
DBCommon,
DBSegment,
DBStorageInternal,
IO
EXPORTS
DBIndexHandle
= {
RealIndexHandle: TYPE = DBIndex.RealIndexHandle;
IndexObject: TYPE = DBIndex.IndexObject;
PriorityList: RealIndexHandle;
this points to a ring buffer of RealIndexHandle's. They form a LRU list, with PriorityList pointing to the most recently used Index and the next one is PriorityList.back, ...back. If what PriorityList points to is free, then everything on the ring buffer is free. If there is any free Index, PriorityList.fron points to a free Index.
FinalizeIndexHandle: PUBLIC PROC[s: DBCommon.Segment] =
BEGIN
i: RealIndexHandle;
segmentID: DBCommon.SegmentID = DBSegment.SegmentIDFromSegment[s];
FOR i ← PriorityList, i.back UNTIL i.back = PriorityList DO
IF i.free AND i.depth # 0 THEN ERROR;
IF NOT i.free THEN {
pageSegment: DBCommon.SegmentID = DBSegment.SegmentIDFromDBPage[i.segment];
IF pageSegment = segmentID THEN {
i.free ← TRUE; i.depth ← 0 } };
ENDLOOP;
END;
IndexHandle manipulation
CreateNewRealIndexHandle: PUBLIC PROC [tid: DBStorageInternal.TID] =
Creates a RealIndexHandle at the head of LRU queue, and set tid.
BEGIN
q: RealIndexHandle;
IF PriorityList.front.free THEN
BEGIN PriorityList ← PriorityList.front; GOTO Initialize END
ELSE
BEGIN
q ← NEW[IndexObject];
q.front ← PriorityList.front;
q.back ← PriorityList;
PriorityList.front.back ← q;
PriorityList.front ← q;
PriorityList ← q;
GOTO Initialize
END;
EXITS
Initialize => {
PriorityList^ ←
[tid, Segment[tid], DBCommon.NullDBPage, NIL, 0, PriorityList.front,
PriorityList.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 ← PriorityList;
tid: DBStorageInternal.TID ← DBStorageInternal.TIDOfTuple[x];
DO
IF q.free THEN GOTO NotFound;
IF q.tid = tid THEN {
put it at the front of PriorityList
IF q = PriorityList THEN GOTO Found;
q.front.back ← q.back;
q.back.front ← q.front;
q.front ← PriorityList.front;
PriorityList.front.back ← q;
PriorityList.front ← q;
q.back ← PriorityList;
PriorityList ← q;
GOTO Found};
q ← q.back;
IF q = PriorityList THEN GOTO NotFound;
REPEAT
Found => {RETURN[q]};
NotFound => {
ttr: DBStorageInternal.TupleTree← NEW[DBStorageInternal.TupleTreeRecord];
CreateNewRealIndexHandle[tid];
DBStorageInternal.ReadIndexObject[x, ttr];
PriorityList.rootDB ← ttr.rootPA;
PriorityList.depth ← ttr.depth;
RETURN[PriorityList]};
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 = PriorityList THEN PriorityList ← PriorityList.back
ELSE
BEGIN
q.front.back ← q.back;
q.back.front ← q.front;
q.front ← PriorityList.front;
q.back ← PriorityList;
q.front.back ← q;
PriorityList.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 = PriorityList THEN PriorityList ← PriorityList.back
ELSE
BEGIN
q.front.back ← q.back;
q.back.front ← q.front;
q.front ← PriorityList.front;
q.back ← PriorityList;
q.front.back ← q;
PriorityList.front ← q
END;
q.rootDB ← DBCommon.NullDBPage;
q.root ← NIL;
q.depth ← 0;
q.free ← TRUE;
END;
Segment: PROC [tid: DBStorageInternal.TID] RETURNS [DBCommon.DBPage] =
Returns the segment in which "tid" exists
BEGIN OPEN DBStorageInternal;
segment: DBCommon.DBPage;
tuple: DBStorage.TupleHandle ← MakeTupleHandle[tid, ];
segment ← SegmentIDOfTuple[tuple];
ReleaseTupleHandle[tuple];
RETURN[segment]
END;
PrintHandle: PROC = {
q: RealIndexHandle ← PriorityList;
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=PriorityList THEN EXIT;
ENDLOOP;
};
PriorityList ← NEW[IndexObject];
PriorityList.front ← PriorityList.back ← PriorityList;
PriorityList.free ← TRUE;
}.
CHANGE LOG
Changed by MBrown on December 15, 1980 10:15 AM
In FinalizeIndexHandle, set i.free ← TRUE in loop.
Changed by MBrown on February 27, 1981 5:34 PM
Allocate from zone. Use CWF instead of IODefs and StringDefs (!)
Changed by Cattell sometime in March 1981
Removed use of CWF.
Changed by Cattell on June 20, 1982 6:23 pm
Added some comments to procedures. Bad names for procs, should change the interface and recompile everything sometime.
Changed by Willie-Sue on June 25, 1982 9:19 am
IOStream => IO
Changed by Willie-Sue on June 30, 1982 4:50 pm
PrivateIO.DebugStream => DBCommon.GetDebugStream[]
Changed by Cattell on August 6, 1982 4:48 pm
POINTERs to REFs.
Changed by Cattell on September 21, 1982 9:20 pm
Re-organization of DBIndex level.
Changed by Willie-Sue on February 18, 1985
made Cedar, added tioga formatting