DIRECTORYDBCommon,DBStorage,DBStorageInternal,DBStoragePagetags;DBIndex: CEDAR DEFINITIONS = BEGINRealIndexHandle: TYPE = REF IndexObject;IndexObject: TYPE = RECORD [tid: DBStorageInternal.TID,segment: DBCommon.DBPage, -- segment in which the index livesrootDB: DBCommon.DBPage, -- NullDBPage iff the index is emptyroot: DBCommon.CacheHandle, -- always a hintdepth: CARDINAL, -- 0 if the index is emptyfront, back: RealIndexHandle, -- for doubly linkded listsfree: BOOLEAN -- TRUE iff it does not point to real index];IndexKey: TYPE = LONG POINTER TO KeyBody;KeyBody: TYPE = DBCommon.KeyBody;Page: TYPE = REF PageObject;PageObject: TYPE = RECORD [tree: RealIndexHandle,db: DBCommon.DBPage,cache: DBCommon.CacheHandle,depth: CARDINAL, -- depth = 1 for leaf, >1 for non-leaf (0 for empty tree)pointer: LONG POINTER TO Core, -- points to the cached pagefree: BOOLEAN, -- so that this page object may be re-usedfront: Page,back: Page];State: TYPE = {normal, split, merge, delete, deleteFromNextPage};Core: TYPE = MACHINE DEPENDENT RECORD [tag: DBStoragePagetags.PageHeader, -- =6 for Btreeleft, right: DBCommon.DBPage,size: CARDINAL,index: ARRAY [0..CoreIndexSize) OF CARDINAL];ItemHandle: TYPE = LONG POINTER TO Item;Item: TYPE = MACHINE DEPENDENT RECORD [value: LONG CARDINAL,length: CARDINAL,text: PACKED ARRAY [0..0) OF CHARACTER];OverHead: CARDINAL = 6;FullPage: CARDINAL = DBCommon.WordsPerPage;HalfPage: CARDINAL = FullPage/2 - 2;CoreIndexSize: CARDINAL = FullPage - OverHead;InitializeIndex: PROCEDURE;CallAfterFinishTransaction: PROC [s: DBCommon.Segment];END.--DBIndexCHANGE LOGCreated by Suzuki on May 8, 1980  3:49 PMRe-created by Cattell on September 21, 1982 9:09 pmChanged halfPage from FullPage/2 to FullPage/2 - 2 to try to fix some boundary threshold problems on when to split and merge pages.by Cattell: June 22, 1982 10:32 amChanged RealIndexHandle and Page to be REFs.by  Cattell: August 6, 1982 2:17 pmChanged by MBrown on December 2, 1982 2:35 pmChanged by MBrown on September 15, 1983 12:46 pmChanged by Willie-Sue on February 15, 1985Changed by Donahue on March 3, 1986 7:46:30 am PST  þ  File: DBIndex.mesaCopyright c 1985 by Xerox Corporation.  All rights reserved.Contents: Declarations of DBIndex level data types, and initialize/finalize procs.Last edited by:Suzuki on May 8, 1980 3:47 PMCattell on September 15, 1983 3:36 pmMBrown on December 2, 1982 2:37 pmWillie-Sue, February 15, 1985 11:22:43 am PSTWidom, September 4, 1985 8:59:35 pm PDTDonahue, March 3, 1986 12:45:39 pm PSTCore is the data structure of a Btree page.  The index array is further divided as follows: The front part of index is ARRAY[0..size) OF CARDINAL, whose elements are indices of this array.  They represent the start index of the i-th entry.  The end part of index is the entries, which are allocated from the end.  Each entry consists of two words of value and a Bstring.  However, for internal nodes, the 0-th entry consists of only value.Item is the internal object representing <key,value> pair.ConstantsInitialization and finalization procs: here because they don't fit anywhere elseRESULTS: initializes the internal structure of dbindeximpl.NOTE: This procedure should be called from DBStorage.Initialize.Created for use by DBStorage.  They should be called by CreateDatabase, OpenDatabase, and CloseDatabase.Moved DBIndexInternal into here: its former log follows:Eliminated Finalize, added CallAfterFinishTransaction.Conversion to 5.0.  IndexKeys may contains REFs to allocated storage, or pointers.made Cedar, added tioga formattingChanges to make Key Bodies visible through DBStorage interface Ê‡  ˜ šœ™Jšœ
Ïmœ1™<—JšœR™Ršœ™Jšœ™Jšœ%™%šœ"™"J™-J™'—Icode™&J˜ —šÏk	˜	J˜	J˜
J˜J˜J˜ —Jšœ	žœžœž˜"˜ Jšœžœžœ˜(J˜ šœžœžœ˜Jšœžœ˜JšœÏc#˜=JšœŸ$˜=JšœŸ˜,JšœžœŸ˜+JšœŸ˜9JšœžœŸ+˜9J˜J˜ —Jš	œ
žœžœžœžœ	˜)šœ	žœ˜!J˜ —Jšœžœžœ˜J˜ šœžœžœ˜J˜J˜Jšœ˜JšœžœŸ9˜JJšœ	žœžœžœŸ˜;JšœžœŸ*˜9J˜J˜J˜ —Jšœžœ6˜AJ˜ š	œžœžœž	œžœ˜'Jšœ#Ÿ˜2J˜Jšœžœ˜Jšœžœžœžœ˜-J˜ —JšœH™HJšœA™AJšœ:™:JšœD™DJšœ>™>JšœE™EJšœ-™-J˜ Jš	œžœžœžœžœ˜(J˜ š	œžœžœž	œžœ˜'Jšœžœžœ˜Jšœžœ˜Jš	œžœžœžœž	œ˜(J˜ —Jšœ:™:J˜ —Jšœ	™	˜ Jšœ
žœ˜J˜ Jšœ
žœ˜+Jšœ
žœ˜$J˜ Jšœžœ˜.—Ihead1šœP™P˜ šÏnœž	œ˜Jšœ;™;Jšœ@™@J˜ —Jš œžœ˜7J˜ J˜ —JšžœŸ	˜J˜ J˜ Jšžœž˜
J˜ Jšœ'ž˜)Jšœh™hJ˜ J˜3Jšœ8™8J˜ ˜ƒJ˜"J˜ —˜,J˜#J˜ —J˜-Jšœ6™6J˜ J˜0JšœR™RJ™ J˜*J™"J˜ J˜2J™>J˜ — …—    ’    