YggIndexImpl.mesa
Copyright Ó 1988, 1989 by Xerox Corporation. All rights reserved.
Bob Hagmann January 6, 1989 3:21:13 pm PST
Cache to support the Yggdrasil BTree package for indices. This package caches BTreeVM objects and provides transparent access to BTreeVM. It also provides all the indexing functions.
DIRECTORY
Ascii USING [NUL],
Basics USING [bytesPerWord, charsPerWord, Comparison, logBytesPerWord, RawBytes, UnsafeBlock],
BasicTime USING [Period],
BTree USING [DeleteKey, Entry, EntSize, EnumerateEntries, Key, New, Open, PageNumber, PagePtr, PageStorage, ReferencePage, ReleasePage, Tree, UpdateEntry],
BTreeVM USING [CacheSize, FlushCache, FreeBuffers, GetStats, Handle, Open, ReferencePage, ReleasePage, Stats],
IO USING [CreateStream, CreateStreamProcs, Flush, GetLength, SetIndex, STREAM, StreamProcs, UnsafeGetBlock, UnsafePutBlock],
PBasics USING [ByteBlt],
Process USING [Detach, MsecToTicks, Pause, SetTimeout, Ticks],
RefTab USING [Create, Delete, EachPairAction, EqualProc, Fetch, GetSize, Insert, Pairs, Ref, Val],
Rope USING [Fetch, Length, NewText, ROPE, Text, UnsafeMoveChars],
SafeStorage USING [CantEstablishFinalization, EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ],
YggDID USING [CompareDIDs, DID, FirstDID, LastDID, SizeForDID, StabilizeDID, VolatilizeDID],
YggDIDMap USING [GetComponentFiles, OpenDocumentFromDID],
YggDIDPrivate USING [DIDRep],
YggEnvironment USING [nullTransID, TransID],
YggFileStream USING [StreamFromComponentFilesAndTid],
YggIndex USING [EntryProc, Index, IndexRep],
YggInternal USING [Document, FileHandle],
YggInline USING [BytesForWords, WordsForBytes],
YggRep USING [AccurateGMT, AccurateGMTRep, BitsRep, date, did, DocType, float, int, rope, shortRope, TypedPrimitiveElement, unknown],
YggTransaction USING [EqualTrans, IsNullTrans];
YggIndexImpl: CEDAR MONITOR
IMPORTS Basics, BasicTime, BTree, BTreeVM, IO, PBasics, Process, RefTab, Rope, SafeStorage, YggDID, YggDIDMap, YggFileStream, YggInline, YggTransaction
EXPORTS YggDID, YggIndex
~ BEGIN
Types and constants
ROPE: TYPE = Rope.ROPE;
DID: PUBLIC TYPE ~ REF DIDRep;
DIDRep: PUBLIC TYPE ~ YggDIDPrivate.DIDRep;
Index: TYPE = YggIndex.Index;
AllNulls: PACKED ARRAY [0..Basics.charsPerWord) OF CHAR ← ALL[0C];
bytesPerPage: INT ← 4096;
MyCondition: CONDITION;
Handle: TYPE = REF VMObject;
VMObject: PUBLIC TYPE = MONITORED RECORD [
backingStream: IO.STREAM,
btreevmHandle: BTreeVM.Handle,
btreeHandle: BTree.Tree ← NIL,
unused: BOOL ← FALSE
];
Cache: RefTab.Ref ← NIL;
desiredSizeOfCache: INT ← 50;
CacheEntry: TYPE = RECORD [
backingStream: IO.STREAM, -- stream with null tid
fileUse: ATOM,
tid: YggEnvironment.TransID ← YggEnvironment.nullTransID,
currentWriteStream: IO.STREAM, -- stream with tid
myHandle: Index,
users: INT ← 0 -- -1 means in the process of being opened
];
scratchKey: REF CacheEntry ← NIL;
Key: TYPE = REF KeyRep;
KeyRep: TYPE = RECORD [
tpe: YggRep.TypedPrimitiveElement,
did: YggDID.DID
];
An entry in a BTree has the following format (32-bit words assumed):
The DID.
A one word type (YggRep.DocType)
The "value" indexed. This is stored in the following type dependant manner:
integer, float: one word with the data
date: two words with the data
short rope (short and contains no nulls): then null terminated string written into just enough words
rope (long and may have nulls) and uninterpreted bytes: size word containing the number of characters/bytes, and enough words to contain the characters/bytes
DID: the did.
The DID. For the Phase 0 implementation, this is a null terminated file name.
varOffset: CARD = WORDS[YggDIDPrivate.DIDRep] + WORDS[YggRep.DocType];
EntryPtr: TYPE = LONG BASE POINTER TO Entry;
Entry: TYPE = MACHINE DEPENDENT RECORD [
didWithValue(0): YggDIDPrivate.DIDRep,
docType(WORDS[YggDIDPrivate.DIDRep]): YggRep.DocType,
val(varOffset): SELECT OVERLAID * FROM
int => [
int(varOffset): INT32
],
float => [
float(varOffset): REAL32
],
date => [
date(varOffset): YggRep.AccurateGMTRep
],
shortRope => [
shortRope(varOffset): PACKED ARRAY [0..0) OF CHAR
],
rope => [
ropeSize(varOffset): INT32,
rope(varOffset+WORDS[INT32]): PACKED ARRAY [0..0) OF CHAR
],
did => [
did(varOffset): YggDIDPrivate.DIDRep
],
bits => [
bitsSize(varOffset): INT32,
bits(varOffset+WORDS[INT]): PACKED ARRAY [0..0) OF BYTE
]
ENDCASE
];
Exported procedures
Open: PUBLIC PROC [did: YggDID.DID, fileUse: ATOM, cacheSize: BTreeVM.CacheSize, initialize: BOOL, trans: YggEnvironment.TransID] RETURNS [index: Index ← NIL] ~ {
Initiates indexing activity. This can be called any number of times to get a new Index handle or reopen an index that has been closed.
index ← OpenBTreeVM[did: did, fileUse: fileUse, bytesPerPage: bytesPerPage, cacheSize: cacheSize, base: 0, initialize: initialize];
};
Close: PUBLIC PROC [index: Index] = {
Terminates indexing activity.
CloseBTreeVM[index];
};
SimpleEntryProc: YggIndex.EntryProc = { -- for debugging purposes
[value: YggRep.TypedPrimitiveElement, did: YggDID.DID] RETURNS [continue: BOOL]
cont: BOOLEAN ← TRUE;
set breakpoint here to look at entry
RETURN[cont];
};
EnumerateEntries: PUBLIC PROC [index: Index, start: YggRep.TypedPrimitiveElement,
end: YggRep.TypedPrimitiveElement, proc: YggIndex.EntryProc] ~ {
Calls `proc' for each entry in the specified range of key values. The enumeration is halted when either the range of entries is exhausted or `proc' returns FALSE. An [unknown, NIL] value for `start' represents the least value, while an [unknown, NIL] value for `end' represents the largest value. Thus, the complete index can be enumerated by specifying start=[unknown, NIL] and end=[unknown, NIL].
enumProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOL ← TRUE] = TRUSTED {
entryPtr: EntryPtr = LOOPHOLE[entry];
value: YggRep.TypedPrimitiveElement;
did: YggDID.DID;
IF lastKey # NIL THEN {
done: Basics.Comparison;
done ← Compare[lastKey, entry];
IF done = less OR done = equal THEN RETURN[FALSE];
};
SELECT entryPtr.docType FROM
YggRep.unknown => ERROR;
YggRep.int =>{
value ← [YggRep.int, NEW[INT32 ← entryPtr.int]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
YggRep.float => {
value ← [YggRep.float, NEW[REAL32 ← entryPtr.float]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
YggRep.date => {
value ← [YggRep.date, NEW[YggRep.AccurateGMTRep ← entryPtr.date]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
YggRep.shortRope => {
ropeLen: INT;
scratch: Rope.Text;
FOR ropeLen IN [ 0 .. INT.LAST ) DO
IF entryPtr.shortRope[ropeLen] = Ascii.NUL THEN EXIT;
ENDLOOP;
scratch ← Rope.NewText[ropeLen];
FOR charNo: INT IN [ 0 .. ropeLen ) DO
TRUSTED {scratch[charNo] ← entryPtr.shortRope[charNo];};
ENDLOOP;
ropeLen ← YggInline.BytesForWords[YggInline.WordsForBytes[ropeLen+1]];
value ← [YggRep.shortRope, NEW[ROPE ← scratch]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
YggRep.rope => {
ropeLen: CARD;
scratch: Rope.Text;
scratch ← Rope.NewText[entryPtr.ropeSize];
FOR charNo: INT IN [ 0 .. entryPtr.ropeSize ) DO
TRUSTED {scratch[charNo] ← entryPtr.rope[charNo];};
ENDLOOP;
ropeLen ← YggInline.BytesForWords[YggInline.WordsForBytes[entryPtr.ropeSize]];
value ← [YggRep.rope, NEW[ROPE ← scratch]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
YggRep.did => {
value ← [YggRep.did, YggDID.VolatilizeDID[buffer: @entryPtr.did]];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
ENDCASE => {
nBytes: CARD;
bitsLen: CARD;
bits: REF YggRep.BitsRep;
nextByteToRead: INT ← 0;
bits ← NEW[YggRep.BitsRep[CARD16[entryPtr.bitsSize]]];
bits.validBytes ← entryPtr.bitsSize;
TRUSTED {nBytes ← PBasics.ByteBlt[
from: [blockPointer: @entryPtr.bits, startIndex: 0, stopIndexPlusOne: entryPtr.bitsSize],
to: [blockPointer: LOOPHOLE[bits, LONG POINTER] + SIZE[YggRep.BitsRep[0]], startIndex: 0, stopIndexPlusOne: entryPtr.bitsSize]];
};
IF nBytes # CARD[entryPtr.bitsSize] THEN ERROR;
bitsLen ← YggInline.BytesForWords[YggInline.WordsForBytes[entryPtr.bitsSize]];
value ← [entryPtr.docType, bits];
did ← YggDID.VolatilizeDID[buffer: @entryPtr.didWithValue];
};
continue ← proc[value, did];
};
keyRef: Key ← NIL;
lastKey: Key ← NIL;
IF start # [YggRep.unknown, NIL] THEN {
keyRef ← CheckoutKey[];
keyRef.tpe ← start;
keyRef.did ← YggDID.FirstDID;
};
IF end # [YggRep.unknown, NIL] THEN {
lastKey ← CheckoutKey[];
lastKey.tpe ← end;
lastKey.did ← YggDID.LastDID;
};
TRUSTED {[] ← BTree.EnumerateEntries[tree: index.tree, relation: greater, key: keyRef, pathStk: NIL, useExistingPath: FALSE, Proc: enumProc];};
IF keyRef # NIL THEN RecycleKey[keyRef];
IF lastKey # NIL THEN RecycleKey[lastKey];
};
WriteEntry: PUBLIC PROC [index: Index, value: YggRep.TypedPrimitiveElement, did: YggDID.DID, replace: BOOLEAN ← FALSE, trans: YggEnvironment.TransID] RETURNS [indexFound: BOOL ← TRUE] ~ {
Adds a new entry to the index.
writeEntryInner: UNSAFE PROCEDURE [entry: BTree.Entry] = UNCHECKED {
entryPtr: EntryPtr = LOOPHOLE[entry];
IF firstTime THEN {
myStream: MyStream;
myStream ← NARROW[index.realStream.streamData];
myStream.tid ← trans;
};
firstTime ← FALSE;
entryPtr.docType ← value.docType;
SELECT value.docType FROM
YggRep.unknown => ERROR;
YggRep.int =>{
ri: REF INT32;
ri ← NARROW[value.bits];
entryPtr.int ← ri^;
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
YggRep.float => {
rReal: REF REAL32;
rReal ← NARROW[value.bits];
entryPtr.float ← rReal^;
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
YggRep.date => {
rAccurateGMT: YggRep.AccurateGMT;
rAccurateGMT ← NARROW[value.bits];
entryPtr.date ← rAccurateGMT^;
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
YggRep.shortRope => {
rRope: ROPE;
size: INT;
nBytes: INT;
nullsToMove: INT;
rRope ← NARROW[value.bits];
size ← Rope.Length[rRope];
TRUSTED {nBytes ← Rope.UnsafeMoveChars[block: [LOOPHOLE[@entryPtr.shortRope], 0, size], rope: rRope, start: 0];};
IF nBytes # size THEN ERROR;
nullsToMove ← YggInline.BytesForWords[YggInline.WordsForBytes[size+1]] - size;
IF nullsToMove <= 0 THEN ERROR;
TRUSTED {nBytes ← PBasics.ByteBlt[
from: [blockPointer: @AllNulls, startIndex: 0, stopIndexPlusOne: nullsToMove],
to: [blockPointer: @entryPtr.shortRope, startIndex: size, stopIndexPlusOne: size+nullsToMove]];
};
IF nBytes # nullsToMove THEN ERROR;
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
YggRep.rope => {
rRope: ROPE;
nBytes: INT;
size: INT;
nullsToMove: INT;
rRope ← NARROW[value.bits];
size ← Rope.Length[rRope];
entryPtr.ropeSize ← size;
TRUSTED {nBytes ← Rope.UnsafeMoveChars[block: [LOOPHOLE[@entryPtr.rope], 0, size], rope: rRope, start: 0];};
IF nBytes # size THEN ERROR;
nullsToMove ← YggInline.BytesForWords[YggInline.WordsForBytes[size]] - size;
IF nullsToMove > 0 THEN TRUSTED {
nBytes ← PBasics.ByteBlt [
from: [blockPointer: @AllNulls, startIndex: 0, stopIndexPlusOne: nullsToMove],
to: [blockPointer: @entryPtr.rope, startIndex: size, stopIndexPlusOne: size+nullsToMove]];
IF nBytes # nullsToMove THEN ERROR;
};
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
YggRep.did => {
rDID: DID;
rDID ← NARROW[value.bits];
YggDID.StabilizeDID[did: rDID, buffer: @entryPtr.did];
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
ENDCASE => {
rBits: REF YggRep.BitsRep;
nullsToMove: INT;
nBytes: INT;
rBits ← NARROW[value.bits];
entryPtr.ropeSize ← rBits.validBytes;
TRUSTED {nBytes ← PBasics.ByteBlt [
from: [blockPointer: LOOPHOLE[rBits, LONG POINTER TO Basics.RawBytes] + SIZE[YggRep.BitsRep[0]] , startIndex: 0, stopIndexPlusOne: rBits.validBytes],
to: [blockPointer: @entryPtr.bits, startIndex: 0, stopIndexPlusOne: rBits.validBytes]];};
IF nBytes # INT[rBits.validBytes] THEN ERROR;
nullsToMove ← YggInline.BytesForWords[YggInline.WordsForBytes[rBits.validBytes]] - rBits.validBytes;
IF nullsToMove > 0 THEN TRUSTED {
nBytes ← PBasics.ByteBlt [
from: [blockPointer: @AllNulls, startIndex: 0, stopIndexPlusOne: nullsToMove],
to: [blockPointer: @entryPtr.bits, startIndex: rBits.validBytes, stopIndexPlusOne: rBits.validBytes+nullsToMove]];
IF nBytes # nullsToMove THEN ERROR;
};
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didWithValue];
};
};
firstTime: BOOL ← TRUE;
keyRef: Key ← NIL;
entSize: INT;
keyRef ← CheckoutKey[];
keyRef.tpe ← value;
keyRef.did ← did;
entSize ← SIZE[YggRep.DocType] + ValueSize[value] + YggDID.SizeForDID[did];
TRUSTED {BTree.UpdateEntry[tree: index.tree, key: keyRef, pathStk: NIL, useExistingPath: FALSE, words: entSize, Proc: writeEntryInner, updateType: insertOrReplace];};
RecycleKey[keyRef];
};
DeleteEntry: PUBLIC PROC [index: Index, value: YggRep.TypedPrimitiveElement, did: YggDID.DID, trans: YggEnvironment.TransID] RETURNS [found: BOOLEAN] ~ {
Deletes the entry that contains the given attribute value for the given key.
myStream: MyStream;
keyRef: Key ← NIL;
keyRef ← CheckoutKey[];
keyRef.tpe ← value;
keyRef.did ← did;
myStream ← NARROW[index.realStream.streamData];
myStream.tid ← trans;
found ← BTree.DeleteKey[tree: index.tree, key: keyRef, pathStk: NIL, useExistingPath: FALSE];
RecycleKey[keyRef];
};
BTreeVM related procedures
OpenBTreeVM: PROC [ did: YggDID.DID, fileUse: ATOM, bytesPerPage: INT, cacheSize: BTreeVM.CacheSize, base: INT ← 0, initialize: BOOL, trans: YggEnvironment.TransID ← YggEnvironment.nullTransID ] RETURNS [ h: YggIndex.Index ← NIL] = {
btreevmHandle: BTreeVM.Handle ← NIL;
ce: REF CacheEntry;
innerOpen: ENTRY PROC = {
found: BOOL;
val: RefTab.Val;
scratchKey.backingStream ← backingStream;
[found, val] ← RefTab.Fetch[x: Cache, key: scratchKey];
IF found THEN {
ce ← NARROW[val];
h ← ce.myHandle;
WHILE ce.users = -1 DO WAIT MyCondition; ENDLOOP;
ce.users ← ce.users + 1;
IF h.unused THEN {
h.unused ← FALSE;
SafeStorage.EnableFinalization[h];
};
}
ELSE {
ce ← NEW[CacheEntry ← [backingStream, fileUse, trans, NIL, NIL, -1]];
IF ~RefTab.Insert[x: Cache, key: Cache, val: ce] THEN ERROR;
IF ~YggTransaction.IsNullTrans[trans] THEN {
ce.currentWriteStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: componentFiles, fileUse: fileUse, tid: trans];
};
};
};
doc: YggInternal.Document ← NIL;
componentFiles: LIST OF YggInternal.FileHandle;
backingStream: IO.STREAM;
doc ← YggDIDMap.OpenDocumentFromDID[did, YggEnvironment.nullTransID];
componentFiles ← YggDIDMap.GetComponentFiles[doc];
backingStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: componentFiles, fileUse: fileUse, tid: YggEnvironment.nullTransID];
innerOpen[];
IF h = NIL THEN {
opened: ENTRY PROC = {
ce.users ← 1;
ce.myHandle ← h;
BROADCAST MyCondition;
};
tree: BTree.Tree;
realStream: IO.STREAM;
realStream ← NewStreamForBTreeVM[componentFiles, fileUse];
btreevmHandle ← BTreeVM.Open[realStream, bytesPerPage, cacheSize, base];
h ← NEW[YggIndex.IndexRep];
h.btreevmHandle ← btreevmHandle;
h.realStream ← realStream;
h.backingStream ← backingStream;
tree ← BTree.New[
repPrim: [compare: Compare, entrySize: EntrySize],
storPrim: [referencePage: BTreeVM.ReferencePage, releasePage: BTreeVM.ReleasePage],
minEntrySize: SIZE[YggRep.DocType] + SIZE[CARD],
initialState: suspended
];
BTree.Open[
tree: tree,
storage: btreevmHandle,
pageSize: bytesPerPage,
initialize: initialize,
maintainRecomputableState: TRUE
];
h.tree ← tree;
opened[];
SafeStorage.EnableFinalization[h];
};
};
CloseBTreeVM: ENTRY PROC [ h: Index ] = {
Done with the current use of the BTree.
ce: REF CacheEntry;
found: BOOL;
val: RefTab.Val;
scratchKey.backingStream ← h.backingStream;
[found, val] ← RefTab.Fetch[x: Cache, key: scratchKey];
IF found THEN {
ce ← NARROW[val];
ce.users ← ce.users - 1;
};
};
Compare: UNSAFE PROC [key: BTree.Key, entry: BTree.Entry] RETURNS [Basics.Comparison ← equal] = UNCHECKED {
keyRef: Key = NARROW[key];
entryPtr: EntryPtr = LOOPHOLE[entry];
IF keyRef.tpe.docType = entryPtr.docType THEN {
SELECT keyRef.tpe.docType FROM
YggRep.unknown => ERROR;
YggRep.int => {
ri: REF INT32;
ri ← NARROW[keyRef.tpe.bits];
IF ri^ < entryPtr.int THEN RETURN[less];
IF ri^ > entryPtr.int THEN RETURN[greater];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
YggRep.float => {
rReal: REF REAL32;
rReal ← NARROW[keyRef.tpe.bits];
IF rReal^ < entryPtr.float THEN RETURN[less];
IF rReal^ > entryPtr.float THEN RETURN[greater];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
YggRep.date => {
rAccurateGMT: YggRep.AccurateGMT;
period: INT;
rAccurateGMT ← NARROW[keyRef.tpe.bits];
period ← BasicTime.Period[rAccurateGMT.gmt, entryPtr.date.gmt];
IF period < 0 THEN RETURN[greater];
IF period > 0 THEN RETURN[less];
IF rAccurateGMT.usecs < entryPtr.date.usecs THEN RETURN[less];
IF rAccurateGMT.usecs > entryPtr.date.usecs THEN RETURN[greater];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
YggRep.shortRope => {
rRope: ROPE;
lenKey: CARDINAL;
rRope ← NARROW[keyRef.tpe.bits];
lenKey ← Rope.Length[rRope];
FOR i: CARDINAL IN [ 0 .. lenKey ) DO
keyC: CHAR = Rope.Fetch[rRope, i];
entryC: CHAR = entryPtr.shortRope[i];
IF keyC = entryC THEN LOOP; -- most probable case
IF entryC = Ascii.NUL THEN RETURN [greater];
SELECT keyC FROM
< entryC => RETURN [less];
> entryC => RETURN [greater];
ENDCASE;
ENDLOOP;
IF entryPtr.shortRope[lenKey] = Ascii.NUL THEN {
ropeLen: CARD;
ropeLen ← YggInline.BytesForWords[YggInline.WordsForBytes[lenKey+1]];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
}
ELSE RETURN[less];
};
YggRep.rope => {
rRope: ROPE;
lenKey: CARD32;
rRope ← NARROW[keyRef.tpe.bits];
lenKey ← Rope.Length[rRope];
FOR i: CARD32 IN [ 0 .. MIN[lenKey, CARD32[entryPtr.ropeSize]] ) DO
keyC: CHAR = Rope.Fetch[rRope, i];
entryC: CHAR = entryPtr.rope[i];
IF keyC = entryC THEN LOOP; -- most probable case
SELECT keyC FROM
< entryC => RETURN [less];
> entryC => RETURN [greater];
ENDCASE;
ENDLOOP;
SELECT CARD32[entryPtr.ropeSize] FROM
< lenKey => RETURN [greater];
> lenKey => RETURN [less];
ENDCASE => {
ropeLen: CARD;
ropeLen ← YggInline.BytesForWords[YggInline.WordsForBytes[entryPtr.ropeSize]];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
};
YggRep.did => {
comp: Basics.Comparison ← equal;
rDID: DID;
rDID ← NARROW[keyRef.tpe.bits];
comp ← YggDID.CompareDIDs[keyRef.did, @entryPtr.did];
IF comp # equal THEN RETURN[comp];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
ENDCASE => {
rBits: REF YggRep.BitsRep;
rBits ← NARROW[keyRef.tpe.bits];
FOR i: CARD32 IN [ 0 .. MIN[rBits.validBytes, CARD32[entryPtr.bitsSize]] ) DO
keyC: BYTE = rBits.b[i];
entryC: BYTE = entryPtr.bits[i];
IF keyC = entryC THEN LOOP; -- most probable case
SELECT keyC FROM
< entryC => RETURN [less];
> entryC => RETURN [greater];
ENDCASE;
ENDLOOP;
SELECT entryPtr.bitsSize FROM
< rBits.length => RETURN [greater];
> rBits.length => RETURN [less];
ENDCASE => {
bitsLen: CARD;
bitsLen ← YggInline.BytesForWords[YggInline.WordsForBytes[entryPtr.bitsSize]];
RETURN [YggDID.CompareDIDs[keyRef.did, @entryPtr.didWithValue]];
};
};
};
IF keyRef.tpe.docType < entryPtr.docType THEN RETURN [less];
RETURN [greater];
};
EntrySize: UNSAFE PROC [entry: BTree.Entry] RETURNS [words: BTree.EntSize ← 4] = UNCHECKED {
entryPtr: EntryPtr = LOOPHOLE[entry];
SELECT entryPtr.docType FROM
YggRep.unknown => ERROR;
YggRep.int =>{
RETURN [WORDS[Entry.int]];
};
YggRep.float => {
RETURN [WORDS[Entry.float]];
};
YggRep.date => {
RETURN [WORDS[Entry.date]];
};
YggRep.shortRope => {
lenKey: CARD;
FOR lenKey IN [ 0 .. CARD.LAST ) DO
IF entryPtr.shortRope[lenKey] = Ascii.NUL THEN EXIT;
ENDLOOP;
RETURN [WORDS[Entry.shortRope] + YggInline.WordsForBytes[lenKey+1]];
};
YggRep.rope => {
RETURN [WORDS[Entry.rope] + YggInline.WordsForBytes[entryPtr.ropeSize]];
};
YggRep.date => {
RETURN [WORDS[Entry.did]];
};
ENDCASE => {
RETURN [WORDS[Entry.bits] + YggInline.WordsForBytes[entryPtr.bitsSize]];
};
};
ValueSize: PROC [value: YggRep.TypedPrimitiveElement] RETURNS [words: BTree.EntSize ← 4] = {
wordsForValue: INT;
SELECT value.docType FROM
YggRep.unknown => ERROR;
YggRep.int => wordsForValue ← WORDS[INT32];
YggRep.shortRope, YggRep.rope => {
bytesForValue: INT;
rRope: ROPE;
rRope ← NARROW[value.bits];
bytesForValue ← Rope.Length[rRope];
wordsForValue ← YggInline.WordsForBytes[bytesForValue];
};
YggRep.float => wordsForValue ← WORDS[REAL32];
YggRep.date => wordsForValue ← WORDS[YggRep.AccurateGMTRep];
YggRep.did => wordsForValue ← WORDS[YggDIDPrivate.DIDRep];
ENDCASE => {
bytesForValue: INT;
rBits: REF YggRep.BitsRep;
rBits ← NARROW[value.bits];
bytesForValue ← rBits.length;
wordsForValue ← YggInline.WordsForBytes[bytesForValue];
};
words ← WORDS[YggRep.DocType] + wordsForValue;
};
GetStats: PROC [ h: Index ] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL] = {
stats: REF BTreeVM.Stats;
stats ← NEW[BTreeVM.Stats];
BTreeVM.GetStats[h.btreevmHandle, stats];
hits ← stats.hits;
misses ← stats.misses;
reads ← stats.reads;
writes ← stats.writes;
cumChainLength ← stats.cumChainLength;
cumReadWriteTime ← stats.cumReadWriteTime;
[hits, misses, reads, writes, cumChainLength, cumReadWriteTime] ← BTreeVM.GetStats[h.btreevmHandle];
};
FlushCache: PROC [ h: Index ] = {
BTreeVM.FlushCache[h.btreevmHandle];
};
FreeBuffers: PROC [ h: Index ] = {
BTreeVM.FreeBuffers[h.btreevmHandle];
};
SizeOfCache: PROC [ size: INT ] = {
desiredSizeOfCache ← size;
};
My streams
myStreamProcs: REF IO.StreamProcs ← IO.CreateStreamProcs[variety: inputOutput, class: $YggdrasilIndex, unsafeGetBlock: myUnsafeGetBlock, unsafePutBlock: myUnsafePutBlock, flush: myFlush, getLength: myGetLength, setIndex: mySetIndex];
MyStream: TYPE = REF MyStreamRep;
MyStreamRep: TYPE = RECORD [
tid: YggEnvironment.TransID,
componentFiles: LIST OF YggInternal.FileHandle,
fileUse: ATOM,
backingStream: IO.STREAM,
currentWriteStream: IO.STREAM
];
NewStreamForBTreeVM: PROC [componentFiles: LIST OF YggInternal.FileHandle, fileUse: ATOM] RETURNS [stream: IO.STREAM] = {
backingStream: IO.STREAM ← NIL;
backingStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: componentFiles, fileUse: fileUse, tid: YggEnvironment.nullTransID];
stream ← IO.CreateStream[streamProcs: myStreamProcs, streamData: NEW[MyStreamRep ← [tid: YggEnvironment.nullTransID, componentFiles: componentFiles, backingStream: backingStream, currentWriteStream: NIL]], backingStream: NIL];
};
NewTransForStream: PROC [trans: YggEnvironment.TransID, backingStream: IO.STREAM] = {
myStream: MyStream = NARROW[backingStream.streamData];
IF ~YggTransaction.EqualTrans[trans, myStream.tid] THEN {
myStream.tid ← trans;
myStream.currentWriteStream ← NIL;
};
};
myUnsafeGetBlock: UNSAFE PROC [self: IO.STREAM, block: Basics.UnsafeBlock] RETURNS [nBytesRead: INT] ~ TRUSTED {
myStream: MyStream = NARROW[self.streamData];
nBytesRead ← IO.UnsafeGetBlock[myStream.backingStream, block];
};
myUnsafePutBlock: PROC [self: IO.STREAM, block: Basics.UnsafeBlock] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.currentWriteStream = NIL THEN {
myStream.currentWriteStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: myStream.fileUse, tid: myStream.tid];
};
IO.UnsafePutBlock[myStream.currentWriteStream, block];
};
myFlush: PROC [self: IO.STREAM] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.currentWriteStream = NIL THEN {
myStream.currentWriteStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: myStream.fileUse, tid: myStream.tid];
};
IO.Flush[myStream.currentWriteStream];
};
myGetLength: PROC [self: IO.STREAM] RETURNS [length: INT] ~ {
myStream: MyStream = NARROW[self.streamData];
length ← IO.GetLength[myStream.backingStream];
};
mySetIndex: PROC [self: IO.STREAM, index: INT] ~ {
myStream: MyStream = NARROW[self.streamData];
IO.SetIndex[self: myStream.backingStream, index: index];
IF myStream.currentWriteStream # NIL THEN IO.SetIndex[self: myStream.currentWriteStream, index: index];
};
Utilities
stockKeys: ARRAY [0..numberOfStockKeys] OF Key ← ALL[NIL];
numberOfStockKeys: INT = 10;
stockKeyIndex: INT ← 0;
CheckoutKey: ENTRY PROC RETURNS [k: Key] = {
IF stockKeyIndex = 0 THEN k ← NEW [KeyRep]
ELSE {
stockKeyIndex ← stockKeyIndex - 1;
k ← stockKeys[stockKeyIndex];
};
};
RecycleKey: ENTRY PROC [k: Key] = {
IF stockKeyIndex < numberOfStockKeys THEN {
stockKeys[stockKeyIndex] ← k;
stockKeyIndex ← stockKeyIndex + 1;
};
};
Equals
equalProc: RefTab.EqualProc = {
PROC [key1, key2: Key] RETURNS [BOOL];
k1: REF CacheEntry;
k2: REF CacheEntry;
k1 ← NARROW[key1];
k2 ← NARROW[key2];
RETURN [k1.backingStream = k2.backingStream];
};
Initialization, cache trim, and finalization
IndexCacheTrimProcess: PROC = {
ticksToWait: Process.Ticks;
ticksToWait ← Process.MsecToTicks[222];
DO
innerTrim: ENTRY PROC = {
eachPairAction: RefTab.EachPairAction = {
PROC [key: Key, val: Val] RETURNS [quit: BOOL ← FALSE];
ce: REF CacheEntry;
ce ← NARROW[val];
IF ce.myHandle.unused THEN [] ← RefTab.Delete[x: Cache, key: ce];
size ← size - 1;
IF size <= desiredSizeOfCache THEN quit ← TRUE;
};
size: INT;
size ← RefTab.GetSize[Cache];
[] ← RefTab.Pairs[x: Cache, action: eachPairAction];
};
Process.Pause[ticksToWait];
IF RefTab.GetSize[Cache] > desiredSizeOfCache THEN innerTrim[];
ENDLOOP;
};
FinalizationProcess: PROC = {
DO
fpInner: ENTRY PROC = {
h.unused ← TRUE;
};
h: Index ← NARROW [SafeStorage.FQNext[finalizationQueue]];
fpInner[];
h ← NIL;
ENDLOOP;
};
finalizationQueue: SafeStorage.FinalizationQueue ← SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[type: YggIndex.IndexRep.CODE, npr: 1, fq: finalizationQueue ! SafeStorage.CantEstablishFinalization => CONTINUE];
TRUSTED {
Process.Detach[FORK FinalizationProcess];
Process.Detach[FORK IndexCacheTrimProcess];
Process.SetTimeout[condition: @MyCondition, ticks: Process.MsecToTicks[153]];
};
Cache ← RefTab.Create[mod: 47, equal: equalProc, hash: NIL];
scratchKey ← NEW[CacheEntry];
END.