<> <> <> <> <> <> <> <> <> DIRECTORY DBCommon, DBSegment USING[AllocPage, FreePage, ReadPage, SegmentIDFromDBPage, SegmentIDFromSegment, UnlockPage, WriteLockedPage], DBStorage, DBStorageField, DBStoragePage, DBIndex, DBIndexPage, RefText USING[TrustTextAsRope], Rope; DBIndexPageImpl: CEDAR PROGRAM IMPORTS DBCommon, DBSegment, DBStorage, DBStorageField, Rope, RefText EXPORTS DBIndexPage = BEGIN Core: TYPE = DBIndex.Core; Page: TYPE = DBIndex.Page; PageObject: TYPE = DBIndex.PageObject; RealIndexHandle: TYPE = DBIndex.RealIndexHandle; ItemHandle: TYPE = DBIndex.ItemHandle; IndexKey: TYPE = DBIndex.IndexKey; KeyBody: TYPE = DBIndex.KeyBody; CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize; FullPage: CARDINAL = DBIndex.FullPage; <> PageList: Page; TakeALookAtThis: SIGNAL = CODE; BadPage: PUBLIC SIGNAL = CODE; WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging <> DestroyPageList: PUBLIC PROC [s: DBCommon.Segment] = BEGIN p: Page; segID: DBCommon.SegmentID = DBSegment.SegmentIDFromSegment[s]; p _ PageList; DO IF DBSegment.SegmentIDFromDBPage[p.db] = segID THEN { IF NOT p.free THEN UnlockPage[p]; -- unlock page p.tree_ NIL; p.cache_ NIL; p.db_ 0; p.pointer_ NIL; p.depth_ 0 }; -- erase invalid data p _ p.front; IF p=PageList THEN EXIT; ENDLOOP; END; DestroyPage: PUBLIC PROC [segment: DBCommon.DBPage, p: Page, db: DBCommon.DBPage] = <> BEGIN DBSegment.FreePage[segment, db, p.cache]; p.free _ TRUE; END; UnlockPage: PUBLIC PROC [p: Page] = BEGIN CheckTag[p.pointer]; DBSegment.UnlockPage[p.cache]; p.free _ TRUE; END; WriteAndUnlockPage: PUBLIC PROC [p: Page] = BEGIN CheckTag[p.pointer]; DBSegment.WriteLockedPage[p.cache]; DBSegment.UnlockPage[p.cache]; p.free _ TRUE; END; WritePage: PUBLIC PROC [p: DBIndex.Page] = <> BEGIN CheckTag[p.pointer]; DBSegment.WriteLockedPage[p.cache]; END; AllocatePage: PROC RETURNS [Page] = <> BEGIN ret: Page; p: Page _ PageList; UNTIL p.free = TRUE DO p _ p.front; IF p=PageList THEN GOTO NoFreePage; REPEAT NoFreePage => {ret _ NEW[PageObject]; PageList.front.back _ ret; ret^ _ [NIL, DBCommon.NullDBPage, NIL, 0, NIL, TRUE, PageList.front, PageList]; PageList.front _ ret; RETURN[ret]}; FINISHED => {RETURN[p]} ENDLOOP; END; CreateEmptyPage: PUBLIC PROC [tree: RealIndexHandle, level: CARDINAL, s: DBCommon.DBPage] RETURNS [Page] = TRUSTED <> BEGIN cache: DBCommon.CacheHandle; db: DBCommon.DBPage; h: Page; p: LONG POINTER TO Core; [db, cache, p] _ DBSegment.AllocPage[s]; p.tag.pageTag _ DBStoragePage.BTree; p.left _ p.right _ DBCommon.NullDBPage; p.size _ 0; h _ AllocatePage[]; h.tree _ tree; h.db _ db; h.cache _ cache; h.depth _ level; h.pointer _ p; h.free _ FALSE; RETURN[h]; END; GetPage: PUBLIC PROC [tree: RealIndexHandle, db: DBCommon.DBPage, level: CARDINAL] RETURNS [Page] = TRUSTED BEGIN p: Page _ AllocatePage[]; cache: DBCommon.CacheHandle; pointer: LONG POINTER TO Core; [cache, pointer] _ DBSegment.ReadPage[db, p.cache]; CheckTag[pointer]; p.tree _ tree; p.db _ db; p.cache _ cache; p.depth _ level; p.pointer _ pointer; p.free _ FALSE; RETURN[p] END; CheckTag: PUBLIC PROC[p: LONG POINTER TO Core] = TRUSTED { IF p.tag.pageTag#DBStoragePage.BTree THEN SIGNAL BadPage}; <<>> <> SetSize: PUBLIC PROC [p: Page, i: CARDINAL] = TRUSTED BEGIN p.pointer.size _ i END; <> FreeSpace: PUBLIC PROC [p: Page] RETURNS [CARDINAL] = <> TRUSTED BEGIN indexArraySize: CARDINAL _ p.pointer.size; free: CARDINAL_ IF indexArraySize=0 THEN CoreIndexSize ELSE p.pointer.index[indexArraySize - 1] - indexArraySize; IF free>CoreIndexSize THEN ERROR; RETURN[free] END; FrontSize: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL] = <> TRUSTED BEGIN RETURN[CoreIndexSize - p.pointer.index[index]] END; CoreAddr: PUBLIC PROC [p: Page, i: CARDINAL] RETURNS [ItemHandle] = <> TRUSTED BEGIN base: LONG POINTER _ @p.pointer.index; index: CARDINAL _ (base+i)^; IF i>CoreIndexSize THEN ERROR; RETURN[LOOPHOLE[base+index, ItemHandle]]; END; EndAddr: PUBLIC PROC [p: Page] RETURNS [LONG POINTER] = <<(Address of the word of the end of the page)+1>> TRUSTED BEGIN RETURN[p.pointer + FullPage] END; SizeOfEntries: PUBLIC PROC [page: Page, from: CARDINAL, to: CARDINAL] RETURNS [CARDINAL] = <> TRUSTED BEGIN left, right: CARDINAL; IF to < from THEN RETURN[0]; left _ page.pointer.index[to]; right _ IF from = 0 THEN CoreIndexSize ELSE page.pointer.index[from - 1]; RETURN[right - left] END; <> Value: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage] = TRUSTED BEGIN RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.DBPage]]; END; Tid: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.TID] = TRUSTED BEGIN RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.TID]]; END; Key: PUBLIC PROC [page: Page, index: CARDINAL] RETURNS [IndexKey] = <> <> TRUSTED BEGIN base: LONG POINTER _ @page.pointer.index; offset: CARDINAL _ (base+index)^; key: IndexKey _ LOOPHOLE[base+offset+2, IndexKey]; IF key.length>CoreIndexSize AND (page.depth=1 OR index#0) THEN ERROR; RETURN[key] END; <> GreaterEq: PUBLIC PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN] = <=right>> TRUSTED BEGIN rightChar: CHAR; i: INT; FOR i IN [0..MIN[left.Size[], right.length]) DO rightChar _ right[i]; SELECT left.Fetch[i] FROM > rightChar => RETURN[TRUE]; < rightChar => RETURN[FALSE]; ENDCASE; ENDLOOP; IF left.Size[] >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE] END; LessEq: PUBLIC PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN] = <> TRUSTED BEGIN rightChar: CHAR; i: INT; FOR i IN [0..MIN[left.Size[], right.length]) DO rightChar _ right[i]; SELECT left.Fetch[i] FROM > rightChar => RETURN[FALSE]; < rightChar => RETURN[TRUE]; ENDCASE; ENDLOOP; IF left.Size[] <= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE] END; Less: PUBLIC PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN] = BEGIN RETURN[NOT GreaterEq[left, right]] END; Greater: PUBLIC PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN] = BEGIN RETURN[NOT LessEq[left, right]] END; <> <> FindTheFirstLeafKey: PUBLIC PROC [p: Page, key: REF TEXT] RETURNS [ret:CARDINAL] = <> TRUSTED BEGIN m: CARDINAL; low: CARDINAL _ 0; high, sizePMinusOne: CARDINAL _ p.pointer.size-1; m _ (low + high)/2; IF p.pointer.size = 0 THEN -- ouch! try to push on anyway... {SIGNAL WhatDoYouThinkOfThis; RETURN[0]}; UNTIL m = low DO IF LessEq[RefText.TrustTextAsRope[key], Key[p, m]] THEN high _ m ELSE low _ m; <> m _ (low + high)/2; ENDLOOP; IF low=0 THEN IF LessEq[RefText.TrustTextAsRope[key], Key[p, 0]] THEN ret _ 0 ELSE IF high=sizePMinusOne AND Greater[RefText.TrustTextAsRope[key], Key[p, high]] THEN ret _ high+1 ELSE ret _ high ELSE IF high=sizePMinusOne AND Greater[RefText.TrustTextAsRope[key], Key[p, high]] THEN ret _ high+1 ELSE ret _ high; RETURN[ret] END; FindTheLastLeafKey: PUBLIC PROC [p: Page, key: REF TEXT] RETURNS [ret: CARDINAL] = <> TRUSTED BEGIN pSize: CARDINAL _ p.pointer.size; low: CARDINAL _ 0; high: CARDINAL _ pSize - 1; m: CARDINAL; m _ (low + high)/2; UNTIL m = low DO IF GreaterEq[RefText.TrustTextAsRope[key], Key[p, m]] THEN low _ m ELSE high _ m; <> m _ (low + high)/2; ENDLOOP; IF low=0 THEN IF Less[RefText.TrustTextAsRope[key], Key[p,0]] THEN ret _ 0 ELSE IF high=pSize-1 AND GreaterEq[RefText.TrustTextAsRope[key], Key[p, high]] THEN ret _ high+1 ELSE ret _ high ELSE IF high=pSize-1 AND GreaterEq[RefText.TrustTextAsRope[key], Key[p,high]] THEN ret _ high+1 ELSE ret _ high END; FindTheInternalKey: PUBLIC PROC [page: Page, key: REF TEXT, Upper, Lower: PROC [Rope.ROPE, IndexKey] RETURNS [BOOLEAN]] RETURNS [ret: CARDINAL] = <> <> TRUSTED BEGIN pageSize: CARDINAL _ page.pointer.size; max: CARDINAL _ pageSize - 1; min: CARDINAL _ 1; m: CARDINAL; IF min>max THEN RETURN[0]; DO m _ (max + min)/2; IF m = min THEN EXIT; IF Upper[RefText.TrustTextAsRope[key], Key[page, m]] THEN min _ m ELSE max _ m; <> <<(min=1 | Key[page, min](Upper)key)&(max=Size[page]-1|key(Lower)Key[page,max])>> ENDLOOP; IF min=1 THEN IF Lower[RefText.TrustTextAsRope[key], Key[page,min]] THEN ret _ 0 ELSE IF min#max AND max=pageSize - 1 AND Upper[RefText.TrustTextAsRope[key], Key[page,max]] THEN ret _ max ELSE ret _ min ELSE IF max=pageSize-1 AND Upper[RefText.TrustTextAsRope[key], Key[page,max]] THEN ret _ max ELSE ret _ min END; JustOver: PUBLIC PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL] = <> <> TRUSTED BEGIN i: CARDINAL; pSize: CARDINAL _ p.pointer.size; FOR i IN [0..pSize) DO IF p.pointer.index[i]+size < FullPage + (i + 1) THEN GOTO Over; REPEAT Over => RETURN[i]; FINISHED => RETURN[pSize - 1]; ENDLOOP; END; <> ReadIndexObject: PUBLIC PROC[t: DBStorage.TupleHandle, result: DBIndexPage.TupleTree] = { <> <> IF SIZE[DBIndexPage.TupleTreeRecord] > DBStorage.IndexObjectSize THEN ERROR DBCommon.InternalError; DBStorage.ReadNWord[t, DBStorageField.TuplesetFieldHandle[], result]; };--ReadIndexObject WriteIndexObject: PUBLIC PROC[t: DBStorage.TupleHandle, val: DBIndexPage.TupleTree] = { <> <> IF SIZE[DBIndexPage.TupleTreeRecord] # DBStorage.IndexObjectSize THEN ERROR DBCommon.InternalError; DBStorage.WriteNWord[t, DBStorageField.TuplesetFieldHandle[], val]; };--WriteIndexObject <

> PageList _ NEW[PageObject]; PageList.front _ PageList.back _ PageList; PageList.free _ TRUE; END. Change Log: Added to check page tag in CreateOldPage by Suzuki November 24, 1980 9:06 AM Changed FreePage. Now Unlocks the page by Suzuki November 24, 1980 1:33 PM Changed AllocatePage. Now initializes the page if it was obtained via AllocateHeapNode by MBrown December 13, 1980 12:41 AM Allocate storage from heap storage mdsZone by MBrown February 27, 1981 6:18 PM Convert to Cedar by Cattell 7-Jun-81 11:24:59 Fixed bug in DestroyPageList: it didn't deallocate the PageObjects, and later code was trying to treat the cache hints to non-existent storage as real! by Cattell June 24, 1982 11:18 am Changed PageObjects from POINTERs to REFs. by Cattell August 6, 1982 5:10 pm Eliminated import of heap storage allocator. by MBrown August 7, 1982 9:38 pm Added BadPage signal. by Cattell August 25, 1982 5:21 pm The following invariant of the "page" data structure was getting messed up: NOT p.free iff DBSegment.LockCount[p.db, p.cache] > 0. The problem was that p.free was assigned FALSE, then a DBSegment call was made that can raise transaction aborted, then p.cache was assigned. Fix is to have AllocatePage return a page with p.free = TRUE, then make DBSegment call. by MBrown May 23, 1983 10:58 am Changed by Willie-Sue on February 18, 1985 <>