BTreeSimpleImpl.mesa
Copyright Ó 1985, 1986, 1987, 1988, 1992 by Xerox Corporation. All rights reserved.
Taft, January 21, 1984 5:00:25 pm PST
Russ Atkinson (RRA) March 11, 1985 9:48:59 pm PST
Tim Diebert: May 18, 1988 4:55:30 pm PDT
Doug Wyatt, June 3, 1987 11:13:55 am PDT
Brian Oki, August 17, 1990 4:12 pm PDT
Willie-s, April 23, 1992 11:34 am PDT
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;
BTree representation
KeyFromEntry: PUBLIC UNSAFE PROC [entryKey: EntryKey]
RETURNS [key: InternalKey ¬ NIL] = UNCHECKED {
IF entryKey # NIL THEN {
key ← NEW[Rope.TextRep[entryKey.length]];
key ¬ Rope.NewText[entryKey.length]; -- on Michael Plass's recommendation
key.length ¬ entryKey.length;
nWords is really the number of bytes to move from src to dst. We first compute of words given the entryKey.length: adding 3 and doing integer division by 4 does the trick. E.g., if the length is 6, then (6+3)/4 = 2 words. Then multiply by SIZE[BYTE], which is 4 for a sun 4. Note that although SIZE[BYTE] = 4 here, it's wrong to multiply through and cancel out the other 4. old comment, left for historical documentation
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<c2 THEN RETURN[less] ELSE RETURN[greater];
}
ENDLOOP;
IF entryKey1.length = entryKey2.length THEN RETURN[equal]
ELSE {IF entryKey1.length < entryKey2.length
THEN RETURN[less]
ELSE RETURN[greater]
};
};
defaultCompareProcs: PUBLIC CompareProcs ¬
[compare: DefaultCompare, compareEntries: DefaultCompareEntries];
BTree global operations
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[];
The following should not be here because it violates abstraction.
WITH storage SELECT FROM
handle: BTreeVM.Handle => file ← handle.backing;
ENDCASE => 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];
};
Higher-level BTree access
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];
};
Lower-level BTree access
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;
entryKey.length ¬ 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];
};
PathStk hints
NewPathStk: PUBLIC PROC RETURNS [pathStk: PathStk] = {
RETURN[BTree.NewPathStk[]];
};
Private
The following are the procedures passed to the BTree package as the RepresentationPrimitives (in addition to the client's Compare and CompareEntries procedures).
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
};
MoveOverlapped: PUBLIC UNSAFE PROC [dst: POINTER, src: POINTER, nWords: CARD] = UNCHECKED
BEGIN
WordPtr: TYPE = POINTER TO WORD;
Test to see if blocks overlap--does destination overlap with source in the direction of increasing addresses? Note that this is an unsafe operation.
IF LOOPHOLE[dst, CARD] > LOOPHOLE[src, CARD]
AND LOOPHOLE[dst, CARD] - LOOPHOLE[src, CARD] < nWords THEN {
WHILE nWords > 0 DO
nWords ¬ nWords - 1 * SIZE[BYTE];
LOOPHOLE[dst+nWords, WordPtr]­ ¬ LOOPHOLE[src+nWords, WordPtr]­;
ENDLOOP;
RETURN
};
Destination either overlaps with source in the reverse direction, or overlaps not at all.
We use Basics.
Basics.MoveWords[dst: dst, src: src, count: nWords/SIZE[BYTE]];
END;
Errors
Bug: ERROR [type: BugType] = CODE;
BugType: TYPE = {cantGetHere};
}.