-- File: DBIndex.mesa -- 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 DIRECTORY DBCommon, DBCache, DBStorage, DBStorageInternal, DBStoragePagetags; DBIndex: 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: DBCache.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 = MACHINE DEPENDENT RECORD [ text: PACKED SEQUENCE length: CARDINAL OF CHAR]; Page: TYPE = REF PageObject; PageObject: TYPE = RECORD [ tree: RealIndexHandle, db: DBCommon.DBPage, cache: DBCache.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]; -- 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. ItemHandle: TYPE = LONG POINTER TO Item; Item: TYPE = MACHINE DEPENDENT RECORD [ value: LONG CARDINAL, length: CARDINAL, text: PACKED ARRAY [0..0) OF CHARACTER]; -- Item is the internal object representing pair. -- Constants OverHead: CARDINAL = 6; FullPage: CARDINAL = DBCommon.WordsPerPage; HalfPage: CARDINAL = FullPage/2 - 2; CoreIndexSize: CARDINAL = FullPage - OverHead; -- Initialization and finalization procs: here because they don't fit anywhere else InitializeIndex: PROCEDURE; -- RESULTS: initializes the internal structure of dbindeximpl. -- NOTE: This procedure should be called from DBStorage.Initialize. CallAfterFinishTransaction: PROC; END.--DBIndex CHANGE LOG Created by Suzuki on May 8, 1980 3:49 PM -- Created for use by DBStorage. They should be called by CreateDatabase, OpenDatabase, and CloseDatabase. Re-created by Cattell on September 21, 1982 9:09 pm -- Moved DBIndexInternal into here: its former log follows: 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 -- Eliminated Finalize, added CallAfterFinishTransaction. Changed by MBrown on September 15, 1983 12:46 pm -- Conversion to 5.0. IndexKeys may contains REFs to allocated storage, or pointers.