<> <> <> <> <> <> DIRECTORY Basics USING [Comparison], File USING [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--; <> <<>> <> <> <> Comparison: TYPE = Basics.Comparison; Compare: TYPE = UNSAFE PROCEDURE [key: Key, entry: Entry] RETURNS [Comparison]; <> CompareEntries: TYPE = UNSAFE PROCEDURE [entry1, entry2: Entry] RETURNS [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 = [0 .. 16*File.wordsPerPage]; -- actually [File.wordsPerPage .. ...], but the damned compiler uses an offset representation if I say that 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 ]; <> State: TYPE = {closed, suspended, open}; <> <<>> New: PROCEDURE [repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives, minEntrySize: CARDINAL _ 1, initialState: State[closed..suspended] _ closed] RETURNS [tree: Tree]; <> <<>> Open: PROCEDURE [tree: Tree, storage: PageStorage, pageSize: PageSize _ File.wordsPerPage, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE]; <> <> <<>> SetState: PROCEDURE [tree: Tree, state: State[closed..suspended]]; <> <<>> GetState: PROCEDURE [tree: Tree] RETURNS [state: State, entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL, storage: PageStorage]; <> <<>> Validate: PROCEDURE [tree: Tree]; <> <> <> <<>> SetUpdateInProgress: PROCEDURE [tree: Tree, updateInProgress: BOOLEAN]; <> <> <<>> <> <> <> <<>> Relation: TYPE = {less, lessEqual, equal, greaterEqual, greater}; ReadRecord: PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record]; <> <> <> <> <<>> EnumerateRecords: PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, 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: UNSAFE PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]]; <> <> <> <> <> <<>> EnumerateEntries: UNSAFE PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, 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]; <> <> <> <> <> <<>> SalvageEntries: UNSAFE PROCEDURE [tree: Tree, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> <> <<>> <> <> <> <<>> PathStk: TYPE = REF PathStkObject; PathStkObject: TYPE; NewPathStk: PROCEDURE RETURNS [pathStk: PathStk]; <> <<>> <> Error: ERROR [reason: Reason]; Reason: TYPE = {badSeal, closed, depthExceeded, entriesOutOfOrder, entrySizesWrong, nilPathStk, other, wrongEntryProduced, wrongPageSize, wrongUpdateType}; UpdateInProgress: SIGNAL; <> <> <> <> <> <> <> <> END.