-- File: DBIndexScanImpl.mesa
-- 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

  DIRECTORY
    DBCommon,
    DBStorage,
    DBStorageConcrete,
    DBIndexFilePage USING[CreateIndexKey, FreeKey, GreaterEq, Key, LessEq],
    DBIndex,
    DBIndexScan;

DBIndexScanImpl: PROGRAM
  IMPORTS
    DBIndexFilePage
  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 ← 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 =
    BEGIN
    s: IndexScanHandle;
    FreeOne: PROC =
      BEGIN
      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];
    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.


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