<> <> <> <> <<>> <> <<>> <> <<>> 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 PROC [entryKey: EntryKey] RETURNS [key: InternalKey]; <> <<>> ValueFromEntry: UNSAFE PROC [entryValue: EntryValue] RETURNS [value: Value]; <> <<>> <> <<>> Comparison: TYPE = Basics.Comparison; Compare: TYPE = UNSAFE PROC [key: InternalKey, entryKey: EntryKey] RETURNS [Comparison]; <> <<>> CompareEntries: TYPE = UNSAFE PROC [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: PROC [compareProcs: CompareProcs _ defaultCompareProcs, initialState: State[closed..suspended] _ closed] RETURNS [tree: Tree]; <> <<>> CacheSize: TYPE = BTreeVM.CacheSize; -- [8..255] FilePagesPerPage: TYPE = BTreeVM.FilePagesPerPage; -- [1..16] Open: PROC [tree: Tree, file: FS.OpenFile, filePagesPerPage: FilePagesPerPage _ 1, cacheSize: CacheSize _ 25, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE]; <> <> <> <<>> SetState: PROC [tree: Tree, state: State[closed..suspended]]; <> <<>> GetState: PROC [tree: Tree] RETURNS [state: State, entryCount: LONG CARDINAL, greatestPage: INT, depth: CARDINAL, file: FS.OpenFile]; <> <<>> GetStatistics: PROC [tree: Tree] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL]; <> <<>> Validate: PROC [tree: Tree]; <> <> <> <<>> SetUpdateInProgress: PROC [tree: Tree, updateInProgress: BOOLEAN]; <> <> <<>> <> <> <<>> <> <<>> Relation: TYPE = BTree.Relation; -- {less, lessEqual, equal, greaterEqual, greater}; ReadRecord: PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [actualKey: InternalKey, value: Value]; <> <> <> <> <<>> ReadValue: PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [value: Value]; <> <> <<>> EnumerateRecords: PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROC [key: InternalKey, value: Value] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> <<>> UpdateType: TYPE = BTree.UpdateType; -- {insert, replace, insertOrReplace}; UpdateRecord: PROC [tree: Tree, key: Key, value: Value, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, updateType: UpdateType _ insertOrReplace]; <> <> <> <<>> DeleteKey: PROC [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [found: BOOLEAN]; <> <> <<>> <> <> <<>> ReadEntry: UNSAFE PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue]]; <> <> <> <> <> <<>> EnumerateEntries: UNSAFE PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> <<>> UpdateEntry: UNSAFE PROC [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, valueLength: CARDINAL, Proc: UNSAFE PROC [value: EntryValue], updateType: UpdateType _ insertOrReplace]; <> <> <> <<>> SalvageEntries: UNSAFE PROC [tree: Tree, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN]; <> <> <> <> <<>> <> <> <<>> <> <<>> PathStk: TYPE = BTree.PathStk; NewPathStk: PROC RETURNS [pathStk: PathStk]; <> <> <> <> Reason: TYPE = BTree.Reason; -- { <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> END.