<> <> DIRECTORY Environment USING [Comparison, wordsPerPage]; BTree: CEDAR DEFINITIONS = BEGIN <<>> <> <<>> <> <> Tree: TYPE = REF TreeObject; TreeObject: TYPE; -- This represents the volatile state of an open BTree Entry: TYPE = LONG POINTER --TO READONLY EntryObject--; <> Record: TYPE = REF ANY --RecordObject--; <> Key: TYPE = REF ANY --KeyObject--; <> <<>> <> <> <> Compare: TYPE = UNSAFE PROCEDURE [key: Key, entry: Entry] RETURNS [Environment.Comparison]; <> CompareEntries: TYPE = UNSAFE PROCEDURE [entry1, entry2: Entry] RETURNS [Environment.Comparison]; <> EntSize: TYPE = [0..LAST[PageSize]]; EntrySize: TYPE = UNSAFE PROCEDURE [entry: Entry] RETURNS [words: EntSize]; <> <> reservedWordsPerPage: CARDINAL = 3; EntryFromRecord: TYPE = UNSAFE PROCEDURE [record: Record] RETURNS [entry: Entry]; <> NewRecordFromEntry: TYPE = UNSAFE PROCEDURE [entry: Entry] RETURNS [record: Record]; <> RepresentationPrimitives: TYPE = RECORD [ compare: Compare, compareEntries: CompareEntries, entrySize: EntrySize, entryFromRecord: EntryFromRecord, newRecordFromEntry: NewRecordFromEntry]; <<>> <<>> <> <<>> <> <> <> <> <> <> PageStorage: TYPE = REF ANY --PageStorageObject--; <> PageNumber: TYPE = CARDINAL; statePage: PageNumber = 0; <> PageSize: TYPE = [Environment.wordsPerPage .. 16*Environment.wordsPerPage]; PagePtr: TYPE = LONG POINTER --TO ARRAY [0..pageSize) OF WORD--; ReferenceType: TYPE = {read, write, new}; UpdateState: TYPE = {startOfUpdate, endOfUpdate, unchanged}; <<>> <> ReferencePage: TYPE = UNSAFE PROCEDURE [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr]; <> <> ReleasePage: TYPE = UNSAFE PROCEDURE [storage: PageStorage, number: PageNumber, update: UpdateState _ unchanged]; <> PageStoragePrimitives: TYPE = RECORD [ referencePage: ReferencePage, releasePage: ReleasePage]; <<>> <<>> <> Open: PROCEDURE [repPrim: RepresentationPrimitives, storage: PageStorage, storPrim: PageStoragePrimitives, pageSize: PageSize _ Environment.wordsPerPage, minEntrySize: CARDINAL _ 1, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE] RETURNS [tree: Tree]; <> <> <> ReOpen: PROCEDURE [tree: Tree]; <> Validate: PROCEDURE [tree: Tree]; <> <> GetState: PROCEDURE [tree: Tree] RETURNS [entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL, storage: PageStorage]; <> SetUpdateInProgress: PROCEDURE [tree: Tree, updateInProgress: BOOLEAN]; <> <<>> <<>> <> <<>> <> <> ReadRecord, ReadRecordL, ReadRecordLE, ReadRecordGE, ReadRecordG: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record]; <> <> <> <> EnumerateRecords: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROCEDURE [record: Record] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> UpdateType: TYPE = {insert, replace, insertOrReplace}; UpdateRecord: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, record: Record, updateType: UpdateType _ insertOrReplace]; <> <> <> <> DeleteKey: PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [found: BOOLEAN]; <> <> <<>> <<>> <> <<>> <> ReadEntry, ReadEntryL, ReadEntryLE, ReadEntryGE, ReadEntryG: UNSAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]]; <> <> <> <> <> EnumerateEntries: UNSAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> UpdateEntry: UNSAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, words: EntSize, Proc: UNSAFE PROCEDURE [entry: Entry], updateType: UpdateType _ insertOrReplace]; <> <> <> <> <> <<>> <<>> <> <<>> <> <> PathStk: TYPE = REF PathStkObject; PathStkObject: TYPE; NewPathStk: PROCEDURE RETURNS [pathStk: PathStk]; <> <<>> <<>> <> Error: ERROR [reason: Reason]; Reason: TYPE = {badSeal, depthExceeded, entriesOutOfOrder, entrySizesWrong, nilPathStk, other, wrongEntryProduced, wrongPageSize, wrongUpdateType}; UpdateInProgress: SIGNAL; <<>> <<>> <> <<>> <> <> <> <> <> <> <> END.