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] = 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] = 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; 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 "File: DBIndexPageImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Last edited by: Suzuki: December 16, 1980 5:15 PM MBrown: May 23, 1983 10:58 am Cattell: September 21, 1982 9:27 pm Willie-Sue, February 18, 1985 1:43:21 pm PST Widom, September 4, 1985 9:41:49 pm PDT Donahue, July 10, 1986 5:19:45 pm PDT global vars Public procs Deallocates the Page and DBPage; it should have a lock count of 1 Mark page p as having been written, but keep locked. Just allocates the DBIndex.Page, i.e. the HANDLE for the DBCommon.Page. Returns a "free" page; caller is responsible for marking it not free. level = 1 if it is a leaf Changes the state of Btree page Query the state of Btree page Returns the number of free words available Returns the size(in words) that entries from 0 to index occupy. Returns the address of i-th entry in p (Address of the word of the end of the page)+1 Returns the number of words, entries from "from" to "to" occupy in page Query the value of elements Returns the key of the index-th entry Assert: key.length should be valid length unless 0th entry on non-leaf page Key comparison functions. Returns TRUE iff left>=right Returns TRUE iff left˜EJšžœ ˜Jšœž˜J˜Jšœžœ˜Jšœžœ˜Jšœ žœ˜&Jšœžœ˜0Jšœ žœ˜&Jšœ žœ˜"Jšœ žœ˜ J˜Jšœžœ˜0Jšœ žœ˜&J˜Jšœ ™ J˜J˜J˜Jšœžœžœ˜J˜Jšœ žœžœžœ˜J˜JšœžœžœΟc˜5J˜Jšœ ™ J˜šΟnœžœžœ˜4Jšž˜J˜Jšœ>˜>J˜ šž˜šžœ-žœ˜5JšžœžœžœŸ˜0Jšœžœ žœžœŸ˜X—J˜ Jšžœ žœžœ˜Jšžœ˜—Jšžœ˜J˜—š  œžœžœ;˜SJšœA™AJšž˜J˜)Jšœ žœ˜Jšžœ˜J˜—š  œžœžœ ˜#šžœ˜J˜J˜ Jšœ žœ˜—Jšžœ˜J˜—š œžœžœ ˜+šžœ˜J˜J˜#J˜ Jšœ žœ˜—Jšžœ˜J˜—š  œžœžœ˜*Jšœ4™4šžœ˜J˜J˜#—Jšžœ˜J˜—š  œžœžœ ˜$Jšœ™Jšž˜J˜ J˜šžœ žœž˜J˜ Jšžœ žœžœ ˜#—šž˜šœžœ ˜%J˜Jš œžœžœžœžœ˜OJ˜Jšžœ˜ —Jšžœžœ˜—Jšžœ˜Jšžœ˜J˜—š œžœžœ žœ˜YJšžœ ž˜Jšœ™Jšž˜Jšœ˜J˜J˜Jšœžœžœžœ˜J˜(J˜$J˜'J˜ J˜J˜NJšœ žœ˜Jšžœ˜ Jšžœ˜J˜—š  œžœžœ5žœžœ ˜cJšžœž˜ J˜Jšœ˜Jšœ žœžœžœ˜J˜3J˜J˜TJšœ žœ˜Jšžœ˜ Jšžœ˜J˜—š œžœžœžœžœžœ žœ˜:Jšžœ#žœžœ ˜:—J™Jšœ™J˜š œžœžœžœ˜-Jšžœžœžœ˜%J˜—Jšœ™J˜š   œžœžœ žœžœ˜5Jšœ*™*Jšžœž˜ Jšœžœ˜*šœžœ˜Jšžœžœ˜&Jšžœ6˜:—Jšžœžœžœ˜!Jšžœ˜ Jšžœ˜J˜—š   œžœžœžœžœžœ˜FJšœ?™?Jšžœžœžœ)žœ˜AJ˜—š  œžœžœžœžœ˜CJšœ&™&Jšžœž˜ Jšœžœžœ˜&Jšœžœ ˜Jšžœžœžœ˜Jšžœžœ˜)Jšžœ˜J˜—š  œžœžœ žœžœžœ˜7Jšœ.™.Jšžœžœžœžœ˜/J˜—š   œžœžœžœžœ˜EJšžœžœ˜JšœG™GJšžœž˜ Jšœ žœ˜Jšžœ žœžœ˜J˜Jšœžœ žœžœ˜IJšžœ˜Jšžœ˜J˜—Jšœ™J˜š  œžœžœžœžœ˜IJšžœž˜ Jšžœžœ-˜Jšœžœžœ˜)—šžœ ž˜Jšžœ1žœ žœ ˜NJšœG™GJ˜Jšžœ˜—šžœžœ˜Jšžœ1žœ ˜@šžœžœžœ5˜SJšžœ ˜Jšžœ ˜——šžœžœžœ5žœ˜eJšžœ ˜—Jšžœ˜ Jšžœ˜J˜—š  œžœžœžœžœžœ˜RJšœW™WJšžœž˜ Jšœžœ˜!Jšœžœ˜Jšœžœ ˜Jšœžœ˜ J˜šžœ ž˜Jšžœ4žœ žœ ˜QJšœI™IJ˜Jšžœ˜—šžœžœ˜Jšžœ.žœ ˜=šžœžœžœ7˜OJšžœ ˜—Jšžœ ˜—šžœžœžœ6˜NJšžœ˜—Jšžœ ˜Jšžœ˜J˜—š œžœžœžœ  œžœžœ žœžœžœžœ˜‘Jšœ<™