Club Amiga de Montreal - CAM/CAM_CD_1.iso/files/294.lha/TurboFile/indexes.def

Modula Definition | 1989-10-09 | 6.9 KB | 216 lines

DEFINITION MODULE Indexes;
(*
     Written by Dexter (Chip) Orange, July, 1987.

3227 Rain Valley Ct.
Tallahassee, FL.  32308

home: [phone]
Work: [phone]
Compuserve: 71450,1162









          Copyright (C) 1987, 1989, Dexter (Chip) Orange
All rights reserved.  None of the files in the TurboFile system, nor a
description of the algorithms used there-in, may be distrinbuted in any way
without the express written permission of the copyright holder (Dexter
Orange).


     This module of the TurboFile system implements routines to manage a
B+tree index.  Each index entry consists
of a key and its associated record number.  The routines in the TurboFile
module RandomIO can then be used to access that record.

          Features of Indexes include:

     1.  The ability to have duplicate keys
     2.  The key length may be up to 64K
     3.  Number of keys in the index is limitted only by disk space
     4.  The ability to traverse the index sequentially, in
 increasing/decreasing order
     5.  The ability to find any key with no more than 2 disk accesses
     6.  The ability to search on partial keys

All I/O is buffered, and the larger the buffer, the faster things will go.


          Version 1.1  October, 1989.
Added procedure DeleteCurEntry.




          Version 1.0,  September 1989.
Converted from TDI to M2Sprint.

*)


FROM SYSTEM IMPORT
  BYTE;
FROM RandomIO IMPORT
  RandomFile, RandomFileMode;


TYPE

  IndexFile;
(* You must declare a variable of this type for each index file you wish to
use. *)

  KeyType = ARRAY [1..CARDINAL(MAX(INTEGER))] OF BYTE;
  KeyPtr = POINTER TO KeyType;


  KeyProc = PROCEDURE (VAR LONGCARD, VAR  KeyPtr): BOOLEAN;
(* A procedure of the above type should exist in your program for CreateIndex
to call to determine if there is
another record to be added to the index.  If so, the first parameter should
be set to the record number, and the second should be set to point at the
associated key value .  CreateIndex will make repeated calls to this
procedure, each time adding the record number and key value supplied, until
it returns a false value.  Usually this procedure simply reads through the
associated data file returning each record number and the key for that
record  until the entire file has been scanned (see the SortFile program
for an example of this).  A more sophisticated program may wish to filter
the records so that only certain ones are added to the index.
*)


VAR
  IndErrorMessage: ARRAY [0..80] OF CHAR;
(* contains the text of any error *)



PROCEDURE CreateIndex(VAR Index: IndexFile; FileName: ARRAY OF CHAR;
FileCComment: ARRAY OF BYTE;            (* stored in the header *)
FileCommentSize: CARDINAL; AnotherRecord: KeyProc; KeyLen: CARDINAL; BufferSize:
LONGCARD) : BOOLEAN;
(* procedure to create an index file. *)
(* Most of the parameters are self-explainatory with the following exceptions:
     AnotherRecord is a procedure in your program which keeps supplying record
 numbers
along with their associated key values, to CreateIndex until there are
no more to be added (this is usually done by reading the next record in the
file and then returning a pointer to the key value in it).  This is functionally
equivalent to, but much faster than, repeated calls to AddToIndex.
     BufferSize is more important here than anywhere else, since it is used
to determine the width (order) of the B+tree.
 The width that will be generated can be estimated with the formula:
(BufferSize/4) / (KeyLen+4)
The minimum width is 10 and the maximum is 125.  The wider the tree, the
fewer disk accesses needed to do any given operation.  Note that once the tree
is generated, the width never changes, a larger BufferSize after that simply
means that more index blocks will be buffered.

FileComment may be any type (since anything is compatable with ARRAY OF BYTE)
and is simply stored in the index header, and will be retrieved with a call
 to OpenIndex.  It is typically used to contain information about the index
such as when it was created, or what was used as its key field/expression.

*)



PROCEDURE OpenIndex(VAR Index: IndexFile; FileName: ARRAY OF CHAR; VAR Comment:
ARRAY OF BYTE;                          (* retrieved from the header *)
VAR FileCommentSize: CARDINAL; Mode: RandomFileMode; BufferSize: LONGCARD) :
BOOLEAN;
(* open an index file for use *)
(* returns true if the open is successful.
Note: Mode should only be either ReadOnly or ReadWrite.
*)




PROCEDURE CloseIndex(VAR Index: IndexFile);
(* flush the write buffer and close the file *)



PROCEDURE Find(Index: IndexFile; Key: KeyPtr; SearchKeyLength: CARDINAL) :
LONGCARD;
(* locate the first occurrance of a key value in the index file and return
its associated record number, or 0 if not found *)
(* only the first "SearchKeyLength" bytes are used for comparison.  If there
are duplicates, the first one in the list is returned.
Subsequent ones can be accessed through calls to NextRecord.
*)



PROCEDURE UpdateIndex(Index: IndexFile; NewKey: KeyPtr) : BOOLEAN;
(* Replace the key value of the current index entry with the new key value *)
(* returns TRUE if the update is successful *)
(* Note that the current index entry is set with Find, FirstRecord, LastRecord,
NextRecord, or PreviousRecord .
*)



PROCEDURE AddToIndex(Index: IndexFile; Key: KeyPtr; RecNum: LONGCARD) : BOOLEAN;
(* add a new record and its associated key to the index. *)
(* returns TRUE if the add is successful *)
(* Note that you must guarantee that this record number isn't already in the
 index ,
since no search for this record number is done before the add.
*)



PROCEDURE NextRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
(* get the record number of the next record (the one with next higher
key value) in the index. *)
(* returns TRUE if there is a next record *)
(* Note that a current index entry must be established with a call to Find,
FirstRecord, or LastRecord before NextRecord can be called.
*)



PROCEDURE PreviousRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
(* get the record number of the previous record (the one with next lower
key value) in the index. *)
(* returns TRUE if there is a previous record *)
(* Note that a current index entry must be established with a call to Find,
FirstRecord, or LastRecord before PreviousRecord can be called.
*)



PROCEDURE FirstRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
(* get the record number of the first record (the one with the
lowest key value) in the index. *)
(* returns TRUE if there is a record in the index *)



PROCEDURE LastRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
(* get the record number of the last record (the one with the highest
key value) in the index. *)
(* returns TRUE if there is a record in the index *)




PROCEDURE DeleteCurEntry(Index: IndexFile): BOOLEAN;

(* Delete the current index entry from the index file.
Returns TRUE if the delete was successful.
Note the current entry is set by FirstRecord, LastRecord,
NextRecord, PreviousRecord, or Find.
*)


END Indexes.