<<>> <> <> <> <> <> <> <> <> DIRECTORY Basics USING [Comparison]; BTree: CEDAR DEFINITIONS = BEGIN <> <> <> Tree: TYPE = REF TreeObject; TreeObject: TYPE; <> <<>> Entry: TYPE = POINTER --TO READONLY EntryObject--; <> <<>> Record: TYPE = REF ANY --RecordObject--; <> <<>> Key: TYPE = REF ANY --KeyObject--; <> <<>> <> <> <> <<>> Comparison: TYPE = Basics.Comparison; Compare: TYPE = UNSAFE PROC [key: Key, entry: Entry] RETURNS [Comparison]; <> <<>> CompareEntries: TYPE = UNSAFE PROC [entry1, entry2: Entry] RETURNS [Comparison]; <> <<>> EntSize: TYPE = PageSize; EntrySize: TYPE = UNSAFE PROC [entry: Entry] RETURNS [bytes: EntSize]; <> <> <<>> <> <<>> reservedWordsPerPage: CARD = 4 * SIZE[BYTE]; EntryFromRecord: TYPE = UNSAFE PROC [record: Record] RETURNS [entry: Entry]; <> <<>> NewRecordFromEntry: TYPE = UNSAFE PROC [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 = CARD; invalidPageNumber: PageNumber = PageNumber.LAST; statePage: PageNumber = 0; <> PageSize: TYPE = CARD [0..CARD.LAST/BITS[WORD]]; <> PagePtr: TYPE = POINTER; ReferenceType: TYPE = {read, write, new}; UpdateState: TYPE = {startOfUpdate, endOfUpdate, unchanged}; <<>> <> <<>> ReferencePage: TYPE = UNSAFE PROC [storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr ¬ NIL]; <> <> <<>> ReleasePage: TYPE = UNSAFE PROC [storage: PageStorage, number: PageNumber, update: UpdateState ¬ unchanged]; <> <<>> PageStoragePrimitives: TYPE = RECORD [ referencePage: ReferencePage, releasePage: ReleasePage ]; <> State: TYPE = {closed, suspended, open}; <> <<>> New: PROC [ repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives, minEntrySize: EntSize ¬ 1, initialState: State[closed..suspended] ¬ closed] RETURNS [tree: Tree]; <> <<>> Open: PROC [ tree: Tree, storage: PageStorage, pageSize: PageSize, initialize: BOOL ¬ FALSE, maintainRecomputableState: BOOL ¬ TRUE]; <> <> <<>> SetState: PROC [tree: Tree, state: State[closed..suspended]]; <> <<>> GetState: PROC [tree: Tree] RETURNS [ state: State, entryCount: CARD, greatestPage: PageNumber, depth: CARD, storage: PageStorage]; <> <<>> Validate: PROC [tree: Tree]; <> <> <> <<>> SetUpdateInProgress: PROC [tree: Tree, updateInProgress: BOOL]; <> <> <<>> <> <> <> <<>> Relation: TYPE = {less, lessEqual, equal, greaterEqual, greater}; ReadRecord: PROC [ tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE] RETURNS [record: Record]; <> <> <> <> <<>> EnumerateRecords: PROC [ tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, Proc: EnumerateProc] RETURNS [exhausted: BOOL]; <> <> <> <<>> EnumerateProc: TYPE = PROC [record: Record] RETURNS [continue: BOOL ¬ TRUE]; <<>> UpdateType: TYPE = {insert, replace, insertOrReplace}; UpdateRecord: PROC [ tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, record: Record, updateType: UpdateType ¬ insertOrReplace]; <> <> <> <> <<>> DeleteKey: PROC [ tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE] RETURNS [found: BOOL]; <> <> <<>> <> <> <<>> ReadEntry: UNSAFE PROC [ tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, Proc: EachEntryProc]; <> <> <> <> <> EachEntryProc: TYPE = UNSAFE PROC [entry: Entry]; <<>> EnumerateEntries: UNSAFE PROC [ tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, Proc: TestEntryProc] RETURNS [exhausted: BOOL]; <> <> <> TestEntryProc: TYPE = UNSAFE PROC [entry: Entry] RETURNS [continue: BOOL ¬ TRUE]; <<>> UpdateEntry: UNSAFE PROC [ tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, bytes: EntSize, Proc: EachEntryProc, updateType: UpdateType ¬ insertOrReplace]; <> <> <> <> <> <<>> SalvageEntries: UNSAFE PROC [tree: Tree, Proc: TestEntryProc] RETURNS [exhausted: BOOL]; <> <> <> <> <<>> <> <> <> <<>> PathStk: TYPE = REF PathStkObject; PathStkObject: TYPE; NewPathStk: PROC RETURNS [pathStk: PathStk]; <> <<>> <> Error: ERROR [reason: Reason]; Reason: TYPE = {badSeal, closed, depthExceeded, entriesOutOfOrder, entrySizesWrong, nilPathStk, other, wrongEntryProduced, wrongPageSize, wrongUpdateType}; UpdateInProgress: SIGNAL; <> <> <> <> <> <> <> <> END.