DIRECTORY DBCommon USING[DBPage, Segment, TID], DBIndex USING [Core, Page, RealIndexHandle, ItemHandle, IndexKey], DBStorage USING[TupleHandle], Rope USING[ROPE]; DBIndexPage: CEDAR DEFINITIONS = BEGIN Page: TYPE = DBIndex.Page; IndexKey: TYPE = DBIndex.IndexKey; TupleTree: TYPE = REF TupleTreeRecord; TupleTreeRecord: TYPE = MACHINE DEPENDENT RECORD[ rootPA: DBCommon.DBPage, depth: CARDINAL, tid: DBCommon.TID, segment: DBCommon.DBPage, padding: ARRAY[0..13) OF CARDINAL_ ALL[0] ];--TupleTreeRecord BadPage: SIGNAL; -- if page is not a B-Tree page DestroyPageList: PROC [s: DBCommon.Segment]; DestroyPage: PROC [segment: DBCommon.DBPage, p: DBIndex.Page, db: DBCommon.DBPage]; UnlockPage: PROC [p: DBIndex.Page]; WritePage: PROC [p: DBIndex.Page]; WriteAndUnlockPage: PROC [p: DBIndex.Page]; CreateEmptyPage: PROC [tree: DBIndex.RealIndexHandle, level: CARDINAL, s: DBCommon.DBPage] RETURNS [DBIndex.Page]; GetPage: PROC [tree: DBIndex.RealIndexHandle, db: DBCommon.DBPage, level: CARDINAL] RETURNS [DBIndex.Page]; CheckTag: PROC[LONG POINTER TO DBIndex.Core]; SetSize: PROC [p: Page, i: CARDINAL]; FreeSpace: PROC [p: Page] RETURNS [CARDINAL]; FrontSize: PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL]; CoreAddr: PROC [p: Page, i: CARDINAL] RETURNS [DBIndex.ItemHandle]; EndAddr: PROC [p: Page] RETURNS [LONG POINTER]; SizeOfEntries: PROC [page: Page, from: CARDINAL, to: CARDINAL] RETURNS [CARDINAL]; Value: PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage]; Tid: PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.TID]; Key: PROC [page: Page, index: CARDINAL] RETURNS [IndexKey]; GreaterEq: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN]; LessEq: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN]; Less: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN]; Greater: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN]; FindTheFirstLeafKey: PROC [p: Page, key: REF TEXT] RETURNS [CARDINAL]; FindTheLastLeafKey: PROC [p: Page, key: REF TEXT] RETURNS [CARDINAL]; FindTheFirstInternalKey: PROC [page: Page, key: REF TEXT] RETURNS [CARDINAL] = INLINE BEGIN RETURN[FindTheInternalKey[page, key, Greater, LessEq]]; END; FindTheLastInternalKey: PROC [page: Page, key: REF TEXT] RETURNS [CARDINAL] = INLINE BEGIN RETURN[FindTheInternalKey[page, key, GreaterEq, Less]]; END; FindTheInternalKey: PROC [page: Page, key: REF TEXT, Upper, Lower: PROC [Rope.ROPE, IndexKey] RETURNS [BOOLEAN]] RETURNS [CARDINAL]; JustOver: PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL]; ReadIndexObject: PUBLIC PROC[t: DBStorage.TupleHandle, result: TupleTree]; WriteIndexObject: PUBLIC PROC[t: DBStorage.TupleHandle, val: TupleTree]; END. Change Log By Cattell September 22, 1982 12:57 pm: Changed names to be clearer. Use UnlockPage instead of FreePage, GetPage instead of CreateOldPage, etc. Changed by Willie-Sue on February 15, 1985 ÆFile: DBIndexPage.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Willie-Sue, February 15, 1985 3:41:24 pm PST Widom, September 4, 1985 9:07:35 pm PDT Donahue, May 22, 1986 11:35:20 am PDT Last edited by: Suzuki: 2-Apr-81 16:09:21 Cattell: September 21, 1982 9:23 pm This is the part of BTree that is permanently stored in the database. B-Tree root page address B-Tree depth TID of tuple that holds permanent copy of this object Segment containing this B-Tree (source of pages) SIZE must exactly equal DBStorage.IndexObjectSize now that copy REFs in/out of a db Managing the BTree page cache Frees the list of page records (DBIndex.Pages) that DBIndexPage maintains Unlock the page and de-allocate the page in the database for re-use. Should be called when the client no longer has pointers into page and p thrown away Mark page p as having been modified, but keep locked. Call when page no longer in use, and page has been modified. Allocates a new DBCommon.DBPage with associated DBIndex.Page, level = 1 if it is a leaf Makes DBIndex.Page pointing to given DBCommon.DBPage. Changes the state of Btree page Query the state of Btree page Returns the number 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 index-th entry Key comparison functions. Returns TRUE iff left>=right Returns TRUE iff leftJšœ?™?J˜—š œžœžœžœ˜CJšœ&™&J˜—š  œžœ žœžœžœ˜/Jšœ.™.J˜—š   œžœžœžœžœžœ˜RJšœ9™9Jšœ™——šœ™Jš œžœžœžœ˜AJ˜Jš  œžœžœžœ žœ˜