<> <> <> <> DIRECTORY Basics USING [Comparison], BTree USING [PathStk, Reason, Relation, State, Tree, UpdateType], BTreeVM USING [CacheSize, FilePagesPerPage], FS USING [OpenFile], Rope USING [ROPE, Text]; BTreeSimple: CEDAR DEFINITIONS = BEGIN <> <> Tree: TYPE = BTree.Tree; -- This represents the volatile state of an open BTree <> <> <> Key: TYPE = Rope.ROPE; InternalKey: TYPE = Rope.Text; -- The package always hands out this version of a Key. InternalKey is a bound variant of Key (see Rope package). Value: TYPE = REF ValueObject; ValueObject: TYPE = RECORD [words: SEQUENCE length: CARDINAL OF WORD]; <> EntryKey: TYPE = LONG POINTER TO EntryKeyObject; EntryKeyObject: TYPE = RECORD [text: PACKED SEQUENCE length: CARDINAL OF CHAR]; EntryValue: TYPE = LONG POINTER TO ValueObject; KeyFromEntry: UNSAFE PROCEDURE [entryKey: EntryKey] RETURNS [key: InternalKey]; <> ValueFromEntry: UNSAFE PROCEDURE [entryValue: EntryValue] RETURNS [value: Value]; <> <> Comparison: TYPE = Basics.Comparison; Compare: TYPE = UNSAFE PROCEDURE [key: InternalKey, entryKey: EntryKey] RETURNS [Comparison]; <> CompareEntries: TYPE = UNSAFE PROCEDURE [entryKey1, entryKey2: EntryKey] RETURNS [Comparison]; <> CompareProcs: TYPE = RECORD [ compare: Compare, compareEntries: CompareEntries]; defaultCompareProcs: CompareProcs; -- the default interpretation of a Key is as an ASCII text string with upper-case letters mapped to lower-case for the purpose of comparison (the same as Rope.Compare[..., case: TRUE]) <> <> <> <> State: TYPE = BTree.State; -- {closed, suspended, open} <> New: PROCEDURE [compareProcs: CompareProcs _ defaultCompareProcs, initialState: State[closed..suspended] _ closed] RETURNS [tree: Tree]; <> CacheSize: TYPE = BTreeVM.CacheSize; -- [8..255] FilePagesPerPage: TYPE = BTreeVM.FilePagesPerPage; -- [1..16] Open: PROCEDURE [tree: Tree, file: FS.OpenFile, filePagesPerPage: FilePagesPerPage _ 1, cacheSize: CacheSize _ 25, 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: INT, depth: CARDINAL, file: FS.OpenFile]; <> GetStatistics: PROCEDURE [tree: Tree] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL]; <> Validate: PROCEDURE [tree: Tree]; <> <> <> SetUpdateInProgress: PROCEDURE [tree: Tree, updateInProgress: BOOLEAN]; <> <> <> <> <> Relation: TYPE = BTree.Relation; -- {less, lessEqual, equal, greaterEqual, greater}; ReadRecord: PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [actualKey: InternalKey, value: Value]; <> <> <> <> ReadValue: PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [value: Value]; <> <> EnumerateRecords: PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROCEDURE [key: InternalKey, value: Value] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> UpdateType: TYPE = BTree.UpdateType; -- {insert, replace, insertOrReplace}; UpdateRecord: PROCEDURE [tree: Tree, key: Key, value: Value, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, 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 [key: EntryKey, value: EntryValue]]; <> <> <> <> <> EnumerateEntries: UNSAFE PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> UpdateEntry: UNSAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, valueLength: CARDINAL, Proc: UNSAFE PROCEDURE [value: EntryValue], updateType: UpdateType _ insertOrReplace]; <> <> <> SalvageEntries: UNSAFE PROCEDURE [tree: Tree, Proc: UNSAFE PROCEDURE [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> <> <> <> <> PathStk: TYPE = BTree.PathStk; NewPathStk: PROCEDURE RETURNS [pathStk: PathStk]; <> <> <> <> Reason: TYPE = BTree.Reason; -- { <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> END.