<<>> <> <> <> <> <> <> <> <> <<>> DIRECTORY Ascii USING [Lower], Basics USING [MoveWords], BTree USING [Compare, CompareEntries, DeleteKey, Entry, EntryFromRecord, EntrySize, EnumerateEntries, GetState, Key, New, NewPathStk, NewRecordFromEntry, Open, PageNumber, PagePtr, PageSize, PageStorage, PathStk, ReadEntry, ReferencePage, Relation, ReleasePage, SalvageEntries, SetState, SetUpdateInProgress, State, Tree, UpdateEntry, UpdateType, Validate], BTreeSimple, BTreeVM, IO USING [STREAM], Rope USING [Flatten, NewText]; BTreeSimpleImpl: CEDAR PROGRAM IMPORTS Ascii, Basics, BTree, BTreeVM, Rope EXPORTS BTreeSimple SHARES Rope = { OPEN BTreeSimple; <<>> <> KeyFromEntry: PUBLIC UNSAFE PROC [entryKey: EntryKey] RETURNS [key: InternalKey ¬ NIL] = UNCHECKED { IF entryKey # NIL THEN { <> key ¬ Rope.NewText[entryKey.length]; -- on Michael Plass's recommendation key.length ¬ entryKey.length; <> Basics.MoveWords[dst: LOOPHOLE[key, POINTER]+SIZE[TEXT[0]], src: LOOPHOLE[entryKey+SIZE[EntryKeyObject[0]]], count: WORDS[EntryKeyObject[entryKey.length]] - WORDS[EntryKeyObject[0]] ]; RETURN[key]; }; }; ValueFromEntry: PUBLIC UNSAFE PROC [entryValue: EntryValue] RETURNS [value: Value ¬ NIL] = UNCHECKED { IF entryValue # NIL THEN { value ¬ NEW[ValueObject[entryValue.length]]; Basics.MoveWords[dst: LOOPHOLE[value, POINTER]+SIZE[ValueObject[0]], src: LOOPHOLE[entryValue, POINTER]+SIZE[ValueObject[0]], count: entryValue.length]; -- entryValue.length is in words RETURN[value]; }; }; DefaultCompare: Compare --[key: InternalKey, entryKey: EntryKey] RETURNS [Comparison]-- = UNCHECKED { FOR i: CARDINAL IN [0 .. MIN[key.length, entryKey.length]) DO kc: CHAR ¬ Ascii.Lower[key[i]]; ec: CHAR ¬ Ascii.Lower[entryKey[i]]; IF kc # ec THEN { IF kc < ec THEN RETURN[less] ELSE RETURN[greater] }; ENDLOOP; IF key.length = entryKey.length THEN RETURN[equal] ELSE {IF key.length < entryKey.length THEN RETURN[less] ELSE RETURN[greater]; }; }; DefaultCompareEntries: CompareEntries --[entryKey1, entryKey2: EntryKey] RETURNS [Comparison]-- = UNCHECKED { FOR i: CARDINAL IN [0 .. MIN[entryKey1.length, entryKey2.length]) DO c1: CHAR ¬ Ascii.Lower[entryKey1[i]]; c2: CHAR ¬ Ascii.Lower[entryKey2[i]]; IF c1 # c2 THEN { IF c1> New: PUBLIC PROC [compareProcs: CompareProcs ¬ defaultCompareProcs, initialState: State[closed..suspended] ¬ closed] RETURNS [tree: Tree] = { RETURN[BTree.New[repPrim: [compare: LOOPHOLE[compareProcs.compare], compareEntries: LOOPHOLE[compareProcs.compareEntries], entrySize: EntrySize, entryFromRecord: EntryFromRecord, newRecordFromEntry: NewRecordFromEntry], storPrim: [referencePage: BTreeVM.ReferencePage, releasePage: BTreeVM.ReleasePage], minEntrySize: SIZE[EntryKeyObject[1]] + SIZE[ValueObject[0]], initialState: initialState]]; }; Open: PUBLIC PROC [tree: Tree, readFile, writeFile: IO.STREAM, pageSize: BTreeSimple.PageSize, cacheSize: CacheSize ¬ 40, offset: CARD ¬ 0, initialize: BOOLEAN ¬ FALSE, maintainRecomputableState: BOOLEAN ¬ TRUE] = { storage: BTreeVM.Ref; storage ¬ BTreeVM.Open[readBacking: readFile, writeBacking: writeFile, pageSize: pageSize, cacheSize: cacheSize, offset: offset]; tree.Open[storage: storage, pageSize: pageSize, initialize: initialize, maintainRecomputableState: maintainRecomputableState]; }; SetState: PUBLIC PROC [tree: Tree, state: State[closed..suspended]] = { tree.SetState[state]; }; GetState: PUBLIC PROC [tree: Tree] RETURNS [state: State, entryCount: CARD, greatestPage: BTree.PageNumber, depth: CARD] = { storage: BTree.PageStorage; [state: state, entryCount: entryCount, greatestPage: greatestPage, depth: depth, storage: storage] ¬ tree.GetState[]; <> <> < file _ handle.backing;>> < file _ NIL;>> }; GetStatistics: PUBLIC PROC [tree: Tree] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: CARD] = { stats: BTreeVM.Stats; h: BTreeVM.Ref; h ¬ NARROW[BTree.GetState[tree].storage]; stats ¬ BTreeVM.GetStats[h]; RETURN [stats.hits, stats.misses, stats.reads, stats.writes, stats.cumChainLength, stats.cumReadWriteTime]; }; Validate: PUBLIC PROC [tree: Tree] = { tree.Validate[]; }; SetUpdateInProgress: PUBLIC PROC [tree: Tree, updateInProgress: BOOLEAN] = { tree.SetUpdateInProgress[updateInProgress]; }; <> ReadRecord: PUBLIC PROC [tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE] RETURNS [actualKey: InternalKey, value: Value] = TRUSTED { EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] = UNCHECKED { IF key=NIL THEN {actualKey ¬ NIL; returnValue ¬ NIL} ELSE {actualKey ¬ KeyFromEntry[key]; returnValue ¬ ValueFromEntry[value]}; }; returnValue: Value; ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; RETURN [actualKey, returnValue]; }; ReadValue: PUBLIC PROC [tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE] RETURNS [value: Value] = TRUSTED { EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] = UNCHECKED { returnValue ¬ (IF value=NIL THEN NIL ELSE ValueFromEntry[value]); }; returnValue: Value; ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; RETURN [returnValue]; }; EnumerateRecords: PUBLIC 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] = TRUSTED { EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN] = UNCHECKED { RETURN [Proc[key: KeyFromEntry[key], value: ValueFromEntry[value]]] }; exhausted ¬ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; }; UpdateRecord: PUBLIC PROC [tree: Tree, key: Key, value: Value, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE, updateType: UpdateType ¬ insertOrReplace] = TRUSTED { ProduceEntry: UNSAFE PROC [value: EntryValue] = UNCHECKED { Basics.MoveWords[dst: LOOPHOLE[value], src: LOOPHOLE[suppliedValue], count: WORDS[ValueObject[suppliedValue.length]]]; }; suppliedValue: POINTER TO ValueObject = LOOPHOLE[value]; UpdateEntry[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, valueLength: suppliedValue.length, Proc: ProduceEntry, updateType: updateType]; }; DeleteKey: PUBLIC PROC [tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE] RETURNS [found: BOOLEAN] = { found ¬ tree.DeleteKey[key: key.Flatten[], pathStk: pathStk, useExistingPath: useExistingPath]; RETURN[found]; }; <> ReadEntry: PUBLIC UNSAFE PROC [tree: Tree, key: Key, relation: Relation ¬ equal, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue]] = UNCHECKED { EntryProc: UNSAFE PROC [entry: BTree.Entry] = UNCHECKED { IF entry=NIL THEN Proc[NIL, NIL] ELSE { entryKey: EntryKey = LOOPHOLE[entry, EntryKey]; entryKeySize: CARD ¬ SIZE[EntryKeyObject[entryKey.length]]; Proc[entry, entry + entryKeySize]; }; }; tree.ReadEntry[key: key.Flatten[], relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; }; EnumerateEntries: PUBLIC 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] = UNCHECKED { EntryProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOLEAN] = UNCHECKED { entryKey: EntryKey = LOOPHOLE[entry, EntryKey]; entryKeySize: CARD ¬ SIZE[EntryKeyObject[entryKey.length]]; RETURN[Proc[entry, entry + entryKeySize]]; }; exhausted ¬ tree.EnumerateEntries[key: key.Flatten[], relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; }; UpdateEntry: PUBLIC UNSAFE PROC [tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOLEAN ¬ FALSE, valueLength: CARD, Proc: UNSAFE PROC [value: EntryValue], updateType: UpdateType ¬ insertOrReplace] = UNCHECKED { EntryProc: UNSAFE PROC [entry: BTree.Entry] = UNCHECKED { entryKey: EntryKey; entryValue: EntryValue; entryKey ¬ LOOPHOLE[entry]; entryValue ¬ LOOPHOLE[entry+entryKeySize]; LOOPHOLE[entryKey, POINTER TO CARD]­ ¬ internalKey.length; <> Basics.MoveWords[dst: LOOPHOLE[entryKey+SIZE[EntryKeyObject[0]]], src: LOOPHOLE[internalKey, POINTER]+SIZE[TEXT[0]], count: WORDS[TEXT[internalKey.length]] - WORDS[TEXT[0]]]; << >> Proc[entryValue]; LOOPHOLE[entryValue, POINTER TO CARD]­ ¬ valueLength; -- entryValue.length ¬ valueLength }; <<--Body of UpdateEntry Procedure>> internalKey: InternalKey = key.Flatten[]; entryKeySize: CARD = SIZE[EntryKeyObject[internalKey.length]]; valueLengthSize: CARD = SIZE[ValueObject[valueLength]]; totalNumberOfBytes: CARD = entryKeySize + valueLengthSize; tree.UpdateEntry[key: internalKey, pathStk: pathStk, useExistingPath: useExistingPath, bytes: totalNumberOfBytes, Proc: EntryProc, updateType: updateType]; }; SalvageEntries: PUBLIC UNSAFE PROC [tree: Tree, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = UNCHECKED { EntryProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOLEAN] = UNCHECKED { RETURN[Proc[entry, entry+EntryKeyObject[LOOPHOLE[entry, EntryKey].length].SIZE]]}; exhausted ¬ tree.SalvageEntries[Proc: EntryProc]; }; <> NewPathStk: PUBLIC PROC RETURNS [pathStk: PathStk] = { RETURN[BTree.NewPathStk[]]; }; <> <> <<>> EntrySize: BTree.EntrySize --[entry: BTree.Entry] RETURNS [bytes: BTree.EntSize]-- = UNCHECKED { lengthOfEntryKey: CARD; lengthOfValueObject: CARD; entryKeySize: CARD; valueObjectSize: CARD; lengthOfEntryKey ¬ LOOPHOLE[entry, EntryKey].length; entryKeySize ¬ SIZE[EntryKeyObject[lengthOfEntryKey]]; lengthOfValueObject ¬ LOOPHOLE[entry+entryKeySize, EntryValue].length; valueObjectSize ¬ SIZE[ValueObject[lengthOfValueObject]]; bytes ¬ entryKeySize + valueObjectSize; }; EntryFromRecord: BTree.EntryFromRecord --[record: BTree.Record] RETURNS [entry: BTree.Entry]-- = UNCHECKED { ERROR Bug[cantGetHere]; -- we never call the BTree procedures that traffic in Records }; NewRecordFromEntry: BTree.NewRecordFromEntry --[entry: BTree.Entry] RETURNS [record: BTree.Record]-- = UNCHECKED { ERROR Bug[cantGetHere]; -- we never call the BTree procedures that traffic in Records }; <> <> <> <> < LOOPHOLE[src, CARD] AND LOOPHOLE[dst, CARD] - LOOPHOLE[src, CARD] < nWords THEN {>> < 0 DO>> <> <> <> <> <<};>> <<>> <> <> <> <> <<>> <> Bug: ERROR [type: BugType] = CODE; BugType: TYPE = {cantGetHere}; }.