--BTree2Defs

BTree2Defs:DEFINITIONS=BEGIN

VArray:TYPE= POINTER TO DESCRIPTOR FOR ARRAY OF WORD;
Entry :TYPE= POINTER TO EntryR;
EntryR:TYPE= RECORD[k:Key,v:Value];
Key :TYPE= DESCRIPTOR FOR ARRAY OF WORD;
Value :TYPE= DESCRIPTOR FOR ARRAY OF WORD;
Index :TYPE= CARDINAL;
nullIndex:CARDINAL= 100000B;

Initialize:PROCEDURE[VArray];
Insert :PROCEDURE[VArray,Index,Entry];
Lookup :PROCEDURE[VArray,Index] RETURNS[EntryR];
Delete :PROCEDURE[VArray,Index];
Replace :PROCEDURE[VArray,Index,Entry];

GetAnother:SIGNAL RETURNS [VArray];
Merger :SIGNAL RETURNS [v:VArray,vOnRight:BOOLEAN];
DeletePage:SIGNAL;

Items:PROCEDURE[VArray] RETURNS[CARDINAL];

END.

VArray stores in a compact way a variable number of variable length items, keyed off an index number. Index numbers start at 0 and run to Items-1. You may insert,lookup, delete,or replace at any index. Structurally, a Varray is a Pointer to a Descriptor for an Array of Word, and any client can create the structure. It must be initialized before use. An Item consists of two parts, a key and a Value. Each part of each item is described by a array descriptor, both for insertion and lookup. No copy is implied by a lookup: the descriptor points directly into the array. Insertion and deletion immediately renumber all of the stored items. Logically, replace is a delete followed by an insert, but by doing it all at once you avoid an ill advised attempt to merge the page (see the Merge signal below). Insertions occur after the index, so you must insert at -1 to put in the first entry.

There are two interesting events which trigger signals: trying to insert something which won’t fit, and trying to delete something when the vArray is pretty empty.
If won’t fit, the implementer signals GetAnother, which the client can resume with a new vArray for the overflow.
If the buffer gets rather empty, the implementer signals Merger. If the client Resumes with a new buffer, then the implementer will try to merge the current vArray with the new buffer. If successful, the implementer will signal DeletePage. It is possible to merge with a following or a preceeding buffer (vOnRight=TRUE or FALSE) but in either case, the modification will occur to the rightmost buffer. If the client resumes with NIL, the short array will remain.