DIRECTORY DBCommon, DBStorage, DBStoragePage; DBIndex: CEDAR DEFINITIONS = BEGIN RealIndexHandle: TYPE = REF IndexObject; IndexObject: TYPE = RECORD [ tid: DBCommon.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: DBStoragePage.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; 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, May 23, 1986 10:24:45 am PDT 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 pair. Constants 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 Κ1˜šœ™Jšœ Οmœ1™<—JšœR™Ršœ™Jšœ™Jšœ%™%šœ"™"J™-J™'—Icode™%J˜—šΟk ˜ 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šœŸ˜.J˜Jšœžœ˜Jšœžœžœžœ˜-J˜—Jšœ·™·J˜Jš œ žœžœžœžœ˜(J˜š œžœžœž œžœ˜'Jšœžœžœ˜Jšœžœ˜Jš œžœžœžœž œ˜(J˜—Jšœ:™:J˜—Jšœ ™ ˜Jšœ žœ˜J˜Jšœ žœ˜+Jšœ žœ˜$J˜Jšœžœ˜.—˜JšΟnœžœ˜7J˜—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˜—…—P©