-- BTreeDefs.mesa
-- last edit by Levin:  28-Jan-82 15:36:33

DIRECTORY
  BTreeSupportDefs USING [FileHandle];

BTreeDefs: DEFINITIONS =

  BEGIN

  Desc: TYPE = LONG DESCRIPTOR FOR ARRAY OF WORD;
  BTreeHandle: TYPE[2];

  Call: TYPE = PROCEDURE [k: Desc, v: Desc] RETURNS [more, dirty: BOOLEAN];
  TestKeys: TYPE = PROCEDURE [a, b: Desc] RETURNS [BOOLEAN];

  CreateAndInitializeBTree: PROCEDURE [
    fileH: BTreeSupportDefs.FileHandle, initializeFile: BOOLEAN,
    isFirstGreaterOrEqual, areTheyEqual: TestKeys ← NIL]
    RETURNS [bh: BTreeHandle];
  ReleaseBTree: PROCEDURE [bh: BTreeHandle]
    RETURNS [fileH: BTreeSupportDefs.FileHandle];
    -- no longer does a close.  Updates info in special page 0.
    -- Releases btree storage.
  ShutDownBTree: PROCEDURE [bh: BTreeHandle]
    RETURNS [fileH: BTreeSupportDefs.FileHandle];
    -- this is the routine, rather than ReleaseBTree, to call
    -- after an unwind has been seen, to "release" the btree storage.

  Insert: PROCEDURE [bh: BTreeHandle, key: Desc, value: Desc];
  Lookup: PROCEDURE [bh: BTreeHandle, key, value: Desc]
    RETURNS [lengthValue: CARDINAL];
  KeyNotFound: CARDINAL = 177777B;  -- for not found at Lookup.
  Delete: PROCEDURE [bh: BTreeHandle, key: Desc];

  EnumerateFrom: PROCEDURE [bh: BTreeHandle, key: Desc, c: Call];
  -- If you use the default ordering routines, the key to start the
  -- enumeration at the lowest point is:
  --  SmallestKey: Desc = DESCRIPTOR[SmallArray]; where
  --  SmallArray: ARRAY [0..1) OF WORD = [0];

  PushBTreeToDisk: PROCEDURE [bh: BTreeHandle];
  -- guarantees disk is up to date.  (Need not be called unless you
  -- deliberately try to read special page 0 directly from the disk
  -- before the btree has been released.)
  PruneBTree: PROCEDURE [bh: BTreeHandle] RETURNS [storageFreed: BOOLEAN];
  -- currently a noop.  When implemented will pack the tree (by pages only)
  -- and then truncate the file.

  AskDepthOfTree: PROCEDURE [bh: BTreeHandle] RETURNS [nLevels: CARDINAL];
  AskNumberOfEntriesInTree: PROCEDURE [bh: BTreeHandle]
    RETURNS [nEntries: CARDINAL];

  CheckTree: PROCEDURE [bh: BTreeHandle];
  -- syntax check.

  END.
					Edit Log

Comments from old btreedefs:

"A B Tree stores and retrieves Entries in a file system. A entry consists of a key and a value. Retrieval is based on the key, and returns the value. The user can insert, lookup or delete entries. He can also Enumerate entries starting at a particular key and getting called with successive entries until the call returns false. There is no provision for deleting the file once it is created; Release only closes it.

A Btree stores ordered Entries. If one attempts a lookup on a non-existent entry, one gets avalue length of -1, and an enumerate returns entries in numerical order (all based on the key). The ordering property is vital internally, since a binary search is going on to find the entry of interest. 

CreateAndInitializeBTree allows the user to supply his own ordering of items in the BTree, by supplying routines which define greater than and equal for the keys. This need never be called if the user is content with the default ordering, which is a simple cardinal compare of the elements one by one (runing out of elements is smaller). A user who builds a tree with one algorithm and searches it with another gets what he deserves. Obsolete comments: Normally the package operates in a "safe" mode, where it writes out changes as they occur. It is possible to change this mode to keep a dirty cache, and write it out only on closing the file, which goes quicker allows no recourse on an abort. If Initialize specifies NullProc , the defaults will be used.

It is improper for the user to store an entry with a zero length key. Enumerating on such a key dumps the whole tree.

Bug: The definition of Lookup is not good:
      a) it doesn't tell you the length of the value
      b) it has no way to change the entry
      c) it is awkward at best - there must be a "found" boolean.

Bug: The current implementation may get horribly lost if you change the tree during the course of an enumeration, and then try to continue the enumeration.

Bug: The enumeration actually returns pointers right into the pages of the tree. It would be quite desirable to change the value part of the entry, say during an enumeration or a lookup, and to have that reflected into the file. So long as the entry does not change length, there is no conceptual difficulty here. Unfortunately, the current implementation has no way of noticing that the page has become dirty, and will "cleverly" avoid rewriting the page, thereby preventing the change from happening (unless some other change marked it dirty later)."

Change: May 13, 1980  1:04 PM: KK: began interface changes so the message system and Juniper can both use this package.    
Change: October 27, 1980  1:00 PM: KK: Added ShutDownBTree.  See BTree.mesa for conventions on UNWINDS.    
RTE: November 4, 1980  1:38 PM: KK: fixed bug found by Mike Schroeder, and changed some Alarms to InvalidTree errors. 
28-Jan-82 15:38:04: Roy Levin:  modernization with LONG DESCRIPTORs and exported types.