home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 294.lha / TurboFile / indexes.def < prev    next >
Text File  |  1989-10-09  |  7KB  |  216 lines
  1. DEFINITION MODULE Indexes;
  2. (*
  3.      Written by Dexter (Chip) Orange, July, 1987.
  4.  
  5. 3227 Rain Valley Ct.
  6. Tallahassee, FL.  32308
  7.  
  8. home: (904) 877-0061
  9. Work: (904) 487-2680
  10. Compuserve: 71450,1162
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.           Copyright (C) 1987, 1989, Dexter (Chip) Orange
  21. All rights reserved.  None of the files in the TurboFile system, nor a
  22. description of the algorithms used there-in, may be distrinbuted in any way
  23. without the express written permission of the copyright holder (Dexter
  24. Orange).
  25.  
  26.  
  27.      This module of the TurboFile system implements routines to manage a
  28. B+tree index.  Each index entry consists
  29. of a key and its associated record number.  The routines in the TurboFile
  30. module RandomIO can then be used to access that record.
  31.  
  32.           Features of Indexes include:
  33.  
  34.      1.  The ability to have duplicate keys
  35.      2.  The key length may be up to 64K
  36.      3.  Number of keys in the index is limitted only by disk space
  37.      4.  The ability to traverse the index sequentially, in
  38.  increasing/decreasing order
  39.      5.  The ability to find any key with no more than 2 disk accesses
  40.      6.  The ability to search on partial keys
  41.  
  42. All I/O is buffered, and the larger the buffer, the faster things will go.
  43.  
  44.  
  45.           Version 1.1  October, 1989.
  46. Added procedure DeleteCurEntry.
  47.  
  48.  
  49.  
  50.  
  51.           Version 1.0,  September 1989.
  52. Converted from TDI to M2Sprint.
  53.  
  54. *)
  55.  
  56.  
  57. FROM SYSTEM IMPORT
  58.   BYTE;
  59. FROM RandomIO IMPORT
  60.   RandomFile, RandomFileMode;
  61.  
  62.  
  63. TYPE
  64.  
  65.   IndexFile;
  66. (* You must declare a variable of this type for each index file you wish to
  67. use. *)
  68.  
  69.   KeyType = ARRAY [1..CARDINAL(MAX(INTEGER))] OF BYTE;
  70.   KeyPtr = POINTER TO KeyType;
  71.  
  72.  
  73.   KeyProc = PROCEDURE (VAR LONGCARD, VAR  KeyPtr): BOOLEAN;
  74. (* A procedure of the above type should exist in your program for CreateIndex
  75. to call to determine if there is
  76. another record to be added to the index.  If so, the first parameter should
  77. be set to the record number, and the second should be set to point at the
  78. associated key value .  CreateIndex will make repeated calls to this
  79. procedure, each time adding the record number and key value supplied, until
  80. it returns a false value.  Usually this procedure simply reads through the
  81. associated data file returning each record number and the key for that
  82. record  until the entire file has been scanned (see the SortFile program
  83. for an example of this).  A more sophisticated program may wish to filter
  84. the records so that only certain ones are added to the index.
  85. *)
  86.  
  87.  
  88. VAR
  89.   IndErrorMessage: ARRAY [0..80] OF CHAR;
  90. (* contains the text of any error *)
  91.  
  92.  
  93.  
  94. PROCEDURE CreateIndex(VAR Index: IndexFile; FileName: ARRAY OF CHAR;
  95. FileCComment: ARRAY OF BYTE;            (* stored in the header *)
  96. FileCommentSize: CARDINAL; AnotherRecord: KeyProc; KeyLen: CARDINAL; BufferSize:
  97. LONGCARD) : BOOLEAN;
  98. (* procedure to create an index file. *)
  99. (* Most of the parameters are self-explainatory with the following exceptions:
  100.      AnotherRecord is a procedure in your program which keeps supplying record
  101.  numbers
  102. along with their associated key values, to CreateIndex until there are
  103. no more to be added (this is usually done by reading the next record in the
  104. file and then returning a pointer to the key value in it).  This is functionally
  105. equivalent to, but much faster than, repeated calls to AddToIndex.
  106.      BufferSize is more important here than anywhere else, since it is used
  107. to determine the width (order) of the B+tree.
  108.  The width that will be generated can be estimated with the formula:
  109. (BufferSize/4) / (KeyLen+4)
  110. The minimum width is 10 and the maximum is 125.  The wider the tree, the
  111. fewer disk accesses needed to do any given operation.  Note that once the tree
  112. is generated, the width never changes, a larger BufferSize after that simply
  113. means that more index blocks will be buffered.
  114.  
  115. FileComment may be any type (since anything is compatable with ARRAY OF BYTE)
  116. and is simply stored in the index header, and will be retrieved with a call
  117.  to OpenIndex.  It is typically used to contain information about the index
  118. such as when it was created, or what was used as its key field/expression.
  119.  
  120. *)
  121.  
  122.  
  123.  
  124. PROCEDURE OpenIndex(VAR Index: IndexFile; FileName: ARRAY OF CHAR; VAR Comment:
  125. ARRAY OF BYTE;                          (* retrieved from the header *)
  126. VAR FileCommentSize: CARDINAL; Mode: RandomFileMode; BufferSize: LONGCARD) :
  127. BOOLEAN;
  128. (* open an index file for use *)
  129. (* returns true if the open is successful.
  130. Note: Mode should only be either ReadOnly or ReadWrite.
  131. *)
  132.  
  133.  
  134.  
  135.  
  136. PROCEDURE CloseIndex(VAR Index: IndexFile);
  137. (* flush the write buffer and close the file *)
  138.  
  139.  
  140.  
  141. PROCEDURE Find(Index: IndexFile; Key: KeyPtr; SearchKeyLength: CARDINAL) :
  142. LONGCARD;
  143. (* locate the first occurrance of a key value in the index file and return
  144. its associated record number, or 0 if not found *)
  145. (* only the first "SearchKeyLength" bytes are used for comparison.  If there
  146. are duplicates, the first one in the list is returned.
  147. Subsequent ones can be accessed through calls to NextRecord.
  148. *)
  149.  
  150.  
  151.  
  152. PROCEDURE UpdateIndex(Index: IndexFile; NewKey: KeyPtr) : BOOLEAN;
  153. (* Replace the key value of the current index entry with the new key value *)
  154. (* returns TRUE if the update is successful *)
  155. (* Note that the current index entry is set with Find, FirstRecord, LastRecord,
  156. NextRecord, or PreviousRecord .
  157. *)
  158.  
  159.  
  160.  
  161. PROCEDURE AddToIndex(Index: IndexFile; Key: KeyPtr; RecNum: LONGCARD) : BOOLEAN;
  162. (* add a new record and its associated key to the index. *)
  163. (* returns TRUE if the add is successful *)
  164. (* Note that you must guarantee that this record number isn't already in the
  165.  index ,
  166. since no search for this record number is done before the add.
  167. *)
  168.  
  169.  
  170.  
  171. PROCEDURE NextRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
  172. (* get the record number of the next record (the one with next higher
  173. key value) in the index. *)
  174. (* returns TRUE if there is a next record *)
  175. (* Note that a current index entry must be established with a call to Find,
  176. FirstRecord, or LastRecord before NextRecord can be called.
  177. *)
  178.  
  179.  
  180.  
  181. PROCEDURE PreviousRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
  182. (* get the record number of the previous record (the one with next lower
  183. key value) in the index. *)
  184. (* returns TRUE if there is a previous record *)
  185. (* Note that a current index entry must be established with a call to Find,
  186. FirstRecord, or LastRecord before PreviousRecord can be called.
  187. *)
  188.  
  189.  
  190.  
  191. PROCEDURE FirstRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
  192. (* get the record number of the first record (the one with the
  193. lowest key value) in the index. *)
  194. (* returns TRUE if there is a record in the index *)
  195.  
  196.  
  197.  
  198. PROCEDURE LastRecord(Index: IndexFile; VAR RecNum: LONGCARD): BOOLEAN;
  199. (* get the record number of the last record (the one with the highest
  200. key value) in the index. *)
  201. (* returns TRUE if there is a record in the index *)
  202.  
  203.  
  204.  
  205.  
  206. PROCEDURE DeleteCurEntry(Index: IndexFile): BOOLEAN;
  207.  
  208. (* Delete the current index entry from the index file.
  209. Returns TRUE if the delete was successful.
  210. Note the current entry is set by FirstRecord, LastRecord,
  211. NextRecord, PreviousRecord, or Find.
  212. *)
  213.  
  214.  
  215. END Indexes.
  216.